Farmer John
Because Rob Kolstad felt bad
that nobody could perfectly solve task tix in the Green Division of the US
Open, he decided that to blame were the cows and Farmer John, who didn’t succed
in teaching us all the tricks. So he decided to search for another person to
help use learn programming.
However we all know how Rob
Kolstad thinks. He wants us to help him search for an alternative name for
Farmer John. Here is what he told us:
„I have included for your use a file called farmerj.in which contains a string of
no more than 50 characters. You will have to search for the new names of our
character in this string. However, there are three tricks. The first trick is
that in order to get two good names, there must be a way to inter„fit” the
second name in the first one such that the resulting string must be a substring
(not a subsequence, but
a substring (note that there is a big difference)) in the string read from the input file. This will become clear after you
read the example I have included for you. The second trick is that there are
some pairs of ASCII characters I don’t like used one after the other. Be sure
that neither the first nor the second name have two consecutive characters that
I don’t like. The last trick is that I want the lenght of the full name to be
as big as possible. Don’t print all solutions. One will do it. In the file farmerj.out you will tell me what are
the names you think I should use in a special way: you are to print two lines
of space separated numbers. Each line of output describes one name. Each number
should represent the position of that letter in the string read from input
(numbering stars with 1). But note that I am a person who doesn’t like to wait
for his answers. This is why your program should output its solution in no more
than 4 computer cycles.”.
Here is the example Rob gave
us:
farmerj.in
FJOHNARMERZ
FJ
FO
FH
FN
ZF
ZJ
ZO
ZH
ZN
ZA
ZR
ZM
ZE
ZR
farmerj.out
1 6 7 8 9 10
2 3 4 5
This output file correspunds
to the name FARMER JOHN
The example is ok because: Z
can’t be used together with any other character, so the number of used
characters in maximal. Also note that we can inter”fit” the two names:
F_JOHN_ARMER. This is a valid substring in the example above.
Other best solutions also
include: FAM JOHNRER(F_JOHN_A_R_M_ER.), FARME JOHNR (F_JOHN_ARME_R). A solution that may score points
will also be: F JOHN (this is however not optimal and you can’t be sure you
will get maximal points).
Wrong solutions are FJOH
NARMER. This is because two letter Rob doesn’t like seen next to each other are
used: F and J.
Other examples:
123456789
5
81
84
89
56
68
A perfect solution for this
example is (for the reasons above): 123459 678
1223
2
22
23
solution: 12 3 (2 can only
stand next to an 1).
Observations.
The input file structure is:
-
on the first line
– a string which contains no more than 50 characters (not necessarily distinct)
– all the characters are alphanumeric (e.g. ‚0’ to ‚9’, ‚a’ to ‚z’ and ‚A’ to ‚Z’— note that ‚A’ in
not the same as ‚a’) (use standard string reading routines in your language –
the input string will contain no spaces/newlines).s
-
on the second
line – the number M of pairs of characters Farmer John doesn’t like seen
together.
-
next M lines each
contain two characters (from the string above) that you can’t use one after the
other.
The output should contain two
lines that meet the requirements that Rob formulated for you above. Don’t
forget to space separate the numbers in the output file and also print the
newline at the end of the first line.
The running time is 4
cycles(about 0.2 seconds)/Athlon 1GHZ.
Good luck!
P.S. This story is entirely fictional
;-)