e-olymp 1442. Одномерная Кликомания

Задача

«Одномерная Кликомания» — это логическая компьютерная игра. Для нее используется полоска размеров $1 \times N$, разбитая на $N$ квадратов $1 \times 1.$ Каждый из квадратов окрашен в красный или желтый цвет.
За один ход игрок может выбрать любой из квадратов и щелкнуть по нему мышкой. В результате компьютер выделяет на полоске группу максимальной длины, состоящую из стоящих подряд квадратов одинакового цвета и содержащую выделенный квадрат, и удаляет все квадраты из этой группы. При этом все квадраты, находящиеся правее удаленной группы (если они существуют), сдвигаются влево так, чтобы пристыковаться к квадратам, находящимся левее удаленной группы (если они существуют) и сохранить целостность полоски:
prb1442-r

Игрок может удалять группы квадратов любой длины, в том числе, состоящие из одного квадрата. Игра продолжается до тех пор, пока все квадраты не удалены.
В начале игры количество баллов у игрока равно нулю. После каждого его хода количество баллов пересчитывается. Если игрок очередным ходом удалил группу из $L$ квадратов, то вычисляется число  $X = A \cdot L + B$, где $A$ и $B$ — некоторые целочисленные константы. Если число $X$ неотрицательное, то количество баллов игрока увеличивается на $X$, иначе оно уменьшается на $-X$.
Цель игрока — набрать по окочанию игры как можно больше баллов. Напишите программу, оптимально играющую в «Одномерную Кликоманию». Программа должна получать на входе цвета всех квадратов исходной полоски, а также целые числа $A$ и $B$, и возвращать максимальное количество баллов, которое может набрать игрок по окончанию игры.

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

В первой строке задана строка, состоящая из символов $’R’/’Y’$, перечисляющих слева направо цвета всех квадратов исходной полоски. Символ $’R’$ соответствует квадрату красного цвета, а символ $’Y’$ — квадрату желтого цвета.
Во второй и третьей строках соответственно целые числа $A(1 \leq A \leq 1000)$ и $B(-100 \leq B \leq 100)$, задающие константы в формуле начисления очков за каждый сделанный ход.

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

Целое число, равное максимальному количеству очков, которое может набрать игрок по окончанию игры.

Тесты

Входные данные Выходные данные
1 YYYYYYY
73
14
525
2 RYRYRYR
100
-100
300
3 YYYRRR
1
-100
-194
4 YRYYRRRYYYYY
12
34
314

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

Решение

По условию задачи необходимо определить максимальное количество очков которое можно получить в игре. Число $a$ всегда положительное и умножается на количество квадратов удалённых за один ход. В конце игры будут удалены все квадраты, а значит этот вклад в общий счёт игры равен $a \cdot n$, где $n$ — количество квадратиков в игре. Число $b$ может быть как положительным так и отрицательным. В первом случае, нам выгодно, что бы игрок совершил максимальное число ходов, то есть ровно столько, сколько содержится последовательностей из квадратиков одного цвета. Если $b$ меньше нуля, то счёт будет наибольший, если игрок сделает наименьшее количество ходов, а именно избавиться от чередования цветов и за один ход удалит все квадраты, это количество последовательностей пополам, плюс один.
Считаем необходимые данные и выводим ответ в зависимости от положительности $b$.

Ссылки

e-olymp 8382. Пароль

Задача

Назовем пароль криптостойким*, если выполнены $5$ критериев

  1. Пароль содержит строчные латинские буквы
  2. Пароль содержит заглавные латинские буквы
  3. Пароль содержит цифры
  4. Символы: ! » # $ % & ‘ ( ) * +
  5. Длина пароля не менее $8$ символов

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

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

Вводится одна строка, состоящая только из латинских букв и цифр. Количество символов в строке не превышает $100$.

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

Выведите количество критериев криптостойкости, которым удовлетворяет пароль.

Тесты

Входные данные Выходные данные
1 1aA 3
2 AaBbCc12 4
3 AAAaaaAAA 3
4 #Abc23$$$ 5

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

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

 

Решение

Для подсчёта удовлетворённых критериев криптостойкости будем использовать 5 булевских флагов, соответствующих каждому из критериев. Длину пароля определим сразу, а наличие символов определенного типа будем проверять в цикле. Для проверки наличия цифр и латинских букв нижнего и верхнего регистров используем встроенные функции isdigit() , islower()  и isupper() , а для специальных символов напишем функцию isspecial() .

Ссылки

Для string:

Для c-string:

* В условии задачи — «крипто стойким».

e-olymp 5090. На перекрёстке

Задача

Есть таблица $n × n.$ Оживленностью строки или столбца назовем сумму чисел в ней. Нам очень хочется определить число на перекрестке самой оживленной строки и самого неоживленного столбца. Причем, чем выше будет этот перекресток (а среди них – чем левее), тем больше будет вероятность прохождения теста.

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

В первой строке находится число $n (1 \leq n  \leq 100).$ В следующих $n$ строчках задана таблица. Числа в таблице натуральные и не превышают $100000.$

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

Выведите число на перекрестке самой оживленной строки и самого неоживленного столбца.

Тесты

Входные данные Выходные данные
1 2
4 3
2 1
3
2 3
1 1 1
1 1 1
1 1 1
1
3 5
13 15 17 2 9
4 56 8 90 0
4 3 5 7 5
23 4 5 71 4
5 6 7 8 10
0
4 4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1

Код

С помощью одномерного массива

С помощью двумерного массива

Решение

Для решения данной задачи используем двумерный массив размера $n \times n$. С помощью цикла for ищем самую оживленную строку, затем самый неоживленный столбец, и выводим элемент таблицы на их перекрёстке.
Для решения с помощью одномерного массива действуем аналогично, работая с массивом длинны $n^2$, используя следующее соответствие: $x[i][j] \sim x[i \cdot n + j]$

Ссылки

  • С помощью одномерного массива
  • С помощью двумерного массива

e-olymp 8525. Четные отрицательные в матрице

Задача

Задана матрица размера $n \times n.$ Найдите количество и сумму ее четных отрицательных чисел.

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

Первая строка содержит число $n (1 \leq n \leq 100).$ Следующие строки содержат матрицу $n \times n.$ Элементы матрицы по модулю не больше $100.$

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

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

Тесты

Входные данные Выходные данные
1 3
4 -2 5
1 -4 -12
0 1 -3
3 -18
2 2
4 -7
2 9
0 0
3 5
3 4 -5 7 2
1 2 3 4 -2
-2 -4 -6 -8
4 2 -4 0 -1
6 -26
4 4
1 2 3 4
-1 -2 -4 -3
4 -5 -8 -12
-4 -5 -7 0
5 -30

Код

С помощью двумерного массива

Без использования массива

Решение

С помощью массива

Создаем массив.  С помощью цикла for проверяем: если число отрицательное и чётное, то прибавляем его к sum. Выводим количество таких чисел и их сумму.

Без массива

С помощью цикла for проверяем: если число отрицательное и четное, то прибавляем его к  sum.  Выводим количество таких чисел и их сумму.

Ссылки

e-olymp 904. Увеличить на 2

Задача

Задана последовательность целых чисел. Увеличить на $2$ каждый ее неотрицательный элемент.

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

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

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

Вывести в одной строке $n$ чисел: новые значения элементов последовательности в том же порядке, в котором они были заданы.

Тесты

Входные данные Выходные данные
1 4
1 2 3 -4
3 4 5 -4
2 7
7 -3 4 -2 5 0 -1
9 -3 6 -2 7 0 -1
3 5
6 -12 28 -32 -1
8 -12 30 -32 -1
4 3
-2 -3 -4
-2 -3 -4

Код

Решение

Вводим количество элементов последовательности. С помощью цикла for вводим элементы последовательности, в то же время проверяя: если число положительное, увеличиваем его на два, если же отрицательное, то оставляем без изменений,  выводим новые элементы.

Ссылки

e-olymp 6777. Автобус

Задача

Автобус с $n$ пассажирами открывает двери на автобусной остановке. В точности половина пассажиров плюс полпассажира выходит. На следующей остановке снова половина пассажиров плюс полпассажира выходит из автобуса. Так продолжается $k$ остановок. Зная, что на последней остановке автобус стал пустым, и никто не пострадал во время поездки, определите начальное количество людей $n$ в автобусе.

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

Первая строка содержит количество тестов  $t$. Каждый тест содержит в отдельной строке количество остановок $k(1 \leq k \leq 30).$

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

Для каждого теста вывести в отдельной строке начальное количество пассажиров.

Тесты

Входные данные Выходные данные
1 2
1
3
1
7
2 3
0
15
12
0
32767
4095
3 7
5
8
10
19
4
1
9
31
255
1023
524287
15
1
511
4 4
23
17
2
8
8388607
131071
3
255

Код

Решение

Число пассажиров обязано быть нечётным, так как если бы оно было чётным, то какого-то пассажира пришлось бы резать пополам, что противоречит условию.
На последней остановке должен выйти всего один пассажир, потому что обязательно из автобуса выйдет пол пассажира и половина от всех едущих, и при этом автобус опустеет.
Значит:
$$\frac{x}{2} + 0.5 = x$$
$$\frac{x}{2} = x — 0.5$$
$$x = 2x — 1$$
$$x = 1,$$
где $x$ — число пассажиров в автобусе.
Тогда на предпоследней остановке было:
$$x = x_0 + \frac{x}{2} + 0.5$$
$$\frac{x}{2} = x_0 + 0.5$$
$$x = 2(x_0 + 0.5) = 2x_0 + 1,$$
где $x_0$ — число пассажиров оставшихся в автобусе. Значит $x = 3$
И так далее. А значит на $k$-ой остановке перед выходом пассажиров было:
$x = 2\cdot \left(2\cdot\left(2\cdot\left( \cdots 2\cdot\left(0\right) + 1\right) + \ldots +1\right) + 1\right) + 1$ или $x = 2^n \cdot 0 + 2^{n-1} + \ldots + 2 + 1$
Свернём по формуле суммы геометрической прогрессии, где $b = 1$ и $q = 2.$
[latex]S_k = \frac{b\left(q^k -1\right)}{q-1} = 2^{k} — 1.[/latex]

Ссылки

e-olymp 8534. Хлопці на ім’я Валя

Задача

У літньому таборі $n$ дітей. Серед будь-яких $L$ дітей є хоча б одна дівчинка. Серед будь-яких $v$ дітей є дитина на ім’я Валя (це ім’я можуть мати і хлопчик, і дівчинка). Напишіть програму, що визначає умову наявності в таборі хоча б одного Валентина.

Вхідні дані

$100≤n≤200$, $40≤L≤140$, $20≤v≤70$. Вхідні дані ввести зі стандартного пристрою введення в один рядок, розділяючи значення пропусками.

Вихідні дані

На стандартний пристрій виведення вивести $1$, якщо відповідь на питання умови стверджувальне. Інакше вивести $0$.

Тесты

Входные данные Выходные данные
110 80 27 1
100 70 30 1
70 50 30 0
85 35 20 1
90 50 50

0

Код програми

Решение

Так як серед $v$ дітей точно знайдеться Валя, то нам необхідно, щоб $n — v + 1$ було додатним. Іншими словами, дітей було більше, ніж достатня для Валь їх кількість. Але так як Валею може бути ще й дівчинка, необхідно, щоб ця різниця була більшою, ніж $l$. Таким чином, завжди знайдеться Валя з інших $v$ дітей, хоча б один з яких не увійшов в $l$. Звідси і формула: $n>v+ l-1$ або  $n> = l + v$.

e-olymp

ideone

 

 

e-olymp 7401. Друзья Степана

Задача

Степан вернулся с международной олимпиады школьников по программированию (ИОИ) и привез с собой $n$ разноцветных камней в качестве сувениров. Степан вовсе не жадный мальчик, поэтому решил поделиться камнями со своими друзьями. Каждому другу Степан отдал ровно один камень. Оказалось, что у самого Степана остался тоже только один камень. Определите, сколько же у него друзей.

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

Одно число $n$ (1 ≤ $n$ ≤ 100).

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

Выведите одно число — количество друзей Степана.

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

Степан привёз 2 камня, один из которых остался у него. Значит, второй камень Степан отдал своему единственному другу.

Тесты

Входные данные Выходные данные
2 1
3 2
6 5
50 49
100 99

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

Решение

Известно, что Степан разделил камни между своими друзьями таким образом, что каждому из друзей досталось по 1 камню, и 1 камень остался. Значит количество камней при делении на количество друзей равно единице с единицей в остатке, из чего следует, что количество друзей разнится от количества камней на единицу, то есть — равно $n-1$.

Ссылки

e-olymp

https://ideone.com