Chefland Army

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JAN20/hindi/CHEFARMY.pdf), [Bengali](http://www.codechef.com/download/translated/JAN20/bengali/CHEFARMY.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JAN20/mandarin/CHEFARMY.pdf), [Russian](http://www.codechef.com/download/translated/JAN20/russian/CHEFARMY.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JAN20/vietnamese/CHEFARMY.pdf) as well. **This is not intended to be the tiebreak problem.** In the Chefland army, there are $M$ generals (numbered $1$ through $M$) and $N$ soldiers (numbered $1$ through $N$). The Army has a vertical hierarchy ― a soldier may command many other soldiers (including zero), but each soldier has at most one commander. A soldier $y$ is a *subordinate* of a soldier $x$ if soldier $x$ is the commander of soldier $y$ or there is a soldier $z$ commanded by soldier $x$ such that soldier $y$ is a subordinate of soldier $z$. No soldier is commanded by one of their subordinates because every soldier is feared by all of his subordinates. Moreover, all soldiers are subordinates of soldier $1$. Let's denote the commander of soldier $i$ by $p_i$ ($p_1 = 0$ since soldier $1$ cannot have a commander). As in any organisation, the generals have some soldiers they hate. If a general meets a soldier whom he hates, this general becomes angry for the rest of the day. The soldiers should be paid some wages over one or more days. For each valid $i$, soldier $i$ should be paid $S_i$ chefcoins. Shyam is in charge of this; he should choose an integer $D$ ($0 \le D \le N^2$) and during each of the next $D$ days, perform the following process:  Choose an integer $K$ and $K$ soldiers, then call these soldiers to report their feats to the generals. Shyam is very careful ― on each day, he chooses these soldiers in such a way that there are no two called soldiers where one is afraid of the other (in other words, no called soldier is a subordinate of another called soldier).  Choose a positive real number $R$ and give each of the called soldiers $R$ chefcoins.  For each soldier $v$ and general $u$, if soldier $v$ was called and is hated by general $u$, then general $u$ becomes angry. Let $G$ be the total number of angry generals on this day. Then, the total angriness of the generals increases by $G \cdot R$.  Before the start of the next day, the generals that were angry calm down and are not angry anymore (so they can become angry again). Help Shyam pay the soldiers while minimising the total angriness of the generals over all $D$ days. ### 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 two spaceseparated integers $M$ and $N$.  Each of the next $M$ lines contains a binary string $B$ with length $N$. For each valid $i$ and $j$, the $j$th character in the $i$th of these strings is '1' if general $i$ hates soldier $j$ or '0' otherwise.  The next line contains $N$ spaceseparated integers $S_1, S_2, \ldots, S_N$.  The last line contains $N$ spaceseparated integers $p_1, p_2, \ldots, p_N$. ### Output For each test case:  First, print a line containing a single integer $D$ ($0 \le D \le N^2$) ― the number of days during which the soldiers are paid.  Then, print $D$ lines. In each of these lines, print an integer $K$, a space, a real number $R$, a space and $K$ spaceseparated integers $x_1, x_2, \ldots, x_K$ ― the numbers of the called soldiers.  For each valid $i$, let the total amount of money received by soldier $i$ be $W_i$; your answer will be considered correct if $W_i  S_i \le 10^{6}$. ### Constraints  $T = 50$  $M = 16$  $N = 128$  $0 \le p_i \le N$ for each valid $i$  $1 \le S_i \le 100$ for each valid $i$ ### Test generation For each test case:  $S_1, S_2, \ldots, S_N$ are chosen uniformly randomly and independently between $1$ and $100$.  For each valid $i$, $p_i$ is chosen uniformly randomly between $1$ and $i1$.  For each test case, a real number $p$ is chosen manually. There are $10$ test cases for each $p \in \{0.1, 0.2, 0.5, 0.7, 0.8\}$.  For each valid $i$ and $j$, $B_{i,j}$ is chosen to be '1' with probability $p$ or '0' with probability $1p$. ### Scoring The score of each test case is the sum of $R \cdot G$ over all $D$ days. The score of a submission is equal to the sum of its scores over all test cases. The goal is to minimise the score of your submission. However, this problem is solvable optimally ― there is a solution which is guaranteed to score 100 points. ### Example Input ``` 1 3 4 0000 1111 0101 1 2 3 4 0 1 1 3 ``` ### Example Output ``` 5 2 1 2 4 2 1 2 3 1 2 3 1 3 4 1 1 1 ```Author:  alei 
Tags  alei 
Date Added:  22122019 
Time Limit:  7 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
HELP
If you are still having problems, see a sample solution here. 