Zavis was born a businessman. One day he got a very good idea. He planned to have his own radio station and to earn a lot of money on advertisement. It would be really great.
He started to seek advertisers for his radio station. Then he calculated the sum of money he would earn in each day of broadcasting. He was satisfied with his results and went to sleep. Next morning he realized it was not so easy. He had no transmitter. He could rent one but it is quite expensive. Moreover a transmitter can be rented only for some continuous period of time. And so Zavis took his pencil and started to calculate the period in which it would be most profitable to rent a transmitter.
Task: Write a program which for given numbers C (cost of one day of transmitting), D (the number of days), B[i], i=1,2,... ,D (the sum of money which Zavis can earn on day i) determines the start and the end of broadcasting which will cause the highest profit for Zavis.
Example:
Input: the number of days: 6
cost of one day of transmitting: 20
the sums of money which can be earned in each day: 18 35 6 80 15 21
Output: It is most profitable to rent a transmitter since 2nd to the 4th
day.
In this period Zavis can earn 35+6+80 - 3x20 = 61
Tiribaki islands are in serious threat. They are periodically robbed by pirates. Inhabitans decided to protect themselves by buing some lions and locating them on the seashore. When pirates arrives next time many of them will leave the islands without legs, arms or heads. The only thing the inhabitans need to know is the length of the seashore (which determines the number of lions which have to be bought).
Inhabitans of Tiribaki found a map of their islands in a royal library, but they have considerable difficulties with determining the length of the seashore. They discovered only following facts: the map is divided into MxN little squares. Each square is covered by either land (denoted by number 1) or sea (denoted by 0). No square contains both land and sea. Squares sharing common edge (not only vertex) belong to the same island. The border of the map consists only of sea squares. The map contains all the Tiribaki islands and there are no other islands on the map. The seashore is formed by the edges which are between sea squares and land squares. Some islands can have lakes (denoted by 0 as well) but their shores should not be counted as a sea shore. There are no islands in the lakes.
Task: Write a program which calculates the sum of seashore lengths of all Tiribaki islands. The input contains numbers M and N and the map of islands.
Example:
Input:
M=5, N=6
The map:
000000
011100
010110
011110
000000
Output:
The length of seashore is 14.
New task was assigned to a software firm SoDr. They have to write a program for one goldsmith. Each of N SoDr employees wrote his own program and now they argue which of them should be used. The programs are numbered from 1 to N and each of them gives another value for given tested piece of gold.
After a long debate they decided not to use programs giving highest values (so that customer should not pay to much) as well as programs giving smallest values (so that customer would not be sued for a theft). They decided to choose such of their programs which give value which is in the middle. More precisely when we divide all other programs into two groups, one containing programs giving smaller values, the other containing programs giving higher values, the numbers of programs in these groups should be the same or the group with higher values can contain one more program than the other group.
All the employees were very happy about this clever decision. But when they started to look for such program, they found out it is not so easy.
Task: Write a program which for given N values given by individual programs (distinct integers) find the value given by the chosen program.
Example:
Input:
N=7
The values given by programs: 10, 4, 3, 15, 2, 6, 1
Vystup:
Chosen programs gives value 4.
Mr. Bracket once read about an interesting sequence: Take any integer N>1. If N is even divide it by 2, if N is odd, multiply it by 3 and add 1. You can repeat this process until you get number 1.
Mr. Bracket immediately realized that this sequence would be good for his naughty students. Next time they will make him angry he would give them some starting number N and let them work. It will teach them to behave. Mr. Brackets needs to find suitable number. Big numbers are not very good because they are difficult to remember.
Task: Help to Mr. Bracket. Find (your program will surely help you) number N such that p(N)/c(N) will be as great as possible where p(N) is the length of sequence starting with N and c(N) is number of decimal digits of number N.
Very important note: We will value especially the number you find - how great the value of the fraction p(n)/c(n) is. It is important to show that value of the fraction is really the one we claim it to be. Describe also your method of searching and enclose your program and its description if you used computer in your searching.
Example:
Sequence of Mr. Bracket for number starting number 7: 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
Therefore p(7) = 17; c(7) = 1
Zmrzlinov is a very cold country. Even trains need to protect themselves against getting cold and so they move incessantly and they never stop at any station. When the train is small its mother tells him where to go in order not to get lost. When the train grows bigger it remembers its route and goes round and round on it on his own. But he is always afraid of collision with some other train. After collision the trains have to be repaired and that is very unpleasant for them (it is the same as when you go to hospital)
Task: Zmrzlinov is a rectangular country divided into 80x25 little squares. Write a program which reads the number of trains N and for each train its length D, color F and his closed route. Route is given as sequence of coordinates of little squares where each to consecutive squares (as well as the first and the last square of the sequence) have one edge in common. Then your program places each train on the first D squares of its route (it means displaying the train on the screen with color F). When all trains are displayed they start to move in their routes with the same speed until some train collision occures.