e-olymp 1099. Говорящий Галчонок

Задача взята с сайта e-olymp

Задача

«Ура-a-a! Заработало!» – радостно воскликнул Матроскин, услышав первую произнесенную Галчонком фразу.

Э.Успенский «Трое из Простоквашино»

Как Вам всем известно, Галчонок из мультфильма «Трое из Простоквашино» при стуке в дверь всегда спрашивал: «Кто там?». Статистика, как и вся математика, наука точная и она утверждает, что Галчонок мог запоминать как отдельные слова, так и целые предложения, только в том случае, если слово было произнесено не менее $n$ раз, а предложение – не менее чем $m$ раз $\left(n\leqslant m\right)$.

Ваша задача по заданному тексту определить количество слов и предложений, которые точно запомнил Галчонок.

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

В первой строке находится два натуральных числа $n$ и $m$ $\left(n , m \leqslant 100 \right)$. Во второй строке находится сам текст. Текст написан грамматически верно.

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

Два числа через пробел: сначала количество запомненных слов $s$, а потом количество запомненных предложений $p$.

Тесты

N,M ТЕКСТ ВЫХОДНЫЕ ДАННЫЕ
2,4 Blessed are the peacemakers,
for they will be called children of God.
0 0
2,3 Kto tam? It is Pechkin. Kto tam? My name is Fedor. Kto tam? Pechkin! 4 1
1,1 Hey you! out there on the road
Always doing what you’re told
Can you help me
Hey you! out there beyond the wall
Breaking bottles in the hall
Can you help me
Hey you! don’t tell me there’s no hope at all
Together we stand, divided we fall
33 3
2,2 Yes! No. Yes Yes! No Yes no no. No yes No No. 2 1
1,1 Workers of the world, unite! 5 1

Решение

Для решения данной задачи найдем все слова и все предложения в тексте. Слова будем считать одинаковыми, если они совпадают без знаков препинания в нижнем регистре они совпадают. Одинаковыми предложениями, соответственно, будем считать предложения, что совпадают без пробелов и знаков препинания. Увеличивая значения ассоциативных массивов, соответствующих предложению или слову на 1, увеличим на 1 значение b, если слова совпали больше чем $n$ раз и значение a, если предложения совпали больше чем $m$ раз.

Код задачи на ideone

Засчитанное решение на e-olymp

e-olymp 7504. Три прямоугольника

Задача взята с сайта e-olymp

Задача

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

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

Одно число — количество закрашенных клеток

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

В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 0 1 1
1 1 2 2
0 0 2 2
4
2 2 -2 -2 2
-1 -1 1 1
40 40 41 41
17
3 -1 2 2 -1
1 0 4 2
1 0 3 6
21
4 -100 -100 -99 -99
100 100 99 99
-100 -100 100 100
40000
5 3 0 4 1
1 0 3 3
1 0 3 3
7

Решение

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

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

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

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

Решение. Многомерные массивы

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

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

e-olymp 914. Модуль максимального

Задача взята с сайта e-olymp

Задача

Задана послідовність дійсних чисел. Обчислимо їх модулі. Знайдіть максимальне значення серед цих модулей.

Вхідні дані

У першому рядку задано кількість елементів $n\left(n  \leqslant 100  \right)$ у послідовності. У наступному рядку задано $n$ дійсних чисел — елементи послідовності, значення яких не первищують за модулем 100.

Вихідні дані

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

Тести

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 -1 1 1.00
2 3
-1.1 1.2 -1.3
1.30
3 5
5.16 0 -7.18 3 4.99
7.18
4 4
-75.111 7.5 -5.1 75.110
75.11
5 10
-1 -2 -3 -4 -5 -6 -7 -8 -9 1
9.00

Решение

Задача сходиться до пошуку максимального елемента послідовності. Зрозуміло, що найменше можливе значення модуля числа — 0. Тому, считуючи дані зі вхідного потоку будемо порівнювати їх зі змінною, що  дорівнює 0. Якщо значення модуля числа більше за змінну — надаємо змінній значення модуля числа. Таким чином після завершення вхідного потоку змінна буде дорівнювати найбільшому числу послідовності за модулем.

  • Зараховане рішення на e-olymp
  • Код задачі на ideone

e-olymp 8654. Целочисленное умножение

Задача взята с сайта e-olymp

Задача

Даны три целых числа $a, b, c.$ Вычислить значение выражения $a \cdot b \text{ mod } c.$

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

Три целых положительных числа $a, b, c \left( a, b, c < 2^{63} \right).$

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

Вывести значение выражения $ a \cdot b \text{ mod } c.$

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 3 2 0
2 11 3 2 1
3 123456789
987654321
17
0
4 5000400000023
23000400400500
100000000070707
68238553233174
5 10000018585
10000000000005
101020304050607080
85850050000993845

Решение

Для решения задачи напишем рекурсивную функцию умножения, основанную на том, что [latex]\displaystyle a\cdot b =\displaystyle[/latex][latex] \begin{cases}\left(a+a\right)\cdot\frac{b}{2} &\text{} b\equiv_{2} 0 \\a+a\cdot\left(b-1\right) &  \text{} b \not \equiv_{2} 0\ \end{cases}.[/latex] Поскольку максимальное значение из условия задачи в два раза меньше максимального числа из 64-битных беззнаковых чисел и[latex]\left(a\cdot b\right)\text{ mod } c =\left(a\text{ mod } с \cdot b\text { mod }c\right)\text{ mod }c,[/latex] мы можем на каждом шагу применять к $a$ и $b$  операцию остатка от деления на $c$ , за счет чего произведение никогда не будет превосходить $2^{64}-1$.

  • Засчитанное решение на e-olymp
  • Код на ideone

e-olymp 2060 Сказка о яблоке

Задача взята с сайта e-olymp

Задача

Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен $n$ заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно». То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

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

Количество заборов $n (1 \leqslant n \leqslant 62)$ в саду.

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 4
2 3 22
3 30 50331646
4 60 3458764513820540926
5 62 13835058055282163710

Решение

Циклы

Последовательность необходимых количеств яблок задается формулой $x_{n+1}=2 \cdot (x_{n}+1);x_{1}=1.$ Мы можем поочередно вычислять элементы последовательности через цикл.

Линейное решение

Преобразуем исходное выражение для $x_{n+1}=2 \cdot x_{n}+2.$ Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для $x_{n+m}=2^{m}x_n+2^{m-1}x_n+\cdots+2.$ Можно увидеть, что $x_{n+m}$ содержит слагаемое $2^{m}x$, а так же сумму слагаемых вида $\displaystyle \sum_{i=1}^{m}2^i \displaystyle.$ Если учесть, что $x_{1}=1$, то $\displaystyle x_n=2^{n}+ \sum_{i=1}^{n}2^i \displaystyle=2^{n+1}+2^n-2=2^{n}\cdot(2+1) -2.$ Следовательно формула $n$-го члена — [latex]x_n=3\cdot 2^n-2.[/latex]

Решения на ideone