Problems of the Month

Give your brain muscles a shuffling break..!

Write a program to perform this simple card trick:

• Give a pack of cards to a member of the audience.
• Have them cut the cards into two approximately equal piles and recombine the piles into one pack by shuffling them together.
• Repeat step 2 a few more times to ensure the cards are thoroughly shuffled.
• Without showing you, have them take the top card, remember which card it is, and replace it somewhere in the middle of the pack.
• Take back the pack and find which card was replaced in the middle of the pack. Show it to the audience to demonstrate your conjuring prowess!

To see how this amazing feat is performed, consider the pack ABCDEFGHIJKLMNOPQRST with 20 cards. Cutting and shuffling twice, then hiding the top card in the middle of the pack gives:

Cut:                    ABCDEFGHI  JKLMNOPQRST

Shuffle:                JKALBCMDNEOPFGQRHSTI

Cut:                    JKALBCMDNE  OPFGQRHSTI
Shuffle:                OJPFKALGBQCMRHDSNTEI
Hide top card in middle:JPFKALGBOQCMRHDSNTEI

If the initial order of the pack is known, cutting and shuffling k times produces 2 to the power of k interleaved sequences. Moving the top card produces 2k+1 (k is a power) sequences, one of which contains only one card. So taking out the JKLMN sequence leaves PFAGBQOCRHDSTEI. Taking out PQRST leaves FAGBOCHDEI. Taking out FGHI leaves ABOCDE and taking out ABCDE leave O. We know this is the card which was moved because there are 2k+1 (k is a power) sequences, and only one contains this card.

INPUT

Each line of the input is the order of cards in the pack after step 4 of the trick. The pack will contain between 4 and 52 cards and have been cut and shuffled between one and four times. Each card is represented by a single letter and the initial order of a full 52 card pack is ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz. Packs with n < 52 cards contain the first n of these beginning with A. The end of the input is indicated by a line containing only #.

OUTPUT

For each pack of cards in the input, output a line of the form

              The card was q.

If the chosen card can be determined or

              I've failed.

If it cannot.

SAMPLE INPUT

BDEACFG

AEIBCHFGDJKL

JPFKALGBOQCMRHDSNTEI

OPQMDHIBJCFKEGNLRSAT

ABRCSDTEUFVGQWHXIYJZKaLbMcNdOePf

#

SAMPLE OUTPUT

The card was A.

I've failed.

The card was O.

I've failed.

The card was Q.

--C/C++ or Java can be chosen as language platform to solve the problem definition written above. 
--The top solution will get a Prize. The solution needs to be correct and with O/P & I/P in the format as specified. In case of more than one correct solution from different students, the solutions will be judged on the basis of time and complexity. 
--The solution has to be submitted within 14 days from the date of publish of this edition. --Maximum of one solution will be accepted for one student.
--Student of any branch can submit the solution.  
--Soft copy of the solution file can be submitted in person to Aakanksha Mehrotra (2k7 CSE Batch) or mail it at aakanksha@cwmag.co.cc


Click this to check out some problems for practice