#3788

Кубики

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

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

ООО «Симптотика» собирается наладить выпуск обучающих игр для детей младшего дошкольного возраста. Одной из придуманных игр был набор кубиков, из которых можно было собирать различные фигуры. Кубики упаковывались в коробку размером N × N × 1 кубиков.

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

$\text{[math]}$

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

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

Сначала вводятся целые числа N и K (1 ≤ N ≤ 10, 0 ≤ K ≤ 10⁹). После этого, во второй строке вводятся N неотрицательных чисел, не превышающих N. i-ое число обозначает количество кубиков в столбце под номером i.

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

Необходимо вывести N чисел через пробел, i-ое из которых обозначает количество чисел в i-ом столбце в полученном после K поворотов расположении кубиков.

Примечание

Пример соответствует иллюстрации из условия.

Примеры

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

5 1
1 3 4 0 1

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

4 2 2 1 0

#111855

Переливания

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

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

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

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

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

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

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

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

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

Примеры

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

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

#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 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.

#111990

Тетрадка

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

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

Рано утром Вася решил сделать домашнее задание по информатике. Начать выполнение задания Вася решил с поиска подходящей тетрадки. Добравшись до ящика с чистыми тетрадями, он открыл одну из них. Вася ещё не до конца проснулся и поэтому видит только часть тетрадки и не может сообразить, какая это тетрадка: в клетку, в линейку или в вертикальную линейку. Помогите ему это сделать.

Формально, дана двухмерная таблица из нулей и единиц — часть тетрадки, которую видит Вася. Единицей обозначается закрашенный участок, а нулем — незакрашенный. Назовём вертикальной линией столбец таблицы, все элементы которого — единицы, а горизонтальной линией — строку таблицы, все элементы которой — единицы. Гарантируется, что каждая единица в таблице содержится в какой-либо линии.

Тетрадкой в клетку называется тетрадка, в которой содержатся вертикальные и горизонтальные линии. Тетрадкой в линейку называется тетрадка, в которой содержатся только горизонтальные линии. Тетрадкой в вертикальную линейку называется тетрадка, в которой содержатся только вертикальные линии.

Известно, что в целой тетрадке все расстояния между линиями одинаковы (то есть все клетки — квадраты, все линейки одинаковой ширины). Гарантируется, что линии не могут располагаться рядом (между ними всегда есть промежуток).

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

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

В первой строке входных данных даны целые числа n и m (1 ≤ n, m ≤ 1 000) — количество строк и столбцов в таблице. Следующие n строк по m чисел содержат целые числа a_i, j (0 ≤ a_i, j ≤ 1) — элементы таблицы, задающие видимую часть тетради.

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

Требуется вывести одну из строк:

«Square», если заданная тетрадка расчерчена в клетку;
«Line», если тетрадка расчерчена в линейку;
«Vertical line», если тетрадка расчерчена в вертикальную линейку;
«?», если невозможно однозначно определить, к какому типу относится данная тетрадь.

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

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

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

Square

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

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

Line

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

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

Примечание

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