Полковник Кругляковский II

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

В **** году полковник Кругляковский развязал Великую Гражданскую Войну. В ходе ожесточенных сражений не погиб никто.
"Хроники Берляндии", том XIXI

Главному командующему Берляндии отряд разведчиков передал в руки N планов близлежащих деревень. Требуется для каждой из N деревень выяснить, захвачена ли она кругляковцами. Отличительная черта захваченных деревень - в деревне всего шесть домов и их можно разделить на две группы по три дома так, что вторая группа будет иметь вид треугольника, лежащего строго внутри треугольника, образованного первой группой. Под треугольниками понимаются треугольники ненулевой площади. Строго внутри означает тот факт, что треугольник лежит внутри другого, и их границы не имеют общих точек. Границей треугольника называется множество точек, состоящее из его сторон и вершин. Все деревни на плане состоят из шести домов.

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

В первой строке входного файла содержится целое число N (1 <= N <= 100). Далее следует описания N планов деревень. Каждое описание представляет собой 6 пар координат, описывающих дома. Координаты - вещественные, по модулю не превосходят 10^3, записанные не более чем с двумя знаками после запятой. Все числа во входном файле разделены пробелами и/или переводами строки. Координаты двух или более деревень могут совпадать.

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

Выведите N строк. В M-ой строке выведите YES, если M-ая деревня захвачена и NO в противном случае.

Пример

Ввод

2
0 0
-1 -2
3 0
0 2
1 0
0 4
-1 0
1 0
0 1
0 2
-1 3
1 3

Вывод

YES
NO

Форматирование текста

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Дана строка состоящая только из букв латинского алфавита, пробелов и знаков препинания "." и ",". Вам необходимо путем удаления и/или вставки пробелов и изменения регистров букв привести ее к такому виду, чтобы:
· между любыми двумя последовательными словами был ровно один пробел, и других пробелов не было;
· непосредственно перед любым знаком препинания стояла буква латинского алфавита и после - пробел если за знаком препинания еще есть слова. В противном случае знак препинания - последний символ строки;
· все латинские буквы должны быть малыми, за исключением первой буквы первого слова любого предложения.
Известно, что в тексте между любыми двумя знаками препинания находится хотя бы одна буква. До первого (левого) знака препинания находится хотя бы одна буква.
Под первым словом предложения подразумевается первое слово строки и любое слово, следующее за точкой.

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

Во входном файле записана строка, состоящая не более чем из 255 символов.

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

Выведите отформатированную строку.

Пример

Ввод

it IS rather Easy problem.Ha

Вывод

It is rather easy problem. Ha

221. Сушки на базу!

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

С продуктовой базы утром каждого понедельника отправляется грузовик, который развозит товар по магазинам. На грузовик помещается 10^4 кг сушек. Пусть дни занумерованы так, что понедельник первой недели это день номер 1, вторник первой недели - номер 2, понедельник второй недели - день номер 8 и т.д.
Известно, что с фабрики по производству сушек было совершенно N поставок. На базу поставки приходят по вечерам. Известно, что i-ая поставка пришла в Pi-ый день и состояла из Qi кг сушек.
Известно, что начальство склада придерживается политики, в соответствии с которой, поставки необходимо как можно скорее отправлять в магазины. Ваша задача узнать наименьший возможный номер дня, когда на базе не останется больше сушек, и все поставки будут уже доставлены на базу.
Считайте, что сушки никак не упакованы и, следовательно, сушки с одной поставки можно свободно делить между различными грузовиками.

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

В первой строке записано натуральное число N (1 <= N <= 200) - количество поставок. Далее в N строках описаны поставки парами чисел Pi, Qi (1 <= Pi <= 1000; 1 <= Qi <= 10^4). Все Pi различны. Числа в парах разделяются пробелами.

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

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

Пример

Ввод

Test #1
1
1 100

Test #2
3
5 9999
1 10000
9 9999

Вывод

Test #1
8

Test #2
22

Океан против Берляндии

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Архипелаг Берайлэндс в беде. Ученые Берляндии предсказали поднятие уровня воды в океане. Карта Берляндии изображена на листе клетчатой бумаги NхM клеток. Если в данной клетке изображен символ ".", то данная территория занята океаном, а если символ "*", то это территория архипелага. Площадь территории, соответствующей одной клетке карты равна 10000 м2. Известно, что после поднятия уровня воды, под водой окажется территория Берайлэндс, соответствующая клеткам, граничащим с океаном. Клетка граничит с океаном, если хотя бы одна из восьми соседних клеток соответствует океану. Ваша задача посчитать площадь территории, которая не подвергнется затоплению. Считайте, что за пределами карты находится океан.

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

В первой строке входного файла записана пара чисел N, M (1 <= N,M <= 50). Далее следует N строк по M символов, описывающих карту Берайлэндс.

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

Выведите площадь территории, которая не подвергнется затоплению.

Пример

Ввод

5 5
.....
.***.
.***.
.***.
.....

Вывод

10000

Расшифровка

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Учительница задала детям вычислить a^b (a в степени b). Ученик должен выбрать пару натуральных чисел a и b, не превосходящих 1000 и выполнить возведение в степень. Петя честно выполнил домашнее задание, но в школу принес только результат вычислений. Учительница отказывается принимать его работу, пока Петя не скажет a и b. Помогите Пете.

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

Во входном файле записан результат Петиной работы. Известно, что данное число имеет вид a^b для некоторых a, b, где 1 <= a,b <= 1000.

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

Выведите a и b. Если решений несколько, то выведите любое.

Пример

Ввод

16

Вывод

2 4

Треугольник

ограничение времени на тест: 1.75 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Дана треугольная таблица из плюсов и минусов, состоящая из N строк. В i-той строке содержится i знаков (для i от 1 до N). Под каждым знаком из верхних (N - 1) строк находится ровно два знака следующей строки. Например, таблица может иметь вид:

+

- +

+ - +

- + + -

 + - - - +

 

 

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

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

В первой строке записано натуральное число N (1 <= N <= 2000), где N - количество строк в треугольнике. Далее в N строках записан сам треугольник. Знаки в строках разделяются последовательностями (возможно пустыми) пробелов. Длина каждой строки входного файла не превосходит 4000 символов.

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

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

Пример

Ввод

3
+
+ -
+ - -

Вывод

1

Баобаб

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

На мебельную фабрику привезли ствол баобаба длиной N метров. Его положили вдоль линейки таким образом, что его левый конец начинается на отметке 0, а правый конец соответствует отметке N. Для производства книжной полки для берляндской научной библиотеки необходимо распилить баобаб поперек в M местах, соответствующим отметкам линейки A1, A2,:, AM. На распил электропилой "Бер 2" одного цельного куска длиной P метров тратиться P кВт энергии. Придумайте такой порядок проведения распилов, что бы суммарное количество потраченной энергии было наименьшим.
Например, если N = 20, M = 3, A1 = 3, A2 = 18, A3 = 10, то при распиливании слева направо будет затрачено 20 + 17 + 15 = 52 кВт энергии. А если сначала сделать 3-ий распил, затем 1-ый, а потом 2-ой, то затраты будут: 20 + 10 + 10 = 40 кВт.

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

В первой строке записана пара натуральных чисел N, M (1 <= N <= 10000; 1 <= M <= 50) через пробел. Во второй строке содержится последовательность целых чисел A1, A2,..., AM (1 <= Ai <= N - 1; для всех i = 1...M). Все числа во второй строке различны.

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

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

Пример

Ввод

20 3
3 18 10

Вывод

40
10 3 18