Another Contest 5 Problem 4 - Tudor Interacts With Poop

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.5s
Memory limit: 256M

Problem type

Tudor decided to build a 30 \times 30 rectangular pen for his goats. Unfortunately, he forgot about a classic problem when it comes to owning goats - dealing with goat poop.

Goats poop in rectangles. Formally, Tudor's pen has vertices at (0, 0) and (30, 30), and the poop for his goats lies exactly on every point inside and on the sides of the axis-aligned rectangle with vertices at (x_1, y_1) and (x_2, y_2) where 0 \le x_1 \le x_2 \le 30 and 0 \le y_1 \le y_2 \le 30 and the vertices are at lattice points. Note that the rectangle may have zero area, and could even be a single point.

Tudor has K poop detectors that he can place anywhere in the field. Each poop detector can be placed at a lattice point and, when turned on, will report the minimum Manhattan distance to any point inside the rectangle with poop.

Help Tudor determine the area of his pen that is covered in poop.


There are three subtasks. The subtasks are cumulative - a solution that passes subtask x should pass subtask x-1 and therefore we will short-circuit your submission on the first test case it fails.

Subtask 1

1 \le T \le 10^2

K = 10^3

Subtask 2

1 \le T \le 10^3

K = 10

Subtask 3

1 \le T \le 10^3

K = 4

Input/Output Specification

The first line contains a single positive integer, T. You will need to solve T independent instances of this problem.

When solving a new instance of the problem, Tudor gives you K new poop detectors. You do not need to use all of them. You may not use unused poop detectors from previous instances. You are not provided the value of K as part of the input to the problem - as the subtasks are cumulative, we guarantee that any solution which would pass a given subtask will also pass all subtasks that precede it.

This is an interactive problem. You may print a query of the form ? k x_1 y_1 ... x_k y_k on a single line, indicating that Tudor uses k poop detectors at the lattice points (x_i, y_i) for 1 \le i \le k. Each point must be inside or on the border of Tudor's pen. After printing and flushing the output, you may read in a line of k integers representing the minimum Manhattan distance from the lattice points, in order, to the poop. The problem is non-adaptive - the rectangle is predetermined when the test case begins.

Whenever you are ready to print the area, output the area of the rectangle in the format ! A, indicating that the area of the rectangle covered in poop is A. After doing so, you may start immediately solving the next instance if any such instance exists. Otherwise, your program should return immediately.

Make sure that each query or area output is printed on its own line. Failure to properly end each operation with a newline will result in the interactor hanging and a TLE verdict. Note that other failures to adhere to the specifications of the output, including but not limited to proper formatting or flushing, may result in unexpected wrong verdicts. You may read up on flushing here.

If you print something unexpected at any point during the problem, including guessing the area incorrectly, the interactor will print -1 and stop processing further input.

Sample Interaction

Note that <<< represents values that you should read from stdin, and >>> represents a string that you print to stdout.

1 <<<
>>> ? 1 0 0
2 <<<
>>> ? 1 2 2
2 <<<
>>> ? 2 0 2 2 0
2 2 <<<
>>> ! 0


There are no comments at the moment.