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.

e-olymp 520. Сумма всех

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]2[/latex] [latex]4[/latex] [latex]6[/latex]
2 [latex]3[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]9[/latex]
4 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]10[/latex]
5 [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]

 

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

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

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

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

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

e-olymp 7944. Площадь прямоугольника

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex]  [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]1[/latex] [latex]1[/latex] [latex]1[/latex]
2 [latex]2[/latex] [latex]4[/latex] [latex]8[/latex]
3 [latex]511[/latex] [latex]428[/latex] [latex]218708[/latex]
4 [latex]5555[/latex] [latex]4444[/latex] [latex]24686420[/latex]
5 [latex]11[/latex] [latex]11[/latex] [latex]121[/latex]

 

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

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

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

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

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

e-olymp 165. Симметрия

Задача

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

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

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

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

 

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]10[/latex] [latex]2[/latex]
2 [latex]116[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]1[/latex]
4 [latex]454[/latex] [latex]2[/latex]
5 [latex]12301230[/latex] [latex]2[/latex]

 

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

 

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

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

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

А394г

Задача
Дана целочисленная квадратная матрица порядка [latex]n[/latex]. Найти номера строк, элементы каждой из которых образуют образуют монотонную последовательность (монотонно убывающую или монотонно возрастающую).

*Строки матрицы нумеруются с единицы, потому их номера в выводе больше соответствующих индексов в массиве на единицу.
Тесты

[latex]n[/latex] Матрица Результат Комментарий
1 0 1 Квадратная матрица первого порядка состоит из одного элемента, следовательно, является и монотонно возрастающей, и монотонно убывающей.
3
1 1 1
2 2 2
3 3 3
Все элементы каждой строки попарно равны.
4
1 2 2 1
0 1 2 3
0.3 11 -2 3
0 0 1 1
2 В прочих строках монотонность нарушается
3
1 2 2
-1 10 15
3 2 1
2, 3 В первой строке последовательность возрастает нестрого.

Алгоритм решения

  1. Анализировать строку на монотонность можно при помощи знака разности соседних элементов. Если при движении по строке слева направо знак изменяется, последовательность не может быть монотонной (дополнительное ограничение для строгой монотонности: разность не должна равняться нулю).
  2. Отдельно следует рассматривать случай [latex]n \le 1[/latex]. По определению, последовательность [latex]\left\{ { a }_{ n } \right\}[/latex] — монотонна [latex]\Leftrightarrow \forall i,j\in N, j>i: a_{ i }\prec a_{ j } (a_{ i }\succ a_{ j })[/latex]. Последовательность из одного элемента имеет вид [latex]\left\{a_{n}\right\} = a_{1}[/latex], следовательно, невозможно выбрать такие [latex]i,j \in N ,j>i[/latex], чтобы выполнилось условие строгой монотонности. Рассмотренный пример является частным случаем понятия «vacuous truth», часто применяемого при доказательстве теорем.

Программный код

Детали реализации

  1. Считывание элементов строки может прекратиться в трех случаях: если монотонность сменяется с возрастания на убывание (или наоборот), или если найдены два равных соседних элемента. Для выхода из внутреннего цикла применяется присваивание [latex]j = n[/latex].
  2. Для корректной работы внутреннего цикла первый элемент строки считывается перед ним.
  3. Проверить, изменяется ли знак разности соседних элементов последовательности можно двумя способами: первый подразумевает умножение двух разностей, второй — реализацию функции signum(). Так как при умножении можно выйти за границы типа, выбран был второй способ.

Программа доступна для тестирования по ссылке: http://ideone.com/n60As6.
Реализация на Java: http://ideone.com/CnFow1