Задачи заочного тура личного первенства 2005

В 1976 году "Теорема о четырех красках" была доказана с помощью компьютера. Эта теорема утверждает, что любая плоская карта может быть раскрашена с помощью четырех красок таким образом, что два соседних региона будут иметь различные цвета.

Вы должны решить более простую задачу – раскрасить связный неориентированный граф, не содержащий петель, в два цвета так, чтобы две соседние вершины имели разные цвета.

Ввод содержит несколько тестовых случаев. Каждый тест начинается со строки, содержащей число `n` (`1\ <\ n\ <\ 200`) – количество вершин графа. Следующая строка содержит число ребер графа l. Далее следует l строк, каждая из которых содержит два целых числа, означающие номера соединяемых этим ребром вершин графа. Вершины графа нумеруются числами от 0 до `n-1`.

Строчка с `n\ =\ 0` означает конец ввода и не обрабатывается.

Вы должны вывести сообщение, можно ли раскрасить граф в 2 цвета, как показано в примере.

3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

NOT BICOLORABLE.
BICOLORABLE.

Требуется определить, можно разместить бифштекс, имеющий форму `n`-угольника (возможно невыпуклого), на круглой тарелке радиусом `R` так, чтобы края бифштекса не выходили за края тарелки.

Ввод содержит несколько тестовых случаев. Первая строка теста содержит целое число `n` (`0\ <\ n\ <\ 100`). Далее следует `n` строк, содержащих по два целых числа – координаты вершин `n`-угольника. Последней строкой в тесте задается вещественное число `R` – радиус тарелки.

Строка с `n\ =\ 0` сигнализирует об окончании набора тестов и не обрабатывается.

В тестовых случаях нет вершин с одинаковыми координатами.

Если многоугольник может быть размещен внутри окружности заданного радиуса, выведите:

В противном случае выведите:

3
0 0
1 0
0 1
1.0
3
0 0
1 0
0 1
0.1
0

The polygon can be packed in the circle.
There is no way of packing that polygon.

Solomon Golomb's self-describing sequence `⟨\ f(1),\ f(2),\ f(3),\ …\ ⟩` is the only non-decreasing sequence of positive integers with the property that it contains exactly `f(k)` occurrences of `k` for each `k`. A few moments thought reveals that the sequence must begin as follows:

In this problem you are expected to write a program that calculates the value of `f(n)` given the value of `n`.

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer `n` (`1\ ≤\ n\ ≤\ 2,000,000,000`). The input terminates with a test case containing a value 0 for `n` and this case must not be processed.

For each test case in the input output the value of `f(n)` on a separate line.

100
9999
123456
1000000000
0

21
356
1684
438744