Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Радость Громозеки#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·10⁵). Во второй строке записано N целых чисел A_i (1 <= A_i <= 10⁹).

Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между 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средняяВойти и решать

BalloonsBOOM#33119

Любимая компьютерная игра Васи называется “Overtouched”. В начале игры на

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

Нужно вывести все оставшиеся шарики.

Формат входных данных:

Вводятся числа n и m (0 <n,m < 1^9999999999 + 11) – количество строк и шариков в каждой строке соответственно. Затем вводится цвет каждого шарика. В следующей строке вводится цвет шариков k, которые нужно удалить.

Формат выходных данных:

Выводятся оставшиеся шарики после удаления.

Ввод	Вывод
4 3 1 2 3 4 2 2 1 7 6 2 2 2 2	1 3 4 1 7 6

(с) Кабицкий А., 2018г.

Алгоритмы обработки Одномерные массивы

✓ 0✗ 81 200средняяВойти и решать

Подземелья Одинокой горы#50865

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

Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет \(b\) единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из \(k\) отрядов, уменьшается на \((k - 1) \cdot X\) единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.

Известно, что в Средиземье проживают \(n\) рас, и количество существ \(i\)-й расы равно \(c_i\). Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.

Формат входных данных
Первая строка входных данных содержит три целых числа \(n\), \(b\) и \(X\) (\(1 \le n \le 200\,000\), \(1 \le b \le 10^6\), \(0 \le X \le 10^9\)) — количество рас и константы \(b\) и \(X\), описанные выше.

Вторая строка содержит \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 200\,000\)) — количество существ каждой из \(n\) рас.

Гарантируется, что \(c_1 + c_2 + \ldots + c_n \le 200\,000\).

Формат выходных данных
Выведите одно целое число — максимальную силу армии, которую могут составить жители Средиземья.

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.

Замечание

В первом примере жители Средиземья могут составить \(3\) отряда. Так как \(X = 0\), то сила армии не уменьшится из-за количества отрядов. Далее жителей по отрядам можно распределить так:

Единственного представителя первой расы можно отправить в первый отряд.
Первого представителя второй расы можно отправить в первый отряд, второго представителя второй расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на \(b = 1\).
Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(3 \cdot b = 3\), так как они образуют три пары, находящиеся в разных отрядах.

Таким образом, суммарная сила армии равна \(4\).

Массивы

✓ 3✗ 21 200средняяВойти и решать

Магический квадрат подрядка N#49391

Магическим квадратом порядка N называется квадратная матрица размера NхN, составленная из чисел 1, 2, ..., N²так, называется квадратная матрица размера NхN, такая что суммы по каждому столбцу, каждой строке и каждой из двух больших диагоналей равны между собой. Напишите программу, которая проверяет, является ли заданная квадратная матрица магическим квадратом.

Формат входных данных
В первой строке вводится размер матрицы N (0 < N <= 100). В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.

Формат выходных данных
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

Двумерные массивы

✓ 1✗ 411 200средняяВойти и решать

Параллельное программирование#44715

Миша занимается параллельным программированием. Сегодня он пишет программу для исполнителя "Квадратик". Исполнитель "Квадратик" живет на клетчатом поле размера N х M, размер одной клетки 1х1. Перемещаясь он закрашивает клетку, на которой побывал. Клетку, на которой он начал движение и на которой остановился он также закрашивает.
Миша установил на поле K "Квадратиков". Каждый "Квадратик" будет двигаться в указанном Мишей направлении и останавливаться дойдя до конца поля. После окончании движения всех "Квадратиков", Миша хочет узнать сколько клеток поля получились закрашенными. Так как задача подсчета не относится к параллельному программированию, а размер поля может быть очень большим, Миша попросил вас написать программу для подсчета таких клеток.

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

Программа получает на вход несколько строк. Первая строка содержит целые числа M и N - размеры поля исполнителя "Квадратик" (1 <= M, N <= 10⁶). Во второй строке записано число K - количество "Квадратиков" на поле (0 <= K <= 10³). Далее идут K строк, каждая из которых описывает положение определенного "Квадратика" и направление, в котором он будет перемещаться. Формат каждой из таких строк: два целых числа, записанных через один пробел и один символ {N, E, S, W} - начальные координаты и направление движения соответствующего "Квадратика". Символ отделен от чисел ровно одним пробелом.
Символами обозначены следующие направления движения: N - вверх, S - вниз, W - влево, Е - вправо.

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

Выведите количество закрашенных клеток поля, после окончания движения всех "Квадратиков".

Пояснения
Поле исполнителя и расположение "Квадратиков" для первого примера, показаны на рисунке ниже. Стрелочкой обозначено направление движения соответствующего "Квадратика".

Примеры

№	Входные данные	Выходные данные
1	8 5 4 4 4 S 6 2 W 6 3 N 6 4 S	13

Двумерные массивы

✓ 6✗ 1201 200средняяВойти и решать

Башни 2.0#44509

В компьютерной игре есть n башен, высота i-й башни равна a_i метров. Определим расстояние между двумя башнями с индексами i и j как |i−j|. Разрешается прыгнуть с i-й башни на j-ю башню тогда и только тогда, когда не существует такого индекса 1 <= k <= n, такого, что расстояние от i-й до j-й башни не меньше расстояния от i-й башни до k-й башни, и k-я башня имеет большую высоту, чем j-я. Башня j достижима из башни i если существует последовательность корректных прыжков, которая начинается в i-й башне и заканчивается в j-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.

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

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

Вторая строка входных данных содержит n чисел a₁, a₂, ..., a_n (1 <= a_n<= 10⁹) - высоты башен.

Выходные данные
Выведите 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средняяВойти и решать

Меняю конфеты на ноутбук#42450

Антон Б., суперспособный ученик 8 класса, обладает неудивительными математическими способностями. Побывав однажды на экскурсии в Колоколамске, он понял, что легко может написать программу, которая бы предсказывала стоимость его любимых конфет на любой промежуток дней вперед.
Используя эту программу, Антон Б. решил приобрести на все свои карманные деньги конфеты (а их у него было всего 10 рублей), затем, чуть позже, продать все купленные им конфеты. Таким образом, Антон Б. хочет заработать как можно больше денег на новый ноутбук.
Так как Антон Б. еще несовершеннолетний и один ездить в другие города не может, ему нужно понять, в какие из двух дней попросить старшего брата отвезти его в Колоколамск. Старший брат совершеннолетний и очень любит своего младшего брата, поэтому всегда готов ему помочь.
Так как Антон Б. очень торопится на кружок по информатике, он просит вас определить эти два дня в ближайшие N дней.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	6 10 3 5 3 11 9	2 5
2	4 5 5 5 5	0 0

Одномерные массивы Порядковые статистики

✓ 16✗ 7421 200средняяВойти и решать

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

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: Y [i₁, i₂, i₃, i₄] = min(X[j₁, j₂, j₃, j₄]), где 1 ≤ i_k ≤ N − M + 1, i_k ≤ j_k ≤ i_k + M − 1, а M - заданное число.

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

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 1	1
2	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

Двумерные массивы

✓ 1✗ 21 200средняяВойти и решать

Луч света в темном царстве#38360

Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

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

Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).

Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.

Примеры

№	Входные данные	Выходные данные
1	3 5 X.... ..... .....	XXXXX XXXXX XXXXX
2	3 3 ... ..X ...	/X\ X.X \X/

Двумерные массивы Задачи на моделирование

✓ 3✗ 01 200средняяВойти и решать

Мама, я диспетчер!#38277

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

Этот процесс не такой уж сложный, как может показаться на первый взгляд. В аэропорту, в котором работает Максим, всего одна посадочная полоса, поэтому самолеты должны садиться по очереди. Посадка занимает b минут. Если самолет прилетел, а посадочная полоса занята, его отправляют совершать дополнительные круги над городом до тех пор, пока он не прилетит к аэропорту со свободной взлётно-посадочной полосой. Один круг занимает f минут. Если посадочная полоса свободна, самолёт немедленно начинает посадку. Если несколько самолётов подлетают к аэропорту со свободной посадочной полосой одновременно, то один из них идёт на посадку, а другие отправляются совершать дополнительные круги.

Сегодня в аэропорт должны прилететь n самолетов, известно время прилета каждого из них. За какое время все самолёты совершат посадку?

Входные данные
В первой строке даны три целых числа n, b, f — количество самолетов (1≤n≤1000), время, которое занимает посадка и время, которое занимает один круг над аэропортом (1≤b, f≤10⁹ ). В следующей строке дано n целых чисел t_i — времена прибытия самолетов, перечисленные в произвольном порядке (0≤t_i≤10⁹ ).

Выходные данные
Выведите одно число: время, за которое все самолёты совершат посадку.

Примеры

№	Входные данные	Выходные данные
1	10 5 12 13 0 1 10 20 20 2 1 10 20	79

Одномерные массивы

✓ 2✗ 131 200средняяВойти и решать

Building a Ski Course#27301

Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:

RSRSSS

Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).

Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.

ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.

Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.

INPUT FORMAT:

* Строка 1: Два разделённых пробелом целых числа M и N.

* Строки 2..M+1: M строк ровно по N символов (каждый R или S),

описывающих желаемое финальное состояние поля.

OUTPUT FORMAT:

* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.

Ввод	Вывод
3 6 RSRSSS RSRSSS RSRSSS	3

OUTPUT DETAILS:

ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец, S в колонках 4-6.

Двумерные массивы Конструктив

✓ 0✗ 41 200средняяВойти и решать

Modern Art #3#27225

Недавно вошла в моду корова-художница Picowso.

Picowso рисует особым образом. Она начинает на чистом холсте N×N, представленной матрицей N×N нолей, где ноль означает пустую ячейку холста. Затем она рисует до 9 прямоугольников на холсте, каждый одним из 9 цветов (последовательно пронумерованных 1…9). Например, она может начать рисовать прямоугольник цветом 2, получая такое промежуточное состояние холста:

2220

0000

Затем она может нарисовать прямоугольник цветом 7:

2220

2777

0000

Затем она может нарисовать прямоугольник цветом 3:

2230

2737

2777

0000

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

По заданному конечному положению холста вычислите сколько из ещё видимых цветов могли быть первым нарисованным цветом.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, размер холста (1≤N≤10). Следующие N строк описывают финальную картинку холста, каждая содержит по N чисел в интервале 0…9. Гарантируется, что такой ввод был получен рисованием как описано выше с использованием различных цветов.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
4 2230 2737 2777 0000	1

Двумерные массивы Конструктив

✓ 4✗ 181 200средняяВойти и решать

Крепкий дом#27001

Джон Доу хочет построить крепкое здание, чтобы никто и никогда не нашел его. У него есть кирпичи 1х2, 1х3 и "уголки", то есть квадратики 2х2, у которых отсутствует одна клетка. Для уточнения смотрите на рисунки.

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

Джон считает стену крепкой, если нельзя провести такую прямую, что по обе стороны от нее есть кирпичи и она не пересекает ни одного кирпича. Касание кирпичей не считается пересечением. Вам требуется спроектировать крепкую стену, величиной NхM. Можно поворачивать кирпичи на углы, кратные 90 градусам.

Формат входных данных

Вводятся числа N и M (1 <=N, M <= 100) высота и ширина требуемой стены.

Формат выходных данных

Выведите N строк, содержащих по M символов от «A» до «Z», описывающие стену. Каждый кирпич должен описываться одинаковыми символами (кирпичи, имеющие общую сторону должны описываться различными символами). Не должно существовать прямой, по обе стороны которой были бы кирпичи и она не пересекала бы ни один из кирпичей. Если стену с заданными ограничениями построить невозможно, выведите «impossible».

Частичные решения, работающие при N, M <=6 получат не менее 40 баллов.

Двумерные массивы

✓ 0✗ 11 300средняяВойти и решать

Крестики-нолики#21821

Пете и Васе стало очень скучно на уроке биологии, и они решили поиграть в любимую всеми школьниками игру в крестики-нолики до пяти в ряд на бесконечном поле.

Рассмотрим кратко правила игры. Игра происходит на бесконечном клетчатом поле, два игрока делают ходы по очереди, первый игрок ходит крестиками, а второй — ноликами. В свой ход игрок

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

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

за один ход. Петя называет ход оптимальным, если для этого хода выполнено одно из двух:

• этот ход приводит к немедленной победе Пети;

• не существует хода, который приводит к немедленной победе Пети, но если Петя сделает этот ход, то Вася не выиграет следующим ходом и, вне зависимости от ответного хода Васи, у Пети

будет следующий ход, который приведет к его немедленной победе.

Помогите Пете найти количество оптимальных ходов.

Формат входных данных

В первой входного файла находятся два натуральных числа n, m (1 ≤ n,m ≤ 200) — размеры прямоугольника, содержащего все уже поставленные на поле крестики и нолики.

Следующие n строк содержат по m символов, каждый из которых равен одному из следующих:

«.» (точка), «X» (заглавная латинская буква «икс») или «0» (ноль). При этом «.» обозначает пустую клетку, «X» обозначает крестик, а «0» обозначает нолик. Гарантируется, что на поле находится

равное число крестиков и ноликов, и ни один игрок еще не одержал победу.

Формат выходных данных

Выведите одно число — количество оптимальных ходов Пети.

Примеры

№	Входные данные	Выходные данные
1	5 3 ... 000 XXX ... ...	2
2	4 4 ..0. .XX0 .0X. ....	0
3	5 6 ...... .XXX.. .0000. ..X... ......	0

Двумерные массивы Задача на реализацию Простые игры

✓ 1✗ 21 300средняяВойти и решать