 n=3 |
 n=4 |
 n=5 |
 n=6 |
 n=7 |
 n=8 |
Dear problem solvers,
Again we have prepared new problems for you. The deadline is November 6, 2000.
A new information office was established in one town and it grew popular very quickly. Soon there was a long queue of people waiting to get information as well as free refreshments provided by the office.
In order to prevent long queues, it was decided to install a new reservation system. Upon arrival each customer enters his/her ID number as well as a number of a counter he/she wants to visit. Each person has a unique ID. There are K counters in the office, each providing a different type of information. The counters are numbered 1 to K. After the system gets information about a customer, the customer has free time that can be pleasantly spent by a walk in a nearby park. When all people who came sooner and waited for the same counter leave the office, the customer is called by a big display in front of the information office. Help to implement this reservation system.
Write a program that would control the display calling customers. The program reads the number of counters K. Then it gets messages of the type ARRIVED x c a FREE c. The first type of a message means the fact that a person with ID number x has arrived to the office and needs to visit the counter number c. The second type of a message means that the customer using counter c has just left the office and the counter is therefore free for the next customer. Each time a counter gets free and there is a customer waiting for that counter or a counter is free and a customer for this counter arrives to the office your program should write the number of the customer which has to be served by the counter. Try to make the program efficient so that it does not cause delays. Since the information office works non-stop, your program should be able to run forever as well.
Input: ARRIVED 20 2 Output: Customer 20, please, proceed to counter 2 Input: ARRIVED 11 2 Input: ARRIVED 15 1 Output: Customer 15: please, proceed to counter 1 Input: FREE 2 Output: Customer 11: please, proceed to counter 2 Input: FREE 2 Input: ARRIVED 99 2 Output: Customer 99: please, proceed to counter 2 Input: FREE 1
Pedro Seaside, president of company Blue Cruisers, Seas, and Ports, decided to develop his ports and thus attract new customers. Unfortunately, he has only a limited amount of money. He wants to choose the most frequently visited port and invest his money there. However this is not an easy task because B CSP only has a list of passenger-shipping routes. Routes are two-way and for any two ports there is at most one route connecting them. Since some employees of B CSP are disorganized some routes can be listed several times.
The inputs are N - the number of ports and a list of routes (list of pairs of ports connected by a route). Write a program computing the number of the most frequently visited port, i.e. the port connected to the greatest number of other ports. If there is more than one such port output all such ports.
Input
N=5 Routes: 1-3, 2-1, 3-1, 3-1, 3-2, 4-2, 5-3
Output
Port connected to the greatest number of other ports: 2.
Once upon a time, there was an extremely curious mathematician. And also his name was Curious, for it was the name of his father, grand-father, great-grand-father, ... Well, being so curious, he wanted to explore everything that he came across to. No wonder that he found out about a "negative binary code" while dilligently researching libraries. He started to like the code at once, but he wavered soon: how can this code possibly work?
Mr Curious would be glad if you wrote a program for him which would translate numbers from the decimal code to the negabinary code and vice versa. The negabinary code uses digits 0 and 1 with a radix -2; consider the number 100110, its value (in the decimal code) is 1*(-2)5 + 0*(-2)4 + 0*(-2)3 + 1* (-2)2 + 1*(-2)1 + 0*(-2)0 = -30. In general, let xn-1xn-2 ... x2x1x0 be digits of a number in the negabinary code, then its value equals xn-1*(-2)n-1 + xn-2*(-2)n-2 + ... + x2*(-2)2 + x1*(-2)1 + x0*(-2)0.
Try to prove that every integer can be represented in the negabinary code by exactly one string of 1s and 0s.
Input 1
7 (radix: 10)
Output 1
11011 (radix: -2)
Input 2
110101 (radix: -2)
Output 2
-11 (radix: 10)
Students of a unnamed college have a lot of strange ideas. Recently they invented this game: they closed their eyes and every one of them grasped with their right hand a randomly chosen left hand. When they were done, their group resembled a huge knot. Now they would like to "unknot" themselves. Help them at least by writing a program that determines the number of cycles formed by the students.
Your program inputs the number of students N and N numbers, where the i-th number is the id-number of the student which's hand is held by the student i. Your program should output the number of cycles formed by the students. A cycle is each sequence of students (of length at least 1) s1,s2,...,sk such that student s1 holds the left hand of student s2, student s2 holds the left hand of student s3, ..., student sk holds the left hand of student s1.
Input
4 1 3 4 2
Output
2(The circles are (1) and (3,4,2).)
I have a pleasure to introduce you to Zeofine, a turtle. "Hello, I am CSP participant". "Hello, my name is Zeofine" says Zeofine. Then she adds: "I have appeared in CSP problems as long as three years ago. But you, dear participant do not remember me. (Or do you? Have you participated in CSP such a long time ago? Then why do you solve the beginners category? Take the more difficult one! :-))..." Zeofine started to talk about her past journeys, about here childhood, about beautiful nights on Galapagos. There were such a wonderful stars on the sky at night. Zeofine would like to see the stars from Galapagos again.
Help Zeofine and write a program which tells Zeofine how to draw a Galapagos star. This might help her in her homesickness. Galapagos n-point star (where n>= 3) has n points located in vertices of regular polygon with n vertices. Each point of a star is connected by lines with the two points located "almost opposite". Here are several examples of such a star.
n=3 |
n=4 |
n=5 |
n=6 |
n=7 |
n=8 |
When Zeofine wants to draw something, she dips her tail in ink, moves to a center of a large piece of paper, and starts to walk on this paper. When she puts her tail down, she draws a line, otherwise she just moves. She learns a sequence of commands to draw a figure in a advance. She knows the following commands:
Your program should read number n and output a sequence of commands that help Zeofine to produce Galapagos n-point star.
Try to minimize the number of down and up commands used in your output sequence. Also try to minimize the total length that Zeofine has to move to draw a star.
Input
n=3
Output
down forward 10 left 120 forward 10 left 120 forward 10