Input File: bachin.txt
Output File: bachout.txt
Time Limit: 1.667 seconds
Back in the era when musicians did not have the opportunity to grace CD covers with pictures of themselves, the composer Bach developed a habit of embedding the letters of his name in his music. At that time, the letters B, A, C and H were all notes of the musical scale, and a number of his pieces contained these four notes consecutively. Thus he left his mark on history.
You have some friends who compose as a hobby, and it has suddenly struck you to see if they have also embedded their names in some of their masterpieces.
For simplicity, we will have ten notes in our musical scale, represented by the digits 0,1,...,9. You cannot go any higher or lower, since your friends are writing for beginner saxophonists. Each musical piece can thus be represented as a sequence of digits.
We will also represent the composer's name as a sequence of digits. Your task is to find the composer's name embedded in the piece.
Take for example the following musical delight:
Say the composer's name translates to
67654. Then we can see
the composer's name beginning at the third character.
Bach also often transposed his name up or down. This corresponds to
adding or subtracting some constant amount from each digit in the
composer's name. We see the digits
45432 starting at the
seventh digit, which corresponds to the composer's name transposed down
Bach even inverted his name from time to time. This
corresponds to replacing each digit d with the corresponding digit
9-d. So in our example the composer's name inverted is
32345, which appears beginning at the tenth digit. Finally,
the composer may even be as bold as to invert and transpose, such
as our composer has done beginning at the fourteenth digit where we see
The first line of the input shall consist of a single string of digits representing the composer's name, whose length will be between 1 and 50 digits inclusive.
The remainder of the input file will contain a musical piece, possibly split over a number of lines for convenience. Each line will be a sequence of between 1 and 50 digits, and there will be at most 600 such lines. Together these lines form the musical piece, and occurrences of the composer's name may run across line breaks.
The musical piece will be terminated by a line containing the single
Your program must output each occurrence of the composer's name, in the order in which they appear in the piece.
If the occurrence is exact
or simply transposed, you must output a line containing the integer
where the occurrence begins at the ith note.
If the output is inverted or
inverted and transposed, you must output a line containing i
followed by a single space and the word "
You are guaranteed that any given occurrence will not be both uninverted and inverted.
If no occurrences are found, your program must output the single line
67654 14676545 43234545679 905 #
3 7 10 inverted 14 inverted
636 14676545 43234545679 905 #
For each test case, let n be the number of occurrences of the composer's name. If your program correctly finds c of these occurrences and incorrectly identifies i fraudulent occurrences, it will be awarded (c-i)/n of the available marks for the test case, down to a minimum of zero.
If there are no occurrences in the test case, your program will be awarded either all or none of the available marks for the test case according to whether or not it correctly identified this fact.