Алгоритмы обработки

265 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Количество чисел, удовлетворяющих условию (java)#46527
На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём (ноль не входит в последовательность). Определить, сколько получено чисел, которые делятся на 3.

Входные данные
На вход программе подаются числа, по одному числу в строке.

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

 

Примеры
№ Входные данные Выходные данные
1 1
2
3
0		 1

 

Алгоритмы обработкиЦикл while
✓ 134✗ 12300лёгкаяВойти и решать
Минимальная и максимальная цифры (java)#46524
Дано натуральное число N. Напишите программу, которая выводит в первой строке его максимальную цифру, во второй строке - его минимальную цифру.

Входные данные 
Вводится одно число N.

Выходные данные 
Вывести два числа, по одному в строке:
- в первой строке - максимальную цифру числа N; 
- во второй строке - минимальную цифру числа N.
 

 

Примеры
№ Входные данные Выходные данные
1 21345 5
1
Алгоритмы обработкиЦикл while
✓ 139✗ 25400лёгкаяВойти и решать
Доля в сумме#44941
Дан двумерный массив A размерностью NxM. Напишите программу, которая определяет сумму всех элементов матрицы, а также какую долю в этой сумме составляет сумма элементов каждого столбца.

Входные данные
В первой строке входных данных записаны через один пробел два натуральных числа N и M ( 0 < N, M <= 25). Далее идут N строк по M положительных целых чисел в каждой - элементы матрицы A (каждый элемент матрицы не превышает 105).

Выходные данные
В первой строке выведите сумму всех элементов матрицы. 
Во второй строке выведите M чисел через пробел - долю, которую составляет сумма элементов каждого столбца в общей сумме. Долю выводить с округлением до ближайшего целого числа, не большего доли. Первое число в строке - доля в общей сумме элементов первого столбца, второе число - доля в сумме элементов второго столбца и т.д. (нумерация столбцов с 1).
 
 
Примеры
№ Входные данные Выходные данные
1 4 4
1 2 3 4 
4 3 2 1
2 1 4 3
3 4 1 2		 40
25 25 25 25
Алгоритмы обработкиДвумерные массивы
✓ 23✗ 142600лёгкаяВойти и решать
Шахматный конь#44615

Шахматный конь, расположенный в центре доски держит под ударом 8 полей. В углу только лишь 2 поля.
Вам задано расположение коня на шахматной доске. Выведите на экран шахматную доску, с расположенным на ней конем, а также отметьте все поля, которые конь держит под ударом. Поле, где расположен конь, отметьте английской буквой «K». Поля, которые он держит под ударом, отметьте символами «*». Остальные клетки заполните точками.


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

Программа получает на вход два числа - координаты коня на шахматной доске (доска размером 8х8). Координаты вводятся на одной строке через пробел. Первое число обозначает номер строки, а второе — номер столбца. Все числа принимают значения от 1 до 8.


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

Выведите на экран изображение доски так, как это показано в примере. Обратите внимание, что символы в одной строке разделены пробелом.

 
Примеры
№ Входные данные Выходные данные
1 
4 5
 
. . . . . . . . 
. . . * . * . . 
. . * . . . * . 
. . . . K . . . 
. . * . . . * . 
. . . * . * . . 
. . . . . . . . 
. . . . . . . .
Алгоритмы обработкиДвумерные массивы
✓ 67✗ 78600лёгкаяВойти и решать
2022#44582

Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных пар индексов, у которых первый индекс в паре меньше второго, таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует пар 1 <= i,j <= n, для которых выполняется ai+aj=2022.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.



Входные данные
В первой строке содержится одно целое число n (1 <= n <= 100000) - количество элементов массива. Во второй строке заданы n целых чисел a1, a2, ..., an (0 <= ai <= 2022) - элементы массива Эвелины.

Выходные данные
Выведите одно число - количество подходящих пар.

Примечание

В первом примере не существует пар с суммой 2022.

Во втором подходят пары (1, 2), (3, 4).

В третьем примере подходят все пары (2, 4), (2, 5), (3, 4), (3, 5). 

 
Примеры
№ Входные данные Выходные данные
1 
2
1 2022
 
0
2 
4
1000 1022 1001 1021
 
2
3 
5
700 1 1 2021 2021
 
4
Алгоритмы обработкиБинарный поиск в массивеИспользование сортировки
✓ 5✗ 22900средняяВойти и решать
Башни 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средняяВойти и решать
Найти и посчитать#42324

Даны две целочисленные последовательности, каждая из которых имеет длину N: A = (A1, A2, ..., AN) и B = (B1, B2, ..., BN).
Все элементы A различны. Все элементы B тоже разные.

Выведите следующие два значения.

  1. Количество целых чисел, содержащихся в обоих A и B, появляющихся в одной и той же позиции в двух последовательностях. Другими словами, количество целых i чисел такое, что Ai = Bi.
  2. Количество целых чисел, содержащихся в обоих A и B, появляющихся в разных позициях в двух последовательностях. Другими словами, количество пар целых (i, j) чисел, таких, что Ai = Bj и i ≠ j.


Входные данные
Программа получает на вход три строки. В первой строке записано одно число N (1 <= N <= 1000) - количество чисел последовательности. Во второй строке записаны числа A1, A2, ..., AN, все числа различные. В третьей строке - числа B1, B2, ..., BN , все числа различные (1 <= Ai, Bi <= 109). 

Выходные данные
Выведите в первой строке ответ на первый вопрос, во второй строке - на второй.
 
 
Примеры
№ Входные данные Выходные данные
1 
4
1 3 5 2
2 3 1 4
 
1
2
2 
3
1 2 3
4 5 6
 
0
0
Алгоритмы обработкиМассивы
✓ 206✗ 289600лёгкаяВойти и решать
Количество различных элементов в монотонном массиве#42272

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


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

Сначала задано число N - количество элементов в массиве (1 <= N <= 100). Далее через пробел записаны N чисел - элементы массива. Массив состоит из целых чисел, находящихся в пределах от -231 до 231


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

Необходимо вывести единственное число - количество различных чисел в массиве.

 
Примеры
№ Входные данные Выходные данные
1 5
1 1 1 2 2		 2
Алгоритмы обработкиОдномерные массивы
✓ 136✗ 188500лёгкаяВойти и решать
Количество элементов, больших обоих соседей#42271

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


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

Сначала задано число N - количество элементов в массиве (1 <= N <= 10000). Далее через пробел записаны N чисел - элементы массива. Массив состоит из целых чисел.


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

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

 
Примеры
№ Входные данные Выходные данные
1 
5
1 2 3 4 5
 
0
2 
5
2 3 2 4 3
 
2
Алгоритмы обработкиОдномерные массивы
✓ 258✗ 296500лёгкаяВойти и решать
Спрятанная карта#42268
В колоде у Громозеки находятся карты, на которых написано по одному целому числу. Каждое число в колоде встречается ровно 4 раза. 
Таким образом, в колоде имеются 4 карты с числом 1, 4 карты с числом 2, ..., 4 карты с числом N. Всего в колоде 4*N карт.

Громозека перетасовал эти карты, а затем спрятал одну из них и дал вам стопку оставшихся 4*N-1 карт. На i-й карте (1<= i <=4*N−1) из стопки написано целое число Ai.

Найдите целое число, записанное на карте, которую спрятал Громозека.

Входные данные
Программа получает на вход две строки. Первая строка содержит целое число N (1 <= N <= 105).  Вторая строка содержит 4*N-1 целых чисел Ai (1 <= Ai <= 4*N−1. 1<= i <=4*N−1). Для каждого k (1<=k<=N) существует не более 4 индексов i, таких, что Ai=k.


Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 3
1 3 2 3 3 2 2 1 1 1 2		 3
2 1
1 1 1		 1
3 4
3 2 1 1 2 4 4 4 4 3 1 3 2 1 3		 2
Алгоритмы обработкиОдномерные массивы
✓ 69✗ 151600лёгкаяВойти и решать
Количество элементов, равных максимальному#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средняяВойти и решать
Подпоследовательность с максимальной суммой#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лёгкаяВойти и решать
Ты решишь это?#39382
Есть N частей некоторого исходного кода. Характеристики i-й части кода представлены M целыми числами Ai1, Ai2, ..., AiM . Вам даны целые числа B1, B2, ..., BM и C.
i-я часть кода правильно решает задачу тогда и только тогда, когда \( A_{i1}\cdot B_1 + A_{i2}\cdot B_2 + ...+ A_{iM}\cdot B_M +C>0\).
Среди N частей исходного кода найдите количество, которые правильно решают эту задачу.

Входные данные
В первой строке заданы три числа через пробел: N, M (1 <= N, M <= 20) и C (-100 <= C <= 100). Во второй строке задано  M чисел Bi (-100 <= Bi <= 100). Каждая из следующих N строк содержит M чисел Ai (-100 <= Aij <= 100, 1 <= i <= N, 1 <= j <= M).

Выходные данные
Выведите одно число - ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 2 3 -10
1 2 3
3 2 1
1 2 2		 1
2 5 2 -4
-2 5
100 41
100 40
-3 0
-6 -2
18 -13		 2
3 3 3 0
100 -100 0
0 100 100
100 100 100
-100 100 100		 0
Алгоритмы обработкиОдномерные массивы
✓ 41✗ 45700средняяВойти и решать
* Две самые большие цифры - 3#39067
Дано натуральное число N. Определите цифры числа, которые больше остальных цифр. Выведите две такие цифры в порядке невозрастания (вторая цифра меньше или равна первой).  

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

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

 

Примеры
№ Входные данные Выходные данные
1 45545 5 5
2 1113 3 1
3 444 4 4
Алгоритмы обработкиЦикл for
✓ 1 073✗ 1 156500лёгкаяВойти и решать
Экспресс тест#38798
В данной задаче вам предлагается автоматизировать оценку результата экспресс теста.
Вам дана двухцветная картинка размером 10×20. Для обозначения цветов используются символы «#» и «.». Тест
считается отрицательным, если на картинке изображена одна вертикальная полоска и положительным, если три. В любом
другом случае тест считается испорченным.
Полоской будем считать область картинки 10×k, состоящую из символов «#», где k может быть произвольным. При этом
все соседние клетки с этой областью должны быть «.». Полоска может находиться на границе картинки.

Входные данные
В первой строке входных данных задано число t - число тестов (1 ≤ t ≤ 30). В следующих t⋅10+(t−1) строках заданы картинки
тестов. Соседние картинки разделены пустыми строками. После последней картинки, пустой строки нет.
Каждая картинка состоит из 10 строк по 20 символов, каждый из которых либо «#», либо «.».

Выходные данные
Для каждой картинки выведите результат теста в отдельной строке:
Negative - если тест отрицательный;
Positive - если тест положительный;
Incorrect - если тест испорчен.

 Примеры
№ Входные данные Выходные данные
1 
4
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

.........##.........
.........##.........
.........##.........
.........#..........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.

..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..#.......#.....###.
 Negative
Incorrect
Positive
Incorrect
Алгоритмы обработкиЗадача на реализациюЗадачи на моделирование
✓ 13✗ 33800средняяВойти и решать
Радость Громозеки#38716
Громозека имеет последовательность целых чисел A длины N. Он сделает три среза в последовательности A и разделит ее на четыре (непустые) смежные подпоследовательности B, C, D и E. Положения срезов он выбирает произвольно. Пусть P, Q, R, S - суммы элементов в B, C, D,  E соответственно. Громозека будет счастлив, когда абсолютная разница между максимумом и минимумом между P, Q, R, S будет минимальной. Найдите минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.

Входные данные
В первой строке записано целое число N  (1 <= N <= 2·105). Во второй строке записано N целых чисел Ai (1 <= Ai <= 109).

Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.
 
Примеры
№ Входные данные Выходные данные Пояснения
1 5
3 2 4 1 2		 2 Если разделить A на B, C, D, E = (3), (2), (4), (1,2), то P = 3, Q = 2, R = 4, S = 1 + 2 = 3.
Здесь максимум и минимум среди P, Q, R, S равны 4 и 2, с абсолютной разницей 2.
Мы не можем сделать абсолютную разницу между максимумом и минимумом меньше 2, поэтому ответ - 2.
2 10
10 71 84 33 6 47 23 25 52 64		 36  
3 7
1 2 3 1000000000 4 5 6		 999999994  
"Два указателя"Алгоритмы обработкиМассивы
✓ 3✗ 171 200средняяВойти и решать
Кольцевые гонки#38690
Участники кольцевых гонок на одноколесных велосипедах нумеруются числами от 1 до N. Им предстоит проехать K кругов и победителем является тот, кто проехал их раньше всех. Участники стартуют одновременно с некоторой линии, которая называется конец круга. Каждый раз, когда участник пересекает эту линию, его номер фиксируется автоматической системой с высокой точностью (то есть два участника не могут пересечь эту линию одновременно). После прохождения K кругов эта же линия является финишной прямой. К сожалению, некоторые участники сходят с дистанции и проезжают меньшее количество кругов.
Организаторы соревнования забыли число K и стесняются спросить его у участников. Помогите организаторам определить победителя соревнования, используя только записи с системы фиксации. Гарантируется, что хотя бы один из участников преодолел необходимые K кругов и никто из участников не проехал более K кругов. Первая фиксация номера участника происходит после
прохождения первого круга.

Формат входных данных
В первой строке задаются целые числа N и M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10000) — количество участников соревнования и записей с системы фиксации соответственно. Во второй строке задается M целых чисел от 1 до N – номера участников в том порядке, как
они фиксировались системой.

Формат выходных данных
Выведите одно число — номер победителя
 
 
Примеры
№ Входные данные Выходные данные
1 3 4
1 3 3 1		 3
2 3 5
1 1 2 3 1		 1
Алгоритмы обработкиреализация
✓ 13✗ 17500лёгкаяВойти и решать
Поделиться
Класснуть