Aunts
Time limit7sMemory limit128 MB
Given altitude reports on an A by B grid where adjacent cells differ by exactly 1, find the first report that makes a consistent assignment impossible.
- Level
Medium6 of 10
- Topics
- Math, Sorting, Implementation
- Solved
- No attempts yet
Problem
The organizing committee of this contest is made up of slackers who would rather do anything than prepare the contest. of them reported that they have to bring medicine to their aunt, so they can skip the work. All of the aunts live in an grid. Each member reports their absence to Dzoni, who records the cell where the aunt's house is located and the altitude of that house.
Dzoni does not know the actual altitudes, but he knows that for any two adjacent cells in the grid, the absolute difference of their altitudes is exactly 1. After each report, Dzoni checks whether he can assign an altitude to every cell so that all reports so far are true. If he cannot (and if an assignment exists, he will always find one), the committee member who made the latest report said something really stupid. Find that member.
Input
The first line contains three integers , , and , where is the number of committee members (), and and are the number of rows and columns of the grid ().
Each of the following lines contains three integers , , and , meaning the -th member claims that the house at row and column has altitude . Here , , and .
Output
Print the index of the member who said something really stupid, counting members from 1. If no such member exists, print bravo komisijo (Serbian for "congratulations, organizing committee").