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

Сдача - 2#47748

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

Входные данные
Программа получает на вход сумму S. Далее идет число N затем P₁, P₂, ..., P_N. Далее идет число M, затем Q₁, Q₂, ..., Q_M.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если они не могут рассчитаться, выведите число -1.

Задача о рюкзаке

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

Весы#47747

Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4^{n - 1} грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

Входные данные
В единственной строке содержаться 2 целых числа m и n (1 ≤ n , m ≤ 10⁹ ) .

Выходные данные
Выведите одно число - количество масс, которые можно измерить с помощью этих гирь.

Задача о рюкзаке

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

Гармоничная последовательность lite - 2#47740

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 500\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

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

Примеры

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

Перебор

—Войти и решать

Магическая энергия - 2#46737

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

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

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел a_i - количество магической энергии в i-м доме.

Ограничения на входные данные

1 <= n <= 100
0 <= a[i] <= 1000
1 <= i <= n

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

Примеры

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

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

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

Range Minimum Query#44992

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

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

запрос: «? i j» — возвращает минимальный элемент между i-ым и j-м, включительно;
изменение: «+ i x» — добавить элемент x после i-го элемента списка. Если i=0, то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.

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

Первая строка входного файла содержит единственное целое число n — число операций над массивом (1<=n<=200000). Следующие n строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 10⁹.

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

Для каждой операции в отдельной строке выведите её результат.

Комментарий к примеру тестов

Нижеследующая таблица показывает процесс изменения массива из примера.

Операция	Массив после её выполнения
изначально	пуст
`+ 0 5`	5
`+ 1 3`	5, 3
`+ 1 4`	5, 4, 3
`+ 0 2`	2, 5, 4, 3
`+ 4 1`	2, 5, 4, 3, 1

Примеры

№	Входные данные	Выходные данные
1	8 + 0 5 + 1 3 + 1 4 ? 1 2 + 0 2 ? 2 4 + 4 1 ? 3 5	4 3 1

Деревья

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

Переворот#44989

Дан массив. Надо научиться обрабатывать два типа запросов.

* 1 L R - перевернуть отрезок [L,R]

* 2 L R - найти минимум на отрезке [L,R]

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

Первая строка файла содержит два числа n, m. (1<=n,m<=10⁵) Во второй строке находится n чисел n_i (1<=a_i<=10⁹) - исходный массив. Остальные m строк содержат запросы, в формате описанном в условии. Для чисел L, R выполняется ограничение (1<=L<=R<=n).

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

На каждый запрос типа 2, во входной файл выведите ответ на него, в отдельной строке.

Примеры

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

Деревья

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

Бинарное дерево (вставка, поиск, удаление)#44987

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

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

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

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

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

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

№	Входные данные	Выходные данные
1	ADD 2 ADD 7 ADD 5 PRINTTREE ADD 5 DELETE 3 ADD 0 PRINTTREE DELETE 7 PRINTTREE	DONE DONE DONE 2 ..5 .7 ALREADY CANNOT DONE .0 2 ..5 .7 DONE .0 2 .5

Деревья

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

Бинарное дерево (вставка, поиск)#44985

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

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

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

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

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

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

№	Входные данные	Выходные данные
1	ADD 2 ADD 3 ADD 2 SEARCH 2 ADD 5 PRINTTREE SEARCH 7	DONE DONE ALREADY YES DONE 2 .3 ..5 NO

Деревья

✓ 6✗ 9—Войти и решать

Промежуток на числовой оси#44940

На числовой оси, в промежутке от L до R, Василий нарисовал N вертикальных палочек. Подумав, Василий решил, что ему на числовой оси необходим пустой промежуток шириной не менее W.
Помогите определить Василию, какое минимальное количество палочек необходимо стереть Василию и какие именно.
После того как Василий сотрет некоторое количество палочек, должен найтись промежуток шириной больше или равной W. Промежуток может располагаться между двумя оставшимися палочками, или между оставшейся палочкой и концом промежутка числовой оси, или между двумя концами промежутка числовой оси.

Входные данные
Первая строка содержит два целых числа N и W — количество нарисованных палочек и минимально необходимую ширину промежутка соответственно. Гарантируется, что 0 <= N <= 1 000 000 и 0 <= W <= 1 000 000.
Во второй строке находятся два числа L и R — координаты левого и правого конца промежутка числовой оси (L <= R). В третьей строке записаны N чисел — координаты нарисованных палочек. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 1 000 000. Гарантируется, что все палочки нарисованы между левым и правым концами стороны.

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

Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите одну строку, содержащую число - 1.

Примеры

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

Бинарный поиск по ответу

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

Ральф любит пончики#44712

Громила Ральф вот уже 30 лет живёт в игровом автомате, и вы его можете увидеть на экране того самого автомата.
Сегодня Ральф гуляет по экрану, на котором отображается прямоугольное изображение, разбитое на N x N клеток. В каждой клетке находится тарелка с его любимыми блинчиками (на всех тарелках разное количество блинчиков). Ральф начинает перемещаться с левой нижней клетки прямоугольника. Съев все блинчики в текущей клетке, он перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, где больше блинчиков в тарелке (за пределами прямоугольника тарелок с блинчиками нет). В конце концов Ральф приходит в правую верхнюю клетку. Вам же предстоит определить, сколко всего блинчиков съел Ральф пока путешествовал по экрану. Блинчики в начальной и конечной клетках Ральф тоже съел с большим удовольствием.

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

Программа получает на вход в первой строке целое число N – размер изображения (2 <= N <= 10). В следующих N строках задаются через пробел числа, обозначающие количество блинчиков на тарелках, начиная с верхнего ряда и заканчивая нижним. Все числа – различные, натуральные, не превосходящие 100.

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

Выведите одно число - количество блинчиков, которое съест Ральф, добравшись до правой верхней клетки.

Примеры

№	Входные данные	Выходные данные
1	2 37 82 23 52	157

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

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

Новый вопрос#44601

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

—Войти и решать

Эффективные сборы#43870

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

1 <= l <= r <= n;
a_l = a_l+1 = a_l+2 =…=a_r;
l = 1 или a_l-1 > a_l;
r = n или a_r < a_r+1;

Примеры

Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:

1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);

2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);

3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).

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

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 2·10⁵) — длину массива. Вторая строка n целых чисел a_i (1 <= a_i<= 10⁹) — количество решенных Лукой задач в i-й день .

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

Примеры

№	Входные данные	Выходные данные
1	`7` `5 3 3 2 3 3 4`	YES
2	`11 2 2 2 3 4 4 5 6 7 7 8`	YES
3	`7 1 2 3 4 3 2 1`	NO

"Два указателя"

✓ 6✗ 12—Войти и решать

K-mex#43131

Вы думали, что сможете спокойно выехать из Озёрска, погостив у друга? Конечно же, нет. Полицейский опять остановил вас и снова просит решить задачу, чтобы удостовериться, что вы можете выехать из города. Придётся вам решить очередную задачу.
Изначально у вас множество, в котором есть единственный элемент — это 0. Вам нужно будет поддерживать q запросов следующего вида:
•   + x — добавить число x в множество. Гарантируется, что раньше его там не было,
•   - x — удалить число x из множества. Гарантируется, что это число там есть,
•   ? k — найти k − mex множества.
В нашей задаче мы считаем, что k − mex множества — это наименьшее целое неотрицательное число x, которое делится на k и которого нет в множестве.
Входные данные
В первой строке находится целое число q (1 <= q <= 2 · 10⁵) — количество запросов.
В следующих q строках находятся описания запросов. Если это запрос добавления, то в формате
+ x (1 <= x <= 10¹⁸), если запрос удаления, то - x (1 <= x <= 10¹⁸), если же запрос поиска, то ? k (1 <= k <= 10¹⁸). Гарантируется, что будет хотя бы один запрос типа ?.

Выходные данные
Для каждого запроса типа ? выведите k − mex множества.

Примеры

№	Входные данные	Выходные данные
1	18 + 1 + 2 ? 1 + 4 ? 2 + 6 ? 3 + 7 + 8 ? 1 ? 2 + 5 ? 1 + 100000000 ? 100000000 - 4 ? 1 ? 2	3 6 3 3 10 3 200000000 3 4

Замечание
После первого и второго запроса во множестве будут элементы 0,1,2. Наименьшее неотрицательное число, которое не делится на 1 и которого нет в множества, равно 3.
После четвертого запроса во множестве будут элементы 0,1,2,4. Наименьшее неотрицательное число, которое не делится на 2 и которого нет в множества, равно 6

реализация Хеш

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

Лети, лети, лепесток...#43127

Лети, лети, лепесток,
Через запад на восток,
Через север, через юг,
Возвращайся, сделав круг.
Лишь коснёшься ты земли
Быть по-моему вели.
© Цветик-семицветик.

Во время осенних каникул, проходящих с 1 ноября по 8 ноября 2022 года, вы планируете совершить экскурсию в один из городов России. Вы даже выбрали город и даты полётов туда и обратно, но страница с результатами прогрузилась лишь частично. Вам требуется по имеющейся информации найти самый дешёвый вариант посетить выбранный город и вернуться, заодно посчитав, сколько у вас будет времени на осмотр достопримечательностей. Стоит учесть, что часто авиакомпании предоставляют скидку на перелёт туда-обратно.

Входные данные
В первой строке входного файла заданы два целых числа n и m — количество вариантов перелёта «туда» и «обратно» (1 <= n,m <= 1000). В следующих n строках описаны варианты перелёта «туда» в формате: CCxxxx yyyy.mm.dd hh:mm YYYY.MM.DD HH:MM TT:tt value, где:
•   CC — код авиакомпании, xxxx — номер рейса,
•   yyyy.mm.dd hh:mm — дата и время вылета,
•   YYYY.MM.DD HH:MM — дата и время прилёта,
•   TT:tt — время в пути, гарантируется, что время перелёта не превышает 24 часа,
•   value — целое число, стоимость перелёта (0 <= value <= 100000).
В следующих m строках описаны варианты перелёта «обратно» в том же формате. Дата вылета рейса «туда» во всех случаях как минимум на три дня раньше даты рейса «обратно».
Гарантируется, что все перелёты начинаются во время осенних каникул.
В последующих строках выписаны скидки, которые предоставляют авиакомпании за полёт тудаобратно. Каждая строка описывает одну авиакомпанию в формате: CC — код авиакомпании и value — целое число, размер скидки в процентах (0 <= value <= 100). Скидка рассчитывается с точностью до рублей, копейки отбрасываются в пользу клиента. Гарантируется, что у перечисленных компаний есть хотя бы один рейс либо «туда», либо «обратно», и что компании в данном списке не повторяются.

Выходные данные
В первой строке выведите два натуральных числа через пробел — оптимальные номера вариантов рейсов туда и обратно. Если существует несколько пар рейсов, дающих оптимальную стоимость, то нужно выбрать ту, которая позволяет провести за осмотром достопримечательностей как можно больше времени. Из всех таких пар выбрать ту, номера вариантов которой как можно раньше встретились в поисковой выдаче. Во второй строке выведите, сколько времени у вас будет на осмотр, в формате dd:hh:mm. Считается, что осмотр достопримечательностей начинается с момента прибытия и продолжается до момента отлёта.

Примеры

№	Входные данные	Выходные данные
1	2 3 DP4160 2022.11.02 07:05 2022.11.02 07:35 02:35 4000 DP4130 2022.11.02 07:45 2022.11.02 08:10 02:36 3423 S71141 2022.11.07 05:55 2022.11.07 09:55 02:40 3432 S71042 2022.11.07 05:59 2022.11.07 09:59 02:45 3422 S71243 2022.11.07 04:25 2022.11.07 09:25 02:30 3432 DP 15 S7 10	2 2 04:21:49

Замечание
Россия – большая страна с 11 часовыми поясами, поэтому, вполне возможно прилететь в город назначения раньше, чем вылетел, поскольку время отправления и прибытия самолетов всегда указывается по местному времени. Из Челябинска можно улететь в Калининград, с разницей -3 часа, или во Владивосток, с разницей +6 часов.

Вычисление по заданной формуле

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

Последовательности длины N#40064

Сколько целых последовательностей длины N, A = (A₁,…,A_N), удовлетворяют всем приведенным ниже условиям?
1) 1 <= A_i <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Входные данные
На вход подается строка, содержащая три целых числа N, M (1 <= N, M <= 50), K (N <= K <= NM).

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 4	6	(1,1) (1,2) (1,3) (2,1) (2,2) (3,1)

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

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

Социальное дистанцирование II#39389

Фермер Джон продолжает бороться за здоровье своих коров.
Имеется N cows (1≤N≤1000) коров, некоторые из которых больны. Коровы выстроены в ряд (на числовой прямой), корова i стоит на позиции x_i. ФД знает что если другая корова находится в радиусе R от больной, то она тоже заболевает. А потом заболевают коровы, которые находятся в радиусе R от этой и т.д.

К несчастью, ФД не знает точное значение R. Однако он знает, какие из его коров больны. По этим данным определите минимальное количество изначально инфицированных болезнью коров.

Входные данные
Первая строка ввода содержит N. Каждая из последующих N строк описывает одну корову двумя числами x и s, где x - позиция коровы, а s равно 0 для здоровой коровы и 1 для больной. Как минимум 1 корова больна. И все коровы, которые могли стать больными от распространения болезни уже больны.
Выходные данные
Определите минимальное количество коров, которые изначально были больны, перед любым распространением болезни.

Примеры

№	Входные данные	Выходные данные
1	6 7 1 1 1 15 1 3 1 10 0 6 1	3

Сканирующая прямая

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

Одностороннее движение#38844

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

Входные данные
В первой строке входного файла находятся числа N - количество площадей в городе и М - количество улиц их соединяющих (1 <= N <= 20000, 1 <= M <= 200000). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).

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

Примеры

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

Обход в глубину

✓ 2✗ 8—Войти и решать

Ананасы на Шешинеру#38832

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

Алиса хочет хочет отправить как можно большее число ананасов. Капитан Полосков решил ей помочь и с радостью согласился слетать на своем космическом корабле. Но есть один нюанс: на некоторых космических маршрутах можно дозаправить корабль, не превышающий максимально установленный вес. А заправлять корабль в пути нужно всегда, иначе он просто не долетит. Поэтому если корабль заполнить ананасами по максимуму, то, его не получится дозаправить в пути и поэтому не удастся воспользоваться самым коротким маршрутов, и придётся лететь через другие планеты. Может случиться даже так, что корабль не успеет долететь до Шешинеры вовремя, и ананасы испортятся.
Итак, сколько же ананасов можно погрузить в космический корабль, чтобы доставить груз вовремя?

Входные данные
Программа получает на вход несколько строк. В первой строке находятся числа n (1 <= n <= 500) и m - количество планет и количество космических маршрутов между планетми, соответственно. В следующих m строках записана информация о маршрутах. Каждый маршрут описывается в отдельной строке следующим образом. Сначала указаны номера планет, которые соединяются космическим маршрутом, потом время, которое тратится на перелет по этому маршруту, и, наконец, максимальный космического корабля, который можно заправить на этом маршруте. Известно, что все космические маршруты соединяют различные планеты, причем для каждой пары планет есть не более одного маршрута, непосредственно их соединяющий. Все числа разделены одним или несколькими пробелами.

Планеты нумеруются числами от 1 до n. Планеты Земля имеет номер 1, а планета Шешинера - номер n. Время перелета по маршруту задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что один ананас весит 100 грамм, а пустой корабль - 3 тонны.

Выходные данные
Выведите одно число - максимальное количество ананасов, которое можно доставить, потратив не более 24часов.

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2

Обход в ширину

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

Игрушечный лабиринт#38829

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

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

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

В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.

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

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

Примеры

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

Обход в ширину

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

Подматрица - 1#38791

У Фили есть квадратная матрица A размера N×N, но она кажется ему слишком большой. Ему гораздо больше нравятся матрицы размера k×k (k<N).
Филя хочет получить матрицу нужного размера взяв некоторую подматрицу исходной матрицы.
Подматрицей k×k матрицы A в данном случае Филя считает матрицу B такую, что b_i,j=a_i+x,j+y, для всех i, j от 1 до k. Из данного определения можно заметить, что подматрица исходной матрицы задается парой чисел (x, y).
Для того, чтобы выбрать наиболее интересную для себя подматрицу, Филя хочет узнать, сколько есть способов выбрать из исходной матрицы две различные (характеризующие пары (x, y) отличаются хотя бы в одной позиции) равные подматрицы k×k. Две матрицы Q и P размера k×k считаются равными, если для любых i,j:1≤i,j≤k выполняется q_i,j=p_i,j.
Если условия равенства не выполняется, матрицы считаются неравными.

Входные данные
В первой строке входного файла содержатся два натуральных числа N и k - размеры исходной и нужной матрицы.
(1<=k<=N<=10). В следующих N строках заданы через пробел по N натуральных чисел ai,j - элементы исходной матрицы (1<=a_i,j<10).

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

Примеры

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

Словари

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