07/04/2025 02:47:29

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1424. Tumble Down

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Imagine a collection of two-dimensional rectangular blocks whose sides are perfectly horizontal or vertical, pushed downward (in the negative

$y$ -direction) by gravity. Blocks resting on the

$x$ -axis or firmly atop another block are well-supported, and resist tumbling downward. In this problem, we are given the positions of a collection of blocks and determine which blocks are supported and which are not supported. In the following example, blocks 2, 3, 5 and 6 are supported, block 4 is not supported, and block 1 is not supported (but would be if moved slightly left or right).

Let

$a$ and

$b$ be blocks. We define

$"top"(b)$ and

$"bottom"(b)$ to be the

$y$ -coordinates of the bottom edge and top edge of

$b$ , and define

$"left"(b)$ ,

$"center"(b)$ and

$"right"(b)$ to be the

$x$ -coordinates of the left edge, vertical center and right edge of

$b$ . We define

$a$ left-supports

$b$ if

$"bottom"(b)\ =\ "top"(a)$ and

$"left"(b)\ <\ "right"(a)$ and

$"center"(b)\ >\ "left"(a)$ .

$a$ right-supports

$b$ if

$"bottom"(b)\ =\ "top"(a)$ and

$"right"(b)\ >\ "left"(a)$ and

$"center"(b)\ <\ "right"(a)$ .

$b$ is supported if

$"bottom"(b)\ =\ 0$ or

$∃a_l,\ a_r$ : [

$a_l$ is supported and

$a_r$ is supported and

$a_l$ left-supports

$b$ and

$a_r$ right-supports

$b$ ].

Input Format

Each line of input describes a block

$b$ and contains non-negative integers

$x,\ y$ and positive integers

$w,\ h$ separated by white space.

$(x,\ y)$ is the coordinate of the bottom left corner,

$w$ is the width, and

$h$ is the height of block

$b$ . Blocks on successive lines are implicitly numbered 1, 2, 3, … You may assume that no two blocks in the input overlap.

Output Format

For each block described in the input, output a line giving the block number and indicating whether or not it is supported, as shown in the output sample.

Sample Input

10 30 20 10
30 20 10 10
10 20 10 10
70 10 20 10
10 10 30 10
20 0 10 10

Sample Output

block 1 is not supported
block 2 is supported
block 3 is supported
block 4 is not supported
block 5 is supported
block 6 is supported

Source: California State Polytechnic University Programming Contest, Fall 2008

24/06/2010	Лето 2010 дорешивание ( 5E)
02/07/2010	Лето 2010 - 5 (E)