Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 544 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 96 97 98 99 100 101 102 >> Отображать по:
#112829
Ремонт дороги
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Для ремонта дороги можно привлечь несколько компаний-подрядчиков. Каждая компания может отремонтировать только непрерывный фрагмент дороги. При этом из-за требований антимонопольного законодательства длина фрагмента дороги, который ремонтирует одна компания, не должна превышать L километров (даже если на фрагменте, который ремонтирует одна компания, есть не нуждающиеся в ремонте участки, общая длина данного фрагмента не должна превышать L километров).

Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.

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

Первая строка входных данных содержит целое число L ( L >  0 ) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N ( N >  0 ) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.

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

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

Примечание

В тесте из примера первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.

Ограничения и система оценивания

Решение, правильно работающее в случае, когда числа L и N не превосходят 10, будет оцениваться в 30 баллов.

Решение, правильно работающее в случае, когда числа L и N не превосходят 1000, будет оцениваться в 60 баллов.

Решение, правильно работающее в случае, когда числа L и N не превосходят 10 5 , будет оцениваться в 100 баллов.

Примеры
Входные данные
3
8
0
0
1
0
1
0
1
0
Выходные данные
2
#112830
Cookie Clicker
  

В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.

Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1  + P печенек в секунду, две фабрики — 1  +  2 P печенек, три фабрики — 1  +  3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.

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

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

Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).

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

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

Примечание

В первом тесте: через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.

Во втором тесте: игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.

Ограничения и система оценивания

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

Решение, правильно работающее в случае, когда все входные числа не превосходят 1000, будет оцениваться в 70 баллов.

Решение, правильно работающее в случае, когда все входные числа не превосходят 10 9 , будет оцениваться в 100 баллов.

Примеры
Входные данные
50
3
100
Выходные данные
75
Входные данные
99
10
100
Выходные данные
100
#112831
Строки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.

Необходимо при помощи этих операций сделать все три строки равными какой-то другой общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать общее количество операций.

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

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

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

Если при помощи указанных операций возможно сделать все три строки равными, выведите такую строку S , что суммарное число операций, необходимых для преобразования всех трёх данных строк к строке S , будет минимальным. Если этого сделать нельзя, программа должна вывести одно слово IMPOSSIBLE (заглавными буквами).

Примечание

Решение, которое выводит правильный ответ только на тестах из условия и тех тестах, на которых ответом является слово IMPOSSIBLE, будет оцениваться в 0 баллов.

Примеры
Входные данные
aaaza
aazzaa
azzza
Выходные данные
aazza
Входные данные
xy
xxyy
yx
Выходные данные
IMPOSSIBLE
#113096
Призы(2016)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Петя участвует в конкурсе, в котором разыгрывается \(n\) призов. Призы пронумерованы от 1 до \(n\).

По итогам конкурса участник может набрать от 2 до \(n\) баллов. Если участник наберет \(k\) баллов, то он получит один из призов с номером от 1 до \(k\). Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся \(k\) – 1.

Список призов стал известен Пете. Петя определил для каждого приза его ценность, для \(i\)-го приза она задается целым числом \(a_i\) .

Требуется написать программу, которая по заданным ценностям призов определяет для каждого \(k\) от 2 до \(n\), приз с какой максимальной ценностью гарантированно достанется Пете, если он наберет в конкурсе \(k\) баллов.

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

Первая строка входного файла содержит число \(n\) (\(2 \le n \le 100 000\)). Вторая строка этого файла содержит n целых чисел: \(a_1, a_2, …, a_n\) (\(1 \le a_i ≤ 10^9\) ).

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

Выходной файл должен содержать одну строку, содержащую \(n\) – 1 целых чисел: для каждого \(k\) от 2 до \(n\) должна быть выведена ценность приза, который достанется Пете, если он наберет \(k\) баллов.

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

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

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

\(n \le 100\)

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

\(n \le 5000\)

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

\(n \le 100000\)

Примеры
Входные данные
5
1 3 4 2 5
Выходные данные
1 3 3 4
#113097
Космическое поселение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером \(a \times b\) метров. Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна \(d\) метрам, будет иметь форму прямоугольника размером \((a + 2d) \times (b + 2d)\) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером \(w \times h\) метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

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

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

Строка содержит пять разделенных пробелами целых чисел: \(n\), \(a\), \(b\), \(w\) и \(h\) (\(1 \le n, a, b, w, h \le 10^{18}\)). Гарантируется, что без дополнительной защиты все модули можно разместить в поселении описанным образом.

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

Ответ должен содержать одно целое число: максимальную возможную толщину дополнительной защиты. Если дополнительную защиту установить не удастся, требуется вывести число 0.

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

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

Во втором примере жилой отсек имеет размер \(5 \times 5\) метров, а поле – размер \(6 \times 6\) метров. Добавить дополнительную защиту к модулю нельзя.

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

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

\(1 \le n \le 1000, 1 \le a, b, w, h \le 1000\).

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

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

\(1 \le n \le 1000, 1 \le a, b, w, h \le 10^9\).

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

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

\(1 \le n \le 10^9 , 1 \le a, b, w, h \le 10^{18}\).

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

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

\(1 \le n \le 10^{18} , 1 \le a, b, w, h \le 10^{18}\).

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

Примеры
Входные данные
11 2 3 21 25
Выходные данные
2
Входные данные
1 5 5 6 6
Выходные данные
0
Страница: << 96 97 98 99 100 101 102 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест