codeforces-scrape

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

441C.md (2215B)


      1 Source: https://codeforces.com/problemset/problem/441/C
      2 
      3 C. Valera and Tubes
      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 Valera has got a rectangle table consisting of *n* rows and *m* columns. Valera numbered the table rows starting from one, from top to bottom and the columns – starting from one, from left to right. We will represent cell that is on the intersection of row *x* and column *y* by a pair of integers (*x*, *y*).
     22 
     23 Valera wants to place exactly *k* tubes on his rectangle table. A tube is such sequence of table cells (*x*1, *y*1), (*x*2, *y*2), ..., (*x**r*, *y**r*), that:
     24 
     25 * *r* ≥ 2;
     26 * for any integer *i* (1 ≤ *i* ≤ *r* - 1) the following equation |*x**i* - *x**i* + 1| + |*y**i* - *y**i* + 1| = 1 holds;
     27 * each table cell, which belongs to the tube, must occur exactly once in the sequence.
     28 
     29 Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled:
     30 
     31 * no pair of tubes has common cells;
     32 * each cell of the table belongs to some tube.
     33 
     34 Help Valera to arrange *k* tubes on his rectangle table in a fancy manner.
     35 
     36 Input
     37 
     38 The first line contains three space-separated integers *n*, *m*, *k* (2 ≤ *n*, *m* ≤ 300; 2 ≤ 2*k* ≤ *n*·*m*) — the number of rows, the number of columns and the number of tubes, correspondingly.
     39 
     40 Output
     41 
     42 Print *k* lines. In the *i*-th line print the description of the *i*-th tube: first print integer *r**i* (the number of tube cells), then print 2*r**i* integers *x**i*1, *y**i*1, *x**i*2, *y**i*2, ..., *x**ir**i*, *y**ir**i* (the sequence of table cells).
     43 
     44 If there are multiple solutions, you can print any of them. It is guaranteed that at least one solution exists.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 3 3 3
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 3 1 1 1 2 1 3  
     58 3 2 1 2 2 2 3  
     59 3 3 1 3 2 3 3
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 2 3 1
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 6 1 1 1 2 1 3 2 3 2 2 2 1
     72 ```
     73 
     74 Note
     75 
     76 Picture for the first sample:
     77 
     78  ![](https://espresso.codeforces.com/1bf7f8d65aab5f082741ee00576819f5e7cdaaef.png) 
     79 
     80 Picture for the second sample:
     81 
     82  ![](https://espresso.codeforces.com/136fa02d5df46dad0fdf9b719396d4d3ae6164b9.png)