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 ;-)