Страница: 1 2 >> Отображать по:
#601
Забор
  
Темы: [Формула]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить \(k\) досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

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

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

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

Первая строка входного файла содержит количество досок в заборе \(n\) (1 ≤ \(n\) ≤ \(10^9\)) и вместимость ведерка \(k\) (1 ≤ \(k\) ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора \(m\) (1 ≤ \(m\) ≤ 50). Далее следуют \(m\) строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей \(l_i\) и правой границей \(r_i\) (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\)). Такое описание означает, что не покрашены \(l_i\)-я, (\(l_i\)+1)-я, …, (\(r_i\)–1)-я, \(r_i\)-я доски забора (доски нумеруются от 1 до \(n\)). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

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

Примеры
Входные данные
5 2
2
1 2
5 5
Выходные данные
12
#990
Праздники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Нерабочими называются выходные, а также праздники: 23 февраля, 8 марта и K первых дней года. Праздник попавшие на выходные, переносятся. По заданному K требуется определить максимальное количество подряд идущих нерабочих дней.

Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля (День олимпиады по информатике) и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (суббота и воскресенье), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни.

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

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

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

На вход подается единственное число K (1≤K≤50).

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

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

Примеры
Входные данные
2
Выходные данные
4
Входные данные
10
Выходные данные
16
#112033
Берляндолимпстрой
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Стройка длилась \(K + 1\) день со дня номер \(0\) по день номер \(K\), причем стоимость j-го объекта в нулевой день была равна \(a_j\) бурлям. Однако каждый следующий день стоимость каждого объекта увеличивалась согласно следующему правилу: стоимость j-го объекта в i-й день становилась равна сумме стоимостей всех объектов с номерами, меньшими или равными j, в предыдущий день. Иначе говоря, \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\), где \(S_{i,j}\) — стоимость j-го объекта в i-й день. В итоге на j-й объект было потрачено \(S_{K,j}\) , то есть его стоимость в последний \(K\)-й день. \t{Назовем эту величину итоговой стоимостью j-го объекта.}

Такие увеличения стоимостей проектов для Берляндии не редкость, однако оказалось, что и этих денег не хватило! Выяснилось, что в некоторый день i > 0 стоимость некоторого объекта j дополнительно повысилась на пока не известную следователям сумму X (то есть \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\) + X), что повлияло на стоимости объектов в последующие дни. Следователи выяснили, что из-за этого сумма итоговых стоимостей всех объектов увеличилась на \(R\) бурлей.

Помогите следователям выяснить минимально возможное значение X.

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

В первой строке входного файла содержатся три целых числа \(N\), \(K\), \(R\): количество олимпийских объектов (\(1 \le N \le 10^5\) ), количество дней увеличения стоимости объектов (\(1 \le K \le 10^5\) ) и количество бурлей, на которое незаконно возросла итоговая сумма (\(1 \le R \le 10^{18}\)). В следующей строке входного файла содержатся N целых чисел \(a_i\) — стоимости объектов в нулевой день (\(1 \le a_i \le 10^9\)).

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

Единственная строка выходного файла должна содержать единственное целое число — минимально возможное значение \(X\)

Система оценки

Тесты к этой задаче состоят из четырех групп.

0. Тест 1. Тест из условия, оцениваемый в ноль баллов.

1. Тесты 2—25. В тестах этой группы \(N \le 10, K \le 10, a_i \le 10\), искомое значение \(X\) не превосходит \(10\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

2. Тесты 26—38. В тестах этой группы \(N \le 1 000, K \le 1 000\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов первой группы.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Тесты в этой группе оцениваются \t{независимо}

Примеры
Входные данные
3 3 12
1 3 3
Выходные данные
2
#112744
Выбор зала
  
Темы: [Формула]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом. Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от \(A\) до \(B\) квадратных метров, включительно.

Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от \(C\) до \(D\) метров, включительно. Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами \(Y\) × \(Z\) и \(Z\) × \(Y\) считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям. Требуется написать программу, которая по заданным \(A\), \(B\), \(C\) и \(D\) определяет количество различных залов, площадь которых находится в пределах от \(A\) до \(B\), а периметр — от \(C\) до \(D\), включительно.

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

Входной файл содержит четыре разделенных пробелами целых числа: \(A\), \(B\), \(C\) и \(D\) (1 ≤ \(A\) ≤ \(B\) ≤ \(10^9\) , 4 ≤ \(C\) ≤ \(D\) ≤ \(10^9\) )

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

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

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

В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2

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

Подзадача 1 (50 баллов)
1 ≤ \(A\) ≤ \(B\) ≤ 1000, 4 ≤ \(C\) ≤ \(D\) ≤ 1000.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (50 баллов)
1 ≤ \(A\) ≤ \(B\) ≤ \(10^9\),
4 ≤ \(C\) ≤ \(D\) ≤ \(10^9\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Примеры
Входные данные
2 10 4 8
Выходные данные
3
#113565
Глупый учитель
  
Темы: [Формула]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 3, Глупый учитель ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Учитель отправил своим ученикам письмо со следующим заданием: "Напишите программу, которая определит значение X по следующему выражению: X = number 1 pot 1 + number 2 pot 2 + ... + number n pot n если известно, что number 1 , number 2 , ... , number n - натуральные числа, а pot 1 , pot 2 , ... , pot n - однозначные натуральные числа."

К сожалению, из-за того что учитель был очень глупый, при записи формулы на компьютер, форматирование текста было потеряно и формула для значения X превратилось в сумму N чисел: X = P 1 + P 2 + ... + P n . Например, без форматирования изначальная формула X =  21 2 + 123 5 превратилась в формулу X =  212 + 1235 . Помогите глупому учителю написать программу, которая по новой формуле (то есть по данным числам P 1 , P 2 , ... , P n ) восстановит изначальное значение X .

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10 ), количество чисел в формуле. Каждая из следующих N строк содержит одно целое число P i ( 10 ≤ P i ≤ 9999 ) - соответствующий элемент формулы.

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

Выведите единственное целое число - изначальное значение X .

Примеры
Входные данные
2
212
1253
Выходные данные
1953566
Входные данные
5
23
17
43
52
22
Выходные данные
102
Входные данные
3
213
102
45
Выходные данные
10385
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест