e-olymp 2507. Граница

Задача

В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [latex]h[/latex] на [latex]w[/latex] километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму. Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.

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

Первая строка содержит два целых числа: [latex]w[/latex] и [latex]h \left(1 \leqslant w, h \leqslant 100\right)[/latex] — размеры прямоугольника в километрах. Далее следуют [latex]h[/latex] строк, описывающих территорию. Каждая из них содержит [latex]w[/latex] символов. Если символ равен [latex]A[/latex], то соответствующий единичный квадрат принадлежит первому государству, а если он равен [latex]B[/latex], то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат. Территории каждого из государств представляют собой связные области.

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

Выведите одно целое число — длину границы между государствами в километрах.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 6
AAABB
ABBBB
AAABB
AAAAB
AAAAB
AABBB
13
2 4 3
AAAA
AAAA
AAAB
2
3 5 9
BBBBB
ABBBB
AABBB
AAABB
AAAAB
AAABB
AABBB
ABBBB
BBBBB
15
4 2 1
AB
1
5 6 5
AABBBB
BBBBBB
BBBAAA
AAAAAA
AAAAAA
10

Код

Решение

Занесем прямоугольную область в многомерный массив символов. Рассмотрим символ x[i][j]. Если он не совпадает с x[i + 1][j], то между ними имеется граница длины 1 (снизу от x[i][j] проходит граница). Аналогично, если x[i][j] не совпадает с x[i][j + 1], то между ними имеется граница длины 1 (справа от x[i][j] проходит граница). Остается перебрать все символы и подсчитать для них количество нижних и правых границ.

Запустить код (ideone) можно здесь
Задача на E-olymp

e-olymp 137. НОД

Задача

Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.

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

НОД заданных чисел.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2
15 25
5
2 3
99 358 2
1
3 5
81 99 72 108 36
9
4 2
25 50
25
5 4
132 36 66 18
6

Код

Решение

Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

Запустить код (ideone) можно здесь
Задача на E-olymp

e-olymp 1753. Младший бит

Задача

Для заданного положительного целого $A$ $(1 \leq A \leq 100),$ вывести младший бит $A$.

Например, если $A = 26$, то его мы можем записать в двоичном виде, как $11010$, и младший бит $A$ есть $10$, и на выходе должно быть $2.$

Другой пример выглядит следующим образом: при $A = 88$, это число $A$ мы можем записать в двоичной форме $1011000$, младший бит в $A$ есть $1000,$ и на выходе должно быть $8.$

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

Каждая строка входных данных содержит только одно целое число $A$ $(1 \leq A \leq 100).$ Строка, содержащая «0» означает конец ввода, и эта строка не является частью входных данных.

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

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

Тесты

Входные данные Выходные данные
 1 26
88
0
2
8
 2 99
45
66
20
1
1
2
4
 3 100
0
6
4
4 66
33
98
42
84
39
2
1
2
2
4
1

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

Решение

Объявляем переменную  a. Начинается цикл while, условием окончания которого будет введённая  a, неравная нулю. В цикле объявляем переменную  LSB = 1, после чего начинается новый цикл while, который сдвигает бит LSB  влево, пока выражение побитовой конъюнкции  a & LSB нулевое. Соответственно, как только выражение будет ненулевым — будет найден первый общий бит, который и будет младшим битом числа a. Его и выводим.

Ссылки

e-olymp 1151. Кладоискатель

Задача

Юный кладоискатель Рома прошел курс обучения по специальности «кладовое дело», и теперь проходит летнюю практику. Летняя практика проходит близ поселка «Каменные Зори» и длится ровно $b$ дней. Каждый день Рома находит $a$ закопанных в окрестности монет. Таким образом, в конце первого дня у него было $a$ монет, в конце второго — $2a,$ а по окончании практики у Ромы должно накопиться $b\cdot a$ монет.

Если в конце дня ответственный преподаватель замечал, что число Роминых монет делится на $b,$ то Роме разрешалось взять с полки пирожок, который он тут же съедал. Помогите Роме посчитать, сколько пирожков он съест за время прохождения практики.

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

Первая строка входного файла содержит два целых числа $a$ и $b$ ($1 \le a, b \le 10^9$).

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 2 1
2 2 2 2
3 10 5 5
4 56000 35 35
5 300 1000000000 100

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

Решение

Нам заданы $a$ и $b$.
Существует 3 случая их отношения между собой:

  1. $a$ кратно $b$. Тогда в последовательности $a, 2a, 3a,\ldots,b \cdot a$ кратным $b$ будет каждый элемент последовательности. То есть количество дней равно $b$. Или НОД от $a$ и $b$, поскольку $a$ кратно $b$.
  2. Существует такое $k, k \in (1; b), k \in N.$ При котором: $k \cdot a$ кратно $b.$ $\frac{ka}{b} = c, c \in N$. Тогда у $b$ и $a$ есть НОД. $(b, a) = p, p > 1, p \in N$. $a = \tilde a \cdot p$, $b = \tilde b \cdot p.$ Тогда в последовательности $a, 2a, 3a,\ldots, b \cdot a$, а кратным $b$ будет каждый $k$-ый элемент данной последовательности. $c = \frac{ka}{b} = \frac{k \cdot \tilde a \cdot p}{\tilde b \cdot p} = \frac{k\tilde a }{\tilde b },$ $k$ обязан равняться $\tilde b $так как $\tilde a $и $\tilde b$ взаимно простые исходя из определения НОД и $c \in N.$ Отсюда $\frac{b}{k} = \frac{\tilde b p}{\tilde b}=p$ — количество кратных элементов последовательности.
  3. Не существует такого $k, k \in (1; b), k \in N$. При котором: $k \cdot a$ кратно $b$. И $a$ не кратно $b.$ Тогда в последовательности $a, 2a, 3a,\dots,b\cdot a$ кратным $b$ будет только последний элемент последовательности. Так как числа взаимно простые, то НОД равен $1.$

Исходя из этих рассуждений решение задачи сводится к нахождению НОД для $a$ и $b.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

e-olymp 8643. Иннолошадь

Задача

В шахматном иннокоролевстве выводят специальные породы инноконей. Порода инноконя задается парой чисел $(x, y), 0 ≤ x ≤ y$. Инноконь перемещается следующим образом: сначала перемещается на $x$ клеток в одну из четырех сторон, затем поворачивает на 90 градусов влево или вправо и перемещается еще на $y$ клеток. Например, обычный шахматный конь — это инноконь породы (1, 2).

Петя и Вася недавно видели инноконя, он прыгнул с поля $A$ на поле $B$. Пете и Васе стало интересно, какой породы был этот инноконь. Помогите им ответить на этот вопрос.

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

Шахматная доска состоит из 8 строк и 8 столбцов. Строки нумеруются числами от 1 до 8, а столбцы буквами от $a$ до $h$. Таким образом, каждое поле задается парой из буквы и цифры. В двух строках ввода содержатся описания полей $A$ и $B$.

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

Выведите два целых числа $x$ и $y$, $(0 ≤ x ≤ y)$, соответствующие породе данного инноконя.

Тесты

Входные данные Выходные данные
a1 b3 1 2
g5 d3 2 3
e1 e1 0 0
d3 d7 0 4
a2 c2 0 2

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

Решение

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

e-olymp

ideone

e-olymp 8531. Делимость на числа

Задача

Задано натуральное число [latex]n.[/latex] Делится ли оно одновременно на [latex] a\ [/latex] и на [latex] b?[/latex]?

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

Три натуральных числа [latex] n, a, b,[/latex] не больших [latex] 10^{9}.[/latex]

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

Выведите «YES» если [latex] n\ [/latex] делится одновременно на [latex] a\ [/latex] и на [latex] b\ [/latex]. Выведите «NO» иначе.

Тесты

Ввод Вывод
1 12 4 6 YES
2 10 5 6 NO
3 1056 22 6 YES
4 98 103 5 NO

Решение

Проверим делимость [latex] n\ [/latex] на [latex] a\ [/latex] и [latex] b.[/latex] Число $n$ делится одновременно на $a$ и $b$ тогда, когда и остаток от деления $n$ на $a$ равен $0$ ( n % a == 0), и остаток от деления $n$ на $b$ равен $0$ ( n % b == 0).

Код с ветвлением

Код без использования ветвления

 

Ссылки

e-olymp 108. Среднее число

Задача

Дано три различных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Вывести среднее из них.

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

Числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] целые и по модулю не превышают 1000.

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

Вывести среднее среди трех чисел.

Тесты

Входные данные Выходные данные
10 4 9 9
2 256 8 8
1 2 3 2

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

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

Я рассмотрел все возможные случаи, а именно 2 на каждую переменную, в которых она может оказаться «средней», удовлетворяя условию. [latex]a[/latex] средняя, если она лежит между [latex]b[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]b[/latex], [latex]b[/latex] если она лежит между [latex]a[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]a[/latex], и [latex]c[/latex] — остальных случаях.

Ссылки

  • Задача на сайте e-olymp
  • Код решения в Ideone

Mif 17.1

Задача. Принадлежит ли точка [latex]\left(x;y \right)[/latex] фигуре на рисунке?

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

Два числа [latex] x[/latex], [latex]y[/latex] — координаты точки.

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

Слово «YES», если точка принадлежит треугольнику и «NO» ,  если не принадлежит.

17_1Тесты

[latex]x[/latex] [latex]y [/latex] Результат
4 -2  NO
2 1 YES
0 3 YES
5 0 NO
0 -1 NO

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

 

Код программы на ideone.com

Решение

Точка будет принадлежать треугольнику только при таких [latex]x[/latex] и [latex]y[/latex], что сумма их модулей не превышает 4. При выполнении условия выводим на экран: «YES». В противном случае — «NO».

Mif 1

Условие задачи

Даны действительные числа [latex] x [/latex], [latex] y [/latex]. Получить [latex]\min (x, y)[/latex].

Код

Код (с тернарной операцией)

Тесты

Входные данные Выходные данные
[latex]x[/latex] [latex]y[/latex] [latex]\min (x, y)[/latex]
4 9 min=4
23 32 min=23
48 125 min=48
842 361 min=361
15 15 min=15

Решение

Вводим данные [latex] x [/latex], [latex] y [/latex]. Затем сравниваем их. Если [latex] x\leq y [/latex], то выводится [latex] x [/latex]. Иначе, то есть,если [latex] y < x [/latex], то выводится [latex] y [/latex].

Ссылки

Условие задачи;

Код программы на Ideone.com;

Mif 17.19

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

file
Тесты:

[latex]x[/latex] [latex]y[/latex] Вывод
-3 0 no
-1.5 2 yes
2 5 yes
3 4 yes
3 3 no

 

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

 

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

В данной программе проверяются допустимые значения [latex]x[/latex] и [latex]y[/latex], при которых точка с данными координатами может принадлежать данной фигуре. Если координаты соблюдают все условия, то программа выводит «yes», т.е. принадлежит . В остальных случаях на экран выводится «no».

Ю2.28

Задача.

Вклад. Банк предлагает 3 вида срочных вкладов: на 3 месяца под [latex]p_{1}[/latex]%, на 6 месяцев под [latex]p_{2}[/latex]% и на год под [latex]p_{3}[/latex]%. Какой из вкладов наиболее выгоден для вкладчика?

Тесты:

[latex]p1[/latex] [latex]p2[/latex] [latex]p3[/latex] Вывод программы
0 0 0 Нет наиболее выгодного вклада из трех
10 10 10 Первый вклад выгоднее
10 10 50 Третий вклад выгоднее
50 10 10 Первый вклад выгоднее
5 20 20 Второй вклад выгоднее

 

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

 

 

 

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

Для решения этой задачи я пользовался следующей формулой: [latex]B = A(1 + \frac{P}{100\%})[/latex], где [latex]B[/latex] — будущая стоимость, [latex]A[/latex] — текущая стоимость, [latex]P[/latex] — процентная ставка за расчетный период, [latex]n[/latex] — количество расчетных периодов. В программе я ее представил в другом виде, так как для сравнения выгодности вкладов одинаковой суммы, саму сумму можно не учитывать.

Код на ideone.com

А58г

 Задача: Дано действительное число  [latex]a[/latex]. Для функции  [latex]f(x)[/latex], график которой представлен на рисунке, вычислить  [latex]f(a)[/latex].
График:
a
Тесты:

a f(a)
1 1
3.2 -0.015371
6 -0.027469
0 0
-1 1
-2.5 2.5
1.5 1
1.8 1
1.001 1

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

Код программы на языке Java:

Ссылка:http://ideone.com/e6UFys

Результат вычисляем по формуле:
[latex]y = ka + b[/latex]
Программа состоит из следующих частей:

  1. Объявление переменных a, y, k, b типа float для хранения данных
  2. Ввод пользователем значений переменной а с помощью scanf
  3. Вычисление и вывод результата по формуле с предварительным сравнением значения а
  4. Завершение программы

Программа сравнивает значение переменной [latex]a[/latex] с значениями переменной [latex]x[/latex] на четырёх диапазонах, и в зависимости от диапазона использует для функции [latex]y = ka + b[/latex] нужные значения [latex]k[/latex] и [latex]b[/latex]. Так вычисляется [latex]f(a)[/latex].
Ссылка на ideone.com : http://ideone.com/N2toyp