codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

508A.md (2145B)


      1 Source: https://codeforces.com/problemset/problem/508/A
      2 
      3 A. Pasha and Pixels
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Pasha loves his phone and also putting his hair up... But the hair is now irrelevant.
     22 
     23 Pasha has installed a new game to his phone. The goal of the game is following. There is a rectangular field consisting of *n* row with *m* pixels in each row. Initially, all the pixels are colored white. In one move, Pasha can choose any pixel and color it black. In particular, he can choose the pixel that is already black, then after the boy's move the pixel does not change, that is, it remains black. Pasha loses the game when a 2 × 2 square consisting of black pixels is formed.
     24 
     25 Pasha has made a plan of *k* moves, according to which he will paint pixels. Each turn in his plan is represented as a pair of numbers *i* and *j*, denoting respectively the row and the column of the pixel to be colored on the current move.
     26 
     27 Determine whether Pasha loses if he acts in accordance with his plan, and if he does, on what move the 2 × 2 square consisting of black pixels is formed.
     28 
     29 Input
     30 
     31 The first line of the input contains three integers *n*, *m*, *k* (1 ≤ *n*, *m* ≤ 1000, 1 ≤ *k* ≤ 105) — the number of rows, the number of columns and the number of moves that Pasha is going to perform.
     32 
     33 The next *k* lines contain Pasha's moves in the order he makes them. Each line contains two integers *i* and *j* (1 ≤ *i* ≤ *n*, 1 ≤ *j* ≤ *m*), representing the row number and column number of the pixel that was painted during a move.
     34 
     35 Output
     36 
     37 If Pasha loses, print the number of the move when the 2 × 2 square consisting of black pixels is formed.
     38 
     39 If Pasha doesn't lose, that is, no 2 × 2 square consisting of black pixels is formed during the given *k* moves, print 0.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 2 2 4  
     47 1 1  
     48 1 2  
     49 2 1  
     50 2 2
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 4
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 2 3 6  
     63 2 3  
     64 2 2  
     65 1 3  
     66 2 2  
     67 1 2  
     68 1 1
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 5
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 5 3 7  
     81 2 3  
     82 1 2  
     83 1 1  
     84 4 1  
     85 3 1  
     86 5 3  
     87 3 2
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 0
     94 ```