(Challenge) Raisins

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/FEB20/hindi/RAISINS.pdf), [Bengali](http://www.codechef.com/download/translated/FEB20/bengali/RAISINS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/FEB20/mandarin/RAISINS.pdf), [Russian](http://www.codechef.com/download/translated/FEB20/russian/RAISINS.pdf), and [Vietnamese](http://www.codechef.com/download/translated/FEB20/vietnamese/RAISINS.pdf) as well. Chef Ada baked a rectangular cake with width $W$ and height $H$. To finish the cake, she placed $R$ raisins on it. For simplicity, we will represent raisins by points in a plane. For each valid $i$, the position of the $i$th raisin is $(X_i, Y_i)$. The price of the cake is twice the area of the smallest convex polygon that contains all raisins. Ada thinks that the current price is too high, so she wants to choose positive integers $N$ and $M$ and cut the cake into a grid of cake pieces with $N$ columns (numbered $1$ through $N$ from left to right) and $M$ rows (numbered $1$ through $M$ from bottom to top), where all pieces have identical widths and heights. Also, the widths and heights of the pieces must be integers, which implies that $N$ must be a divisor of $W$ and $M$ must be a divisor of $H$. Let's denote a piece at column $i$ and row $j$ by $(i,j)$. Next, Ada wants to reorder the pieces using the following operations (they may be performed in any order and any number of times):  `1 r`: Shift the row $r$ of the matrix to the right, i.e. for each valid $c$, the final position of the piece $(c,r)$ becomes $(c+1,r)$ if $c+1 \le N$ or $(1,r)$ otherwise.  `2 c`: Shift the column $c$ of the matrix upwards, i.e. for each valid $r$, the final position of the piece $(c,r)$ becomes $(c,r+1)$ if $r+1 \le M$ or $(c,1)$ otherwise. At the end, Ada does not sell the pieces separately, but as a single cake. Therefore, the final price of the cake is still twice the area of the smallest convex polygon that contains all raisins for this new cake. Help Ada slice the cake into at most $2^{10}$ pieces and perform at most $2^{10}$ operations to minimise the final price of the cake. ### Input  The first line of the input contains three spaceseparated integers $W$, $H$ and $R$.  $R$ lines follow. For each $i$ ($1 \le i \le R$), the $i$th of these lines contains two spaceseparated integers $X_i$ and $Y_i$. ### Output  First, print a line containing three spaceseparated integers $N$, $M$ and $Q$.  Then, print $Q$ lines. Each of these lines should describe one operation you want to perform, in the format described above. ### Test generation  $W = H = 720720$  $R = 10^5$  for each valid $i$, $X_i$ is chosen uniformly randomly among all integers between $1$ and $W1$ (inclusive) that are coprime with $W$  for each valid $i$, $Y_i$ is chosen uniformly randomly among all integers between $1$ and $H1$ (inclusive) that are coprime with $H$ ### Scoring If $N \cdot M \gt 2^{10}$, $Q \gt 2^{10}$ or the widths or heights of the pieces are not integers, your solution will receive the Wrong Answer verdict. The score of a test file is the final price of the cake. The score of a submission is the sum of scores of all test files. Your goal is to minimise the score of your submission. There are three test files. During the contest, the displayed score will account for exactly two test files, i.e. your score reflects your submission's performance on approximately 66.66% (2/3) of the test files. However, if your program gets a nonAC verdict on any test file, your submission's verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the third test file. ### Example Input ``` 9 6 6 2 3 1 1 5 3 2 5 5 1 8 5 ``` ### Example Output ``` 3 3 3 1 2 2 3 2 3 ``` ### Explanation  $N=M=3$  The red points in the picture are the raisins.  The piece highlighted in blue is denoted by $(3,2)$.  After shifting the second row to the right and the third column twice upwards, the resulting cake is:  The score is twice the area of the polygon $\mathsf{NORP}$, but there may be a better solution that leads to a smaller area.Author:  alei 
Editorial  https://discuss.codechef.com/problems/RAISINS 
Tags  alei, challenge, feb20, tmwilliamlin 
Date Added:  28012020 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions