“Only question I ever thought was hard was do I like Kirk, or do I like Picard?”
—Weird Al Yankovic: White and Nerdy
If you’re in a hurry and you don’t have a good pseudorandom generator, you can try asking a Trekkie whether they prefer Kirk or Picard. Or ask them whether they prefer to be called a Trekker instead. And in case there is no Trekkie around, simply breathe in through your nose and check which nostril carried most of the air.
This task is also about imperfect pseudorandom generators. We’ll give you most of the output and your task is to fill in the blanks – literally.
We have generated two sequences of pseudorandom bits. Each sequence has been generated by using a specific linear congruential pseudorandom generator (not necessarily a good one). For more information, see the Wikipedia page about linear congruential generators.
You are given those two sequences. Each consists of 4 000 000 values from the set {0, 1, 2}. 0 and 1 are actual bits output by a pseudorandom generator. 2 is a blank – it represents a bit with an unknown value. Each sequence contains exactly 4 000 blanks.
In the easy subproblem K1 choose either of the two sequences and guess at least 2 500 of the blanks correctly.
In the hard subproblem K2 guess at least 2 500 blanks in each of the two sequences correctly.
The input file k.in contains two lines, each describing one of the sequences. Each sequence is given in base-81 encoding. More precisely, the sequence is divided into groups of four values and a group (a, b, c, d) is encoded into the character with ASCII value (33 + 27a + 9b + 3c + d).
In the easy subproblem K1 output a single string of exactly 4 000 zeroes and ones: your guess for the contents of the blanks in one of the sequences. The guesses correspond to the blanks in the order in which they appear in the given input sequence.
Your output will be accepted if it has enough correct guesses for either of the two input sequences. (You do not have to indicate which sequence is the one you chose.)
In the hard subproblem K2 output two whitespace-separated strings, each consisting of exactly 4 000 zeroes and ones. The first string is your guess for the first sequence given in the input, and the second string is your guess for the second input sequence. Your output will be accepted if both guesses are good enough.
Input:
++2+a1Output:
0110The sample input encodes the sequence 010101010122010121010121.
This sequence is not really random, it looks like it’s just alternating zeroes and ones. Thus, the missing bits seem to be 0, 1, 0, and 0. If that was indeed the case, the sample output would be 75% correct. Getting 2500 out of 4000 correct means having 62.5% of your guesses correct.