---> 151 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 15 16 17 18 19 20 21 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Король Флатландии понял, что дальше так продолжаться не может, и нанял отважного Рыцаря, чтобы тот победил рептилию.

Рыцарь принял предложение Короля и начал готовиться к битве. Сам он участия в битве принимать не желал (не рыцарское это дело –– мечом махать), поэтому решил собрать войско из копейщиков. Но копейщикам надо платить, а у Рыцаря из-за кризиса осталось совсем немного сбережений. Помогите ему определить минимальное число копейщиков, необходимое для победы над Черным Драконом.

У копейщика и у дракона есть два параметра: количество очков здоровья и наносимый противнику урон.

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

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

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

Вводятся четыре натуральных числа через пробел: Hd, Dd, hp, dp –– количество очков здоровья дракона, урон, наносимый драконом, количество очков здоровья одного копейщика и урон, наносимый одним копейщиком. Все числа положительные и не превосходят 109.

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

Выведите на экран одно целое число –– минимальное число копейщиков, необходимое для победы над драконом.

Примеры
Входные данные
500 50 10 10
Выходные данные
20
Входные данные
500 28 10 10
Выходные данные
15
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Андрей Сергеевич — учитель математики в начальной школе. Вчера на уроке он записал на доске выражение вида

a1 ? a2 ? ... ? aN - 1 ? aN = S

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

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

В первой строке содержится число N (1 ≤ N ≤ 30) — количество чисел в левой части равенства, записанного на доске и число S, записанное в правой части равенства (1 ≤ S ≤ 106). В следующей строке даны N целых чисел в том порядке, в каком они были выписаны на доске. Все числа неотрицательные и не превышают 106.

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

Выведете на экран одно число –— количество различных вариантов расстановки знаков между числами, приводящих к правильному результату в записанном на доске выражении.

Примеры
Входные данные
2 4
2 2
Выходные данные
2
Входные данные
2 46
4 6
Выходные данные
0
Входные данные
4 8
2 2 2 2
Выходные данные
5
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Рассмотрим N-домино. В таком домино каждая костяшка состоит из двух половинок, на каждой из которых нарисовано от 0 до N точек. Полный комплект костяшек такого домино содержит все возможные костяшки, каждую — по одному разу. Например, для N=2 в комплект войдут следующие костяшки: (0,0), (0,1), (0,2), (1,1), (1,2) и (2,2)

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

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

Вводится натуральное число N (1<=N<=30).

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

Программа должна напечатать одно число - общее количество точек на всех костяшках полного комплекта N-домино.

Примеры
Входные данные
2
Выходные данные
12
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

  • высота замка (всегда целое положительное число) должна быть строго больше высот замков его вассалов (для соблюдения субординации).
  • замки первого из двух вассалов и всех вассалов этого вассала должны быть построены слева, второго вассала и его вассалов – справа (для пресечения междоусобиц). Это правило должно выполняться для всех
  • высота замка должна быть минимально возможной (для экономии ресурсов)
  • число всех подчиненных (непосредственно или через промежуточных) у правого и левого вассалов одинаково (для баланса сил).

Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i j)

Однажды в город приехал новый феодал и пожелал выкупить там замок у одного из жителей. Также ему стало интересно узнать социальный статус соседей по улице, однако, город к тому времени так разросся, что феодал уже не мог сделать этого самостоятельно. Напишите программу, которая поможет ему!

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

Первая строка входного файла содержит число N (1 ≤ N ≤ 30000) — высота замка единственного главного феодала в городе, который никому не подчиняется. Далее, в следующих двух строках идут числа i и j (\(0 \leq i, j < 10^{10000}\)), задающие улицу (i, j), на которой хочет приобрести замок новый феодал (гарантируется, что замки с номерами i и j находятся в черте города, i j, ji ≤ 105).

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

Примечание

Будут оцениваться и частичные решения задачи при малых N. Частичные решения для N<20 набирают до 40 баллов, а для N<50 набирают не более 70 баллов.

Ввод
Вывод
2
1
3
1 2 1
3
3
7
1 3 1 2 1
50
128873293
128873293
1

Фирма «АйОйЛ» построила на скоростном шоссе Москва-Тверь N автозаправок. Каждая автозаправка имеет свой номер, который присваивался ей при строительстве, начиная с единицы. Кроме того, каждая автозаправка располагается на определенном километре шоссе. Километры на шоссе нумеруются от 0, начиная от Москвы.

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

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

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

Первая строка входного файла содержит количество автозаправок N (2 ≤ N ≤ 105). Вторая строка входного файла содержит N различных целых чисел xi – километр, на котором расположена автозаправка с номером i (1 ≤ iN). Числа в строке разделены пробелом. Значения всех xi не меньше ноля и не  превосходят 109 по абсолютной величине.

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

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

Ввод
Вывод
5
10 3 7 2 5
4

Страница: << 15 16 17 18 19 20 21 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест