Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 3 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Заключительный этап --> 2013
    1 день(4 задач)
    2 день(4 задач)
Страница: 1 Отображать по:
#111634
Робот
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.

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

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

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

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

В первой строке входного файла записано число K > 0 "— количество операций, которые можно записать в память робота.

Вторая строка состоит из N > K строчных латинских букв, обозначающих операции "— процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.

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

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. N ≤ 100. Подзадача оценивается в 30 баллов.

  3. N ≤ 2000. Подзадача оценивается в 30 баллов.

  4. N ≤ 200 000. Подзадача оценивается в 40 баллов.

Примеры
Входные данные
2
zabacabab
Выходные данные
5
Входные данные
2
abc
Выходные данные
0
#111636
Древние династии
  

История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KLi лет, но не более KRi лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее MLi лет, но не более MRi лет.

Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X1, X2, ..., XN (1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 109) — годы проведения праздников.

В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KLi, KRi, MLi, MRi (1 ≤ KLi ≤ KRi ≤ 109), (1 ≤ MLi ≤ MRi ≤ 109).

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

Первая строка выходного файла должна содержать числа P и Q, где P — номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а Q — показатель сомнительности этого распределения.

Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. 2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.

  3. 2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.

  4. 2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.

  5. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.

  6. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

Примеры
Входные данные
3
1 2 3
1
1 1 1 1
Выходные данные
1 1
211
Входные данные
4
1 6 9 13
2
1 2 2 3
6 7 3 3
Выходные данные
0
Входные данные
5
3 6 8 9 10
2
2 3 1 1
1 4 1 10
Выходные данные
2 0
21212
#111644
Морской бой
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В рамках Чемпионата Урала планируется проведение турнира стратегий по игре «Морской бой 1D».

Игра проходит на поле, которое представляет собой прямоугольник размером 1 × N клеток. На поле расставляются T кораблей, каждый из которых имеет вид прямоугольника размером 1 × K клеток. Расстановка кораблей на поле является допустимой, если различные корабли не имеют общих клеток и разделены хотя бы одной пустой клеткой. Игровая программа осуществляет выстрелы в клетки поля, а сервер сообщает, является ли выстрел промахом или попаданием в корабль.

В процессе игры про некоторые клетки становится известно, что при любой допустимой расстановке кораблей они принадлежат какому-либо из кораблей. Назовём такие клетки заведомо занятыми.

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

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

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

Задача является интерактивной. После каждого вывода требуется сбросить буфер вывода.

Роль игровой программы исполняет программа жюри. Программа-решение исполняет роль сервера.

Первая строка стандартного ввода программы-решения содержит параметры игры — три числа: N — размер игрового поля, T — число кораблей и K — длина каждого корабля (1 ≤ N ≤ 100 000, 1 ≤ T, 1 ≤ K). Гарантируется, что на поле длины N можно по описанным правилам разместить T кораблей длины K.

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

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

  1. Считать из стандартного потока ввода одно число q — номер клетки, в которую игровая программа осуществляет выстрел (1 ≤ q ≤ N). Игровая программа никогда не делает два выстрела в одну и ту же клетку.
  2. Если клетка q является заведомо занятой, вывести в стандартный поток вывода число 1 и завершить работу.
  3. Если клетка q не является заведомо занятой, вывести в стандартный поток два числа, разделенных пробелом: 0 и количество заведомо занятых клеток после этого выстрела. После этого программа-решение переходит к пункту 1 и продолжает взаимодействие с игровой программой.

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.
  2. N ≤ 15. Подзадача оценивается в 30 баллов.

  3. N ≤ 3000. Подзадача оценивается в 30 баллов.

  4. N ≤ 100 000. Подзадача оценивается в 40 баллов.

Примеры
Входные данные
8 2 3
4
1
Выходные данные
4
0 5
1
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест