Problemas acm 2010 - traducidos

Problema B – BARCODES
Código-11 es un sistema de código de barras para la codificación de caracteres que se utilizan principalmente en el etiquetado de equipos de telecomunicaciones. Los caracteres codificados se limitan a los dígitos del 0 al 9, el ("-"), guión y un caracter especial star/stiop que aparece al principio y al final de cada código-11 del código de barras.
Código-11 es un sistemadiscreto, y cada carácter se codifica de manera independiente. Un carácter de codificación es representado por cinco regiones adyacentes, o barras, que se alternan entre un color oscuro y un color claro, a partir de una barra oscura. El ancho de cada barra es pequeño o grande, de acuerdo con el esquema de codificación se muestra a continuación, donde 0 representa una barra estrecha y 1 representauna barra ancha.

Así, el personaje 1 se codifica como una barra ancha oscuro, una barra de luz angosto, estrecho y oscuro de un bar, una barra de luz estrecho, y por último, una barra oscura de ancho. Los códigos de barras para los caracteres individuales deben estar separados por una estrecha barra de luz cuya única función es separar los personajes.
 
Una codificación de dos de ancho comola utilizada para el código-11 tiene la ventaja de la simplicidad. Puesto que es necesario sólo para distinguir una barra estrecha de una barra de ancho, Código-11 permite un gran nivel de tolerancia de impresión en la parte baja calidad condiciones de impresión.
 
Para permitir la detección de errores, el Código-11 códigos de barras que utilizamos tendrá dos caracteres de control, C y K, añadeal final del mensaje (antes de que el carácter de parada). Si el n caracteres a codificar (de izquierda a derecha) son c1 a cn, entonces el peso del carácter de control C es:

donde w(ci) es el peso asociado con ci carácter. Las ponderaciones de los dígitos del 0 al 9 son del 0 al 9, el peso, con el guión es de 10. (Tenga en cuenta que mod tiene mayor precedencia que.) El peso del carácter decontrol K es:

cuando cn 1 es el carácter de control C. Por ejemplo, supongamos que el mensaje se codifica es 123-45. Entonces, el C carácter de control es 5 y el carácter de control K 2. Los códigos de barras para los ocho caracteres 123-4552, precedido y seguido por el código de barras para el inicio / parada de carácter, constituyen el Código completo de códigos de barras-11 de la codificaciónel mensaje.
Los lectores de códigos de barras simple medida de la intensidad de la luz reflejada por un código de barras en una matriz lineal que contiene cientos de diminutos sensores CCD, cada luz de informes u oscuro. La luz y las regiones oscuras son identificados, y el ancho de cada región es utilizada por el software de decodificación para validar el código de barras y obtener la informacióncodificada. Dado que la orientación del código de barras no es fijo, el software debe ser capaz de descifrar el código de barras si es escaneado de izquierda a derecha o de derecha a izquierda.

Su problema es decodificar la información obtenida mediante el escaneo de un código de barras-11, teniendo en cuenta el ancho de las regiones claras y oscuras detectados por el lector. Suponga que unabarra ancha está destinada a ser dos veces tan anchas como una barra estrecha. Debido a las incoherencias entre las impresoras, el ancho de una barra puede ser de hasta 5 por ciento más grande o más pequeño de lo esperado. No hay mensajes de longitud cero (con códigos de barras que contiene sólo de arranque / parada, caracteres de control, e inter-espaciado de caracteres).

Entrada
La entradacontiene varios casos de prueba, cada uno representando un solo intento de exploración. Los datos de cada caso comienza con un número entero m ≤ 150 que especifica el número de regiones detectadas por un lector de código de barras. Esto es seguido por m enteros d1…dm (1 ≤ di ≤ 200) dar el número de sensores en cada región (dentro de una región, todos los sensores de la memoria del misma intensidad...