Страница: << 3 4 5 6 7 8 9 >> Отображать по:

#111489

Города

Темы: [Двумерные массивы] [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача B ]

Юный программист решил придумать собственную игру. Игра происходит на поле размером \(N \times N\) клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

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

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

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

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

Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля (\(1 \leq N \leq 50\)).

Последующие N строк содержат по \(N\) заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: ‘C’ обозначает клетку, занятую городом, ‘D’ – пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.

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

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

Система оценивания

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

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

Примеры

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

3
DDD
DDC
DDC

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

111
111
112

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

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

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

#111519

Праздничные дни

Темы: [Одномерные массивы] [Задачи на моделирование]

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, 2013, Задача B ]

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

Вот неделю назад вернулось посольство из Тридесятого царства. И главный посол доложил царю: дескать, придумал Тридесятый царь следующую вещь. Чтобы как-то зарегулировать гуляния народные, повелел он указать определенные дни, и в эти дни устраивать широкие гуляния, а в остальные дни массовые сборища запретить. И с тех пор жизнь в Тридесятом царстве стала прекрасной: гулять так гулять, работать так работать, и все строго по цареву указу.

Понравилась мысль такая царю Тридевятого царства. Подумал он ввести и у себя такие порядки. Собрал царь советников своих, и говорит: подготовьте мне список дней, в которые гулять можно. Только не на год, а на \(N\) дней вперед — посмотрим, дескать, что получится; понравится — сделаем круглогодичным.

И вот вчера принесли советники царю список. Но вот незадача: каждый советник свой список приготовил, да еще и обоснование предложил, какой праздник в какой из этих дней надо отмечать. И у всех советников праздники важные, но у всех — разные! Царь думал-думал и решил: а возьмем их все — объединим предложения советников! Если какой-то день есть в списке хотя бы одного советника, то объявим этот день праздничным, и пускай народ гуляет! Глядишь, и не будет недовольных.

Только одна проблема осталась: некоторые дни оказались в списках сразу у нескольких советников. Но царь и тут нашел выход: перенесем некоторые праздники на более поздние дни, так, чтобы в каждый день получался только один праздник, и переносы были бы как можно короче.

Пусть, например, четыре советника сразу предложили сделать некоторый день (пускай день 5) праздничным. Тогда перенесем три из этих четырех праздников на дни 6, 7 и 8 — так, что праздничными будут дни с 5 по 8 включительно. А если оказывается, что, например, день 7 тоже предложен в качестве праздничного кем-нибудь из советников, то перенесем этот праздник еще дальше — на день 9.

Напишите программу, которая, зная предложения советников, определит, какие дни будут праздничными, а какие нет. Не забывайте, что праздники можно переносить только на более поздние дни; на более ранние переносить нельзя.

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

На первой строке входного файла находится одно число \(N\) — количество дней, на которые царь хочет произвести планировку праздников.

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

Гарантируется, что \(1\leq N\leq 100\,000\), и что сумма всех чисел во второй строке входного файла не превосходит \(100\,000\).

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

В выходной файл выведите одну строку, состоящую из символов “+” или “-”. “+” обозначайте праздничный день, “-” — непраздничный. Выведите как минимум \(N\) символов — по одному для каждого из дней, на которые проводится планирование. Но если праздники приходится переносить на дни после \(N\)-го (что допустимо), то выведите больше символов — до последнего праздничного дня.

Символы разделяйте пробелами.

Система оценки

Подзадача 0 (0 баллов) тест из условия.
Подзадача 1 (50 баллов) \( N \le 1000 \). Необходимые подгруппы: 0.
Подзадача 2 (50 баллов) без дополнительных ограничений. Необходимые подгруппы: 0-1.

Примеры

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

5
0 3 0 0 0

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

- + + + -

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

10
0 4 0 2 0 0 0 0 1 0

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

- + + + + + + - + -

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

3
0 3 0

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

- + + +

#111855

Переливания

Темы: [Одномерные массивы] [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2012, Задача B ]

Имеется 10 колб с водой и известен объем воды в каждой из них. За одно “касание” можно взять одну колбу и часть воды (или всю воду) из этой колбы разлить по одной или нескольким другим колбам в любом количестве. За какое наименьшее количество “касаний” можно уравнять объемы воды во всех колбах? Каждая колба может вместить любой объем воды.

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

Программа получает на вход 10 целых чисел \(a_i\), каждое записанное в отдельной строке \(--\) объем воды в каждой из колб. Все числа — целые, от 0 до 100.

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

Выведите одно целое число — минимальное количество “касаний”, за которое можно уравнять объемы воды во всех колбах.

Примечание к примеру

В примере можно из первой колбы перелить 20 во вторую, оставляя в первой колбе 10. Затем из второй колбы разлить воду по всем остальным колбам так, чтобы в каждой из колб оказалось по 10.

Примеры

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

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

#111876

Гипер-минимум

Темы: [Двумерные массивы]

Источники: [ Личные олимпиады, Жаутыковские олимпиады, 2011, Задача B ]

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: \(Y\) [\(i_1\), \(i_2\), \(i_3\), \(i_4\)] = min(\(X\)[\(j_1\), \(j_2\), \(j_3\), \(j_4\)]), где 1 \(\le\) \(i_k\) \(\le\) \(N\) − \(M\) + 1, \(i_k\) \(\le\) \(j_k\) \(\le\) \(i_k\) + \(M\) − 1, а \(M\) - заданное число.

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

В первой строке входного файла задаются \(N\) и \(M\) (\(1\) \(\le\) \(M\) \(\le\) \(N\)). Остальные строки файла содержат элементы массива \(X\). Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению \(10^9\). Они расположены в таком порядке, что считать их можно с помощью псевдокода:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]

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

Выведите искомый массив \(Y\) в том же формате, в котором был дан массив \(X\).

Примеры

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

1 1
1

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

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

3 2
3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1

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

-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5

#111989

Телефон

Темы: [Одномерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 10-11 классы, Телефон ]

У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланировано n разговоров, про каждый из которых известно число P_i — сколько рублей прибыли получит бизнесмен, если i-й разговор состоится (P_i может быть равно 0 — в этом случае никакой выгоды от i-го разговора нет).

Телефон у бизнесмена сделан по новейшим технологиям, но иногда барахлит. Сегодня, например, телефон внезапно разрядился, поэтому он позволит бизнесмену провести только первые A₀ разговоров, а затем выключится до конца дня. Однако телефон можно зарядить, пропустив несколько первых запланированных разговоров. Более формально, если предприниматель будет заряжать телефон вместо первых j разговоров (то есть разговоров с номерами от 1 до j), то он потом сможет провести ровно A_j разговоров (с номерами от j + 1 до min(n, j + A_j)), после чего телефон опять же перестанет работать до конца дня.

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

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

На вход программе дается целое число n — количество запланированных звонков (1 ≤ n ≤ 2·10⁵). На следующей строке вводятся через пробел \(n\) целых чисел P_i, обозначающие прибыли от звонков (0 ≤ P_i ≤ 1 000). Затем вводятся \(n+1\) целых чисел A_j, обозначающие, сколько звонков можно будет провести после подзарядки (0 ≤ A_j ≤ 10⁶).

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

Выведите два числа, первое — это максимальная выгода, которую может получить бизнесмен, второе — количество пропущенных первых звонков, при котором она получается (0, если выгоднее всего не заряжать телефон вовсе).

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

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

5
1 2 0 4 1
2 0 8 3 5 6

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

5 3

Примечание

Рассмотрим пример из условия: n = 5, P₁ = 1, P₂ = 2, P₃ = 0, P₄ = 4, P₅ = 1, A₀ = 2, A₁ = 0, A₂ = 8, A₃ = 3, A₄ = 5, A₅ = 6.

Если бизнесмен не будет заряжать телефон, то результат будет равен P₁ + P₂ = 1 + 2 = 3 рубля. Если предприниматель будет заряжать телефон вместо первого звонка, то он не сможет позвонить ни разу, так как A₁ = 0. Если вместо первых двух звонков, то результат составит P₃ + P₄ + P₅ = 0 + 4 + 1 = 5 рублей. Если вместо первых трех, то P₄ + P₅ = 4 + 1 = 5. Если вместо четырёх звонков, то P₅ = 1 рубль. Наконец, если бизнесмен будет заряжать телефон вместо всех n = 5 звонков, то он заведомо ничего не получит. Таким образом, два лучших варианта — это заряжать либо вместо 2 первых звонков, либо вместо 3, в обоих случаях получаем 5 рублей прибыли. По условию, из них мы выбираем выбираем вариант с 3 пропущенными звонками.

Тесты к этой задаче состоят из трех групп.

Тест 1 — тест из условия, оценивается в ноль баллов.
Тесты 2 – 19. В тестах этой группы 1 ≤ n ≤ 10⁴. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 20 – 36. В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.

Страница: << 3 4 5 6 7 8 9 >> Отображать по:

Выбрано

Отменить

Добавить в контест