Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 29 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Муниципальный этап
    Москва(40 задач)
    Московская область(30 задач)
    Сыктывкар(10 задач)
Страница: << 1 2 3 4 5 6 Отображать по:
#111991
Волшебный квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

На день рождения Егору подарили волшебный квадрат.

Волшебный квадрат — это таблица 3 × 3, в каждой из ячеек которой находятся числа от 0 до 9. Егор придумал следующую игру с волшебным квадратом: он загадывает число N и пытается так поставить числа в каждую ячейку квадрата, чтобы сумма чисел в каждой строке и каждом столбце была равна в точности N.

Пусть расстановка — это волшебный квадрат, заполненный числами. Тогда расстановки A и B считаются различными, если хотя бы для каких-то строки x и столбца y выполняется неравенство Ax, y ≠ Bx, y, где Ax, y и Bx, y — это числа, находящиеся в строке x и столбце y в расстановках A и B соответственно.

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

Напишите программу, которая поможет ответить на вопрос Егора.

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

Единственная строка входных данных содержит целое число N (0 ≤ N ≤ 109).

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

Требуется вывести одно число — искомое количество расстановок.

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

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

Примечание

В примере из условия существует всего одна допустимая расстановка — это таблица 3 × 3, состоящая из нулей. Очевидно, что сумма элементов в любой строке или столбце в такой расстановке равна 0.

#111992
Олимпийский огонь — 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из N этапов, каждый длиной ai километров (1 ≤ i ≤ N). У организаторов имеется бесконечное количество олимпийских факелов, каждый из которых может непрерывно гореть на протяжении K километров забега. По правилам эстафеты каждый факел используется только один раз. В начале каждого этапа участникам эстафеты выдаётся некоторое число факелов, такое, чтобы олимпийский огонь удалось донести до конца этапа. По окончании этапа все использованные (полностью или частично) факелы передаются в дар своим факелоносцам.

В процессе подготовки эстафеты выяснилось, что последовательно идущие этапы можно объединить в один этап, и таким образом на проведение эстафеты потребуется меньше факелов. Однако по соображениям техники безопасности нельзя объединять больше, чем M подряд идущих этапов.

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

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

В первой строке заданы 3 натуральных числа N, M и K (N ≤ 106, M ≤ 10, K ≤ 108).

Во второй строке заданы N натуральных чисел ai (ai ≤ 109).

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

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

Во второй строке выведите одно натуральное число P — количество групп объединённых этапов.

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

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

Входные данные
5 3 3
1 1 1 3 3
Выходные данные
2
1
1 3
Входные данные
6 3 3
1 1 1 1 1 1
Выходные данные
4
2
1 3
4 3
Входные данные
5 5 2
2 4 6 8 10
Выходные данные
0
0

#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
Страница: << 1 2 3 4 5 6 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест