One of popular traditional tournaments on KIRIBATI is game called FACIN'. The rules are simple: two teams stand facing each other and at once start shouting: FACIN' US, YOU DON'T WIN SO EASILY, YOU ENEMY FUSS!
Then first team starts saying: FACIN' US, FACIN' US,... and second: US FACIN', US FACIN',... Team, that mistakes first, loses. But many people have got bored by this tournaments, since there is just one winner. And this is why they decided to make a little change this year. In the beginning, every participant starts as an individual team. During the tournament, every losing team joins the team, that it was beaten by, and both teams continue as one team. In the end, there is just one big team, and so everyone wins. In the evening, they hold a celebration of monumental victory...
Task: Write a program, that will continuously evaluate the modified version of the FACIN' game. There are N participants numbered from 1 to N. As an input, your program will read N in the beginning and then, in infinite loop, it will recieve information about tournament progress and queries about current status, that it will answer. Input information will be one of following kinds:
Make sure your program responds as quickly as possible. There can be many players and the Kiribations are very impatient.
Sue Bodkova will celebrate her birthday, soon. Preparations for great garden/party are in full action, snacks, cake, fireworks... But still it's needed to prepare the seating. The Bodka family has three long tables in the garden. Sue wants to invite many girls to attend, but some of them hate each other and for peace' sake it would be better not to seat hating couple of girls at the same table. Sue made a list of invited girls as well as list of pairs of girls disliking each other. Then she started preparing the seating. After a long while she was found by her fried Christine still worrying about it.
"Look, it's simple," stated Christine. "You should firstly sort girls acoording to how many girls they don't like. Look, Lucy is in dislike wih the biggest number of girls. So, let's put her at the first table. Next girl, Dana, she hates Lucy, so let's put her to second table. Now we have here Jane. She also dislikes Lucy, but she likes Dana, co we can seat her at the second table, too. We will continue this way; we'll take next girl and decide, whether we can seat her at the first, second or third table. You'll see, we shall seat all the girls in this manner." but soon afterwards the girls discovered, that it's impossible to settle all the girls this way. "So, all you can do now is call daddy to bring one table more. There is no way to seat the girls among three tables," said Christine and trotted away. However, Sue was in doubt: isn't there an arrangement, so that three tables were sufficient, really?
Task: Let's number Sue's friends from 1 to N. Your task is to write a program, that will read list of pairs of hostile girls and will find seating for them among three tables, or it will find out, that there is not such seating. If you are confident that Christine's method finds eligible solution every time it exists, program it. In this case, we expect you also to write reason (proof) why it's so. Conversely, if you thinkher method doesn't find the solution all the time, despite it exists, think out your own and program it. Find one contra-example, or just argue, why is Christine wrong.
After the return from his wanderings around the world, Zoro said to himself once again, that he'll figure out the date of the end of the world. The technique he learnt from monks od Hanoi, who use the method tTTT - the Towers Transfer Technique. On the sacred altar there are three rods made of steel, on which there are massive discs loaded. Long, long ago, when the prophecy was uttered, all the discs were on the first rod, sorted by their size, the biggest on the bottom. It;s said that when all the disks willbe transfered from the first rod to the second, the Armageddon will happen. But there are rules for moving the discs:
Task: Zoro has N different discs. There are A[1] smallest discs, A[2] second smallest dicss and so on..., A[N] biggest discs. All the discs are on the first rod, from biggest to smallest. Help Zoro and write a program, that will read these numbers and will write the shortest sequence of moves, that transfers all the discs from first to second rod, fulfilling all the rules, of course. Try to reason why your program works correctly.
Example:
Input: Output:
N = 2, from 1 to 3
A[1] = 3, A[2]=2 from 1 to 3
from 1 to 3
from 1 to 2
from 1 to 2
from 3 to 2
from 3 to 2
from 3 to 2
Zanzibarian ivory paid the Zanzibarian people back well, considering their conditions, so the government decided to invest into improving transportation in the country. Zanzibarian railways achieved the purchase of up-to-date train set, that their rail networks needed so much. During making of new railway guide they realised, that all their railway stations were too small for this train to reverse. So they want to find a circular tour for for locomotive, so that it didn't have to turn or shrink back. They also wish the train not to visit one station more than once.
Task: Zanzibarian railways have N stations numbered 1..N. Some of them are connected directly, all rails are bidirectional. Write a program, that will read the number N and pairs of directly connected stations and will find circular tour for the train. If there are more than one such tour, it's enough to choose one of them. If there is none, program will print appropriate message.
Example:
Input: Output: Stations: N = 6 Tour's running through stations: Rails: 3 4 2 5 6 1 2 3 1 1 4 4 2 2 5 3 4 6 3 5 6
"I'm not doin' it this way," cook Karol said with arms akimbo. "Don't be crazy, it has to work some way. Just imagine we had to spill some of these pots - two hours of our work would be lost," argued cook Kveto. "We should rather think out how we'll do it, for cook Kleofas is here in just a moment and... You know, how big ladle he has," continued Kveto.
What were our cooks worrying about? All pots they had in the kitchen they filled with various creams for the Royal Cake. All pots except one pan - all that remained was to fill it with exactly n decilitres of milk for vanilla cream. But, what a shame, that pan could contain m dl. Although n<=m, but there is only one big milk tank available (we don't know, how much milk there is, but there is plenty) and two ladles with volume a and b dl. The pan is now empty and they can do just one of the following:
Task: Help them and write a program that will read integers a, b, m, n (you can assume that a, b and n are from set {1,2,...,m}) and will output sequence of manipulations, or the message, that it's impossible to get such volume of milk from milk-tank to pan.
Example:
Input: Output: Ladles: a = 4, b = 5 Add 4 Pan volume: m = 6 Add 2 Wanted volume: n = 1 Remove 5