Page not loading? Try clicking here.
Placeholder

#10379
Interactive
Grading on hold

Pen Testing 90s 1024MB

Problems

You have N ballpoint pens. You know that each has a distinct integer number of units of ink between 0 and N-1, but the pens are given to you in random order, and therefore you do not know which pen is which.

You are about to go on a trip to the South Pole (where there are no pens), and your luggage only has room for two pens, but you know you will need to do a lot of important postcard writing. Specifically, the two pens you choose must have a total of at least N ink units.

Your only way to get information about the pens is to choose one and try writing something with it. You will either succeed, in which case the pen will now have one unit of ink less (and is now possibly empty), or fail, which means that the pen already had no ink left. You can repeat this multiple times, with the same pen or different pens.

Eventually, you must select the two pens to take on your trip, and you succeed if the total amount of ink remaining in those two pens is at least N units.

You will be given T test cases, and you must succeed in at least C of them. Note that all test sets in this problem are Visible.


Example 

2 5 1

1 0

0 1

0 1
4 5

4 3

0 2

0 0
3 4 3 4
Here is the same interaction, explained: // The following reads 2 into t, 5 into n and 1 into c. t, n, c = readline_int_list() // The judge secretly picks the number of units for each pen: // in test case 1: 2 0 4 1 3 // in test case 2: 1 3 2 4 0 // We write with the 4-th pen in test case 1, and with the 5-th pen in test case 2. printline 4 5 to stdout flush stdout // Reads 1 0, as the 4-th pen in test case 1 still had ink left, // but the 5-th pen in test case 2 did not. a1, a2 = readline_int_list() // We write with the 4-th pen in test case 1 again, and with the 3-rd pen in test case 2. printline 4 3 to stdout flush stdout // Reads 0 1. a1, a2 = readline_int_list() // We only write in test case 2 this time, with the 2-nd pen. printline 0 2 to stdout flush stdout // Reads 0 1. a1, a2 = readline_int_list() // We decide we are ready to answer. printline 0 0 to stdout flush stdout // We take the 3-rd and the 4-th pens to the South Pole in both test cases. printline 3 4 3 4 to stdout flush stdout // In test case 1, the remaining amounts in the 3-rd and the 4-th pens are 4 and 0, and 4+0<5, // so we did not succeed. // In test case 2, the remaining amounts in the 3-rd and the 4-th pens are 1 and 4, and 1+4≥5, // so we succeeded. // We have succeeded in 1 out of 2 test cases, which is good enough since c=1. exit

Source

GCJ 2020r3 C

You must sign in to write code.