ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Personal Contest 2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Astrolocation

Time limit: 1.0 second
Memory limit: 64 MB
 — Did you call for me, general?
 — Come in. You were recommended to me as a young promising programmer. As you probably know, our new … though how can you know, it's all secret. Well, our department needs a program for the analysis of … let's say signals from … let's call it a locator. This locator is designed for searching for … well, objects, which move in a layer of … no, I can't tell you in a layer of what. The locator is placed on our new … well, it also can move. You'll get the signal through the interface … though it's not important, for you it will be a sequence of numbers, each from 0 to 100. First you find in this sequence a signal from the front wall of the layer, this is a number 95 or greater. If there are several such numbers, the first of them will be regarded as the front wall. And you should take into account that someplace before this number in the sequence there must be a number not exceeding 35, otherwise it's not a wall, it's … well, you don't have to know what. Further you have to check two chan… two places where these objects can be. You'll be given for each of the places two numbers, which are the beginning and the end of the search zone counting from the front wall of the layer. You have to search in these zones for an object, that means you have to find maximal numbers in these zones of numbers. If a maximal number is equal to or greater than a certain level, which you'll be given, then you report that you have found an object and give us its location. If there are several maximal numbers in a search zone, we regard only the first of them as an object. There's another complication: the width of the layer is not constant though it has a lower bound, and you'll have to watch for a signal from the back wall of the layer. This signal is also a number 95 or greater and it must be not earlier than after a certain amount of numbers from the front wall. Note that somewhere between the front and the back wall there must be a number not exceeding 35. Of course, if you don't find a signal from the front wall, you don't have to search for objects or the back wall at all. And you don't have to search for anything behind the back wall. I suppose you understand that a signal from the back wall may fall into a search zone, then you don't regard it as an object. Is everything clear to you?
 — And if…
 — No ifs. You're free, you may go now. Wait, one more thing: according to our recent investigations, the signal decays inside the layer, so after you have found the front layer you have to multiply each subsequent number by a decay coefficient and only then you may analyze it. The decay coefficient for the m-th number is calculated by the formula 1 + (m − f) · А, where f is the location of the front wall, and the value А will be given to you later. That's all, now go.


The input begins with 9 numbers separated with spaces or ends of line. These numbers are:
  1. the total amount of numbers in the sequence N (4 ≤ N ≤ 10000);
  2. the minimal layer width D (1 ≤ D ≤ N − 1), which is the minimal possible difference between the positions of the numbers corresponding to the back wall and the front wall;
  3. the beginning of the first search zone S1 (1 ≤ S1 ≤ N − 1) (if S is the position of the front layer, then S1 + S is the first number of the search zone);
  4. the end of the first search zone E1 (S1 ≤ E1 ≤ N − 1) (the point S + E1 must also be checked);
  5. the level at which an object is reported in the first zone L1 (1 ≤ L1 ≤ 100; if a signal is equal to or greater than L1, then there is an object, whose location is the first maximal number in the search zone);
  6. S2,
  7. E2,
  8. L2 are similar numbers for the second search zone;
  9. the parameter for calculating the decay coefficient A (0 ≤ A ≤ 0.1; A has no more than 3 digits after decimal point).
The following N lines contain a record of the signal; in each line there is one number from 0 to 100.


If the front wall of the layer was not found, you should output “No surface.”. If the front wall was found, you should output “Surface found at *.”, where there is the position of the front wall instead of * (the very first number of the sequence has position 1). In this case the next line of the output should contain your report concerning the back wall: either “Bottom found at *.”, where instead of * there is the difference between the positions of the back wall and the front wall, or “No bottom.” The next line should contain information on the first search zone. If no numbers were analyzed in this zone, you should output “Channel 1: No search.”, otherwise there should be one of the two messages: either “Channel 1: Object at *.”, if an object was found, where instead of * there is the difference between the positions of the object and of the front wall, or “Channel 1: No object.”, if no object was found. The last line should contain an analogous information on the second search zone (note that there must be “Channel 2” in this line).


10 4 1 1 50 2 2 56 0.09
Surface found at 3.
Bottom found at 4.
Channel 1: Object at 1.
Channel 2: No object.
Problem Author: Alexander Mironenko
Problem Source: USU Personal Contest 2004
To submit the solution for this problem go to the Problem set: 1288. Astrolocation