Have you ever met the members of the ten European royal houses, the Argentinian football team including
their coach Diego Maradona, or all of the Turing and Fields medal prize winners? We have invited many
celebrities from all over the world to the CEOI 2010 closing ceremony. Unfortunately, very few of them
responded to our invitation, and those who did, politely rejected. Nevertheless, do not forget to bring your
camera to the ceremony, one never knows who might turn up!
As you can imagine, the security of the guests is of utmost importance. The problem is how to seat their
bodyguards in the audience so that maximal security is guaranteed.
The auditorium contains many seats, arranged into a large grid. Based on the safety regulations a security
expert has determined necessary bodyguard counts for each row and each column of the auditorium.
Assume that the auditorium is initially empty, i.e., you may seat bodyguards wherever you wish. Each seat may
only be occupied by a single bodyguard.
There are multiple test case in the input file, which begins with an integer T indicating the total number of test cases. For each test case, the input begins with the description of the rows. The first line of the input contains one positive integer R: the
number of groups of rows. R lines follow. Each of these lines contains 2 positive integers: the required number
of bodyguards in each row of the group and the number of rows that form the group.
This is followed by the description of column groups. The next line contains one positive integer C: the number
of groups of columns. C lines follow. Each of these lines contains 2 positive integers: the required number of
bodyguards in each column of the group and the number of columns that form the group.
You may assume that the total number of bodyguards required by row constrains is the same as the total
number of bodyguards required by column constraints. You may assume that this total number of bodyguards
is at most 1018.
You may assume that all numbers are positive integers that do not exceed 109.
You may assume that 1<=R, C<=200000.
For each test case, output a single line with the number "1" if the constraints are satisfiable and the number "0" otherwise (quotes
for clarity).
2 2 2 1 1 2 1 2 2 2 3 2 1 1 2 3 2 1 1
1 0
Migrated from old NTUJ.
CEOI2010
| No. | Testdata Range | Score |
|---|