Задача A. Кафель в ванной

Автор:Д. Давидюк   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Требуется написать программу для определения минимального количества плит кафеля, которое потребуется для укладки стены в ванной. Стена имеет длину W и высоту H. Кафельная плита имеет форму квадрата со стороной A. Плитку можно разрезать на любое число частей частей и класть разные её куски в разных частях комнаты.

Формат входного файла

Входной файл содержит целые числа W H A.

Формат выходного файла

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

Ограничения

1 ≤ W, H, A ≤ 10000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 5 3
2
2
2 4 3
1

Задача B. Вынутый разворот

Автор:Владивостокская городская олимпиада школьников по информатике 2002/2003   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

Во входном файле содержатся два целых числа A и B — номера страниц на стороне листа, в произвольном порядке

Формат выходного файла

В выходном файле должно содержаться единственное число:

Ограничения

1 ≤ A, B ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 14
16
2
9 1
0

Задача C. Подсчёт баллов за задачу

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Формат входного файла

В первой строке файла содержится единственное число N.

Во второй строке файла содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

Формат выходного файла

Выходной файл должен содержать единственное число — количество баллов за задачу.

Ограничения

1 ≤ N ≤ 100

1 ≤ ai ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 5 10 
+-++-
9
2
6
1 1 3 5 10 25
+-+--+
29

Задача E. Болезнь

Автор:Анна Малова (Жюри XXI командной олимпиады школьников Санкт-Петербурга по информатике и программированию)   Ограничение времени:2 сек
Входной файл:disease.in   Ограничение памяти:256 Мб
Выходной файл:disease.out  

Условие

В Байтландии вспыхнула эпидемия опасной болезни. Известно, что возбудителями болезни являются n различных болезнетворных бактерий.

Для правильного лечения пациента врачам необходимо знать, чем именно была вызвана его болезнь. Для этого пациент сдает m анализов: каждый анализ проверяет наличие или отсутствие некоторых видов бактерий. Анализ дает положительный результат, если в крови у человека есть хотя бы один из проверяемых этим анализом возбудителей болезни.

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

Формат входного файла

В первой строке входного файла заданы два числа n (1 ≤ n ≤ 100) — число различных возбудителей болезни и m — число анализов. Следующие m (1 ≤ m ≤ 10 000) строк содержат по n + 1 числу. Первые n чисел описывают, какие возбудители обнаруживаются этим анализом, i-е число равно 1, если анализ проверяет наличие i-го возбудителя и 0 — в противном случае.

Последнее число в строке равно 1, если анализ дал положительный результат, и 0 — в противном случае.

Формат выходного файла

Если входные данные противоречивы, выведите в выходной файл единственную строку Incorrect. В противном случае выведите в выходной файл три строки. Каждая строка задается в формате: число бактерий, далее их номера.

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

Примеры тестов

Входной файл (disease.in) Выходной файл (disease.out)
1
3 3
1 0 0 0
1 1 1 1
0 1 0 0
2 1 2
1 3
0
2
2 2
1 1 0
1 0 1
Incorrect
3
2 1
1 1 1
0
0
2 1 2

Задача F. Большой линейный коллайдер

Автор:Центральная предметно-методическая комиссия   Ограничение времени:3 сек
Входной файл:linear.in   Ограничение памяти:256 Мб
Выходной файл:linear.out  

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e − , либо положительно заряженную частицу — позитрон e + . В эксперименте i-я частица исходно размещается в точке с координатой xi. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e −  частицы перемещаются по направлению уменьшения координаты, а e +  частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

Если в процессе перемещения частицы e −  и e +  оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.

Ученые выбрали m различных моментов времени t1, t2, ..., tm, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени tj, не должны учитываться при подсчете количества частиц для этого момента времени.

Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.

Формат входного файла

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (x1 < x2 < x3 < ... xn). Частица e −  описывается значением vi =  − 1, а частица e +  описывается значением vi = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t1,t2,...,tm.

Формат выходного файла

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1 ≤ n, m ≤ 200000

 − 109 ≤ xi, m ≤ 109

0 ≤ ti ≤ 109

vi равно  − 1 или 1

Описание подзадач и системы оценивания

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

Подзадача Баллы Ограничения Необходимые подзадачи
nximti
1351 ≤ n ≤ 100 − 100 ≤ xi ≤ 100m = 10 ≤ ti ≤ 100
2121 ≤ n ≤ 100 − 109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091
3121 ≤ n ≤ 200000 − 109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091, 2
4411 ≤ n ≤ 200000 − 109 ≤ xi ≤ 109 1 ≤ m ≤ 2000000 ≤ ti ≤ 1091, 2, 3

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примеру

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e +  в точке  − 1, частица e −  в точке 0, частица e +  в точке 1 и частица e −  в точке 5.

В момент времени 0.5 первая частица e +  и первая частица e −  сталкиваются в точке с координатой  − 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

Примеры тестов

Входной файл (linear.in) Выходной файл (linear.out)
1
4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3
4
2
0
0

Задача G. Фонари

Автор:А. Кленин, И. Бураго   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На улице длиной в 100 метров установлено N фонарей высотой y1, y2, …, yN метров на расстоянии x1, x2, … xN метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

Рекомендуется рассмотреть частичные решения:

  1. N ≤ 2

Формат входного файла

Во входном файле содержится число N, за которым следует N пар целых чисел x1 y1 x2 y2… xN yN.

Формат выходного файла

Выходной файл должен содержать единственное число — максимальное количество фонарей.

Ограничения

1 ≤ N, yi ≤ 100, 0 ≤ xi ≤ 100.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 50 10 51 10
2

Задача I. Кондиционеры

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:cond.in   Ограничение памяти:256 Мб
Выходной файл:cond.out  

Условие

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна ai ватт.

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

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе — кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для n, m ≤ 1000 будут оцениваться из 50 баллов.

Формат входного файла

Первая строка входного файла содержит одно целое число n — количество классов в школе.

Вторая строка содержит n целых чисел ai — минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i.

Третья строка содержит одно целое число m — количество предложенных моделей кондиционеров.

Далее, в каждой из m строк содержится пара целых чисел bj и cj — мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 50000;

1 ≤ ai ≤ 1000;

1 ≤ m ≤ 50000

1 ≤ bj ≤ 1000, 1 ≤ cj ≤ 1000;

Примеры тестов

Входной файл (cond.in) Выходной файл (cond.out)
1
1
800
1
800 1000
1000
2
3
1 2 3
4
1 10
1 5
10 7
2 3
13

Задача J. Ближайшее число

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

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

Формат выходного файла

В выходной файл необходимо вывести N целых чисел bi, таких что bi является ответом на задачу для числа ai.

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

Задача K. Космическое поселение

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:1 сек
Входной файл:space.in   Ограничение памяти:256 Мб
Выходной файл:space.out  

Условие

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из N одинаковых модулей.

Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером A × B метров.

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

Модуль с защитным слоем, толщина которой равна D метрам, будет иметь в основании форму прямоугольника размером (A + 2D) × (B + 2D) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером W × H метров.

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

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

Пояснения к примеру

В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.

Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле — размер 6 × 6 метров.

Добавить дополнительный защитный слой к модулю нельзя.

Формат входного файла

Входной файл содержит пять разделенных пробелами целых чисел: N, A, B, W, H.

Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.

Формат выходного файла

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

Если дополнительный защитный слой установить не удастся, требуется вывести число 0.

Ограничения

1 ≤ N, A, B, W, H ≤ 1018

Система оценки и описание подзадач

Подзадача 1 (26 баллов)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (23 балла)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 109.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (24 балла)

1 ≤ N ≤ 109; 1 ≤ A, B, W, H ≤ 1018.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (27 баллов)

1 ≤ N ≤ 1018; 1 ≤ A, B, W, H ≤ 1018.

В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

Входной файл (space.in) Выходной файл (space.out)
1
11 2 3 21 25
2
2
1 5 5 6 6
0

Задача L. online addition

Автор:известная   Ограничение времени:1 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

Данная задача является интерактивной.

На вход подаются числа. Ваша программа должна вычислить их сумму.

Протокол взаимодействия

На каждом шаге взаимодействия ваша программа должна:

  1. Считать число x со входного потока.
  2. Если это число равно  − 1 — завершить выполнение.
  3. Иначе произвести необходимые вычисления и вывести во выходной поток текущую сумму s всех x с последующим символом конца строки. Не забудьте сбросить (flush) выходной буфер.

Формат входных данных

единственное число x на каждой из n итераций

Формат выходных данных

единственное число s на каждой из n итераций

Ограничения

|x| ≤ 263 − 1

|s| ≤ 264 − 1

1 ≤ n ≤ 107


0.663s 0.010s 33