CCO '09 P4 - Bottle Caps

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 7.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Olympiad: 2009 Day 2, Problem 1

You have N (1 \le N \le 10\,000) caps and N bottles. Each bottle has a unique size and each cap corresponds to a single bottle. Unfortunately, the caps and bottles are so close together in size that it is impossible to compare them visually.

The only comparison that we can make is between a cap and a bottle. We do this by attempting to put the cap on the bottle. From this, we know whether the cap is too small, too large, or just the right size in relation to the bottle.

Match all the caps to their corresponding bottles as quickly as possible by interacting with a library that compares the pieces.

You may make at most 500\,000 queries.

In 20\% of the test cases, N \le 700.
In another 40\% of the test cases, N \le 3000.

Interactive Instructions

The first line contains the integer N.

Afterwards, you must start interaction.

To query, output 0 capid bottleid. You will receive a 1 if the cap is too large for the bottle, 0 if the cap fits the bottle, and -1 if the cap is too small for the bottle.

To report, output 1 capid bottleid. You will not receive anything back from the interactor.

You may interlace reports and queries. Once you have reported N times, your solution must exit. Otherwise, your result is undefined. Only queries (type 0) count towards your 500\,000 query limit.

Note: Up to 3s of the time limit may be taken up by the interactor.

Sample Interaction

The cap sizes are: [2, 1, 3]. The bottle sizes are: [3, 2, 1]. >>> denotes your output. Do not print this out.

>>> 0 1 1
>>> 0 1 2
>>> 0 1 3
>>> 1 1 2
>>> 0 2 1
>>> 1 3 1
>>> 1 2 3

Description of Sample Interaction

There are three caps and three bottles. The first, second and third cap match the second, third, and first bottle, respectively.


There are no comments at the moment.