Страница: 1 2 >> Отображать по:
#111633
Хоккей на Урале
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

Для популяризации хоккея и повышения мастерства хоккейных команд Урала был организован Всеуральский турнир. Для участия в турнире были приглашены N хоккейных команд из городов Урала.

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

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

В первой строке входного файла содержится число N (2 ≤ N ≤ 100 000, N — чётное).

Последующие N строк содержат описания всех прошедших матчей. Описание каждого матча состоит из двух натуральных чисел, не превышающих N — номеров команд, игравших в матче. Первые N / 2 из них соответствуют матчам первого тура, оставшиеся — матчам второго тура.

Последняя строка входного файла содержит одно число K (2 ≤ K ≤ N).

Гарантируется, что каждая команда сыграла ровно два матча: один в первом туре и один — во втором.

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

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

Примечание

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

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

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

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

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

Примеры
Входные данные
6
1 2
3 5
4 6
2 3
4 5
1 6
3
Выходные данные
1 3 4
Входные данные
4
1 2
3 4
2 1
4 3
3
Выходные данные
0
#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
#111635
Графический редактор <<Хамелеон>>
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Юный информатик осваивает новый графический редактор «Хамелеон». Этот редактор обладает необыкновенной простотой. Он поддерживает ровно два цвета — чёрный и белый, и один инструмент — «Хамелеон».

Поле редактора — это квадрат N × N клеток. На одной из клеток поля находится курсор-хамелеон. Его можно передвигать в пределах поля в четырех направлениях — вверх, вниз, вправо или влево ровно на одну клетку. Цвет курсора всегда должен совпадать с цветом клетки, в которой он находится. Для этого, когда он перемещается на клетку другого цвета, должно произойти одно из двух событий: либо курсор меняет свой цвет на цвет этой клетки, либо наоборот — клетка меняет свой цвет на цвет курсора. Например, если курсор перемещается из чёрной клетки в белую, либо он должен перекраситься в белый цвет, либо белая клетка, в которой он теперь находится, должна стать чёрной. Если клетка и курсор имеют одинаковый цвет, то их цвет не изменяется.

Изначально курсор имеет чёрный цвет и находится в левой верхней клетке поля. Эта клетка также окрашена в чёрный цвет. Все остальные клетки поля окрашены в белый цвет.

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

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

В первой строке входного файла задано число N (5 ≤ N ≤ 100) — размер поля.

В следующих N строках описывается картинка, которую необходимо получить. Каждая строка описания картинки имеет длину N и состоит из символов «W», если соответствующая клетка белая, и «B», если чёрная.

Последняя строка файла содержит номер теста.

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

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

Для обозначения перемещения влево, вверх, вправо или вниз с изменением цвета курсора следует использовать буквы «l», «u», « r» или «d» соответственно. Для обозначения перемещения влево, вверх, вправо или вниз с изменением цвета клетки следует использовать буквы «L», «U», «R» или «D» соответственно. Если курсор перемещается на клетку своего цвета, можно использовать как заглавную, так и строчную букву.

Примечание

В этой задаче тестовые данные доступны участникам. Скачать тестовые данные.

Тесты нумеруются в соответствии с названиями файлов от 0 до 20. Тест из примера имеет номер 0, он используется для предварительной проверки. Тесты с номерами с 1 по 20 включительно используются для окончательной проверки.

Окончательная проверка данной задачи осуществляется на наборе из 20 тестов. Каждый тест оценивается из 5 баллов. Тесты оцениваются независимо.

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

Первые 10 тестов оцениваются в 5 баллов, если тест пройден.

Оставшиеся 10 тестов оцениваются следующим образом. Если тест пройден, то:

  • в 5 баллов, если ответ содержит не более 3N2 действий;
  • в 4 балла, если ответ содержит не более 5N2 действий;
  • в 3 балла, если ответ содержит не более 10N2 действий;
  • в 2 балла, если ответ содержит не более 2.5N3 действий;
  • в 1 балл, если ответ содержит не более 5 000 000 действий.

Визуализатор

Для просмотра последовательности действий участнику предоставляется визуализатор. Скачать архив визуализатора.

При запуске визуализатора без параметров будет предложено выбрать входной и выходной файлы для визуализации. Имя входного и выходного файла также можно указать в виде параметров командной строки, запустив команду «visualize.cmd <входной файл> <выходной файл>».

Примеры
Входные данные
5
BWWWW
BWWWW
BWBWW
WWWWW
WWWWW
0
Выходные данные
DDRRdlU
#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
#111637
Звёздный путь
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Экспедиция готовится отправиться в путь на космическом корабле нового поколения. Планируется последовательно посетить N планет звёздной системы — от планеты Земля до планеты Победа. Планеты пронумерованы от 1 до N в порядке их посещения, Земля имеет номер 1, а Победа — номер N.

Для перелёта между планетами корабль может использовать любой тип топлива, существующий в звёздной системе. Перед началом экспедиции корабль находится на планете Земля, и бак корабля пуст. Существующие типы топлива пронумерованы целыми числами, на планете с номером i можно заправиться только топливом типа ai. При посещении i-й планеты можно заправиться, полностью освободив бак от имеющегося топлива и заполнив его топливом типа ai.

На каждой планете станция заправки устроена таким образом, что в бак заправляется ровно столько топлива, сколько потребуется для перелёта до следующей планеты с топливом такого же типа. Если далее такой тип топлива не встречается, заправляться на этой планете невозможно. Иначе говоря, после заправки на i-й планете топлива хватит для посещения планет от (i + 1)-й до j-й включительно, где j — минимальный номер планеты, такой что j > i и aj = ai. Для продолжения экспедиции дальше j-й планеты корабль необходимо снова заправить на одной из этих планет.

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 300 000) — количество планет.

Во второй строке входного файла записано N целых чисел a1, a2, ..., aN (1 ≤ ai ≤ 300 000) — типы топлива на планетах.

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

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

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

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

Примечание

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

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

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

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

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