Submit | All submissions | Best solutions | Back to list |
KAZAKHSTA - Kazakh Stairs |
[The original version of this problem (in Spanish) can be found at https://drive.google.com/file/d/0ByI9GfoY63_aYVdjOXRCN3ZGRG8/view?usp=sharing]
Kazakh engineers are somewhat creative. Such is the case that the stairs in Kazakhstan are totally irregular: some steps are too short and others are too tall, not to mention how tilted some of them are.
The contestants from the International Olympiad in Informatics were hosted in a university building with several stories. Besides sleeping, all the remaining activities were done outside their rooms, which made the kids to go up and down the stairs constantly.
Román noticed that short people were likely to trip easily while taller people seldom did. While Román was waiting for his friends to show up for an excursion, he sat down to watch people trip over. He asked himself, for each person going up the stairs, which would be the first step which made them trip.
For every person, Román knows the exact number of centimeters in height a step can be so that the person doesn't trip over, he also knows exactly the height of every Kazakh step.
He now asks you to help him by writing a program that will answer for every person the index of the first step which makes them trip or that it won't happen, in such a case print "NO SE TROPIEZA".
Input
- Line 1: N (1<=N<=1000000), the number of steps
- Line 2..N+1: one integer h each (1<=h<=1000000), the height of the ith step
- Line N+2: Q (1<=Q<=1000000), the number of queries
- Line N+3..N+Q+3: one integer m each (1<=m<=1250000), the maximum height a step can have so that the current person doesn't trip over.
Output
For each query, print one line with the index (starting from 1) of the first step too high or "NO SE TROPIEZA" if it doesn't exist.
Example
Input: 4 1 1 7 1 3 0 2 10 Output: 1 3 NO SE TROPIEZA
Added by: | MartÃnV |
Date: | 2015-10-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | Argentinian Regional for IOI |