KOLICA - Kolica
A number of shopping carts filled with explosives are floating in a coordinate system, in one of the four main directions (up, down, left or right). All carts are moving at a speed of one unit per second.
Movement is continuous; for example, in one third of a second, a cart travels one third of a unit.
When two or more carts collide (are at the same place at the same time), there is an explosion and all carts taking part in the collision explode and cease to exist.
Write a program that, given the starting points and directions of all carts, determines which carts never explode.
Input
The first line of input contains an integer N (2 ≤ N ≤ 500), the number of carts.
Each of the following N lines contains two integers and a string. Each pair of integers describes the starting coordinates of one cart (between 0 and 100 000 000, inclusive), and the string describes the direcction in which the cart is moving ("gore" for up, "dolje" for down, "lijevo" for left, or "desno" for right).
No two carts will start at the same coordinates.
Output
Output the indices of all carts which never explode, sorted in ascending order, one index per line. The first cart in the input is labeled 1, the second is labeled 2 etc. If no carts survive, output "nema".
Example
Input:
4
5 5 dolje
5 6 lijevo
5 7 desno
5 8 gore Output: 1
2
3
4
Input:
5
3 3 dolje
1 1 desno
5 1 lijevo
100000 500000 desno
900000 500000 lijevo
Output:
nema
Input:
3
10 0 gore
0 10 desno
15 5 lijevo
Output:
2
hide comments
[shifted to another user]:
2011-06-09 06:44:33
Could you give a hint where my code goes wrong in the failing case? Submission ID: 5216437 Last edit: 2011-06-09 06:45:00 |
Added by: | Stjepan Glavina |
Date: | 2011-02-28 |
Time limit: | 0.195s-0.390s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Croatian Nationals 2007 |