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

Сумма чисел в массиве#33724

Дан массив произвольных целых чисел. Напишите программу, которая за один проход по массиву находит непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i<=j), что сумма всех элементов массива от a_i до a_j включительно будет максимальна. Индексация элементов начинается с 1.

Входные данные
В первой строке задается натуральное число n <= 100000 — количество элементов в массиве. В следующих n строках задаются сами элементы массива — целые числа, по модулю не превосходящие 30 000.

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

Примеры

№	Входные данные	Выходные данные
1	5 -1 2 3 -2 2	2 3
2	7 2 -2 3 -1 5 -2 7	3 7

Алгоритмы обработки Динамическое программирование: один параметр

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

Инопланетный геном#32979

Геном жителей системы Тау Кита содержит 26 видов оснований, для обозначения которых будем использовать буквы латинского алфавита от A до Z, а сам геном записывается

строкой из латинских букв. Важную роль в геноме играют пары соседних оснований, например, в геноме «ABBACAB» можно выделить следующие пары оснований: AB, BB, BA,

AC, CA, AB.

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

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

Программа получает на вход две строки, состоящие из заглавных латинских букв. Каждая строка непустая, и её длина не превосходит 10⁵.

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

Ввод	Вывод	Примечание
ABBACAB BCABB	4	Следующие пары оснований первого генома встречаются во втором геноме: AB, BB, CA, AB. Обратите внимание на то, что пара AB в первом геноме встречается два раза, поэтому и подсчитана в ответе два раза.

Алгоритмы обработки Строки Хеш

✓ 108✗ 317800средняяВойти и решать

Плацкартный вагон#31790

В плацкартном вагоне 54 места, пронумерованных числами от 1 до 54. Вагон разбит на 9 купе. Первые 36 мест расположены по левую сторону от прохода, места 1–4 находятся в первом купе, места 5–8 – во втором и т. д. В девятом купе находятся места с номерами 33– 36. По правую сторону от прохода находятся боковые места, их номера от 37 до 54, причём они нумеруются в противоположном направлении: места 37 и 38 находятся напротив девятого купе, а места 53 и 54 – напротив первого. Ниже приведена схема всех мест в вагоне.

Группа школьников едет на олимпиаду и будет всю дорогу крутить спиннеры.

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

Программа получает на вход число N – количество свободных мест в вагоне (0 ≤ N ≤ 54). Следующие N строк содержат номера свободных мест – различные числа от 1 до 54 в произвольном порядке, по одному числу в строке.

Программа должна вывести одно целое число – максимальное число подряд идущих свободных купе (купе – 4 места слева от прохода и 2 боковых места) в этом вагоне.

Ввод	Вывод	Примечание
12 5 6 3 4 8 7 51 9 10 54 49 52	1	Свободно одно купе с местами 5, 6, 7, 8, 51, 52.
1 1	0	В вагоне только одно свободное место, поэтому свободных купе нет совсем.

Алгоритмы обработки реализация

✓ 53✗ 132800средняяВойти и решать

Пираты!#27043

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

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

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

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

Помогите ему определить, на какое минимальное расстояние придјтся подойти к пиратской базе, двигаясь по самому безопасному маршруту.

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

В первой строке записано натуральные числа N и M (1 <= N, M <= 1 000 000) количество строк и столбцов на игровом поле.

Во второй строке записано натуральное число K (1 <= K <= 500) количество пиратских баз.

В следующих K строках записаны пары чисел R_i , C_i (1 <= R_i <= N, 1 <= C_i <= M) координаты пиратских баз (строка, столбец).

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

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

Система оценки

Решения, верно работающие при N, M 6<=500, будут набирать не менее половины баллов.

Ввод	Вывод
10 10 4 2 2 5 3 5 9 8 8	3

Замечание

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

Двумерные массивы Использование сортировки

✓ 9✗ 221 100средняяВойти и решать

Массив#26995

У Пети есть массив отсортированных в порядке неубывания натуральных чисел. Известно, что чисел N. Петя пытливый мальчик, поэтому хочет найти в массиве три числа x, y и z (x <= y <= z), такие, что сумма (x - y)² + (x - z)² + (z - y)² была бы максимальна. Помогите ему в этом.

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

В первой строке входного файла находится число N> (3<=N <= 100000). На следующей строке находятся N натуральных чисел, каждое из которых не превышает 10000.

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

Нужно вывести три числа x, y и z в порядке возрастания. Если вариантов такой тройки несколько, вывести любой.

Ввод	Вывод
4 1 2 3 5	1 2 5

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

✓ 12✗ 65800средняяВойти и решать

2048#26981

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

Напомним правила игры 2048. На поле 4 × 4 разбросаны числа, являющиеся степенями двойки от 2 до 1024, некоторые клетки могут быть пустыми. Каждый ход игрок может сдвинуть все плитки игрового поля в одну сторону. Если при сдвиге две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. За каждое соединение игровые очки увеличиваются на номинал получившейся плитки. Плитка, получившаяся при слипании двух других, не может больше участвовать в слипании.

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

Программа получает на вход четыре строки, в каждой из которых записано четыре числа. Числа являются степенями двойки от 2 до 1024. В некоторых клетках записано число 0, означающий, что данная клетка пуста.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0	4
2	2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0	8
3	2 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0	4
4	2 2 4 0 0 2 2 2 0 2 4 0 2 4 4 0	16

Примечания

Внимательно прочитайте этот раздел для лучшего понимания правил игры.

Наилучший ответ на первый тест достигается движением вниз.
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0

Наилучший ответ на второй тест достигается движением вниз.
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0

Наилучший ответ на третий тест достигается движением влево.
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Наилучший ответ на четвертый тест достигается движением вниз.
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2

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

✓ 5✗ 161 000средняяВойти и решать

Организация конференции (С, B')#23368

Недавно в солнечный весенний день директору Летней Флатландской Компьютерной Школы (ЛФКШ) Сергею Александровичу пришла в голову идея организовать первую флатландскую конференцию для школьников по программированию. Теперь перед ним стоит задача выбрать место проведения.

Флатландия представляет собой прямоугольник из m строк и n столбцов, в каждой из клеток которого расположен один город? Сергей Александрович уже посчитал для каждого города количество желающих принять участие в конференции. Известно, что флатландцы не любят далеко ездить, так что в каком бы городе она проводилась, в конференции смогут принять участие только школьники из самого города и соседних с ним по стороне городов. Формально говоря, если конференция проводится в городе, находящемся в i-ой строке и j-ом столбце, то в этой конференции будут участвовать школьники из городов (i, j), (i − 1, j) ( при условии, что i > 1) , (i + 1, j) (при условии, что i < m), (i, j − 1) (при условии, что j > 1) , и (i, j + 1) , (при условии, что j < n).

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

Обратите внимание на то, что школьникам, живущим в том же городе, в котором проводится конференция, поселение не нужно.

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

В первой строке записаны два числа m и n (1 <= m, n <= 350) - размеры Флатландии. В каждой из последующих m строк содержатся по n чисел.
В i-ой стоке и j-ом столбце содержится число a_i,j ( 0<= a_i,j<=10000) - количество школьников из города (i, j), желающих принять участие в конференции.

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

Выведите m строк по n чисел в каждой. Число в строке с номером i и стобце с номером j должно равняться количеству приезжих участников конференции, если местом проведения будет

выбран город, с координатами (i, j).

Ввод	Вывод
3 4 1 0 3 2 5 6 1 2 1 1 0 11	5 10 3 5 8 7 11 14 6 7 13 2
1 1 5	0

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

✓ 20✗ 21900средняяВойти и решать

Хождение за золотом - 3#22014

Однажды царь решил вознаградить одного из своих мудрецов за хорошую работу. Он привел его в прямоугольную комнату размром NxM, в каждой клетке которой лежало несколько килограммов золота. Царь разрешил мудрецу сделать обойти несколько клеток (переходя с клетки, где сейчас находится мудрец, в одну из четырех с ней соседних), и собрать все золото, которое попадется на его пути.
Мудрецу разрешено более одного раза проходить по одной и той же клетке. Золото с нее он берет при этом только один раз - когда проходит по клетке в первый раз.

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

Входные данные
Входные данные содержат план комнаты и маршрут мудреца. Сначала записано количество строк N, затем - количество столбцов M (1<=N<=20,1<=M<=20).
Затем записано N строк по M чисел в каждой - количество килограммов золота, которое лежит в данной клетке (число от 0 до 50).
Далее записано число X - сколько клеток обошел мудрец (1<=X<=10000).

Известно, что мудрец начал с клетки с координатами (1, 1). Далее записано X-1 число: куда перемещался мудрец:

число 1 обозначает, что мудрец делал шаг вправо,
число 2 обозначает, что мудрец делал шаг вверх,
число 3 обозначает, что мудрец делал шаг влево,
число 4 обозначает, что мудрец делал шаг вниз.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	3 4 1 2 3 4 5 6 7 8 9 10 11 12 9 4 1 1 2 3 3 1 4	24

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

✓ 78✗ 751800средняяВойти и решать

Отсутствующее число#21844

Вам даны n чисел a1, a2, ..., an. Найдите наименьшее целое положительное число x, не содержащееся в множестве {a1, ..., an}, то есть, такое, что не существует i, для которого верно ai = x.

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

В первой строке записано целое число n (1 ≤ n ≤ 10⁵) — количество чисел. Во второй строке через пробел записаны n чисел: a1, ..., an (1 ≤ ai ≤ 10⁹).

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

Выведите наименьшее целое положительное x не содержащееся в множестве {a1, ..., an}.

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

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

5
1 2 3 4 5

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

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

5
1 3 4 5 6

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

Примечание

Тесты разделены на группы, но оцениваются отдельно

n = 1 — 10 баллов
n ≤ 100 — 20 баллов
ai ≤ 10⁶ — 30 баллов
Без дополнительных ограничений.

Так, если вы решили задачу для n ≤ 100, то вы получите 30 баллов за первую и вторую группы, если вы решили задачу для a_i ≤ 10⁶, то вы получите 30 баллов за третью группу. Если ваша программа будет работать в обоих случаях, то вы получите 60 баллов. За полное решение вы получите 100 баллов.

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

✓ 67✗ 520800средняяВойти и решать

Жизнь#21839

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

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

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

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

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

Ввод состоит из 10-ти строк. Каждая строка содержит в себе 10 символов. Символ '#' означает, что в соответствующей ячейки находится живая клетка бактерии, а символ '.' означает, что ячейка пуста.

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

Необходимо вывести таблицу 10 на 10 — изображение бактерии в следующий момент времени.

Алгоритмы обработки Задача на реализацию

✓ 7✗ 901 100средняяВойти и решать

15580#15580

Годовые оценки по девяти предметам за 9й класс каждого из N учеников класса напечатаны в виде таблицы (в первой строке - оценки первого ученика, во второй - второго и т.д.) Фамилия ученика записана в первом столбце. Необходимо вывести данную таблицу в алфавитном порядке (по возрастанию, начиная с A заканчивая Z)

Входные данные: на вход программе подаются
в первой число N - количество учеников, 1<=N<=25
далее идут N строк, в формате <фамилия-последовательность латинских символов> <оценка за 1й предмет> <оценка за 2й предмет>... <оценка за 9й предмет>

Выходные данные: вывести на экран исходную таблицу, записанную в алфавитном порядке от A до Z

Примеры

входные данные

Sidorov 1 1 1 1 1 1 1 1 1 
Ivanov 5 5 5 5 5 5 5 5 5
Petrov 4 4 4 5 4 5 5 5 5

выходные данные

Ivanov 5 5 5 5 5 5 5 5 5

Petrov 4 4 4 5 4 5 5 5 5

Sidorov 1 1 1 1 1 1 1 1 1

Алгоритмы обработки Использование сортировки

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

15578#15578

Известны данные о количестве учащихся в каждом из N учебных заведений и о типе этого заведения (s-школа, t-техникум, u-училище). Составить программу, с сипользованием структур, которая находит среднее количество учащихся в каждом типе учебного заведения. Предполагается, что в записях имеется хотя бы 1 учреждение каждого типа

Входные данные: на вход программе подаются
в первой число N - количество записей, 1<=N<=25
далее идут N строк, в формате <число от 100 до 500 - число учащихся> <тип учебного заведения - буква s, t или u>

Выходные данные: вывести три числа через пробел в формате <среднее количество учащихся школ> <среднее количество учащихся техникумов> <среднее количество учащихся училищ> - все числа выводить с точностью до 6 знаков после запятой

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

✓ 13✗ 76800средняяВойти и решать

15576#15576

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

Входные данные: на вход программе подаются
в первой число N - количество записей, 1<=N<=25
далее идут N строк, в формате <число от 1 до 101 - возраст человека> <пол - буква m (мужской) или f (женский)>

Выходные данные: вывести одно число - средний возраст мужчин (число, с точностью 6 знаков после запятой)

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

✓ 8✗ 89900средняяВойти и решать

15575#15575

Известна информация о 25 моментах времени одних и тех же суток: часы (значения от 0 до 23) и минуты (от 0 до 59). Составить программу, с сипользованием структур, сравнивающую два любых момента времени по их условному порядковому номеру (определяющую, какой из моментов был в эти сутки раньше).

Входные данные: на вход программе подаются
в первой строке два целых числа, номера первого и второго моментов времени
далее идут 25 строк, в формате <номер записи> <часы-число от 0 до 23> <минуты-число от 0 до 59>

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

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

✓ 14✗ 154800средняяВойти и решать

1155#1155

Выберите строку, в которой правильно объявлен массив A, состоящий из 10 строк

1) string A [10];
2) string A[9];
3) string A[0..9];
4) string A[0..10];

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

900средняяВойти и решать

1135#1135

Сколько элементов содержит массив, объявленный как int А[10]?

1) 20
2) 9
3) 10
4) 11

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

900средняяВойти и решать

293#293

Что выполняет следующий фрагмент программы?

...
int random(int N)
{
 return rand()%N;
}
...
main()
{
const int N = 10;
int A[N], i;
printf("Исходный массив:\n");
for (i=0; i

1) Заполняет массив случайными числами и не выводит их на печать.
2) Заполняет массив случайными числами и выводит их на печать.
3) Заполняет массив одинаковыми числами и выводит их на печать.
4) Исходный фрагмент содержит ошибку

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

900средняяВойти и решать

292#292

Что может содержать в себе ячейка массива ?

Варианты:
1) только строковые данные
2) только отрицательные числа
3) числа совпадающие с номером ячейки
4) любые данные

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

800лёгкаяВойти и решать

291#291

Выберите наиболее правильное продолжение фразы: "Массив - это ..."

Ответ:
1) Ограниченная упорядоченная совокупность однотипных величин
2) Ограниченная совокупность различных элементов
3) Совокупность ограниченного числа логически связанных компонент, принадлежащих к разным типам
4)нет правильного утверждения

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

800лёгкаяВойти и решать

227#227

Как задать элементу массива случайное целое число в диапазоне от -10 до 10, если в программе определена функция int random(int N) { return rand() % N; }?

Варианты
1) x[i]=random(20)-10;
2) x[i]=random(21)-10;
3) x[i]=random(10)-10;
4) x[i]=random(-10..10);

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

1 000средняяВойти и решать