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

Казума и его спутницы#39838

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

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

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

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

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

Входные данные:
В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения.
Следующие n строк содержат описание заданий — i-я строка содержит три числа a_i, m_i, d_i — величины, на которые изменятся отношения к Казуме Аквы, Мегумин или Даркнесс соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания.
Все числа во входных данных целые и не превышают по абсолютному значению 10⁷.

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

Примеры:

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

meet in the middle

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

Максимальная по модулю подпоследовательность#39835

Дан массив A, состоящий из n целых положительных чисел, и число m. Выберите последовательность позиций B₁, B₂, ..., B_k (1 <= B₁ < B₂ < ... < B_k <= n) такую, чтобы значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) было максимально (то есть, чтобы остаток от деления суммы элементов подпоследовательности на число m был максимально возможным). Выбранная последовательность может быть пустой.
Посчитайте максимальное возможно значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Входные данные
В первой строке даны два целых числа n и m (1 <= n <= 35, 1 <= m <= 10⁹). Во второй строке дано n целых чисел A₁, A₂, ..., A_n (1 <= A_i <= 10⁹)

Выходные данные
Выведите одно число - максимальное значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

Примеры

№	Входные данные	Выходные данные
1	4 4 5 2 4 1	3
2	3 20 199 41 299	19

Пояснения

В первом примере можно выбрать B = {1, 2}. (A₁ + A₂) mod m = (5 + 2) % 4 = 3.
Во втором примере можно выбрать B = {3}.

meet in the middle

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

ДВ-2022#39815

В лесополосе осуществляется посадка деревьев. Причем саженцы высаживают рядами на одинаковом расстоянии.
Через какое-то время осуществляется аэросъемка, в результате которой определяется, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд не менее 11 неприжившихся саженцев, при условии, что справа и слева от них саженцы прижились.
В ответе запишите сначала наибольший номер ряда, затем наименьший номер из неприжившихся мест.

Входные данные
В первой строке входного файла находится число N - количество прижившихся саженцев (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места, на котором прижились саженцы.

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

Пример входного файла

7
40 30
40 34
50 125
50 129
50 64
50 68
50 70

Ответ для примера (при поиске 3 подряд идущих неприжившихся саженца):
50 65

Файл к заданию

Алгоритмы сортировки ЕГЭ_информатика ЕГЭ-26. Обработка массива целых чисел. Сортировка

1 300труднаяВойти и решать

Бункеры#39676

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

Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n.
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут.
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете.

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

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

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 10⁵) - количество бункеров.
В следующих n - 1 строках находится по два целых числа u_i и v_i (1 <= u_i, v_i <= n, u_i ≠ v_i) - номера бункеров, которые соединяет i-ый тоннель.
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:

Входные данные	Выходные данные
2 1 2	NO
3 1 2 2 3	YES

Деревья Хеш

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

Культурный контакт#39675

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

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

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

Помогите руководителю определить максимальное количество фрагментов, которое может получиться.

Входные данные:
В первой строке дана строка s (1 <= |s| <= 5000000).

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

Примеры:

Входные данные	Выходные данные
abbabbbab	3
aabb	1

Пояснения:
В первом примере исследователи могут разбить цепочку 'abbabbbab' на фрагменты 'abb', 'abb', 'bab', тогда вождю каждого встреченного ими племени достанется по одной стекляшке типа 'a' и по две стекляшки типа 'b'.

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

Перебор Префиксные суммы(минимумы, ...)Хеш

✓ 3✗ 16—Войти и решать

Гекльберри Финн и две строки#39674

У Гекльберри Финна есть две строки s и t одинаковой длины n.
Гекльберри Финну нравится, когда у строк одинаковые префиксы (начала), поэтому он может поменять местами два символа в строке s, чтобы общий префикс строк s и t стал больше.
Однако этот трюк довольно утомительный, поэтому Гекльберри Финн либо совсем не будет его делать, либо сделает ровно один раз.

Помогите Гекльберри Финну определить наибольшую длину общего префикса строк s и t, которую он может получить.

Входные данные:
В первой строке дано натуральное число n (1 <= n <= 200000) - длина строк s и t
Во второй строке дана строка s, состоящая из строчных латинских букв.
В третьей строке дана строка t, состоящая из строчных латинских букв.

Выходные данные:
Выведите одно натуральное число - наибольшую длину общего префикса s и t, которую можно получить, применив операцию обмена двух символов в строке s не более одного раза.

Примеры:

Входные данные	Выходные данные
3 wai add	1
5 qdyid xreac	0

Перебор Префиксные суммы(минимумы, ...)Хеш

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

Чтение вслух#39673

Том Сойер и Гекльберри Финн вместе читают вслух вырезку из газеты. Но получилось так, что Том Сойер начал читать с i-ого символа, а Гекльберри Финн с j-ого.
Сколько букв они смогут прочитать, прежде чем обнаружат, что начали читать с разных мест или пока оба не дочитают до конца?

Входные данные:
В первой строке дана строка S (1 <= |S| <= 10⁵), состоящая из строчных латинских букв - надпись из газетной вырезки.
В следующей строке дано натуральное число q - количество запросов.
В следующих q строках дано по два натуральных числа i и j - позиции, с которых начинают читать Том Сойер и Гекльберри Финн соответственно.

Выходные данные:
Выведите q строк, в каждой из которых должно быть одно целое число - количество символов, совпадающих при чтении подстрок, начинающихся с i-ого и j-ого символа.

Примеры:

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

Бинарный поиск по ответу Префиксные суммы(минимумы, ...)Хеш

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

Том Сойер и слово на заборе#39672

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

Входные данные:
В первой строке дано слово s (1 <= |s| <= 200000), состоящее из строчных латинских букв.

Выходные данные:
Выведите минимально возможное по длине слово g, которое нужно дописать, чтобы слово sg на заборе стало палиндромом. Если дописывать ничего не надо, то выведите '-'.

Примеры:

Входные данные	Выходные данные
abc	ba
a	-

Жадный алгоритм Префиксные суммы(минимумы, ...)Хеш

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

Странный сон Константина#39670

Однажды Константин, поучаствовав в очередной, уже 13-ой по счету международной олимпиаде, возвращался на поезде домой. Он как всегда сидел и размышлял о смысле жизни, попутно решая задачи по программированию. Через некоторое время Константин задремал, но вот беда, для того, чтобы проснуться, он должен решить всплывшую у него в голове задачу, не дающую ему покоя!

В этот раз Константину приснилось дерево, изначально состоящее всего из одной вершины с номером 1. В поставленной им задаче к дереву постепенно добавлялись новые вершины. В i-ую секунду в дерево добавлялась вершина с номером i+1, которая подвешивалась в качестве сына к вершине p_i, а на ребре между вершинами i+1 и p_i записывалась буква c_i.

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

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

Входные данные:
В первой строке записано число n - количество запросов на добавление новой вершины в дерево (1 <= n <= 300000).
В следующих n строках описаны запросы добавления вершин. i-ый запрос описывается параметрами p_i (1 <= p_i <= i) и c_i, которые означают, что добавленная вершина с номером i+1 подвешивается к вершине с номером p_i в качестве потомка, а на полученном ребре записывается символ c_i - строчная буква латинского алфавита.

Выходные данные:
Выведите n строк. В i-ой строке выведите ответ на задачу Константина после добавления i+1-ой вершины.

Примеры:

Входные данные	Выходные данные
2 1 b 2 p	1 2
3 1 o 1 o 2 j	1 1 2

Бор Деревья Хеш

✓ 59✗ 363500лёгкаяВойти и решать

Перевозки#39626

В связи с приближающимся завершением эпидемии коронавируса правительство города Энска приняло решение отправить на южные морские курорты отличников школ города - N отдыхающих.
В авиакомпаниях для перевозки имеются K типов самолётов с различным количеством пассажирских мест (P₁, P₂,...,P_k). Необходимо решить логистическую задачу: зарезервировать необходимое количество рейсов (R₁, R₂,...,R_k).
Суммарное количество посадочных мест не может быть меньше, чем количество пассажиров, а общее количество незанятых пассажирских мест (V) должно быть минимальным. Если будет обнаружено несколько вариантов, одинаковых по количеству незанятых мест, то следует выбрать вариант с меньшим общим количеством рейсов самолётов. Если и таких вариантов будет несколько, то нужно вывести любой из них.
Входные данные
в первой строке через пробел записаны 2 натуральных числа N и K, во второй - K натуральных чисел P₁ P₂ … P_k. N не превышает 10000, K не превышает 20, любое P_i меньше 500.
Выходные данные
в первой строке вывести число V, во второй через пробел вывести R₁ R₂ … R_k. Порядок количеств рейсов должен соответствовать исходному порядку типов самолётов.

Примеры

№	Входные данные	Выходные данные
1	1000 3 300 220 150	30 0 0 4 1
2	80 4 100 50 40 30	0 0 1 0 1 (вариант - 0 0 2 0)

Динамическое программирование

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

В троичную систему счисления#39624

Задано натуральное число N, не превышающее 10⁸ . Требуется определить, сколько чётных цифр входит в его запись в троичной системе счисления.
Входные данные
число N, записанное в десятичной системе счисления.
Выходные данные
количество чётных цифр, входящих в запись числа N в троичной системе счисления.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4	0	4₁₀=11₃
2	15	2	15₁₀=120₃

Системы счисления

✓ 105✗ 87400лёгкаяВойти и решать

Фотография коров#39570

Фермер Джон хочет сфотографировать своих пасущихся коров, чтобы повесить эту фотографию на стене. Пастбище представлено решёткой из N * N ячеек (как шахматная доска размером N×N) (2≤N≤1000). ФД хочет, чтобы коровы были распределены по пастбищу с выполнением следующих правил:
Никакие две коровы не могут находится в одной и той же ячейке.
Каждая подрешётка размером 2×2 (всего таких подрешёток (N−1)×(N−1)) должна содержать ровно 2 коровы
Например, такое размещение соотвествует правилам:

CCC
...
CCC
А такое размещение - нет

C.C
.C.
C..
поскольку 2×2 регион в правом нижем углу содержит только одну корову.
Других ограничений нет. Вы можете считать, что у ФД есть бесконечное количество коров.

Некоторые ячейки более предпочтительный для ФД, нежели другие. В частности, ФД считает. что если корова размещена в ячейке (i,j), красота фотографии увеличивается на a_ij (0≤a_ij≤1000) единиц.

Определите максимально возможную красоту корректного размещения коров.

Входные данные
Первая строка содержит число N. Каждая из следующих N строк содержит по N целых чисел. j-ое число в i-ой строке сверху есть значение a_ij.
Выходные данные
Выведите одно целое число - максимально возможную красоту результирующего фото.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	4 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3 3	22	В этом примере максимальная красота может быть достигнута следующим размещением: CC.. ..CC CC.. ..CC Красота этого размещения 3+3+3+1+3+3+3+3=22.

Перебор

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

Коровий алфавит#39561

Малоизвестен тот факт, что у коров свой алфавит "cowphabet". Он состоит из тех же 26 букв от 'a' до 'z', но в другом порядке.
Чтобы скоротать время, Беси бормочет cowphabet опять и опять. Фермеру Джону интересно, сколько раз она его пробормотала.

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

Входные данные
Первая строка ввода содержит 26 маленьких латинских букв от 'a' до 'z' в порядке их появления в cowphabet. Следующая строка содержит строку из маленьких латинских букв, которые услышал ФД. Эта строка имеет длину от 1 до 1000.
Выходные данные
Выведите минимальное количество раз, которое Беси пробормотала алфавит.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	abcdefghijklmnopqrstuvwxyz mood	3	В этом примере cowphabet упорядочен как нормальный алфавит. Бесси пробормотала cowphabet как минимум 3 раза. Ниже показано, как Беси бормотала, и большими буквами - какие буквы услышал ФД. abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz

Перебор Строки

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

Количество чисел кратное К#39529

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат кратное K количество отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой. Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.

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

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1

Остатки Префиксные суммы(минимумы, ...)

✓ 0✗ 7—Войти и решать

Количество подпоследовательностей - 2#39518

На вход программе подается последовательность целых чисел. Рассматриваются все непрерывные подпоследовательности исходной последовательности, сумма элементов которых кратна K. Найдите количество таких подпоследовательностей. Гарантируется, что в последовательности такая подпоследовательность есть.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число – количество таких подпоследовательностей.

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	4

Остатки Префиксные суммы(минимумы, ...)

✓ 1✗ 5—Войти и решать

Треугольники#39517

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 100) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.

Вывод формулы Перебор

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

Три четыре пять корову поменять#39515

N коров (1 ≤ N ≤ 100) Фермера Джона выстроены в ряд. i-ая корова слева имеет метку i, для всех 1≤i≤N.
ФД приказал коровам повторить ровно K (1 ≤ K ≤10⁹) раз следующий двухшаговый процесс:

Последовательность коров в позициях A1…A2 слева реверсивно меняют свой порядок (1≤A₁<A₂≤N).
Затем последовательность коров в позициях B1…B2 слева реверсивно меняют свой порядок (1≤B₁<B₂≤N).
Выведите получившийся порядок коров для всех i 1 ≤ i ≤ N после выполнения этого процесса ровно K раз.

Входные данные
Первая строка содержит N и K. Вторая строка содержит A₁ и A₂, третья строка содержит B₁ и B₂.
Выходные данные
На i-ой строке выведите метку i-ой коровы слева после завершения процесса всех обменов.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой [1,2,3,4,5,6,7] После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. Повторив оба шага ещё раз получим результат, приведенный в выводе.

Вывод формулы Задачи на моделирование

✓ 1✗ 13—Войти и решать

Треугольники - 2#39513

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 10⁵) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.

Алгоритмы сортировки Вывод формулы

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

Часовое дерево#39505

Новый амбар Фермера Джона состоит из N комнат (2 ≤ N ≤ 2500), последовательно пронумерованных 1…N, и N−1 коридоров. Каждый коридор соединяет пару комнат таким образом, что возможно пройти из лбой комнаты в любую через серию коридоров.
Каждая комната в амбаре имеет круглые часы на стене со стандартным размещением цифр 1…12 на лицевой стороне. Однако на этих часах имеется только одна стрелка, которая всегда показывает точно на одно из целых чисел (она никогда не показывает между двумя из этих чисел).

Корова Беси хочет синхронизировать все часы в амбаре, чтобы они все показывали на число 12. Но со своим коровьим мышлением, каждый раз, когда она входит в комнату, она перемещает стрелку вперёд на одну позицию. Например, если стрека показывала на 5, Беси переводит стрелку на 6. Если часы указывали на 12, она переводит стрелку на 1. Если Беси входит в комнату несколько раз, она переводит стрелку при каждом входе.

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

Входные данные
Первая строка ввода содержит N. Следующая строка содержит N целых чисел, каждое в интервале 1…12, указывающих начальные положения стрелок в каждой комнате. Каждая из следующих N−1 строк описывает коридор двумя целыми числам a и b, каждое в интервале 1…N, и задающих номера комнат, соединённых этим коридором.

Выходные данные
Выведите номера комнат, в которых Беси может начинать, чтобы установить все часы на 12.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 11 10 11 11 1 2 2 3 2 4	1	В этом примере Беси может установить все стрелки на 12, тоько в том случае, если она начнёт в комнате 2 (например перемещаясь так: 1, 2, 3, 2, 4.

Вывод формулы Обход в глубину

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

Концертная площадка#39498

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

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

В первой строке входного файла 26.txt находится число N – количество свободных мест (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер свободного места.

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

Пример входного файла

6 1 1 1 2 1 3 1 4 1 5 1 6

Файл к заданию

Алгоритмы сортировки ЕГЭ_информатика ЕГЭ-26. Обработка массива целых чисел. Сортировка

1 400труднаяВойти и решать