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

Пляжный волейбол#23314

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

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

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

Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствую- щем считалке номером K. Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны Q считалок, соответствующих различным значениям K. Для каждого из этих чисел K_i необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две коман- ды будут играть в матче с номером K_i.

Формат входного файла
Первая строка входных данных содержит единственное целое число N — количество команд (2 <= N <= 100 000). Вторая строка содержит N различных чисел от 1 до N — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди. Третья строка содержит единственное целое число Q (1 <= Q <= 100 000) — коли- чество известных Вере считалок. Каждая из следующих Q строк содержит число Ki (1 <= K_i <= 10¹⁸) — номер очередного интересующего Веру матча. Обратите внимание, Ki может быть больше N. Формат выходного файла Выведите Q строк: для каждого интересующего Веру числа K_i два числа в любом порядке — силы команд, сыграющих на K_i-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.

Примеры

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

Комментарии
Разберем первый тест из условия:

	Кто играет	Состояние очереди	Победитель	Проигравший
Матч № 1 Матч № 2 Матч № 3	1 3 3 2 3 4	2 4 4 1 1 2	3 3 4	1 2 3

Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.

Конструктив

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

Сумма чисел последовательности - Задание 3#23242

Напишите программу, которая находит сумму квадратов целых чисел от a до b.

Входные данные
В одной строке задаются два числа a и b (\(-100 < a,\ b < 100\)).

Выходные данные
Выведите одно число - сумму квадратов целых чисел от a до b.

Примеры

№	Входные данные	Выходные данные
1	1 5	55

Пояснение ответа: 1*1+2*2+3*3+4*4+5*5=55

Цикл for

✓ 8 984✗ 11 013100лёгкаяВойти и решать

Сумма чисел последовательности - Задание 2#23241

Напишите программу, которая находит сумму целых чисел от a до b (включительно), где a и b вводятся с клавиатуры.

Входные данные
В одной строке заданы два целых числа a и b (\(-100 <a,\ b < 100\)).

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

Примеры

№	Входные данные	Выходные данные
1	1 5	15

Цикл for

✓ 9 086✗ 30 281200лёгкаяВойти и решать

Оператор цикла for. Таблица умножения#23082

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

2*1=2
2*2=4
2*3=6
2*4=8
2*5=10
2*6=12
2*7=14
2*8=16
2*9=18
2*10=20

Цикл for

✓ 11 615✗ 35 823200лёгкаяВойти и решать

23073#23073

Дано натуральное число N (N<=15). Заполните и выведите на экран квадратный двумерный массив размером NxN по следующему правилу:

1 2 3 4 5 6

2 3 4 5 6 1

3 4 5 6 1 2

4 5 6 1 2 3

5 6 1 2 3 4

6 1 2 3 4 5

Каждый элемент массива отделяется от другого одним пробелом, каждая строка массива выводится с новой строки

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	6	1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5

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

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

23072#23072

1 1 1 1 1 1
1 2 3 4 5 6
1 3 6 10 15 21
1 4 10 20 35 56
1 5 15 35 70 126
1 6 21 56 126 252

Каждый элемент массива отделяется от другого одним пробелом, каждая строка массива выводится с новой строки
Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	6	1 1 1 1 1 1 1 2 3 4 5 6 1 3 6 10 15 21 1 4 10 20 35 56 1 5 15 35 70 126 1 6 21 56 126 252

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

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

Ожидание трамвая#23042

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

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

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

тот,что придёт раньше.Если данные введены некорректно,вывести "Absent";

Так же известно,что Ваня приходит на остановку в тот момент времени,когда к ней подъезжает первый трамвай

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

Сначала вводятся два числа d и k такие,что 0<=d<=100 и 0<=k<=100.

Затем вводится t строк(0<=t<=100,само число t нам неизвестно),заканчивающихся одним числом -1 по 2 числа в каждой- количество людей в трамвае и его номер

Вывод:

В выводе должно быть одно число-количество минут,которые Ваня простоит на остановке в ожидании трамвая,или же слово "Absent"

Задачи на моделирование

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

Веселый Новый Год#23039

У нас было 2 набора юного химика, 75 мятных таблеток, 5 упаковок оберточной бумаги, полфунта детских драже и целое множество подарков всех сортов и расцветок, а также машинки, куклы, мешок вкусного оленьего корма, пинта чистого сока и стадо быстрых оленей.
Не то что бы это был необходимый запас для поездки. Но если начал развозить подарки, становится трудно остановиться.
Единственное что вызывало у меня опасение - это олени. Нет ничего более непредсказуемого, чем стадо северных оленей, кто знает чего от них ожидать? Я догадывался, что рано или поздно они дадут о себе знать.
Самое страшное, что домов, куда нужно доставить подарки, более 10^100000000 и ребенок сильно расстроится, узнав, что не получил подарка на Новый Год. Этого допускать нельзя, благо вы - не единственный Санта, и вам будет достаточно доставить подарки только в своем городе. Детишек в вашем городе не больше 10^4, но все они живут в разных домах. У вас есть список, в котором не больше 10^4 элементов, каждый элемент списка представляет собой 2 целых числа – координаты дома следующего ребеночка. Доставив подарки в очередной дом, вы, как порядочный Санта, обязаны стирать координаты этого дома из своего списка. Но ваши олени не хотят спокойно доставлять подарки, они коллективно прокладывают на их взгляд более оптимальный и правильный маршрут, и выбирают номер следующего дома из вашего списка по своей очень логичной и тривиальной формуле:
N_next = |(K₁ - K₂) *R|% L,
где N_next – номер следующего дома в вашем списке (Как делают настоящие ТРУ-программисты? Они считают элемент с ~~единицы~~ нуля!) K₁ - количество еще не посещенных домов, K₂ – количество уже посещенных домов, R – коэффициент рандомности стада и L – длина текущего списка. Заметим, что после посещения дома, количество элементов в вашем списке уменьшается, вы же порядочный Санта, верно? Вечером, после тяжелого трудового дня, вы, как и остальные труженики Новогоднего фронта, выкладываете в свой блог количество километров, которые сегодня преодолели. Изначально вы находитесь в доме с индексом 0 и считается, что подарок в этот дом уже доставлен. Зная столь тривиальную, понятную и очевидную формулу расчета следующего дома, а также имея список домов и хорошо зная свое стадо, вплоть до их коэффициента рандомности, скажите какое расстояние вы пройдете за всю поездку? Ответ округлите вверх до целых, в таких вещах можно чуть-чуть преувеличить.

Входные данные:
В первой строке входного файла находятся целые положительные числа N, R (1<N<=10000,1< R <1000000) – количество детей в вашем списке и коэффициент рандомности вашего стада, соответственно.
В следующих N строках находятся по 2 целых числа X,Y (-100000<=X,Y<=100000) – координаты конкретного дома.
Выходные данные:
Выведете одно целое число – ответ на поставленную задачу.

Пример, как же без примера:
Входит:
4 2
1 1
0 0
2 0
2 1
Выходит:
6

(с) Ярослав Свиридов 10и

Задачи на моделирование реализация

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

Зл 9.26#22042

Дано слово вертикаль. Путем "вырезок" и "склеек" его букв получить слова тир и ветка.
Результирующие слова выводить в столбик.

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	вертикаль	тир ветка

Строки

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

Набор точек на плоскости#22029

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

В первой строке вводится одно целое положительное число – количество точек N. Каждая из следующих N строк содержит два целых числа – сначала координата х, затем координата у очередной точки.

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

Пример входных данных:

0 0

2 0

3 3

5 5

-6 -6
1 2

Пример выходных данных для приведенного выше примера входных данных:

ЕГЭ - вычислительные задачи

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

Ведьмак#22027

По приезде Геральда в Каэр-Морхен уже наступила зима. Вокруг стояла тишина, а окна замка приветливо светились в темноте. Редкие факелы создавали теплую и согревающую атмосферу, освещая ровный белый ковер из снега. Среди этой красоты особенно порадовал Геральда отъезд Весемира, ведь теперь можно закатить грандиозную пьянку!
Для этого на кухонный стол достали n кружек. Геральд суетился и переставлял кружки с l по r в позицию i, Ламберт с упоением доливал Ривский эль в кружки с l по r по s литров в каждую, а вот Эскель , пока никто не видит, выпивал или доливал в каждую кружку с l по r столько, чтобы в них осталось ровно по k литров в каждой. Спустя почти час Йеннифер, которой порядком надоела брань Ламберта и Эскеля, спустилась вниз, чтобы узнать причину шума. После небольшой перепалки Йеннифер решила помочь отнести кружки в главную столовую, где бурное веселье ведьмаков не мешало бы ей спать. Но так как кружки очень тяжелые, то она может унести не более l литров. Естественно, она хочет пойти спать как можно быстрее, а значит собирается унести как можно больше эля, но общим весом не более l.

Помогите Йеннифер узнать, какой максимальный вес и количество кружек с таким весом она может унести?

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

Дано число n(1 <= n <= 10^4) количество кружек и q(1 <= q <= 10^4) – количество операция. Далее идет описание операций(1 <= l <= r <= 10^4)

• G l r i - Геральд переставляет кружки с l по r в позицию I (1 <= I <=10^4+1)(вставка отрезка производится перед указанным индексом)

• L l r s - Ламберт доливает в кружки с l по r по s литров (1 <= s <= 10^3)

• E l r k – Эскель выпивает из кружек с l по r так, чтобы в каждой оказалось по k литров (1 <= k <= 10^3)

Затем на новой строке идет число l(1 <= l <= 10^5) – количество литров которые может унести Йеннифер.

Изначально в кружках по 0 литров.

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

На первой строке через пробел вывести последовательность кружек после проделанных операций, а на второй строке максимальное количество кружек, которые сможет унести Йеннифер и их общий вес.

Пример входных данных	Пример выходных данных
5 7 L 2 5 10 G 1 3 5 L 1 4 3 L 3 3 4 E 2 3 2 E 2 2 4 E 5 5 15 15	13 4 2 13 15 2 15
5 6 E 1 1 1 E 2 2 2 E 3 3 3 E 4 4 4 E 5 5 5 G 5 5 1 10	5 1 2 3 4 4 10
5 8 E 1 1 1 E 2 2 2 E 3 3 3 E 4 4 4 E 5 5 5 G 5 5 1 G 1 1 6 G 1 5 1 10	1 2 3 4 5 4 10

Пояснения к 1 примеру

1. 0 10 10 10 10

2. 10 0 10 10 10

3. 13 3 13 13 10

4. 13 3 17 13 10

5. 13 2 2 13 10

6. 13 4 2 13 10

7. 13 4 2 13 15

Йеннифер может унести 15 литров. Это значит что она может взять либо одну кружку (15 литров или 13 литров), либо две кружки(4 и 2 литра или 13 и 2 литра). Так как она хочет унести как можно больше кружек, то ответ 2.

Пояснения к 3 примеру

1. 1 0 0 0 0

2. 1 2 0 0 0

3. 1 2 3 0 0

4. 1 2 3 4 0

5. 1 2 3 4 5

6. 5 1 2 3 4

7. 1 2 3 4 5

8. 1 2 3 4 5

Йеннифер может унести 10 литров. Наилучший вариант будет 4 и 3 и 2 и 1 литр. Ответ 4.

(с) Аксенов Владимир 10и

Задача о рюкзаке реализация

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

Украшение елки#22025

В преддверии Нового Года Вася купил ёлку и решил её украсить. Для этого он должен достать с верхней полки шкафа самые красивые украшения. К сожалению, ставить стул на стул было плохой идеей… Теперь у него вместо коробки украшений – куча, состоящая из украшений, осколков и вещей из других коробок. Конечно же, её нужно разобрать. Но Вася так хочет смотреть новогодние фильмы! Помогите ему написать программу, которая разберёт кучу мусора за него.

Входные данные
На вход подаётся две строки. Первая – примеры украшений. Вторая – собственно куча.

Выходные данные
Нужно вывести количество украшений каждого вида, а также количество разбитых (обозначены точкой) украшений.

Примеры

№	Входные данные	Выходные данные
1	60oQ 484QQQQ.Qhu.6.oodnh...ddh76762..300ojha.	6: 3 0: 2 o: 3 Q: 5 Broken: 9
2	80 ..7.8.7.8.9.8	8: 3 0: 0 Broken: 7

Строки

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

Шурик и бомба#22023

В канун Нового Года радостный Шурик решил отправиться в ближайший торговый центр, чтобы купить подарки для своих друзей. Хороший морозный вечер, снегопад из крупных снежных хлопьев, яркие новогодние огни и приятная предпраздничная суета. Казалось бы, что может испортить этот день?

Но вдруг Шурик заметил подозрительный черный джип, ехавший по прямой, характеризующейся уравнением y=kx + b. Затем в точке М(x;y) джип остановился, и из него вышел крепкий юноша азиатского происхождения с черным чемоданом, предположительно бомбой. Он двигался по прямой, также проходящей через точку М и перпендикулярной прямой, характеризующей движение машины.

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

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

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

Помогите Шурику узнать площадь этого четырехугольника!

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

В первой строке записаны вещественные числа k (0.1<k<10)

и b (-20<b<20, b!=0)

Во второй строке записаны два целых числа: x и y (1<x,y<20) – координаты точки М.

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

Нужно вывести одно число – площадь четырехугольника с точностью до двух знаков после запятой.

Пример

Ввод:

2 1

1 3

Вывод:

11.00

Примечание:

(с) Курбатов Егор 9и

Элементарная геометрия

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

Компоненты связности#22021

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

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

Выходные данные: Выведите одно число - количество компонент связности

Примеры

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

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

✓ 1 101✗ 1 365300лёгкаяВойти и решать

Путь#22020

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

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

Формат выходных данных
Выведите сначала L - длину пути (количество ребер, которые нужно пройти). Затем выведите L+1 число - вершины в порядке следования вдоль этого пути. Если пути не существует, выведите одно число -1.

Примеры

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

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

✓ 707✗ 1 955600лёгкаяВойти и решать

Цветной дождь#22019

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

Формат входных данных
В первой строке записано N (\(0<N<=100\)) - число холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). В последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый.

Формат выходных данных
Вывести количество "плохих" мостов.

Способы задания графа

✓ 1 165✗ 751400лёгкаяВойти и решать

Светофорчики-1#22018

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

Формат входных данных
В первой строке записано два числа N и M (\(0<N<=100\), \(0<=M<=N*(N-1)/2\) ). В следующих M строках записаны по два числа i и j (\(1<=i,j<=N\)), которые означают, что перекрестки i и j соединены тоннелем.

Формат выходных данных
Вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

Примечание
Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

Способы задания графа

✓ 1 274✗ 962400лёгкаяВойти и решать

Города и дороги#22017

В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.

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

Формат выходных данных
Вывести одно число - количество дорог на планете "Neptune".

Примечание

Все дороги двусторонние, то есть если есть дорога из города i в город j, то есть и дорога из города j в город i, и это та же самая дорога.

Способы задания графа

✓ 1 532✗ 1 017300лёгкаяВойти и решать

Минимальный путь в таблице#22016

В прямоугольной таблице NxM (в каждой клетке которой записано

некоторое число) в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку

либо вправо, либо вниз (влево и вверх перемещаться запрещено).

При проходе через клетку с игрока берут столько у.е., какое число

записано в этой клетке (деньги берут также за первую

и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может

попасть в правый нижний угол.

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20,

1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов

в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

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

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

в правый нижний угол.

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

3 4

1 1 1 1

5 2 2 100

9 4 2 1

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

Динамическое программирование на таблицах

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

Хождение за золотом - 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средняяВойти и решать