e-olymp 7623. Счастливые случаи

Счастливые случаи

Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

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

В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.

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

Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 $1$ $1$
$4$
$4$
2 $2$ $4$
$0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$
$12$
3 $3$ $2$
$10$ $10$ $10$ $10$ $4$ $5$
$13$
4 $2$ $2$
$1$ $2$ $3$ $4$
$12$
5 $0$ $0$ $0$

 

Код программы

Решение задачи

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

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

e-olymp 179. Распределение

Распределение

Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов [latex]N[/latex] различных отрядов, которые были отправлены на завоевания. Однако прибывшие лишь только сейчас разведчики донесли о силах противников, скопленных в этих поселениях, что естественно скорректировало планы Оргрима. И теперь он хочет произвести перераспределение войск по отрядам, переводя воинов из одного отряда в другой. При этом, чтобы не создавать неразбериху в рядах своей армии и выполнить перераспределение как можно быстрее, количество таких переводов должно быть минимально возможным (за один раз переводится один солдат из некоторого отряда в другой).

Напишите программу, которая определяет минимальное количество переводов для перераспределения войск.

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

Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
2
4 2
5 1
1
1
4
4
0
3
2 2 2
4 1 1
2
3
6 3 1
0 0 10
9

 

Код программы

Решение задачи

Данная задача решается вычислением и суммированием разности соответствующих элементов второго массива и первого. Таким образом мы найдем количество воинов, которых не хватает и которых надо перевести в другой отряд. Возьмём эту разность по модулю, затем поделим на [latex]2[/latex], так как мы учитывали всех воинов. В итоге получим минимальное количество переводов из одного отряда в другой.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

e-olymp 4482. В стране невыученных уроков 2

Задача

Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.

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

Первая строка содержит количество элементов в массивеn (1n106). Во второй строке находится n чисел – элементы ai (1ai109) массива. В третьей строке находится количество запросовm (1m 105). Далее в m строках находится по три числа q, l, r (1lrn). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

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

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».

Код

Тесты

Входные данные Выходные данные
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 1
wins
wins
wins
draw
5
7 7 7 7 7
4
1 1 5
2 2 1
1 1 5
1 3 5
draw
wins
draw

Задача взята отсюда.

Решенная задача на e-olymp.

Код программы.

 

Related Images: