_______________________________________________________________________________
G Rama Krishna						rk_gaddipati@yahoo.com
MMS, BITS Pilani,
Rajasthan - 333 031.
INDIA.

Dt: 24-04-2002.
_______________________________________________________________________________

Problem: Kitty Fishing
Source: ACM ICPC 1997-98, Asia Regional Programming Contest

A WORD BEFORE
-------------
Normally, at least in the one I participated, in ACM ICPCs you will be awarded mark/points only when your program compiles and runs with out any error and the output matches with the output which they have, for a different set of test cases which they have and that too with in specified time limit (3 min, for all the cases in the input file! Not the one which you have!! They may try with a huge test case sets.  So an efficient algo and implementation, (if you have to choose between time and memory... choose time efficient), will give you better result in ICPC).
For C programs, they wanted us to write the whole code in one single source file and you are allowed to use any standard C headers (ansi), they will take care about the flags that should be used for compilation or an online form would be provided to enter the compilation command string!

So this program is written keeping all these things in mind...

LOGIC
-----
Esentially, there is nothing much to do with this problem, except implimentation of a queue and a stack (efficientcy does matter).
Each of the participant is treated as a queue and the table is treated as a stack.  Other than the standard stack ADT methods, push and pop, you may have to implement one more method... is_available(value) (or stack_has(value)), which says wether an element is present in the stack or not.

Done with this.... the Algo is :
1. Build the que of A
2. Build the que of B
3. If A is empty... goto 17.
4. Dequeue A and store the value in val.
5. If val is in the elements on table goto 14.
6. Push val into table stack.
7. turns++; If it exceeds the max turns in input goto 16.
8. If B is empty... goto  18.
9. Dequeue B and store the value in val.
10. If val is in the elements on table goto 15.
11. Push val into table stack.
12. turns++; If it exceeds the max turns in input goto 16.
13. Goto 3.
14. enque the val to A.
    14.1 pop table and store value in temp.
    14.2 if temp == val, enque to A and go to 7.
    14.3 enqueue temp to A and goto 14.1
15. enque the val to B.
    15.1 pop table and store value in temp.
    15.2 if temp == val, enque to A and go to 12.
    15.3 enqueue temp to B and goto 14.1
16. Print value in A, B and Table; Goto 19
17. Print B; Goto 19 
18. Print A;
19. Exit.

I hope the source code explains it all...
_______________________________________________________________________________
Gaddipati Rama Krishna
http://www.geocities.com/rk_gaddipati
_______________________________________________________________________________
