Разбиение многоугольника

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

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

 

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

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

Первая строка входного файла содержит целое число n -- количество вершин многоугольника (3 <= n <= 50000). Следующие n строк содержат координаты вершин многоугольника (x_i, y_i) в порядке их обхода по контуру -- целые числа, не превосходящие 10^8 по абсолютной величине.
Многоугольник не имеет самопересечений или самокасаний, никакие две вершины многоугольника не совпадают. Многоугольник имеет ненулевую площадь.

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

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

Пример

Ввод

Test #1
4
0 0
2 0
2 2
0 2

Test #2
10
0 0
1 2
2 2
3 1
4 1
5 2
4 0
3 0
2 1
1 1

Вывод

Test #1
2
1

Test #2
4
1

Пояснение

Эту задачу можно сдавать, используя 32бит компиляторы.

Ременная передача

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

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

 

На плоскости расположены N <= 100 валов (XK, YK - координаты центров, RK - радиусы; для каждого K такого, что 1<=K<=N, XK, YK - целые числа в диапазоне [-10000, 10000], RK - целые числа в диапазоне [1..10]), связанные M ременными передачами. Валы, имеющие общий центр вращения (одинаковые X и Y координаты центра) жестко связаны, т.е. при всех условиях имеют одинаковую угловую скорость (количество оборотов в единицу времени). При этом, естественно, задаваемая система геометрически правильна, т.е. валы не пересекаются между собой и валы, имеющие общий центр вращения, не могут быть соединены ремнем. Положим вал с номером J вращающимся по часовой стрелке с угловой скоростью 1000 оборотов в минуту. Требуется для каждого вала найти количество полных оборотов, которое он совершит за 1 час.

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

Первая строка входного файла содержит три числа: N, M, J разделенные пробелами. Затем следуют N строк, каждая из которых содержит тройку чисел XK, YK, RK. Следующая группа состоит из M строк вида a,b, где a и b - номера валов, связанных ремнем.

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

Выходной файл должен содержать N строк, где i-я строка содержит число полных оборотов i-го вала, которое он совершит за 1 час или строку "IDLE", если вал не вращается. В случае, если заданная система противоречива, т.е. на один вал передается вращение с разными угловыми скоростями от нескольких источников, выходной файл должен содержать строку "DO NOT TURN IT ON!".

Пример

Ввод

5 2 1
0 0 1
10 10 3
10 10 1
20 20 3
30 30 10
1 2
3 4

Вывод

60000
20000
20000
6666
IDLE

Короткий путь

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

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

 

Дед Мороз в отчаянии. Он не успевает раздать подарки. Сейчас он должен доставить подарок мальчику Пете. Он очень торопиться, поэтому хочет дойти до Петиного дома как можно быстрее. Дед Мороз составил план местности и понял, что он находится в точке (x1, y1), а пункт его назначения - точка (x2, y2). Более того, если в какой - то момент времени он находится в точке (x, y), то за одну минуту он может переместиться в одну из восьми точек: (x + 1, y), (x + 1, y + 1), (x + 1, y - 1), (x, y + 1), (x, y - 1), (x - 1, y), (x - 1, y + 1), (x - 1, y - 1). Ваша задача найти минимальное время, за которое Дед Мороз сможет добраться до Петиного дома.

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

Входной файл содержит 4 целых числа x1, y1, x2, y2 (-10^6 <= x1, y1, x2, y2 <= 10^6).

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

Выведите в файл единственное число - ответ на задачу.

Пример

Ввод

0 0 20 20

Вывод

20

Прямоугольники

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

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

 

Как всегда перед Новым Годом Петя украшал ёлку новогодними игрушками. На этот раз он решил украсить её игрушками из бумаги. Для этого он заготовил квадратный лист клетчатой бумаги, размером N * N клеток. Некоторые клетки были черного цвета, остальные белого. Интересно, ведь все игрушки, которые умел делать Петя, изготавливались из прямоугольного листа бумаги белого цвета. И тут он задумался, а сколько существует способов вырезать один прямоугольник из имеющегося у него листа бумаги. Это Вам и предстоит выяснить.

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

В первой строке входного файла находится натуральное число N (4 <= N <= 700). Затем следует N строк по N символов в каждой - описание листа бумаги. Символ '.' (символ 46) означает, что данная клетка белого цвета, а '#' (символ 35) - черного.

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

Выведите в файл единственное число - ответ на задачу.

Пример

Ввод

4
####
#.##
...#
.#..

Вывод

14

Ноты

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

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

 

После того как все игрушки были сделаны, Петя решил сочинить новогоднюю мелодию. У него есть специальное новогоднее фортепиано, в котором ровно N новогодних нот. У каждой ноты свой тон, который можно охарактеризовать натуральным числом. Петя смотрит на ноты слева направо и нажимает на некоторые из них, затем он идет справа налево и нажимает на оставшиеся. Таким образом, получается мелодия, в которой звучит каждая из нот.
Например, если ноты звучат как 1 4 5 2, то Петя, двигаясь слева направо, мог выбрать ноты c номерами 1, 3, 4. Тогда получившаяся мелодия звучала бы как 1, 5, 2, 4.
Известно, что мелодия будет звучать лучше всего, если тоны соседних нот в мелодии наиболее близки, а точнее, если сумма модулей разностей тонов соседних нот в мелодии будет минимальной. Это число Петя называет характеристикой мелодии.
Например, если мелодия звучит как 1, 5, 2, 4, то её характеристика равна |1 - 5| + |5 - 2| + |2 - 4| = 4 + 3 + 2 = 9.
Ваша задача для данных тонов нот найти мелодию с наименьшей характеристикой.

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

Первое число во входном файле - N (2 <= N <= 1000). Затем следует N натуральных чисел - тоны нот. Все тоны не превышают 10^6.

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

Выведите в файл единственное число - наименьшую возможную характеристику мелодии.

Пример

Ввод

4
1 4 5 2

Вывод

5

Пояснение

Лучшая мелодия - 4 5 2 1, её характеристика - |4 - 5| + |5 - 2| + |2 - 1| = 1 + 3 + 1 = 5.

[отсортированные по размеру решения]

Прямоугольная игра

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

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

 

Совсем недавно Петя придумал новогоднюю игру. Суть её заключается в следующем:

 

· Игра проходит на прямоугольном поле, размера N * M, заполненном числами.

· Сначала ходите Вы, выбирая некоторое число, стоящее в строке x и столбце y.

· Затем Петя выбирает некоторый прямоугольник из чисел, правая нижняя клетка которого - выбранное вами число, имеющее координаты (x, y).

· Подсчитывается число S - среднее арифметическое чисел, находящихся в выбранном Петей прямоугольнике.

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

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

Первая строка входного файа содержит два натуральных числа N и M (N, M <= 10). Затем идут N строк по M целых чисел - описание поля, на котором проходит игра. Все числа не превосходят 100 по модулю.

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

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

Пример

Ввод

2 2
0 -1
2 1

Вывод

1.0000

Кран

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

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

 

Дед Мороз подарил Пете железную дорогу. Больше всего его заинтересовал кран, который ставит контейнеры на железнодорожные вагоны. Вагоны пронумерованы в порядке 1, 2,.... На каждый вагон можно поставить не более одного контейнера. За один ход кран берет три контейнера из хранилища и переносит их на вагоны с номерами i, i + p и i + p + q или с номерами i, i + q, i + p + q (для некоторых констант p, q >= 1).
Кран нужно запрограммировать так, чтобы он поставил контейнеры на первые n вагонов поезда (всего в поезде n + p + q вагонов). Программа состоит из последовательности инструкций. Каждая инструкция описывает один ход крана. Такая инструкция является тройкой (x, y, z), где 1 <= x < y < z <= n + p + q, и определяет номера вагонов, на которые кран должен поставить контейнеры. Программа является правильной, если после ее исполнения на каждом из первых n вагонов будет находится ровно один контейнер.
Напишите программу, которая строит правильную последовательность инструкций для крана.

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

Входной файл содержит три натуральных числа p, q, n. (1 <= n <= 30000, 2 <= p + q <= 21000).

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

Первая строка выходного файла должна содержать ровно одно целое число m, равное количеству инструкций в сгенерированной программе. Каждая из следующих m строк должна содержать ровно три целых числа x, y, z, разделенные одиночными пробелами, 1 <= x < y < z <= n + p + q, x <= n, либо у равно x + p, либо у равно x + q, z = x+p+q. Это номера вагонов, на которые кран ставит контейнеры очередным ходом.

Пример

Ввод

2 3 10

Вывод

4
1 3 6
2 4 7
5 8 10
9 11 14

Длина пути

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

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

 

На уроке информатике учитель задал Пете задачу следующего содержания. На координатной прямой Ox заданы положения трех городов A, B и C. Пусть город A находится в точке с координатой a, город B в точке с координатой b, а С - в точке с координатой c. Путешественник проделал путь из города A в город B, а затем из B в C. Какой длины проделал путь путешественник?
Петя не до конца понял задачу, и подумал, что a <= b <= c. В этом случае длина пути, конечно, равна c - a. Он быстро написал решение. Так как Петя одинаково знает языки Pascal и C++, то решение он написал на обоих языках.

Var a, b, c: longint; begin assign(input, 'input.txt'); reset(input); read(a, b, c); close(input); assign(output, 'output.txt'); rewrite(output); writeln(c - a); close(output); end.

#include <stdio.h> int main() { freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); int a, b, c; scanf("%d %d %d", &a, &b, &c); printf("%dn", c - a); return 0; }

Учитель проверил решение Пети и сказал, что его программа работает правильно лишь только, если a <= b <= c. Например, на тесте a = 10; b = 30; c = 20 его программа выведет 10, вместо правильного ответа 30. Помогите Пете изменить решение так, чтобы его программа работала правильно для любых a, b, c.
Разумеется, вам надо представить решение лишь на одном языке программирования.

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

Во входном файле содержатся натуральные числа a, b, c (1 <= a <= 100; 1 <= b <= 100; 1 <= c <= 100), записанные через пробел.

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

В выходной файл выведите искомое расстояние.

Пример

Ввод

Test #1
10 30 20

Test #2
30 20 10

Вывод

Test #1
30

Test #2
20

Золотой песок

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

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

 

Грабитель пробрался на завод по производству золотого песка из воздуха. Он обнаружил, что склад завода заполнен тремя видами золотого песка. Один килограмм золотого песка первого вида на черном рынке стоит A1 у.е., второго -- A2 у.е., а третьего - A3 у.е. К несчастью, у грабителя есть только три сумки: первая рассчитана на B1 килограмм груза, вторая на B2 килограмм, а третья на B3 килограмм. В силу целого ряда причин, грабитель не может смешивать песок (то есть помещать в одну сумку более одного вида песка) и размещать песок таким образом, что один вид будет находиться более чем в одной сумке. Ваша задача найти сколько у.е. выручит грабитель в случае наилучшего для себя заполнения песком сумок. Следует считать, что на заводе неограниченные запасы песка любого вида.

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

Входной файл содержит 6 натуральных чисел записанных через пробел A1, A2, A3, B1, B2, B3. Все числа не превосходят 100.

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

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

Пример

Ввод

1 2 3 3 2 1

Вывод

14

Конфеты

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

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

 

На Новый Год каждый в компании из N человек получил в подарок K конфет. После продолжительной игры в фанты на конфеты выяснилось, что конфеты между участниками перераспределились. Теперь у первого игрока A1 конфет, у второго - A2,..., у N-ого - AN. Вскоре компания решила, что было нечестно играть в фанты на конфеты, и поэтому решено было заново распределить конфеты поровну. Они это решили делать следующим образом: кто-то за 1 ход отдает свою конфету другому игроку. За один ход лишь только один человек может отдавать одну конфету. Какое наименьшее количество ходов им понадобится? Как следует проводить перераспределение?

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

В первой строке входного файла содержатся два натуральных числа N, K (1 <= N <= 5000; 1 <= K <= 1000). Далее во второй строке содержится последовательность неотрицательных целых чисел A1, A2,..., AN. Числа в последовательности записаны через пробел. Гарантируется, что A1 + A2 +... + AN = N*K.

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

В выходной файл выведите искомое наименьшее количество ходов M. Гарантируется, что M <= 10000. Далее в M строках выведите описание каждого хода в виде двух целых чисел Pi, Qi (1 <= i <= M). Эта пара чисел обозначает, что игрок под номером Pi отдает конфету Qi-ому игроку. Если решений несколько, выведите любое.

Пример

Ввод

4 2
0 3 2 3

Вывод

2
2 1
4 1

Расшифровка

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

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

 

Компания Macrohard решила повысить уровень защищенности своих операционных систем, осуществляя шифрование всех сообщений, передаваемых внутри локальных сетей. Будем считать, что сообщение представляет собой строку S = s1s2...sn, состоящую исключительно из букв латинского алфавита. Шифрование производится в K фаз. На каждой фазе строка S заменяется строкой, в которой в первую очередь выписаны все буквы строки S, стоящие на местах, номера которых являются простыми числами (первый блок), а затем все остальные буквы (второй блок). Относительный порядок букв в каждом из двух блоков остается неизменным. Например, строка S = abcdefgh за первую фазу шифруется в строку S = bcegadfh. Если осуществить вторую фазу шифрования, то строка S примет вид S = ceafbgdh. Напомним, что число называется простым, если оно натуральное и имеет ровно два различных натуральных делителя. Простые числа: 2, 3, 5, 7, 11... Вам дан результат шифрования строки S после K фаз. Ваша задача произвести дешифрование строки.

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

В первой строке входного файла содержится натуральное число K (1 <= K <= 100), вторая строка содержит строку S, которая состоит только из букв латинского алфавита. Ее длина - натуральное число, не превосходящее 255.

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

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

Пример

Ввод

Test #1
2
CEAFBGDH

Test #2
1
BAAAACB

Вывод

Test #1
ABCDEFGH

Test #2
ABACABA

Соревнование

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

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

 

Петя с Колей решили выяснить, кто из них лучше программирует. Для этого они стали собираться в местном компьютерном классе и решать задачи из небезызвестного местного архива. Было решено, что мальчики могут готовиться дома, но не могут приносить готовые решения. Также было решено, что нужно решать с результативностью не менее 50%, то есть если у Пети решено P задач, то он не может решать задачу с номером большим, чем 2P+2. Петя очень внимательно прочел дома все N задач из архива и для каждой выписал время, за которое он может ее решить. Помогите Пете составить расписание его работы, если в соревновании побеждает решивший наибольшее количество задач за время K.

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

В первой строке записаны целые числа N и K (0 < N <= 15000, 1 <= K <= 10^9). Во второй строке записано N целых чисел A1, A2,...,AN, где Ai - время, необходимое для решения i-ой задачи (1 <= Ai <= 10^9). Числа в строках разделены пробелами.

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

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

Пример

Ввод

10 30
10 9 8 7 6 5 4 3 2 1

Вывод

6
2 4 6 8 10 9