e-olymp 7261. Трудный путь

Задача

Вася хорошо выпил и теперь, когда он добрался до своей улицы, он полностью потерял чувство направления. Поскольку он не помнит, с какой стороны его дом, он выбирает направление наобум. Более того, на каждом перекрёстке он с вероятностью $50\%$ продолжает идти вперёд, а иначе разворачивается и идёт назад. Он настолько потерял связь с реальностью, что может даже пройти мимо своего дома и не заметить этого!

Пройдя $n$ кварталов, Вася засыпает прямо на улице. Проснувшись, он задаётся вопросом: какой у него был шанс заснуть рядом с домом? Ведь от перекрёстка, от которого он начал свой путь, до перекрёстка рядом с домом Васи всего $m$ кварталов. Помогите ему.

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

В одной строке содержатся два целых числа $n$ и $m$ [latex](0 \le n , m \le 1000)[/latex].

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

Выведите одно число — вероятность Васи заснуть на перекрёстке рядом со своим домом. Выведите ответ с абсолютной погрешностью не более $10^{-7}$.

Тесты

Входные данные Выходные данные
1 1 0.500000000
10 20 0.000000000
1000 100 0.000169397
16 2 0.174560547
90 44 0.000001273

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

Решение

Обьявим двумерный массив x ,  в котором x[time][y]  равно вероятности оказаться в точке с абсциссой $y$ в момент времени $time$. Пусть изначально (в момент времени $t = 0$) Вася находится в точке с абсциссой $y = n$. Тогда x[0][n] = 1 .  Вычислим x[i][j]  – вероятность того что Вася в момент времени $i$ будет находиться в позиции$j$. Для этого Васе следует находиться в момент времени i – 1 либо в позиции j – 1 , либо в позиции j + 1 . Тогда в момент времени $i$ он сможет попасть из них в позицию $j$ с вероятностью 50%. То есть x[i][j] = (x[i – 1][j – 1] + x[i – 1][j + 1]) / 2 .

Ссылки

e-olymp 407. Обмін

Задача

У різдвяний вечір у віконці стояло три квіточки, зліва на право: герань, крокус та фіалка. Кожен ранок Маша витирала віконце і міняла містами стоявшу праворуч квіточку з центральною кввточкою. А Таня кожен вечір поливала квіточки і міняла місцями ліву та центральну квіточку. Потрібно визначити порядок квітів вночі після того, як пройде $k$ днів.

Вхідні дані

Перший рядок містить кількість тестів $t$ [latex](1 \leq t \leq 12)[/latex]. В кожному з наступних $t$ рядків знаходиться кількість днів $k$ [latex](k \leq 1000)[/latex].

Вихідні дані

Вивести $t$ рядків, що містять по три латинських літери: «G», «C» и «V» (великі літери без пропусків), які описують порядок квітів на вікні по закінченню $k$ днів (зліва направо). Позначення: G – герань, C – крокус, V – фіалка.

Тести

Вхідні дані Вихідні дані
1 2
1
5
VGC
CVG
2 6
1
2
3
4
5
6
VGC
CVG
GCV
VGC
CVG
GCV
3 3
3
6
9
GCV
GCV
GCV

 

Код програми

Розв’язок

Якщо кожного вечора звертати увагу на те, як Маша і Таня міняють місцями квіти, то можна помітити, що їх перестановки періодично повторюються кожні три дні. Цим я скористався для розв’язку задачі. Достатньо лише задати ці три перестановки і брати залишок від ділення на три для визначення конкретної.

Посилання

e-olymp
ideone.com

e-olymp 8357. Точка в многоугольнике

Задача

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

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

В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

Вывести строку «YES», если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

Входные данные Выходные данные
3 0 0
1 0
0 1
1 1
NO
4 3 2
0 0
1 5
5 5
6 0
YES
3 5 6
2 3
8 0
-1 -3
NO
4 -2 3
0 0
5 0
0 6
3 3
NO
5 3 1
9 2
3 0
-2 -4
-4 0
-4 5
YES

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

Решение

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

Ссылки

e-olymp 8532. Печать квадратов и кубов

Задача

Заданы два целых числа $a$ и $b$. Выведите квадраты и кубы всех целых чисел от $a$ до $b$ включительно.

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

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

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

В первой строке выведите квадраты всех целых чисел от $a$ до $b$ включительно по возрастанию. Во второй строке выведите кубы всех целых чисел от $a$ до $b$ включительно по убыванию.

Тесты

 

Входные данные Выходные данные
5 10 25 36 49 64 81 100
1000 729 512 343 216 125
120 123 14400 14641 14884 15129
1860867 1815848 1771561 1728000
9995 10000 99900025 99920016 99940009 99960004 99980001 100000000
1000000000000 999700029999 999400119992 999100269973 998800479936 998500749875
0 3 0 1 4 9
27 8 1 0
25 27 625 676 729
19683 17576 15625

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

Решение

Ввожу $a$ и $b$, создаю цикл вывода по возрастанию квадратов чисел из промежутка, и с новой строки — кубы по убыванию.

Ссылки

Ideone

e-olymp

e-olymp 2. Цифры

Задача

Вычислить количество цифр целого неотрицательного числа $n$.

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

Одно целое неотрицательное число $n$ [latex](0 \ge n \ge 2\cdot10^9)[/latex].

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

Количество цифр в числе $n$.

Тесты

Входные данные Выходные данные
12345 5
1 1
353628 6
5454 4
0 1

Код программы (с использованием условных операторов)

 

Код программы (без использования условных операторов)

Решение

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

Ссылки

E-Olymp

Ideone (с условными операторами)

Ideone (без условных операторов)