Массивы

716 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Башни 2.0#44509
В компьютерной игре есть n башен, высота i-й башни равна ai метров. Определим расстояние между двумя башнями с индексами i и j как |i−j|. Разрешается прыгнуть с i-й башни на j-ю башню тогда и только тогда, когда не существует такого индекса 1 <= k <= n, такого, что расстояние от i-й до j-й башни не меньше расстояния от i-й башни до k-й башни, и k-я башня имеет большую высоту, чем j-я. Башня j достижима из башни i если существует последовательность корректных прыжков, которая начинается в i-й башне и заканчивается в j-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.


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

Первая строка входных данных содержит одно целое число n (1 <= n <= 500000) - количество башен.

Вторая строка входных данных содержит n чисел a1, a2, ..., an (1 <= an <= 109) - высоты башен.


Выходные данные
Выведите n чисел, i-е из которых должно быть равным количеству башен, достижимых из i-й башни.
 
Примечание

В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.

Во втором примере из 1-й и из 2-й башни достижимы башни 1,2,3,4,5. Из 3-й башни достижимы башни 3,4,5. Из 4-й и 5-й башни достижимы башни 4,5. Из 6-й башни достижимы башни 4,5,6. Из 7-й башни достижимы башни 4,5,6,7.

 
 
Примеры
№ Входные данные Выходные данные
1 
5
7 6 3 4 10
 
2 3 4 2 1
2 
7
1 1 1 2 2 1 1
 
5 5 3 2 2 3 4
Алгоритмы обработкиЗадача на реализациюЛинейные алгоритмыСтруктуры данных
✓ 3✗ 31 200средняяВойти и решать
Количество равных последнему#43566
Входные данные
В первой строке вводится число N (1<=N<=20)  - количество элементов одномерного массива. Во второй строке вводится N целых чисел (все числа по модулю не более 100).

Выходные данные
Выведите одно число - количество элементов исходного массива, равных последнему элементу (последний элемент в подсчете не учитывается).
 
Примеры
№ Входные данные Выходные данные
1 5
1 5 5 -4 5		 2
Одномерные массивы
✓ 190✗ 334400лёгкаяВойти и решать
В обратном порядке#43565

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

Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=100). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел, по модулю не превышающих 100.
 
Выходные данные
Необходимо вывести все элементы массива в обртаном порядке.
 
 
Примеры
№ Входные данные Выходные данные
1 5
1 1 3 4 6		 6 4 3 1 1
Одномерные массивы
✓ 102✗ 199500лёгкаяВойти и решать
Счастливая последовательность#43533

У Пети есть последовательность A неотрицательных целых чисел длины n. Числа в последовательности пронумерованы, начиная с нуля. Петя считает последовательность счастливой, если четность каждого элемента последовательности совпадает с четностью номера данного элемента. Формально это означает, что если для всех i (0 <= i <= n - 1) выполнено равенство i mod 2 = a[i] mod 2, где x mod 2 - остаток от деления x на 2, то последовательность является счастливой.

Петя хочет сделать свою последовательность счастливой, для этого он берет любые два элемента и меняет их местами (элементы не обязательно соседние). Помогите найти Пете минимальное количество ходов, за которое он сможет сделать свою последовательность счастливой. Если у Пети не получится сделать последовательность счастливой, выведите -1.


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

Программа получает на вход в первой строке целое число n (1 <= n <= 40) — размер последовательности A. Далее следует строка, содержащая n целых чисел a0,a1,…,an−1 (0 <= ai <= 1000) — целые неотрицательные числа последовательности.


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

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

Примеры
№ Входные данные Выходные данные
1 
4
3 2 7 6
 
2
2 
1
7
 
-1
3 
7
4 9 2 1 18 3 0
 
0
Одномерные массивы
✓ 70✗ 114700средняяВойти и решать
Книжки с полки#43532

Петя обладает обширной библиотекой книг. Сейчас он стоит возле полки с приключенческими рассказами. На ней расположены n книг. Все книги на полке у Пети всегда пронумерованы слева направо. Книга с номером i имеет ai страниц. На полке, возле которой сейчас стоит Петя, количество страниц в каждой книге различно.

Особенность полок в библиотеке Пети такова, что он может брать только крайнюю книгу с полки (то есть либо самую левую, либо самую правую).

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

 

Входные данные
В первой строке записано одно целое число n (2 <= n <= 100) - количество книг на полке. Во второй строке находится n целых различных чисел a1, a2, ..., an (1 <= ai <= 106) - количество страниц в книге.

 

Выходные данные
Выведите одно целое число — минимальное количество книг, которое необходимо Пете убрать с полки.

 
Примеры
№ Входные данные Выходные данные
1 
5
1 5 4 3 2
 
2
2 
8
2 1 3 4 5 6 8 7
 
4
Задача на реализациюОдномерные массивы
✓ 58✗ 439900средняяВойти и решать
Праздник Осени#43517

В детском саду Солнышко на Праздник Осени у всех детей должно быть по одинаковому числу воздушных шариков. Воспитательница Анна Николаевна узнала, сколько воздушных шариков сможет принести из дома каждый ребенок на праздник.  Чтобы уравнять количество шариков у всех детей, родительский комитет решил закупить необходимое число воздушных шариков.

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

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

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

 

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

В первой строке входных данных содержится целое число n (1 <= n <= 100) — количество воспитанников в группе у Анны Николаевны.

Во второй строке содержатся n чисел a1,a2, ..., an, где ai (0 <= ai <= 106) — количество воздушных шариков, которое i-й ребенок сможет принести из дома.

 

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

В единственную строку выходных данных выведите выведите целое число — минимальное количество воздушных шариков, которое которое необходимо закупить.

 
Примеры
№ Входные данные Выходные данные
1 5
0 1 2 3 4		 10
2 5
1 1 0 1 1		 1
3 3
1 3 1		 4
4 1
12		 0
Одномерные массивы
✓ 159✗ 164500лёгкаяВойти и решать
Секретная последовательность#43349

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

  • первым числом слева записано число a1;
  •  первым числом справа записано число a2;
  • вторым числом слева (после a1) записано число a3;
  • вторым числом справа (то есть перед числом a2) записано число a4;
  • все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.



Входные данные
Первая строка содержит размер последовательности n (1 <= n <= 300), записанной Алисой для своего отца. Вторая строка содержит n чисел ai (1 <= ai <= 109) - саму последовательность.

Выходные данные
Выведите исходную последовательность, которую Алиса выписывала для отца.
 
 
Примеры
№ Входные данные Выходные данные
1

6
1 3 5 6 4 2

 1 2 3 4 5 6
2 1
23		 23

 

"Два указателя"Задача на реализациюОдномерные массивы
✓ 112✗ 161700средняяВойти и решать
Пять блюд#42838
В лунном ресторане Селена подают следующие пять блюд:

Нягао (рисовый пирог): на подачу уходит А минут.
Цзяо (пельмени): на подачу уходит B минут.
Тан (сладкие рисовые шарики): для подачи на стол требуется C минут.
Шиитаке (тушеные грибы): на подачу уходит D минут.
Ханбагу (котлета для гамбургера): на подачу уходит E минут.

Будем считать, что время подачи блюда - это время между размещением заказа и доставкой блюда.

В лунном ресторане действуют следующие правила в отношении заказов:
  • Заказ может быть размещен только в момент времени, кратный 10 минутам (0, 10, 20, ... минут). 
  • Одновременно можно заказать только одно блюдо.
  • Новый заказ не может быть размещен, если еще не доставлено блюдо предыдущего заказа. Но новый заказ может быть размещен точно в то время, когда доставлено блюдо из предыдущего заказа.

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

Входные данные
Программа получает на вход 5 целых чисел А, B, C, D, E (1 <= A, B, C, D, E <= 123). Каждое число в отдельной строке.

Выходные данные
Выведите на экран целое число - ответ на задачу.
 
Примеры
№ Входные данные Выходные данные Примечание
1 29
20
7
35
120

215

 Если мы решим заказать блюда в порядке Нягао, Цзяо, Тан, Хангбау, Шиитаке, то максимально раннее время для каждого заказа будет следующим:

Закажите Нягао в 0 минут, который будет доставлен через 29 минут. Текущий момент времени будет 29 минут.
Закажите Цзяо в 30 минут, которое будет в момент 50 минут . 
Закажите Тан в момент 50 минут, который будет доставлен в момент 57 минут.
Закажите Ханбагу в момент 60, который будет доставлен в момент 180 минут.
Закажите Шиитаке в 180 минут, который будет доставлен в момент 215 минут.
Невозможно заказать блюда другим способом так, чтобы последнее блюдо было бы доставлено раньше, чем указанное в примере.
Одномерные массивы
✓ 54✗ 131600лёгкаяВойти и решать
Меняю конфеты на ноутбук#42450
Антон Б., суперспособный ученик 8 класса, обладает неудивительными математическими способностями. Побывав однажды на экскурсии в Колоколамске, он понял, что легко может написать программу, которая бы предсказывала стоимость его любимых конфет на любой промежуток дней вперед. 
Используя эту программу, Антон Б. решил  приобрести на все свои карманные деньги конфеты (а их у него было всего 10 рублей), затем, чуть позже, продать все купленные им конфеты. Таким образом, Антон Б. хочет заработать как можно больше денег на новый ноутбук. 
Так как  Антон Б. еще несовершеннолетний и один ездить в другие города не может, ему нужно понять, в какие из двух дней попросить старшего брата отвезти его в Колоколамск. Старший брат совершеннолетний и очень любит своего младшего брата, поэтому всегда готов ему помочь.
Так как Антон Б. очень торопится на кружок по информатике, он просит вас определить эти два дня в ближайшие N дней. 

Входные данные
В первой строке записано число N (2 <= N <= 100000) количество дней, на которые Антон Б. делает прогноз. Вторая строка содержит N целых положительных чисел ai (1 <= i <= N , 1 <= ai <=  5000 ), где ai - предсказанная стоимость конфет в i-й день.

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

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

 
Примеры
№ Входные данные Выходные данные
1 
6
10 3 5 3 11 9
 
2 5
2 
4
5 5 5 5
 
0 0
Одномерные массивыПорядковые статистики
✓ 16✗ 7421 200средняяВойти и решать
Заполнение спиралью#42449
Дано натуральное число n. Создайте массив A[2*n+1][2*n+1] и заполните его по спирали, начиная с числа 0 в центральной клетке A[n+1][n+1]. Спираль выходит вверх, далее закручивается против часовой стрелки.

Формат входных данных
Программа получает на вход число  n.

Формат выходных данных
Программа должна вывести полученный массив. Каждый элемент массива необходимо записывать в трех знакоместах.
 
Примеры
№ Входные данные Выходные данные
1 2 
 12 11 10  9 24
 13  2  1  8 23
 14  3  0  7 22
 15  4  5  6 21
 16 17 18 19 20
Двумерные массивы
✓ 24✗ 79800средняяВойти и решать
Третья планета от Солнца#42441
На третью планету от Солнца отправили n космических кораблей для сбора различных объектов для изучения. На каждом корабле было размещено по m контейнеров различного объема. После изучения планеты, отобрано n·m экземпляров. Командный состав решил взять несколько экземпляров самого большого объема. Необходимо определить какой объем должен иметь самый большой экземпляр, чтобы его можно было вывезти с планеты, а также количество кораблей и их номера, на которые можно поместить самые большие экземпляры. Все корабли пронумерованы, начиная с нуля.

Входные данные
Первая строка содержит два целых числа n и m: n - количество кораблей, отправленных на третью планету (1 <= n <= 100), m - количество контейнеров на каждом корабле. В следующих n строках содержат по m чисел, каждое из которых показывает объем контейнера (1 <= m <= 100, каждое число - неотрицательное не более 100). 

Выходные данные
Выведите в первой строке - количество космических кораблей, которыми можно привезти самый большой экземпляр, через пробел максимальный объем, который можно вывезти с планеты. На следующей строке выведите через пробел номера кораблей (нумеруются с нуля), на которые можно загрузить самый большой экземпляр.
 
Примеры
№ Входные данные Выходные данные
1 
3 3
1 2 3
3 5 4
5 2 2
 
2 5
1 2
Двумерные массивы
✓ 52✗ 133600лёгкаяВойти и решать
С видом на океан#42274
С востока на запад простираются горы, а на западе - океан. На вершине каждой горы есть отель. Вы хотите выбрать, в каком отеле остановиться. Высота i-й горы с запада равна Hi. Вы, конечно, можете увидеть океан из отеля, который расположен на вершине самой западной горы. Для отеля на вершине i-й горы с запада (i = 2, 3, ..., N) вы сможете увидеть океан тогда и только тогда, когда H1<=Hi, H2<=Hi, ... и Hi-1<=Hi. Посчитайте, со скольких из этих отелей вы сможете увидеть океан?

Входные данные
В первой строке записано натуральное число N (1 <= N <= 20) - количество гор. Вторая строка содержит N чисел Hi (1 <= Hi <= 100) высоты гор, начиная с самой западной (первой).


Выходные данные
Выведите количество отелей, из которых вы сможете увидеть океан.
 
 
Примеры
№ Входные данные Выходные данные
1 
4
6 5 6 8
 
3
2 
5
4 5 3 5 4
 
3
3 
5
9 5 6 8 4
 
1
Одномерные массивы
✓ 149✗ 206600лёгкаяВойти и решать
Количество элементов, равных максимальному#42260
Последовательность состоит из натуральных чисел и завершается числом 0. Определите, какое количество элементов этой последовательности, равны ее наибольшему элементу.

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

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 5
4
8
8
8
0		 3
Алгоритмы обработкиЦикл while
✓ 136✗ 221600лёгкаяВойти и решать
Подпоследовательность с K числами#39528
Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат ровно K отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой.  Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.

Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и целое число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 109.

Выходные данные
Выведите на экран ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Пояснение
1 8 2 3
6
-3
-2
4
-1
-13
8
13		 12 Нужные нам числа -3 и -13. Вся исходная последовательность даст максимальную сумму элементов.
Алгоритмы обработкиПрефиксные суммы(минимумы, ...)
✓ 21✗ 1381 000средняяВойти и решать
Безумный ученый#39516
Фермер Джон упорядочил N своих коров (1 ≤ N ≤ 1000) каждая из которых имеет одну из двух пород Holsteins или Guernseys. Он зафиксировал этот порядок в виде строки из N символов, каждый из которых либо H, либо G соответственно. К несчастью, когда коровы прибыли на ферму и он снова их выстроил, они образовали строку, отличную от исходной.

Назовём эти две строки A и B, где A - исходная строка, которую он хотел увидеть, B - строка которая получилась по прибытию коров. ФД попросил помощи у кузена Бена.

После нескольких месяцев работы, Бен создал замечательную машину MCBF-3000, которая способна взять любую подстроку и поменять в ней все G на H, а все H на G. Теперь ФД хочет узнать минимальное количество применений этой машины, которые позволят превратить строку B в строку A. Помогите ФД.

Входные данные
Первая строка содержит N, а следующие две строки содержат строки A и B. Каждая из строк состоит только из символов H и G.
Выходные данные
Выведите минимальное количество раз применения машины MCBF-3000 для трансформации строки B в строку A.
Примеры
№ Входные данные Выходные данные
1 
7
GHHHGHH
HHGGGHH
 2
Одномерные массивыЦикл for
✓ 11✗ 16900средняяВойти и решать
Подпоследовательность с максимальной суммой#39477
Дана последовательность из N целых чисел. Рассматриваются все её непрерывные подпоследовательности, начинающиеся с первого элемента последовательности. Найдите максимальную сумму подпоследовательности, кратную K, и количество таких подпоследовательностей.

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 106) и число K (1 <= K <= 100). Далее идет N строк, по одному целому числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран два числа через пробел: максимальную сумму подпоследовательности, кратную K и количество таких подпоследовательностей.
 
Примеры
№ Входные данные Выходные данные
1 5 2
2
-2
2
-2
2		 2 3
Алгоритмы обработкиЗадача на реализациюПрефиксные суммы(минимумы, ...)
✓ 112✗ 210600лёгкаяВойти и решать
Громозека и Алиса - 2#39397
Алиса и Громозека пошли гулять по городу. Заходя в первое кафе, Алиса посмотрела на часы и запомнила время входа. Далее она запоминала только количество минут, которое они с Громозекой тратили между двумя посещенными кафе (от входа в одно кафе, до входа в другое). По окончании прогулки, Алиса решила восстановить хронологию - время входа в очередное кафе.
Напишите программу, которая определит, в какое время Алиса и Громозека заходили в очередное кафе. 

Входные данные
В первой строке задан, момент времени, в который Громозека и Алиса вошли в первое кафе. Формат времени: часы (число от 00 до 23), далее идет двоеточие, затем минуты (число от 00 до 59). Строка времени записана без пробелов.
Во второй строке записано натуральное число N (2 <= N <= 1000) - количество посещенных кафе (включая кафе из которого они вышли в начальный момент времени и последнее кафе). В третьей строке записано N-1 число: первое показывает время в минутах от входа в первое кафе до входа во второе, второе - время от входа во второе кафе до входа в третье и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные
Выведите для каждого кафе время входа Алисы и Громозеки. Формат времени должен быть такой же, как и во входных данных.
 
Примеры
№ Входные данные Выходные данные
1 07:00
4
10 5 3		 07:00
07:10
07:15
07:18
Задача на реализациюОдномерные массивыЦиклы
✓ 1✗ 41 100средняяВойти и решать
* Две самые большие цифры - 3#39067
Дано натуральное число N. Определите цифры числа, которые больше остальных цифр. Выведите две такие цифры в порядке невозрастания (вторая цифра меньше или равна первой).  

Входные данные 
На вход подается одно число N (10 <= N <= 109).

Выходные данные 
Выведите ответ на задачу.

 

Примеры
№ Входные данные Выходные данные
1 45545 5 5
2 1113 3 1
3 444 4 4
Алгоритмы обработкиЦикл for
✓ 1 050✗ 1 152500лёгкаяВойти и решать
Поделиться
Класснуть