e-olymp 3912. Реверс удавов

Задача

На каждом удаве из стаи написано его имя. Имя удава написано маленькими латинскими буквами от головы к хвосту. Все удавы из стаи ползут друг за другом, ведь так легче ползти. Иногда вожак даёт команду «Реверс». В этом случае каждый удав стаи разворачивается, и стая начинает ползти в противоположном направлении. Название стаи можно прочитать, если читать от головы удава, ползущего первым, к хвосту последнего. При этом название может измениться после команды «Реверс». Имена же удавов не меняются.

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

Первая строка содержит одно число $N (1 ≤ N ≤ 100000)$ – количество удавов. В следующих $N$ строках написаны имена удавов в том порядке, в котором они ползут. Имя удава – строчка, содержащая не более $10$ маленьких латинских букв.

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

Выведите единственную строку – название стаи после команды «Реверс».

Тесты

Входные данные Выходные  данные
3
abc
def
ghi
ghidefabc
3
zxcgh
i
db
dbizxcgh
4
mn
kjl
iu
ghj
ghjiukjlmn
8
kdh
jg
lqwoc
kfxvk
iduhx
nsh
s
kjwyv
kjwyvsnshiduhxkfxvklqwocjgkdh

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

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

Записываем каждого удава в одномерный массив  flock типа  string размера N, а затем выводим его, начиная с конца.

Ссылки

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

e-olymp 396. Дождь

Задача

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

Как это выглядит на координатной плоскости

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X$$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y  =  0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$$0$ точки появления капли $(0  < X$$0$ $<  10000)$ и количество отрезков-препятствий $N (0  ≤ N  ≤  100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$$1$,  $y$$1$,  $x$$2$,  $y$$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$,  $x$$1$ $ < x$$2$,  $y$$1$ $≠$ $y$$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные Выходные данные
30 4
25 35 40 30
1 32 20 30
33 22 50 29
18 10 33 19
18
12 5
12 9 13 5
17 8 19 5
13 10 10 7
6 17 4 12
13 4 5 12
 13
40 3
12 30 21 39
41 5 45 70
20 30 25 35
 40
70 6
45 75 598 37
489 48 726 47
673 873 46 36
60 735 373 762
483 73 364 59
462 375 583 457
726

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

 

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

  1. Если $X$ $ ∈ [x$$1$$, x$$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
  2. Тогда мы сравниваем координаты $y$$1$ и $y$$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$$1$ или $x$$2$ координате нашей капли $X$.
  3. Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

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

e-olymp 1503. Вписанные треугольники

Задача

Пример первого теста на графике

На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих $C_{n}^3$ треугольников.

Входные данные
Состоит из не более чем $16$ тестов. Каждый тест начинается двумя целыми числами $n \left(0 ≤ n ≤ 500\right)$ и $r \left(0 < r ≤ 100\right)$. Через $n$ обозначено количество точек, а через $r$ радиус окружности. Центр окружности находится в центре координат. Дальше следуют $n$ строк, каждая из которых содержит действительное число $θ \left(0 ≤ θ < 360 \right)$, которое определяет угол в градусах между точкой и направлением $x$-оси. Например, если $θ$ равно $30$ градусов, то соответствующая точка имеет декартовы координаты $\left(r \cdot \cos(30°), r \cdot \sin(30°) \right)$. Последняя строка содержит $n = r = 0$ и не обрабатывается.

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

Тесты

Входные данные Выходные данные
5 10
10
100
300
310
320
3 20
10
100
300
0 0
286
320
3 5
25
176
243
0 0
25
4 20
30
80
130
330
0 0
822
2 7
30
230
0 0
0

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

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

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции  sort().

В переменную res  изначально заносится площадь, равная площади кругов радиуса $r$,
то есть значение $C_{n}^3 \cdot \pi \cdot r^2 = n(n-1)(n-2)(n-2)\pi \cdot \frac{r^2} {6}$. Значение $\frac{r^2} {2}$ присваивается переменной r2, а sq – площадь одного круга, то есть $\pi \cdot r^2$.

Перебираются пары точек, а затем вычисляется угол.
Если угол меньше, то проходимся по меньшему сегменту, площадь которого равна $\pi r^2-0.5r^2(\alpha-\sin \alpha)$, $\alpha = 2\pi -\alpha$. В ином случае мы проходим по большему сегменту.
В любом случае переменной s  присваивается площадь сегмента, который мы проходим от $P_{i}$ к $P_{j}$ при движении против часовой стрелки.

Количество точек, лежащих на сегменте, равно $n-(j-i+1)$.
Значит, из переменной res необходимо вычесть площадь сегмента s такое количество раз, которому равно количество точек, то есть pts .

Количество точек, которые лежат на сегменте площади s , равно $n-2-  $  pts.
Площадь противоположного сегмента равна разности площади круга и сегмента. Для получения ответа вычитаем площадь противоположного сегмента из переменной res такое количество раз, которое равно значению переменной  pts и выводим полученное значение.

Ссылки

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

e-olymp 6350. Изированная вода

Задача

Изированная вода

В Бердичеве ещё в советские времена продавалась знаменитая изированная вода. Собственно это была обычная газировка на разлив, но продавал её Изя, поэтому и воду все называли изированной. Продавец газировки был человеком не только очень умным и добродушным, но и очень сообразительным. О складе его ума говорит хотя бы тот факт, что у него было $2$ диплома о высшем образовании: он закончил физмат пединститута и мехмат университета, а о сообразительности – то, что имея два диплома, он продавал газировку и довольно успешно. Старожилы утверждают, что попить его газировки прилетали в те времена даже с самой Москвы…

Изя, герой задачи

С постоянными покупателями, и не только с ними, Изя был очень общительным человеком, и иногда, как говорится «под настроение клиента», задавал им свои задачки на сообразительность, которых у него в запасе было великое множество. Одна из подобных его задачек приведена в задаче «Покупка воды». Задав подобную задачку, он ждал от клиента быстрого, сообразительного и, главное, верного ответа на неё, если же ответ запаздывал, или был не верным, Изя всегда говорил что-то типа: «Молодой человек, придёте завтра – Вы сегодня не заслужили на обслуживание». Естественно, это была шутка и клиент всё равно имел возможность приобрести очень вкусную изированную воду.

Перед тем как сформулировать наш вопрос, напомним задачку, упоминаемую выше: «Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет $1$ руб. $20$ коп., а стоимость пустой бутылки – $20$ коп. Сколько бутылок воды можно выпить на $N$ руб., учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды?».

Нас же будет интересовать ответ на следующий вопрос: «А сколько покупателей услышали сегодня от Изи фразу «Приходите завтра!»?».

Входные данные
В первой строке входных данных находится единственное число $N (1 ≤ N ≤ 10^6)$ — количество покупателей, которым Изя задавал упоминаемую в условии задачку.

В последующих $N$ строках задано через пробел $N$ пар чисел, первое из которых — количество денег в кошельке перед началом операции «Покупка ГазВоды», а второе — ответ покупателя.

Все входные данные — целые неотрицательные числа, не превышающие $10^9$.

Выходные данные
Вывести единственное число — количество покупателей, услышавших от продавца ответ «Придёте завтра» и при этом ответили неправильно. Подсчитывать же тех, кто долго думал, не обязательно, за Вас это сделает проверяющая система вердиктом TL (Time Limited).

Тесты

Входные данные Выходные данные
5
2 1
2 2
1 2
1 1
2 1
3
3
45 45
38 37
12 10
2
3
5 4
7 6
3 2
0
2
1280 1280
1900 1899
1
7
1 1
2 2
3 2
6 5
6 6
7 3
2 2
5

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

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

Для решения этой задачи необходимо решить задачу «Покупка воды». Решение очень простое: количество бутылок воды, которое можно выпить на $n$ грн. равно $n — 1$.

Используем это в цикле для проверки на правильность ответа покупателя. Если ответ неправильный, то увеличиваем переменную  j, которая считает количество неправильных ответов, на один, и, после завершения цикла, выводим ее значение.

Ссылки

Код задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 27. Циклические сдвиги

Задача

Циклический сдвиг

Циклический сдвиг

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

Например, если $n = 11$, то в двоичной системе это $1011$$2$, его циклические сдвиги: $0111$$2$, $1110$$2$, $1101$$2$, $1011$$2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110$$2$ $=$ $14$$10$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n \left(1 ≤ n ≤ 2 \cdot 10^9\right)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные Выходные данные
11 14
23 30
256 256
257 384
34132 43664

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

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

  1. Сначала мы находим степень двойки, большую данного числа;
  2. Далее мы циклически сдвигаем влево данное число на один бит и из полученных чисел выбираем наибольшее.

Возможный вариант решения задачи

Возможно избавиться от первого цикла путем нахождения количества двоичных разрядов кратных степени двойки с помощью:
1. взятия логарифма числа по основанию $2$ с последующим округлением до целого;
2. возведение двойки в степень, полученную выше, и увеличенную на единицу.
То есть $2^{\lfloor \log_{2}n \rfloor + 1}$.

Тогда код будет выглядеть так:

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com
Возможное решение задачи на ideone.com

e-olymp 43. Количество участников олимпиады

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью. В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d \left(1 ≤ k, n, m, d ≤ 1000 \right)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$
$n$ $m$ $d$ Выходные данные
2 4 7 3 28
4 5 2 1 20
3 7 5 4 -1
6 6 6 1 -1
2 3 6 4 -1
3 2 5 8 -1

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

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

Пусть $x$ — количество учеников Пифагора. Тогда $\frac{x} {2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\frac{x} {4}$ — ученики, которые изучают природу, а $\frac{x} {7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.
Получили уравнение вида $\frac{x} {2} + \frac{x} {4} + \frac{x} {7} + 3 = x$, в общем виде $\frac{x} {k} + \frac{x} {m} + \frac{x} {n} + d = x$.
Отсюда выходит, что $\frac{1} {k} + \frac{1} {m} + \frac{1} {n} + \frac{d} {x} = 1;$
$\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$
$(mn + kn + km)x + kmnd = kmnx;$
Отсюда получаем формулу $x = \frac{kmnd} {kmn — mn — kn — km}$.
Следовательно, если мы получаем целое число, то секретарь оказался прав, а если число дробное, то секретарь ошибся.

Для того, чтобы проверить, является ли переменная $x$ целым числом или нет, используем функцию  floor()  из встроенной библиотеки  <cmath>.

Помимо этого делаем проверку для суммы чисел $\frac{1} {k}$, $\frac{1} {n}$ и $\frac{1} {m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\frac{q} {k}$, $\frac{q} {n}$ и $\frac{q} {m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

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