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 1215. Камень, ножницы или бумага?

Задача

Условие

Камень > ножницы > бумага > камень > ножницы > ...

Камень > ножницы > бумага > камень > ножницы > …


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

  • Камень всегда побеждает Ножницы (Камень раздавливает Ножницы)
  • Ножницы всегда побеждают Бумагу (Ножницы режут Бумагу)
  • Бумага всегда бьет Камень (Бумага покрывает Камень)

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

Первая строка содержит количество тестов $t$ ($0 < t < 1000$). Первая строка каждого теста содержит количество раундов $n$ ($0 < n < 100$), сыгранных в игру Камень, Ножницы, Бумага. Каждая из следующих $n$ строк содержит одну из заглавных букв $R$ (Камень), $P$ (Бумага) или $S$ (Ножницы), пробел и снова заглавную букву $R$, $P$ или $S$. Первая буква обозначает выбор первого игрока, вторая буква — выбор второго игрока.

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

Для каждого теста в отдельной строке вывести имя победителя (Player 1 или Player 2). Если игра заканчивается вничью, вывести TIE.

Тесты

Входные данные Выходные данные
1 3
2
R P
S R
3
P P
R S
S R
1
P R
Player 2
TIE
Player 1
2 1
1
S P
Player 1
3 2
3
S P
P S
R R
2
P R
S R
TIE
TIE
4 4
1
R P
2
R P
S R
3
R P
S R
P S
4
P R
R S
P S
S S
Player 2
Player 2
Player 2
Player 1

Решение

Для решения задачи необходимо сравнить выбор первого и второго игрока в каждом раунде каждого теста.
Подсчитываем количество побед для игроков во всех раундах теста. Получаем победителя для каждого теста.
В данной реализации используем вложенные циклы. Вводим переменную $t$ — количество тестов. Затем задаём цикл, в котором вводим новую переменную $n$ — количество раундов для каждого теста. Этот цикл будет работать, пока не проверим все тесты. Так же заводим два счётчика sum1 и sum2, которые будут подсчитывать победы первого и второго игрока. Задаём ещё один цикл, который будет выполняться, пока не проверим все раунды для каждого теста. В нём вводим выбор первого игрока и выбор второго игрока. Сравниваем данные значения согласно правилам победы, которые описаны в условии. В случае победы первого игрока увеличиваем переменную sum1 на единицу, в случае победы второго — sum2 на единицу. После завершения циклов сравниваем переменные sum1 и sum2, выводим соответствующие результаты.

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

Ссылки

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 8653. Прибавить вычесть и умножить

Задача

Пусть x — переменная, изначально равная 0. Промоделируйте выполнение следующих операций над ней:

  • add a: прибавить значение a к x;
  • subtract a: вычесть значение a из x;
  • multiply a: умножить x на a;

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

Каждая строка содержит операцию и значение. Промоделируйте все операции. Значение переменной x при выполнении каждой операции не превышает по модулю $10^9$.

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

Выведите результирующее значение переменной x.

Тесты

Ввод Вывод
1 add 2
subtract 5
subtract 1
multiply -3
12
2 subtract 5
multiply -5
add 5
30
3 add 6
add 543
multiply 23
12627
4 multiply 45678
add 3
3
5 subtract 58
add 38
multiply -1
add 100
120

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

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

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

Ссылки

e-olymp 8533. Числа с разными цифрами

Задача

Выведите все четырехзначные числа от $a$ до $b$, содержащие разные цифры.

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

Два целых числа $a$ и $b$ ([latex]1000 \le a \le b \le 9999[/latex]).

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

Выведите в одной строке все числа от $a$ до $b$ с разными цифрами.

Тесты

 Входные данные Выходные данные
 2000 2015  2013 2014 2015
 9875 9999  9875 9876
 1000 1234  1234
 3612 3612  3612
 8800 8888  Standart output is empty
 1000 1000  Standart output is empty

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

 

Решение

Для каждого числа из заданного промежутка [latex][a;b][/latex] выделяем его цифры и сравниваем их между собой. Искомые числа будут состоять из неравных между собой цифр.

Ссылки

Ideone

e-olymp

e-olymp 1119. Пирамида из символов

Задача

Вася хочет напечатать на принтере пирамиду из какого-то символа высоты $h$. Напишите программу, которая поможет ему в этом, не забывая, что программа должна быть «экономически выгодной», т.е печатать наименьшее количество символов.

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

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

В одной строке задан сначала символ, при помощи которого должна быть напечатана пирамида, а затем через пробел натуральное число, задающее высоту пирамиды $h (h ≤ 50)$.

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

В первой сроке выведите общее количество напечатанных «печатных» символов а ниже саму пирамиду.

Тесты

Входные данные Выходные данные
A 3 12
A
AAA
AAAAA
M 9 117
M
MMM
MMMMM
MMMMMMM
MMMMMMMMM
MMMMMMMMMMM
MMMMMMMMMMMMM
MMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMM

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

Решение

Для решения данной задачи потребуется выводить пробелы для отступов в каждой строке и заданный символ в виде пирамиды. Для этого напишем цикл, который будет перебирать строки. Для нахождения количества символов в пирамиде используем формулу: по арифметической прогрессии, где первый элемент это $1$, а каждый следующий больше предыдущего на $2$. В вывод пишется столько пробелов, сколько нужно для правильного расположения (с каждой следующей строчкой пробелов на $1$ меньше, в первой строке $b$ пробелов).

Ссылки

e-olymp
Ideone

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 1611. Реверс подстроки

Задача

Дана строка $s$, в которой выделили подстроку, состоящую из символов с $i$-го по $j$-ый включительно (символы строки $s$ нумеруются с единицы) и поменяли местами $i$-ый символ с $j%-ым, %(i + 1)%-ый с %(j — 1)$-ым и так далее (конвертировали подстроку). Выведите строку $s$ после внесенных изменений.

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

В первой строке содержится строка $s$ длиной не более $1000$ символов, во второй — два числа $i$ и $j$ $\left (i \leqslant j \right).$

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

Выведите строку $s$ после внесенных изменений.

Тесты

Входные данные Выходные данные
$zbbg \\ 2 \; 3$ $zbbg$
$gaqipkajibk \\ 5 \; 6$ $gaqikpajibk$
$helloworld \\ 5 \; 7 $ $helloworld$
$rkdobnjfyy \\ 6 \; 3 $ $rkdobnjfyy$

Код программы (c-string)

Решение задачи (c-string)

Для решения задачи объявим массив, в котором будем хранить входную строку. Далее в цикле обращаем подстроку и выводим строку $s$ после внесенных изменений.

Код программы (string)

Решение задачи (string)

Для решения задачи вводим строку $s$. Далее в цикле конвертируем подстроку и выводим строку $s$ после внесенных изменений.

Ссылки

Условие задачи на e-olymp
Код решения на ideone(c-string)
Код решения на ideone(string)

e-olymp 1477. Наибольшее среднее

Задача

На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n.$ Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1.$ После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.

Определите порядок действий, который приводит к максимально возможному числу в конце.

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

В первой строке записано целое число $n$ $(1 \leqslant n \leqslant 10^5).$ Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000.$

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

Выведите $n — 1$ строку, в каждой из которых должны быть записаны по два целых числа, определяющие номера тех чисел, которые выбираются на соответствующем шаге.

Тесты

Входные данные Выходные данные
$3$
$7\;2\;4$
$2\;3$
$1\;4$
$4$
$6\;2\;7\;1$
$2\;4$
$1\;5$
$3\;6$
$4$
$12\;4\;7\;2$
$2\;4$
$3\;5$
$1\;6$
$5$
$234\;2\;5\;54\;5$
$2\;3$
$5\;6$
$4\;7$
$1\;8$

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

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

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

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 1607. Число в обратном порядке

Задача

Запишите целое неотрицательное число $n$ в обратном порядке.

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

Одно целое неотрицательное $64$-х разрядное число.

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

Выведите число в обратном порядке.

Тесты

Входные данные Выходные данные
$1234$ $4321$
$100$ $001$
$34567$ $76543$
$10983743$ $34738901$
$98352374234$ $43247325389$

Код программы(String)

Решение задачи(String)

Для решения задачи вводим строку. Узнаем ее длину с помощью функции s.length(), затем циклом выводим строку в обратном порядке. Задача решена.

Код программы(C-string)

Решение задачи(C-string)

Для решения задачи вводим входные данные в массив x[64]. При вводе считаем какое количество символов заполнилось в массив. Затем от этого числа( length) начинаем цикл, который выводит массив в обратном порядке. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(String)
Код решения на ideone.com(C-string)

e-olymp 922. Сдвинь элементы

Условие задачи
Задан массив целых чисел длины [latex]n[/latex]. Сдвинуть элементы массива вправо циклически на [latex]1[/latex] шаг.

Входные данные
В первой строке задано количество элементов массива [latex]n[/latex] [latex](n ≤ 100)[/latex]. Во второй строке заданы сами элементы массива, значение каждого из которых по модулю не превышает [latex]100[/latex].

Выходные данные
В одной строке вывести [latex]n[/latex] чисел — новые значения элементов массива.

Continue reading

e-olymp 7809. Утренняя зарядка

Задача


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

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

Единственная строка входного файла содержит последовательность чисел, записанных через пробел, означающие цвет футболки. Цвет — число в диапазоне от [latex]0[/latex] до [latex]9[/latex]. Всего в строке не более, чем [latex]10^6[/latex] чисел.

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

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

Тесты

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

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

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

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 842. Разложение на простые множители

Условие задачи
Вывести представление целого числа [latex] n [/latex] в виде произведения простых чисел.

Входные данные
Единственное число [latex] n [/latex] [latex] (2 ≤ n ≤ 2^{31} — 1). [/latex]

Выходные данные
Вывести список простых множителей в порядке не убывания, разделённых знаком [latex] «*» [/latex] .
Continue reading

A321. Циклы

Задача

Даны натуральные числа [latex]m, n[/latex], действительные числа [latex] a_1, a_2, …, a_{mn}[/latex]. Вычислить [latex]a_1 a_2 … a_m + a_{m+1} a_{m+2} … a_{2m} + a_{(n – 1) m + 1} a_{(n – 1) m + 2} … a_{nm}[/latex].

Входные данные:
[latex]m, n[/latex] — натуральные числа.
В следующей строке содержится [latex]m \cdot n[/latex] действительных чисел.

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

Тесты:

Входные данные Выходные данные
1
3 3
1.1342 2.82113 3.5431 4.541 5.081 6.761 7.35781 8.456451 9.6461 10.9321
767.5218903911781
2
5 4
23.2312 -13.016 0.78 1.0 73.48992
-3441.32150 39.94 87.04 0.1 -0.02
94.094 23.0001 0.005 -2.0 -1.0
0.004 -1.01 42.0 0.454 1.5
6593.637250058031
3
3 2
1.1 2.2 3.3 4.4 5.5 6.6
327.426

Код на языке C++:

Код на языке Java:

Решение задачи:
Заведём массив для хранения чисел. Пользуясь циклом [latex]for[/latex] от [latex]1[/latex] до [latex]m \cdot n[/latex], по мере заполнения массива будем считать слагаемые нашего выражения. Для этого воспользуемся оператором [latex] if [/latex], проверяя индексы элементов массива.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 321