codeforces-scrape

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

411B.md (2731B)


      1 Source: https://codeforces.com/problemset/problem/411/B
      2 
      3 B. Multi-core Processor
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 The research center Q has developed a new multi-core processor. The processor consists of *n* cores and has *k* cells of cache memory. Consider the work of this processor.
     22 
     23 At each cycle each core of the processor gets one instruction: either do nothing, or the number of the memory cell (the core will write an information to the cell). After receiving the command, the core executes it immediately. Sometimes it happens that at one cycle, multiple cores try to write the information into a single cell. Unfortunately, the developers did not foresee the possibility of resolving conflicts between cores, so in this case there is a deadlock: all these cores and the corresponding memory cell are locked forever. Each of the locked cores ignores all further commands, and no core in the future will be able to record an information into the locked cell. If any of the cores tries to write an information into some locked cell, it is immediately locked.
     24 
     25 The development team wants to explore the deadlock situation. Therefore, they need a program that will simulate the processor for a given set of instructions for each core within *m* cycles . You're lucky, this interesting work is entrusted to you. According to the instructions, during the *m* cycles define for each core the number of the cycle, during which it will become locked. It is believed that initially all cores and all memory cells are not locked.
     26 
     27 Input
     28 
     29 The first line contains three integers *n*, *m*, *k* (1 ≤ *n*, *m*, *k* ≤ 100). Then follow *n* lines describing instructions. The *i*-th line contains *m* integers: *x**i*1, *x**i*2, ..., *x**im* (0 ≤ *x**ij* ≤ *k*), where *x**ij* is the instruction that must be executed by the *i*-th core at the *j*-th cycle. If *x**ij* equals 0, then the corresponding instruction is «do nothing». But if *x**ij* is a number from 1 to *k*, then the corresponding instruction is «write information to the memory cell number *x**ij*».
     30 
     31 We assume that the cores are numbered from 1 to *n*, the work cycles are numbered from 1 to *m* and the memory cells are numbered from 1 to *k*.
     32 
     33 Output
     34 
     35 Print *n* lines. In the *i*-th line print integer *t**i*. This number should be equal to 0 if the *i*-th core won't be locked, or it should be equal to the number of the cycle when this core will be locked.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 4 3 5  
     43 1 0 0  
     44 1 0 2  
     45 2 3 1  
     46 3 2 0
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 1  
     53 1  
     54 3  
     55 0
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 3 2 2  
     62 1 2  
     63 1 2  
     64 2 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 1  
     71 1  
     72 0
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 1 1 1  
     79 0
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 0
     86 ```