#1244

Дремучий лес

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2003, Задача H ]

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.

Входные данные

Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

Выходные данные

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

Примеры

Входные данные

3
      0.00      30.00      25.00
      0.00     -30.00      25.00
     40.00       0.00      16.00

Выходные данные

NO
     -833.3333340000      -552.7707973875
      833.3333340000       552.7707973875

Входные данные

3
      0.00      30.00      29.00
      0.00     -30.00      29.00
     40.00       0.00      19.00

Выходные данные

YES

#1379

Рамка

Темы: [Условный оператор (if)]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача B ]

Дана рамка (края прямоугольника единичного размера). Требуется определить, можно ли замостить рамку отрезками 1 на X.

Рассмотрим прямоугольник размером X × Y, из середины которого вырезали прямоугольник размером (X – 2) × (Y – 2). Назовем такую геометрическую фигуру рамкой размера X × Y. На рисунке 1 изображена рамка размера 5 × 6.

Рисунок 1. Рамка 5 × 6

Рисунок 2. Рамка 5 × 6, замощенная плитками 3 × 1

Предположим, что у нас имеется неограниченный запас плиток размера A × 1. Рассмотрим следующую задачу: можно ли полностью замостить рамку размера X × Y такими плитками (плитки разрешается поворачивать на 90 градусов). Например, рамку 5 × 6 можно полностью замостить плитками размера 3 × 1 (один из способов показан на рисунке 2), а плитками размера 4 × 1 – нельзя.

Входные данные

Первая строка входного файла содержит два целых числа – X и Y (3 ≤ X, Y, ≤ 10⁶). Вторая строка содержит число N – количество видов плиток, которые следует проанализировать (1 ≤ N ≤ 1000). Третья строка содержит N натуральных чисел, не превышающих 10⁶. Обозначим i-ое число третьей строки входного файла за A_i.

Выходные данные

Выведите в выходной файл N строк, i-ая строка должна содержать слово yes, если можно замостить рамку размера X × Y плитками размера A_i × 1, и no в противном случае.

Примеры

Входные данные

5 6
2
3 4

Выходные данные

yes
no

#1380

Умный чертежник

Темы: [Двумерные массивы] [Стек]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача C ]

Линия задается набором вертикальных и горизонтальных отрезков единичной длины. Требуется изменить порядок отрезков так, чтобы линия не имела самопересечений (замена на самокасания).

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

Этот робот умеет выполнять программу, которая может состоять из команд E,W,N,S — переместиться по листу в соседнюю вершину сетки вправо, влево, вперед, назад соответственно. Перемещаясь в соседний узел сетки, робот оставляет за собой ровную линию. При этом по правилам техники безопасности ему категорически запрещается проводить дважды одну и ту же линию, так как при попытке провести линию второй раз, он очень сильно пачкается в своих же собственных чернилах (они очень долго сохнут), и выходит из строя.

При этом, правда, через одну и ту же вершину сетки робот может проходить дважды. Возможно два случая (более толстой линией показано, как мы проезжаем через вершину в первый раз, более тонкой - во второй).

В первом случае мы оба раза проезжаем через вершину "прямо" (будем называть это самопересечением маршрута), а во втором случае — оба раза "поворачиваем" (это будем называть самокасанием).

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

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

Входные данные

В первой строке входного файла содержится программа для робота. Таким образом, в первой строке входного файла могут встречаться только символы E,W,N,S, а также пробельные символы, которые должны игнорироваться. Общая длина строки (включая пробельные символы) не превышает 200 символов.

Выходные данные

В выходной файл вы должны вывести одну строку с оптимизированной программой. Эта строка должна удовлетворять тем же условиям, что и входная строка.

Примеры

Входные данные

EENWSSWNN

Выходные данные

ENESWSWNN

#1382

Трубочист

Темы: [Быстрая сортировка]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача E ]

Дана последовательность чисел. Необходимо переставить все числа (кроме одного фиксированного) так, чтобы сумма модулей разностей соседних чисел была минимальна.

После пожара 1812 года на одной из главных улиц Москвы уцелел лишь один дом. Вернувшиеся после победы жители решили вновь поселиться на этой улице. При этом каждый решил построить себе дом такой же высоты, каким он был у него до пожара.

Дома будут строиться вплотную друг другу, а крыши соседних домов будут соединяться лестницами (длина лестницы равна разнице высот домов), чтобы трубочист мог путешествовать по крышам и чистить трубы.

Когда план постройки домов был уже почти утвержден, свое веское слово сказал Главный Трубочист. Он попросил построить дома так, чтобы суммарная длина лестниц была минимальной. Помогите ему составить такой план постройки домов.

Входные данные

Во входном файле записано сначала число N (1 ≤ N ≤ 10000), затем N чисел — высоты домов до пожара (это натуральные числа от 1 до 10⁹), и затем K — номер уцелевшего дома.

Выходные данные

В выходной файл выведите высоты домов в таком порядке, чтобы выполнялось требование Главного Трубочиста. Обратите внимание, что K-ый дом (уцелевший) перестраивать не нужно (и следовательно его высота должна остаться прежней).

Примеры

Входные данные

5
1 3 4 2 6
2

Выходные данные

6 3 4 2 1

#1384

Репортаж

Темы: [Динамическое программирование: последовательности]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача H ]

Для N дней заданы высоты. Требуется выделить максимальное подмножество дней нечетной длины (2K+1), так что бы впервые K дней высота увеличивалась,на K+1 день был достигнут максимум, а в оставшиеся дни высота уменьшалась.

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте h_i. Поскольку главный редактор газеты настаивает, чтобы название статьи было «Восхождение и спуск», решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x₁-ом, x₂-ом, …, x₂_k₊₁-ом (x₁ < x₂ < … < x_2k+1)) дне, то должно выполняться условие h_x1 < h_x2< … < h_xk< h_xk+1 > h_xk+2> … > h_x2k+1. Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.

Входные данные

Первая строка входного файла содержит число N – количество дней в походе (1 ≤ N ≤ 100). Следующая строка содержит N целых чисел – h₁, h₂, …, h_N (0 ≤ h_i≤ 10⁴).

Выходные данные

В первой строке выходного файла выведите число k. Затем выведите 2k+1 число - номера дней, репортаж о которых следует включить в статью, в возрастающем порядке. Если возможных ответов несколько, выведите любой.

Примеры

Входные данные

7
0 3 1 10 7 2 1

Выходные данные

2
1 2 5 6 7

Входные данные

4
1 2 3 4

Выходные данные

0
1