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

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

Входные данные
Первая строка входного файла содержит целое число N – количество кратеров, отмеченных на карте (1 ≤ N ≤ 500). Следующие N строк содержат описания кратеров с номерами от 1 до N. Описание каждого кратера занимает отдельную строку и состоит из трех целых чисел, принадлежащих диапазону [-32768, 32767] и разделенных пробелами. Первые два числа представляют собой декартовы координаты его центра, а третье – радиус. Все кратеры различны.

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

Пример входного файла
4
0 0 30
-15 15 20
15 10 5
10 10 10

Пример выходного файла
3
3 4 1

   Решение

Для каждого натурального n обозначим через S_n сумму первых n простых чисел:  S₁ = 2,  S₂ = 2 + 3 = 5,  S₃ = 2 + 3 + 5 = 10,  ... .
Могут ли два подряд идущих члена последовательности (S_n) оказаться квадратами натуральных чисел?

   Решение

Страница: << 1 2 [Всего задач: 8]      

Пусть точки A , B , C лежат на окружности, а прямая b касается этой окружности в точке B . Из точки P , лежащей на прямой b , опущены перпендикуляры PA₁ и PC₁ на прямые AB и BC соответственно (точки A₁ и C₁ лежат на отрезках AB и BC ). Докажите, что A₁C₁ AC .

Прислать комментарий

Решение

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

Прислать комментарий

Решение

Для каждого натурального n обозначим через S_n сумму первых n простых чисел:  S₁ = 2,  S₂ = 2 + 3 = 5,  S₃ = 2 + 3 + 5 = 10,  ... .
Могут ли два подряд идущих члена последовательности (S_n) оказаться квадратами натуральных чисел?

Прислать комментарий

Решение

Страница: << 1 2 [Всего задач: 8]