Problem I. 304. (November 2012)

I. 304. Tom has created a counter based on a description he found on the Internet. According to this, the 3-digit counter should have counted from 0 to 999, increasing its value by one in every second. Something must have gone wrong, however, since the counter changed the states in every 1/10th of a second. Moreover, the liquid crystal display consisting of 7 segments did not always react to the control instantaneously: sometimes a segment updated its state normally at once as it should, but sometimes it stopped responding to the control for at most k tenth of a seconds. If, for example, k=2, then the activation of a dark segment may take place in the 0th, 1st, or in the 2nd tenth of a second. But it is also possible that the activation did not happen at all if the next ``off signal'' to the segment was executed earlier than the delayed ``on signal''.

Tom was wondering whether one could figure out the correct value (i.e. the one it displayed if there were no delay present) of the last digit without knowing the initial state and without stopping the counter. Although errors are encountered with different delays, he soon realized that the correct state of the last digit could be found out by inspecting sufficiently many previous states.

Write your program that determines the correct value of the last digit by knowing some previous successive states.

The first line of the input file contains the reaction time of the display (0k5, integer). The next line contains the number of successive previous states n (1n100). The following n lines then encode the state of the last digit of the display from the beginning of the observation and measured in tenth of a seconds. Each line describes the last digit of the display in the actual moment by giving the state of each segment (0 - off, 1 - on).

The output file should contain the number of states to be observed so that the correct value of the last digit could be figured out, further, the correct value of the last digit itself should be included. If the given time frame happens to be insufficient to unambiguously determine the correct value of the last digit, the output should be ``0''.

The first table with the figure tells us how digits from 0 to 9 are built up from the segments.

Then an example is given, showing an input (``Bemenet'') together with its corresponding output (``Kimenet'').

The explanation of the final figure is the following. The first row shows the 10 states of the last digit if no delay is present. The second row shows an example of 10 successive states of a digit if the delay is k=1. Black segments are lit (``on''), white segments are ``off'', while the state of the grey segments cannot be determined. The third row contains the first three states of the example ``Bemenet'', which are sufficient to uniquely determine the next correct value of the last digit.

The first command line argument to your program is the name of the input file, while the second argument is that of the output file.

The source code (i304.pas, i304.cpp, ...) together with a short documentation (i304.txt, i304.pdf, ...) - also describing which developer environment to use for compiling, further a brief description of your solution - should be submitted.

(10 pont)

Deadline expired on December 10, 2012.

Sorry, the solution is available only in Hungarian. Google translation

A beküldők által vázolt megoldási mód szinte minden esetben a következő volt:

- a reakcióidő függvényében le kell generálni minden számjegyhez a megfelelő kijelzőállapotot, amely rögzíti, hogy az egyes szegmensek biztosan be, biztosan kikapcsolt állapotot vesznek fel, vagy éppen bizonytalan a helyzetük

- a bemenetben rögzített állapotokat sorban vizsgálva a lehetséges számjegyek halmaza folyamatosan szűkíthető; a vizsgálatnál figyelembe kell venni, hogy a következő állapot vizsgálatával egy időben a halmaz elemeinek értékét is növelni kell

A feladat szövegében megadott minta eggyel nagyobb értékeket tartalmazott, mint ami a szövegből következett volna, így az értékelésnél mindkét változatot elfogadtuk, ha az indokolt volt. Ennek kiderítésére a következő vizsgálatot végeztük: a fájlban csak a a szükséges számú sort meghagyva vizsgáltuk, hogy az eredmény változik-e. Ha így is az eggyel nagyobb eredmény született, akkor a megoldást helyesnek tekintettük.

A tesztesetek: teszt304.zip

Az egyetlen 10 pontos megoldás Gema Barnabásé volt: i304.pas

Statistics:

7 students sent a solution.
10 points:	Gema Barnabás.
9 points:	Jákli Aida Karolina, Kalló Kristóf, Kocsis 789 Mátyás.
8 points:	1 student.
5 points:	1 student.
1 point:	1 student.

Problems in Information Technology of KöMaL, November 2012