e-olymp 7534. Замкнутое сокровище

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

Задача

Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.

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

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

Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков — ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.

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

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n(1 \leqslant n \leqslant 30)$ и $m(1 \leqslant m \leqslant n)$.

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

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 4
3 2
5 1
10 7
5 3
3
1
210
10
2 2
5 3
3 2
10
3
3 6
2 1
7 2
3 1
5 4
3 2
9 2
1
7
1
10
3
9

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

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.
Для нахождения биномиальных коэффициентов воспользуемся треугольником Паскаля, который будем хранить в двумерном массиве.

Ссылки

Условие задачи на e-olymp

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

Треугольник Паскаля на Wikipedia

e-olymp 1325. Васькины дорожки

Задача. Васькины дорожки

Кот Василий узнал, что у соседа Димы, проживающего от него через какое-то количество заборов завелись мыши. Так как в своём хозяйстве всех мышей он уже давно выловил, кот отправляется на охоту за мышами к соседу, пролезая через дыры в ограде. На каждом участке Василий, как любой воспитанный кот, перемещается по уже проложенным там тропинкам. В деревне Старые Васюки, где проживает Василий, всего одна улица и та протянулась вдоль реки, поэтому домики расположены только по одну сторону улицы. Известно, что между любыми соседними участками в заборе ровно одна дыра. Сколькими способами Василий может попасть на участок Димы, если известно, что Дима проживает на участке под номером $k,$ а сам Василий проживает на участке под номером $m$?

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

В единственной строке находятся через пробел сначала количество домов в деревне $n,$ затем номер участка Василия $m,$ номер участка Димы $k,$ а далее $n$ чисел, обозначающее количество тропинок, ведущих либо к дыре в заборе, либо от дыры в заборе, либо между дырами в заборе соседей $i$ и $i+1.$ Все входные данные натуральные числа, не превышающие $10.$

 

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

Единственное число — количество различных способов для Василия попасть на нужный участок для охоты.

Тесты

Ввод Вывод
1 3 2 3 4 5 3 15
2 10 5 7 1 2 3 4 5 6 7 8 9 10 210
3 4 2 1 3 4 7 8 12
4 10 8 8 1 9 6 7 5 3 8 2 4 10 2
5 1 1 1 1 1
6 10 1 10 1 1 1 1 1 1 1 1 1 10 10
7 7 5 3 2 2 2 4 4 4 5 32
8 10 1 10 10 10 10 10 10 10 10 10 10 10 10000000000
7 5 3 2 1 2 3 4 5 6 7 8 9 10 6

Решение

Что бы определить количество различных способов попасть на нужный участок мы должны, сначала, посчитать сколькими способами кот Василий может пересечь (по тропинкам) участок на котором он находится. Затем, для каждого из возможных вариантов пересечения первого участка посчитать сколькими способами Василий может пересечь второй участок и так далее, до заданного. Таким образом общее количество вариантов попасть, для нашего друга, из участка $m$ в участок $k$ является произведением количества вариантов пересечения каждого участка в отдельности.

Прочтём значения $n$, $m$ и $k$. Переменная rez будет хранить результат. В цикле от $1$ до наибольшего номера из участков Димы и Василия, будем проверять достигли ли мы наименьшего номера их участков. По достижении начинаем перемножать количества тропинок ведущих к дыркам в заборе. Мы можем это делать с начиная с любого из участков так как операция умножения коммутативна. Завершив цикл в переменной rez у нас уже будет правильный ответ. Выведем его.

Типа данных  unsigned long хватит по условию данной задачи, так как все числа натуральные, а значит большие $0$. И не превышают $10$, следовательно максимальное значение переменной  rez будет $10^{10}$ что помещается в unsigned long.

Код

Условие задачи

Решение

Код на ideone

e-olymp 8514. Never drink too much!

The task is taken from e-olymp

Task

Mahmoud together with his friends visited Georgia. They would stay in a hotel at Rustavelli. When the cowboys reached the hotel, they hung their hats in the entrance and settled in. The beer bottles on the table could not escape from Mahmoud’s attention when passing through the corridor. At the suggestion of Mahmoud, all the cowboys began drinking. They drank too much, thus none of them was mindful. Then they decided going downtown. On the way out, everyone had a hat on, but they mixed up the hats as they were so drunk.

The man who is able to have on his own hat while he is drunk is considered clever and who is not able to do so is considered stupid.

You are given the number of cowboys — n (including Mahmoud). You should find in how many ways the cowboys may have on the hats so that all of them are stupid. Two ways are considered different if there is at least one cowboy who has a hat in this case and another hat in the other case.

As the answer may become very large, you should output the result modulo 109 + 7.

Input

Given the number of cowboys — n (1 ≤ n ≤ 107).

Output

The answer to the problem as specified above.

Tests

Inputs Outputs
1
1 0
2
4 9
3
9 133349
4
555 335132588
5
10000000 824182295

Code

 

Solution

We have all possible permutations [latex]C_n^0 \cdot n![/latex] , minus one fixed (one of them is not stupid) we get [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)![/latex] but we subtract for minimum fixed pair (two of them are not stupid) we need to add them [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! [/latex] etc.
So the [latex]k[/latex] member is [latex]C_n^k \cdot (n-k)! \cdot (-1)^k[/latex]
Let`s find the attitude of [latex]k[/latex] member to the previous one. It`s [latex]-k -1[/latex]
The last one will be [latex]-1[/latex] it depends on parity of [latex]n[/latex].
First two are the same ( [latex]n![/latex] ) so we skip them, but in this case we need to check if[latex]n[/latex] equals [latex]1[/latex]
And next we make a loop to find the answer by multiplying start value and add it to the answer.
The complexity is [latex]O(n)[/latex]

Links

ideone
e-olymp

e-olymp 1326. В хоккей играют настоящие…

Задача

prb1326 Лесные жители решили провести хоккейный турнир между $N$ командами. Сколькими способами могут быть распределены комплекты золотых, серебряных и бронзовых медалей, если одно призовое место может занять только одна команда?

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

В единственной строке расположено единственное натуральное число $N$, не превышающее 100.

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

Единственное число — искомое количество способов.

Тесты

Ввод Вывод
1 1 1
2 2 2
3 3 6
4 5 60
5 56 166320
6 100 970200

Код

Решение

Чтобы рассчитать количество способов воспользуемся формулой размещения из комбинаторики $A_N^k = \frac{N!}{(N−k)!}$, где $k = 3$, так как существует всего 3 призовых места и следовательно комплекты медалей можно распределить $N$$(N — 1)$$(N — 2)$ способами, при $N >= 3$. При $N < 3$ существует всего $N$ способов распределения, так как команд меньше чем призовых мест.

Ссылки

e-olymp
ideone

e-olymp 1289. Ланч

Задача

Влад хочет взять с собой для ланча пару фруктов. У него есть $a$ различных бананов, $b$ различных яблок и $c$ различных груш. Сколькими способами он может выбрать 2 разных фрукта из имеющихся у него?

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

В одной строке заданы три неотрицательных числа: $a$, $b$, $c$. Все числа не превышают [latex]10^6[/latex].

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

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

 

Тесты

Вход Выход
2 3 4 26
6 2 4 44
0 4 8 32
1052 886 225 1368122
772 621 124 652144

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

Решение

Пусть у нас $1$ банан и $b$ различных яблок. Мы можем взять $1$ банан  и одно яблоко $b$ способами. Так как бананов $a$, по одному яблоку и банану можем взять [latex](a \cdot b)[/latex] способами. Аналогично, так как груш $с$,  то есть [latex](a \cdot с)[/latex] способов взять по одному банану и одну грушу, и [latex](c \cdot b)[/latex] способов взять по одному яблоку и одну грушу. То есть всего [latex](a \cdot b + b \cdot c + c \cdot a) [/latex].

Ссылки

e-olymp

ideone

e-olymp 97. Числа Белла

Задача

Число Белла [latex]B_n[/latex] равно количеству разбиений множества из [latex]n[/latex] элементов на произвольное количество непересекающихся непустых подмножеств. Например, [latex]B_3 = 5[/latex], так как существует [latex]5[/latex] возможных разбиений множества [latex]\lbrace a, b, c\rbrace[/latex]: [latex]\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace[/latex]. Дополнительно считаем, что [latex]B_0 = 1[/latex].
Рассмотрим определитель [latex]D_n[/latex]:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа [latex]p[/latex] найти наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

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

Каждая строка ввода содержит два целых числа [latex]n[/latex] и [latex]p[/latex] ( [latex]\;0\leq\; n,\;p \;\leq\; 10000[/latex] ). Известно, что [latex]p[/latex] – простое.

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

Для каждой пары входных значений [latex]n[/latex] и [latex]p[/latex] в отдельной строке выведите наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Тесты

Входные данные Выходные данные
1 5
3 2
4 2
4 3
10000 3
0
2
5
2
24962375
18 2
465 1009
9998 9221
548 11
134
0
778
14412
1093 1093
1103 1723
3931 617
4868 6113
9534 71
1
0
10635
0
639989
617 17
42 11
0 5
11295
63
0

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

 

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i! $$

Воспользуемся этим свойством для решения данной задачи. Найдём степень числа [latex]p[/latex] в разложении  на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число [latex]k[/latex].

Ссылки

Условия задачи на e-olymp
Код задачи на ideone
Число Белла на wikipedia

e-olymp 239. Треугольники

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные Выходные данные
5
2 -1
3 0
0 4
-3 0
-2 1
6
5
0 0
2 4
6 6
10 34
-42 -48
10
4
0 0
0 1
1 0
1 1
0
8
0 0
2 2
1 1
3 3
0 1
2 1
1 0
1 2
24
5
0 0
0 1
-1 0
-1 -1
3 -3
3

 

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex].  Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

Условие задачи на сайте  E-Olymp

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

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

A1029

Задача о восьми мирных ладьях

Задача о восьми мирных ладьях

Условие

Получить все расстановки   [latex]8[/latex]   ладей на шахматной доске, при которых ни одна ладья не угрожает другой.


Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска   [latex]8 \times 8[/latex].

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

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение   [latex]j[/latex]   по индексу   [latex]i[/latex]   соответствовало строке [  [latex]j[/latex],   в которой находится ладья в   [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел   [latex]1,..,8[/latex].   Как известно, число различных перестановок длины [latex]n[/latex]   —   [latex]P_{n}=n![/latex]. Следовательно, всего существует   [latex]8!=40320[/latex]   различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья


Детали реализации

Для получения перестановок использована функция стандартной библиотеки [latex]next\_permutation()[/latex]

В силу большого объёма выходного файла (5.5 мб) он доступен отдельно, по ссылке: https://www.dropbox.com/s/yyaz7vq08jczsnl/out?dl=0

А1033

Условие

Получить все размещения из [latex]9[/latex] элементов [latex]\left\{1,2, \ldots, 9\right\}[/latex] по [latex]5[/latex] элементов в каждом.

Код на С++

 

Код на Java:

 

Решение

При решении этой задачи мне понадобились 2 источника информации:

Там были приведены алгоритмы генерирования перестановок («Комбинаторные алгоритмы», стр. 27-29) и генерирования сочетаний («Комбинаторика для программистов», стр. 39-41).
Размещения я получал следующим образом:

  • Посчитал кол-во всевозможных размещений по формуле [latex]A^{k}_{n}=\frac{n!}{(n-k)!}=\frac{9!}{4!}=15120[/latex];
  • Заметил, что размещения — это перестановки всех уникальных комбинаций из 5 чисел (т.е сочетаний);
  • Поскольку кол-во перестановок [latex]P_{k}=k![/latex], а кол-во сочетаний — [latex]C_{n}^{k}=\frac{n!}{k!(n-k)!}[/latex], то кол-во размещений [latex]A_{n}^{k}=P_{k}\times{C_{n}^{k}}=\frac{n!k!}{k!(n-k)!}=\frac{n!}{(n-k)!}=15120[/latex];

Таким образом, генерируя вначале сочетание, я генерировал перестановки этого сочетания. В результате вышло 15120 размещений.

e-olimp 4475. Часы

4475. Часы

Постановка задачи

Ученые разработали часы, которые могут налаживаться для отсчета времени на любой планете. Они состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

Во входном потоке содержится количество секунд в минуте [latex]S[/latex], минут в часе [latex]M[/latex], часов в сутках [latex]H[/latex] и число шариков [latex]K[/latex].

Алгоритм решения

  1. Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
  2. Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
  3. Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Реализация:

ideone: http://ideone.com/nz2JlG
Засчитанное решение: http://www.e-olimp.com/solutions/1937971

Примечания

  • Экспериментально выяснено, что только тип long double является достаточно вместительным для избежания переполнения.
  • Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.
  • Модификатор fixed используется для предотвращения вывода чисел в научном формате (с использованием степеней десятки).

А36

Задача: Даны действительные числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]Проверить, выполняются ли неравенства  [latex]a<b<c[/latex].

Тесты:

Ввод Вывод Результат
a b c неравенство                     не выполнено
2 1 3 b<=a<c: нер-во a<b<c                 не выполняется неравенство                     не выполнено
1 3 2 a<=c<=b: нер-во a<b<c                 не выполняется неравенство                     не выполнено
3 1 2 b<=c<=a: нер-во a<b<c                 не выполняется неравенство                     не выполнено
3 2 1 c<=b<=a: нер-во a<b<c                 не выполняется неравенство                     не выполнено
2 3 1 c<=a<b: нер-во a<b<c                 не выполняется неравенство                     не выполнено
1 2 3 нер-во a<b<c справедливо неравенство выполнено

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

Отчет:

После ввода чисел a, b, c программа проверит их соотношения. Ввиду наличия трех сравниваемых чисел имеем 3! = 6 возможных комбинаций чисел, и только одна из них соответствует требованию. Если неравенство [latex]a<b<c[/latex] имеет место быть, то программа сообщит о его выполнении. В противном же случае консоль выдаст ответ о не выполненном неравенстве, предварительно сообщив причину.

Копия кода на сайте Ideone: ideone.com/aYmMJ2