Chef and War with Taran (Challenge)

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Technology has advanced so much that it is now common for everyone to have robots do their work. Codechef is still the popular choice of competitive programming platform, the reason being great quality of problems. One fine day, Taran decided to gain access to all problems by beating Master Chef of Codechef in a robot war. There are $N$ types of robots numbered $1$ through $N$ with an infinite supply for each type. If two robots of different types fight, one of them wins and the other loses; you are given a matrix $M$ with size $N\times N$, where for each valid $i, j$, a robot of type $i$ wins against a robot of type $j$ if $M_{ij} = 1$. If two robots of the same type fight, the result is a draw. Chef will buy $N$ robots in total and Taran will also buy $N$ robots in total. Both Taran and Chef can buy any number of robots of each type, including zero. Taran cleverly decided to buy his robots only after knowing the $N$ robots bought by Chef, so that his chances of winning are maximized. After buying the robots, the war begins. It happens in $N$ turns; two robots fight in each turn, one of them is Chef's and the other is Taran's. For the first $A$ turns, Chef chooses his robot as well as Taran's robot which will fight in the current turn. For the next $B$ turns, Taran chooses his robot as well as Chefâ€™s robot that will fight against each other. At the end of a turn, both robots are completely destroyed and can't be used again. Since Master Chef trusts his talented programmers, you were asked to fight against Taran to save their problems for future contests. Your goal is to maximize the number of turns when your robot won a fight. _P.S.: After seeing this problem, Taran decided to befriend Master Chef instead. The problems are safe now._ ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains three spaceseparated integers $N$, $A$ and $B$.  For each $i$ ($1 \le i \le N$), the $i$th of the following $N$ lines contains $N$ spaceseparated integers $M_{i1}, M_{i2}, \dots, M_{iN}$. ### Interaction  After reading the input, you should print a line containing $N$ integers. For each valid $i$, the $i$th of these integers denotes the number of robots of type $i$ you bought.  Afterwards, you should read a line containing $N$ integers describing Taran's robots in the same format.  Then the war begins. For each of the first $A$ turns, you should print a line containing two spaceseparated integers $x$ and $y$, where $x$ is the type of the robot fighting for Chef and $y$ is the type of robot fighting for Taran.  For each of the next $B$ turns, the judge will print a line containing two spaceseparated integers $x$ and $y$, describing the robots fighting in this turn in the same format. You are not allowed to buy less or more robots than $N$ or to choose (neither for Chef nor for Taran) a robot of a type such that there are no robots of this type remaining. If you do that, the verdict of your submission will be Wrong answer and interaction will terminate immediately. Also, remember to flush the output after printing each line, or the judge will wait for your response forever and the verdict of your submission will be Time Limit Exceeded. **It is to be noted that first, you have to read input for first test case, followed by interaction for the first test case, then input for second test case and its interaction and so on.** ### Constraints  $T = 5$  $N = 1,000$  $0 \le A, B \le N$  $1 \le A+B \le N$  $N$ is divisible by $A+B$  $0 \le M_{ij} \le 1$ for each valid $i, j$  $M_{ij}+M_{ji} = 1$ for each valid $i \neq j$  $M_{ii} = 0$ for each valid $i$ ### Scoring Your score for each test case is the number of fights won by your robots. Your score for each test file is the sum of your scores for all test cases. ### Test Generation Plan There are twenty test files. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission's performance on 20% (4 out of 20) 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 the sum of your program's scores over the other sixteen test files. The matrix $M$ is generated randomly. There are four types of tests:  type 1: $A = B = 250$  type 2: $A$ and $B$ are integers chosen uniformly randomly in the range $[0, 10]$ such that $A+B = 10$  type 3: $A$ and $B$ are integers chosen uniformly randomly in the range $[0, 100]$ such that $A+B = 100$  type 4: $A$ and $B$ are integers chosen uniformly randomly in the range $[0, 1000]$ such that $A+B = 1000$ ### Example ``` 1 5 3 2 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 Interaction User Judge 2 0 2 1 0 1 1 2 0 1 1 2 4 1 1 3 3 3 3 5 ``` ### Explanation Note that the example test does not satisfy the constraints on $T$ and $N$ for clarity. These constraints will hold for all real tests. Also note that the judge's interaction may vary, this example only shows one possible way the interaction could go. The player chose 2 robots of the 1st type, 2 robots of the 3rd type and 1 robot of the 4th type. The judge chose 2 robots of the 3rd type and 1 robot each of types 1, 2 and 5. The matches went as follows:  The player chose a robot of the 1st type against Taran's robot of the 2nd type and gained a point.  The player chose a robot of the 4th type against Taran's robot of the 1st type and gained another point.  The player chose a robot of the 1st type against Taran's robot of the 3rd type and gained one more point.  The judge chose the player's robot of the 3rd type against the judge's remaining robot of the 3rd type. The player gained no points.  The judge chose the player's robot of the 3rd type against the judge's robot of the 5th type. The player gained one point. The player's score for this test case is 4.Author:  taran_1407 
Editorial  https://discuss.codechef.com/problems/WARTARAN 
Tags  taran_1407 
Date Added:  26062018 
Time Limit:  4 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions