Темы
Информатика(2656 задач)
--->
97 задач
<---
Юный информатик осваивает новый графический редактор «Хамелеон». Этот редактор обладает необыкновенной простотой. Он поддерживает ровно два цвета — чёрный и белый, и один инструмент — «Хамелеон».
Поле редактора — это квадрат 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 тестов оцениваются следующим образом. Если тест пройден, то:
Для просмотра последовательности действий участнику предоставляется визуализатор. Скачать архив визуализатора.
При запуске визуализатора без параметров будет предложено выбрать входной и выходной файлы для визуализации. Имя входного и выходного файла также можно указать в виде параметров командной строки, запустив команду «visualize.cmd <входной файл> <выходной файл>».
5 BWWWW BWWWW BWBWW WWWWW WWWWW 0
DDRRdlU
История Татаро-монгольского ханства богата на правителей. Каждый из 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.
Данная задача содержит шесть подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
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
Экспедиция готовится отправиться в путь на космическом корабле нового поколения. Планируется последовательно посетить 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.
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.
7 1 3 2 1 3 2 3
3 1 3 5
7 4 3 2 4 3 2 1
0
В рамках Чемпионата Урала планируется проведение турнира стратегий по игре «Морской бой 1D».
Игра проходит на поле, которое представляет собой прямоугольник размером 1 × N клеток. На поле расставляются T кораблей, каждый из которых имеет вид прямоугольника размером 1 × K клеток. Расстановка кораблей на поле является допустимой, если различные корабли не имеют общих клеток и разделены хотя бы одной пустой клеткой. Игровая программа осуществляет выстрелы в клетки поля, а сервер сообщает, является ли выстрел промахом или попаданием в корабль.
В процессе игры про некоторые клетки становится известно, что при любой допустимой расстановке кораблей они принадлежат какому-либо из кораблей. Назовём такие клетки заведомо занятыми.
Игра заканчивается после первого попадания в корабль. Сервер пытается добиться того, чтобы игра продолжалась как можно дольше. Для этого он не фиксирует расстановку кораблей в начале игры, а рассматривает все возможные допустимые расстановки и сообщает о попадании, только если клетка, в которую осуществляется выстрел, является заведомо занятой.
Требуется написать программу, исполняющую роль сервера для этой игры. Сервер сначала загружает параметры игры, а затем взаимодействует с игровой программой, сообщая после каждого выстрела информацию о промахе или попадании, а также количество заведомо занятых клеток.
Задача является интерактивной. После каждого вывода требуется сбросить буфер вывода.
Роль игровой программы исполняет программа жюри. Программа-решение исполняет роль сервера.
Первая строка стандартного ввода программы-решения содержит параметры игры — три числа: N — размер игрового поля, T — число кораблей и K — длина каждого корабля (1 ≤ N ≤ 100 000, 1 ≤ T, 1 ≤ K). Гарантируется, что на поле длины N можно по описанным правилам разместить T кораблей длины K.
После считывания параметров игры программа-решение должна определить и вывести в стандартный поток вывода количество заведомо занятых клеток.
Затем начинается игра. Программа-решение должна последовательно считывать ходы игровой программы из стандартного потока ввода и обрабатывать их следующим образом:
Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.
8 2 3 4 1
4 0 5 1
В выборах председателя школьного клуба информатиков участвуют K кандидатов и N избирателей. Кандидаты пронумерованы от 1 до K, избиратели — от 1 до N.
По результатам голосования составляется список, i-й элемент этого списка равен номеру кандидата, за которого проголосовал i-й избиратель. Для каждого отрезка списка назначается наблюдатель, который подсчитывает голоса на этом отрезке. Таким образом, на выборах работают N(N + 1) / 2 наблюдателей.
Если наблюдатель обнаружит кандидата, набравшего на его отрезке более половины голосов, он публикует в социальной сети прогноз о том, что этот кандидат победит в выборах.
Требуется написать программу, которая по списку голосов определяет количество опубликованных наблюдателями прогнозов.
Первая строка входного файла содержит два числа N и K (1 ≤ N ≤ 500 000, 1 ≤ K ≤ 500 000). Вторая строка содержит N чисел V1, V2, ..., VN — список голосов избирателей (1 ≤ Vi ≤ K).
Выходной файл должен содержать единственное число — количество прогнозов.
Для окончательной проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения N и K в тестах приведены в таблице.
| Тест | N | K | Тест | N | K | Тест | N | K |
| 1 | 2 | 2 | 18 | 2000 | 20 | 35 | 90000 | 1000 |
| 2 | 3 | 1 | 19 | 3000 | 2000 | 36 | 100000 | 5000 |
| 3 | 5 | 5 | 20 | 5000 | 2000 | 37 | 125000 | 1 |
| 4 | 10 | 10 | 21 | 7500 | 200 | 38 | 150000 | 12000 |
| 5 | 20 | 2 | 22 | 10000 | 10000 | 39 | 150000 | 18 |
| 6 | 30 | 3 | 23 | 15000 | 1500 | 40 | 200000 | 42000 |
| 7 | 50 | 20 | 24 | 20000 | 10 | 41 | 250000 | 26000 |
| 8 | 75 | 75 | 25 | 25000 | 100 | 42 | 300000 | 10000 |
| 9 | 100 | 2000 | 26 | 30000 | 15 | 43 | 350000 | 102000 |
| 10 | 150 | 30 | 27 | 35000 | 35 | 44 | 400000 | 12000 |
| 11 | 200 | 50 | 28 | 40000 | 10000 | 45 | 450000 | 5000 |
| 12 | 300 | 10 | 29 | 45000 | 10000 | 46 | 500000 | 2 |
| 13 | 400 | 100 | 30 | 50000 | 10000 | 47 | 500000 | 102000 |
| 14 | 500 | 2 | 31 | 55000 | 13000 | 48 | 500000 | 102000 |
| 15 | 300 | 200 | 32 | 60000 | 174 | 49 | 500000 | 102000 |
| 16 | 1000 | 2000 | 33 | 70000 | 10000 | 50 | 500000 | 501 |
| 17 | 1500 | 100 | 34 | 80000 | 1000 |
5 2 1 2 1 2 1
9
3 7 5 2 6
3