Темы --> Информатика --> Язык программирования --> Массивы --> Одномерные массивы
---> 11 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 >> Отображать по:
#3788
Кубики
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

Примечание

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

Примеры
Входные данные
5 1
1 3 4 0 1
Выходные данные
4 2 2 1 0
#111519
Праздничные дни
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Понравилась мысль такая царю Тридевятого царства. Подумал он ввести и у себя такие порядки. Собрал царь советников своих, и говорит: подготовьте мне список дней, в которые гулять можно. Только не на год, а на \(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
Переливания
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примечание к примеру
В примере можно из первой колбы перелить 20 во вторую, оставляя в первой колбе 10. Затем из второй колбы разлить воду по всем остальным колбам так, чтобы в каждой из колб оказалось по 10.
Примеры
Входные данные
30
26
2
3
4
5
6
7
8
9
Выходные данные
2
#111989
Телефон
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

Входные данные
5
1 2 0 4 1
2 0 8 3 5 6
Выходные данные
5 3

Примечание

Рассмотрим пример из условия: n = 5, P1 = 1, P2 = 2, P3 = 0, P4 = 4, P5 = 1, A0 = 2, A1 = 0, A2 = 8, A3 = 3, A4 = 5, A5 = 6.

Если бизнесмен не будет заряжать телефон, то результат будет равен P1 + P2 = 1 + 2 = 3 рубля. Если предприниматель будет заряжать телефон вместо первого звонка, то он не сможет позвонить ни разу, так как A1 = 0. Если вместо первых двух звонков, то результат составит P3 + P4 + P5 = 0 + 4 + 1 = 5 рублей. Если вместо первых трех, то P4 + P5 = 4 + 1 = 5. Если вместо четырёх звонков, то P5 = 1 рубль. Наконец, если бизнесмен будет заряжать телефон вместо всех n = 5 звонков, то он заведомо ничего не получит. Таким образом, два лучших варианта — это заряжать либо вместо 2 первых звонков, либо вместо 3, в обоих случаях получаем 5 рублей прибыли. По условию, из них мы выбираем выбираем вариант с 3 пропущенными звонками.

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

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

#112099
Воды слонам!
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода.

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

Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!

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

В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис.

Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .

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

Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.

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

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