Задача A. Гаджет в кредит

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

Условие

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

В магазине Васе объяснили правила предоставления кредита.

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

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

  1. P = 0
  2. C, P ≤ 103

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

Входной файла содержит целые числа N P C.

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

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

Ограничения

1 ≤ C ≤ 109; 0 ≤ P ≤ 109; 1 ≤ N ≤ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0 1
1
2
1 124 12
8
3
1 1 12
2

Задача B. Дипломы

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

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

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

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

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

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 109

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

Входной файл (diploma.in) Выходной файл (diploma.out)
1
2 3 10
9

Задача C. Скучные дни

Автор:Михалев Ю.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

Чтобы не дать Васе умереть от скуки, вы должны срочно научиться отвечать на следующий вопрос: является ли промежуток с l по r день включительно скучным?

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

Первая строка входных данных содержит два целых числа N — количество дней и M — количество запросов.

Вторая строка содержит N чисел:  − 1, если i-ый день был скучным, и 1 иначе.

Следующие M строк содержат запросы вида: li ri

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

Выходные данные должны содержать M строк - ответы на запросы

В i − й строке необходимо вывести  − 1, если промежуток с li по ri дни включительно считается скучным, и 1 в противном случае

Ограничения

1 ≤ N ≤ 5 ⋅ 104

1 ≤ M ≤ 5 ⋅ 104

1 ≤ li ≤ ri ≤ N

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

Стандартный вход Стандартный выход
1
6 6
1 -1 -1 1 1 -1
1 2
1 6
2 3
4 5
3 6
1 5
-1
-1
1
1
1
1
2
5 4
1 1 -1 1 1
1 5
4 5
3 3
2 2
-1
1
-1
1
3
10 5
-1 -1 -1 1 -1 -1 1 1 -1 -1
1 3
1 4
3 5
8 10
3 9
-1
-1
1
1
1

Задача D. Рейд на босса

Автор:Михалев Ю.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Вася играет в новую MMORPG и собирается пойти в рейд на босса. Однако, он столкнулся с двумя проблемами:

1. Он не знает на какого босса пойти

2. У него нет нужной экипировки для похода в рейд

Чтобы пойти в рейд на i-го босса, персонажу Васи нужно иметь уровней вещей персонажа не менее bi. Начальный уровень вещей персонажа Васи равен нулю. Вещи можно купить во внутриигровом магазине: j-ая вещь стоит aj монет и добавляет столько же к уровню вещей персонажа.

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

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

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

Первая строка входных данных содержит два целых числа: N — количество вещей в магазине и M — количество боссов.

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

Третья строка содержит M чисел: bi  — минимальный уровень вещей, необходимый для похода в рейд на i-го босса

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

Выходные данные должны содержать M чисел: ci  — минимальные затраты на покупку вещей для похода на i-го босса

В случае, если для данного босса невозможно получить необходимый уровень вещей, программа должна вывести -1

Ограничения

1 ≤ N ≤ 5 ⋅ 104

1 ≤ M ≤ 5 ⋅ 104

1 ≤ ai, bi ≤ 109

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

Стандартный вход Стандартный выход
1
6 5
1 4 5 7 7 8
3 5 16 25 33
5 5 17 32 -1
2
10 8
10 20 30 40 50 60 70 80 90 100
1 2 9 10 550 551 151 150
10 10 10 10 550 -1 210 150

Задача E. Мёд и справедливость

Автор:Кленин А. С.   Ограничение времени:4 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит ai микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел ai.

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ ai ≤ 105

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

Стандартный вход Стандартный выход
1
3
1 1 2
1 2 3
2
2
2 5
-1

Problem G. Caterpillar

Author:И. Блинов   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

A caterpillar of length L crawls over rough terrain. Rough terrain can be represented as a one-dimensional array of N cells with different heights. A cell ai is called a downhill if ai > ai + 1. A cell ai is called an uphill if ai < ai + 1. Initially, the caterpillar occupies the first L cells.

In order to advance one cell, the caterpillar spends 1 second of time. However, if it occupies more downhills than uphills, and the head of the caterpillar is on the downhill, it immediately moves one cell to the right.

Determine after how many seconds the head of the caterpillar reaches the last cell.

Input format

The first line of the input file contains two integers L, N. The second line contains N integers ai.

Output format

The output must contain one integer — time after which the caterpillar reaches the last cell.

Constraints

1 ≤ ai, N, L ≤ 106, L ≤ N, ai ≠ ai + 1

Sample tests

No. Standard input Standard output
1
1 4
4 3 2 3
1
2
3 10
10 9 8 7 8 9 10 9 8 7
4

0.458s 0.017s 25