e-olymp 972. Сортировка времени

Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

Тесты

Входные данные Выходные данные
1 [latex]\begin{matrix}
4 & & \\
10 &20 &30 \\
7 &30 &00 \\
23&59 &59 \\
13&30 &30
\end{matrix}[/latex]
[latex]\begin{matrix}
7 & 30 &00 \\
10&20 &30 \\
13&30 &30 \\
23& 59 & 59
\end{matrix}[/latex]
2 $\begin{matrix}
6\\
12 &55 &59 \\
8 &33 &34 \\
6 &56 &46 \\
10 &23 &52 \\
3 &20 &00 \\
19 &31 &0\\
10&23&52
\end{matrix}$
$\begin{matrix}
3 &20 &0 \\
6 &56 &46 \\
8 &33 &34 \\
10 &23 &52 \\
12 &55 &59 \\
19 &31 &0
\end{matrix}$

Решение

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

Ссылки

e-olymp
ideone

e-olymp 8367. Таксі

Задача

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

Проте Аліна — дівчинка відповідальна, вона бажає поїхати із найдосвідченішим таксистом, тобто з тим, який вже здійснив найбільшу кількість перевезень. Але ось невдача — додаток не показує кількість перевезень, здійснених водієм. Єдина інформація, якою володіє Аліна — рейтинг водія.

Нагадаємо, що по завершенню кожного перевезення пасажир виставляє водієві оцінку — ціле число від $1$ до $5$ включно. Рейтинг таксиста $R$ рахується як середнє арифметичне усіх отриманих ним оцінок.

Завдання

Допоможіть Аліні – напишіть програму, яка визначить мінімально можливу кількість перевезень, які мав здійснити таксист щоб отримати рейтинг рівно $R$ (без округлень).

Вхідні дані

В єдиному рядку вхідного файлу знаходиться дійсне число $R$ $\left(1 \leqslant R \leqslant 5 \right)$ — рейтинг водія з точністю не більш ніж $18$ знаків після десяткової крапки.

Вихідні дані

В першому рядку вихідного файлу виведіть єдине натуральне число — відповідь на задачу, або $-1,$ якщо заданий рейтинг отримати неможливо.

Якщо рейтинг отримати можливо, у другому рядку необхідно вивести $5$ цілих невід’ємних чисел — кількість оцінок $1,$ $2,$ $3,$ $4$ і $5$ відповідно, отриманих водієм. У разі коли існує декілька варіантів оцінок, які призводять до оптимальної відповіді, дозволяється вивести будь-який з них.

Оцінювання

Пiдзадача. Бали. Додатковi обмеження. Необхідні підзадачі.

  1. $0$ Тести з умови —
  2. $41$ Точнiсть $R$ не бiльш нiж $1$ знак пiсля коми —
  3. $33$ Точнiсть $R$ не бiльш нiж $6$ знаків пiсля коми $0,$ $1$
  4. $26$ Точнiсть $R$ не бiльш нiж $18$ знаків пiсля коми $0,$ $1,$ $2$

Тести

# Вхідні дані Вихідні дані
1 3.0009 10000
0 0 9991 9 0
2 2.0805216 312500
0 287337 25163 0 0
3 4.999999999999999998 500000000000000000
0 0 0 1 499999999999999999
4 1.123581321345589144 125000000000000000
109552334831801357 15447665168198643 0 0 0
5 3.141592653585793236 250000000000000000
0 0 214601836603551691 35398163396448309 0

Код (cтроки string)

Код (cтроки c-string)

 

Розв’язок задачі

Спочатку зазначимо, що для рейтингу з точністю $k$ знаків після десяткової коми оптимальна відповідь завжди $\leqslant 10^k$. Розглянемо це на прикладі. Нехай ми маємо рейтинг $3.xxx,$ де $xxx$ — $3$ будь-які цифри. Припустимо, що таксист отримав $10^3=1000$ оцінок $3.$ Тоді його рейтинг буде дорівнювати $\frac{3\cdot1000}{1000}=3.000,$ тобто рівно $3.$ Тепер спробуємо замінити одну оцінку $3$ на $4.$ Тоді його рейтинг дорівнюватиме $\frac{3\cdot 999+4\cdot 1}{999+1}=\frac{3001}{1000}.$ Тобто замінивши одну трійку на четвірку ми збільшили рейтинг на $\frac{1}{1000}.$ Таким чином якщо поступово змінювати усі $3$ на $4$ ми зможемо отримати будь-який рейтинг від $3.000$ до $4.000$ з трьома знаками після коми, а отже і заданий рейтинг $3.xxx.$

Підзадача $1$:

Виходячи з вищезазначеного відповідь $\leqslant 10.$ Тоді ЇЇ можна отримати просто перебравши усі можливі комбінації оцінок $5$-ма вкладеними циклами.

Підзадача $2$:

Доведемо, що оптимальну відповідь завжди можна отримати тільки за допомогою оцінок двох сусідніх типів $a$ та $\left(a+1\right),$ або одного типу (якщо рейтинг цілий). Припустимо, що існує оптимальна відповідь, у якій НЕ сусідні оцінки $x$ та $y,$ $x<y.$ У випадку, якщо $y-x=3,$ ми можемо замінити їх на $x+1$ та $y-1.$ Якщо $y-x=2$ або $y-x=4,$ можна замінити їх на дві оцінки по $x+1$ або $x+2$ відповідно. Ці дії жодним чином не впливають ні на суму, ні на кількість оцінок, а тому не впливають і на середнє арифметичне. Таким чином, будь-який набір оцінок можна звести до набору оцінок з щонайбільше двох типів. Очевидно, що ці два типи — рейтинг округлений вниз та вгору.

Тоді розв’язання полягає у тому щоб перебрати кількість оцінок першого типу, порахувати скільки потрібно оцінок другого типу, аби отримати заданий рейтинг і перевірити, чи кількість оцінок другого типу ціла (тобто такий розподіл оцінок можливий). Нехай рейтинг рівня $R,$ покладемо $a=\lfloor R\rfloor,$ кількість оцінок типу $a$ дорівнює $x,$ а кількість оцінок типу $a+1$ (якщо вони необхідні) дорівнює $y.$ Тоді, $x\cdot a+y\cdot\left(a+1\right)=R\cdot x+R\cdot y.$ З цього, щоб отримати точну відповідь, потрібно виконувати операції у цілих числах або у $64$-бітних числах з плавоючою комою.

Підзадача $3$:

Представимо рейтинг $R$ у вигляді звичайного дробу, домноживши чисельник та знаменник на $10^{18}$. Виходячи з визначення середнього арифметичного, знаменник цього дробу $10^{18}$ — кількість отриманих оцінок, а чисельник $\left( R \cdot 10^{18} \right)$ — їх сума. Якщо цей дріб можна скоротити, це зменшить кількість оцінок, тому що знаменник (тобто кількість оцінок) зменшиться, а відношення чисельника до знаменника (тобто рейтинг) не зміниться. Отже, чисельник і знаменник потрібно поділити на їх НСД. Припустимо, що після скорочення ми отримали дріб $\frac{a}{b}.$ Очевидно, що отримане у знаменнику число $\left( b \right)$ і є оптимальною відповіддю, адже дріб нескоротний і зменшити знаменник не вдасться. Тепер потрібно довести, що ця відповідь завжди досяжна, тобто існує набір з $b$ оцінок від $1$ до $5$, сума яких дорівнює $a.$

Доведення цього факту аналогічне доведенню у підзадачі $2.$ Зауважимо, що завжди $b \leqslant a \leqslant 5b,$ бо рейтинг за умовою від $1$ до $5$. Тепер припустимо, що усі оцінки дорівнюють $1.$ Тоді чисельник дорівнюватиме $1 \cdot b,$ тобто $b.$ Тепер змінемо будь-яку оцінку $\left( m \neq 5 \right)$ на $m+1.$ Тоді чисельник збільшиться на $1,$ а знаменник залишиться рівним $b.$ Поступово здійснюючи такі заміни, можемо припустити «пройти» через усі значення від $b$ до $5b,$ зокрема і через $a,$ яке нам потрібно отримати.

Аби відновити самі оцінки, згадаємо доведений у другій підзадачі факт про те, що оптимальну відповідь завжди можна отримати з оцінок $\lfloor R\rfloor$ та $\lceil R\rceil.$ Якщо б усі оцінки дорівнювали $\lfloor R\rfloor,$ чисельник був би $b \cdot \lfloor R\rfloor .$ Але чисельник дорівнює $a \geqslant b \cdot \lfloor R\rfloor ,$ тому кількість оцінок $\lceil R\rceil$ як раз дорівнює залишку, тобто $a-b \cdot \lfloor R\rfloor .$ Решта оцінок – оцінки $\lfloor R\rfloor .$ Також зауважимо, що через недостатню точність зберігання чисел з плаваючою комою у пам’яті комп’ютера, необхідно зчитувати рейтинг у вигляді рядка і конвертувати одразу у ціле число.

Посилання

Умова на e-olymp
Код (cтроки string)
Код (cтроки c-string)

e-olymp 8655. Простая сумма

Даны три целых числа x, m и n. Вычислите $(1 + x + x^2 + \ldots + x^m) (mod\quad n)$.

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

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

Первая строка содержит количество тестов. Каждая следующая строка содержит три целых числа $x, m$ и $n (1 \le x, m, n \le 10^{16})$.

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

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

Тесты

Входные данные Выходные данные
1 1000 1 10000 1001
1 999999999999999 999999999999999 13 8
1 99999999999999 99999999999999 23 8
1 3 2 5 3

Алгоритм

Для решения этой задачи можно использовать следующий алгоритм. Сумму данной последовательности будем считать рекурсивно. Базой рекурсии является случай когда степень $m = 0$. Также есть два случая:

  1. Количество членов последовательности четно (а следовательно степень $m$ нечетная), тогда заметим что $(1 + x + x^2 + \ldots + x^m)$ можно представить как $(1 + x + x^2 \ldots +x^{\frac{m}{2}}) + x^{\frac{m+1}{2}} \cdot (1 + x + x^2 + \ldots + x^{\frac{m}{2}}) = $ $= (1 + x + x^2 + \ldots + x^{\frac{m}{2}}) \cdot (1 + x^{\frac{m+1}{2}})$
  2. Количество членов последовательности нечетно (степень $m$ четная), тогда от последовательности $(1 + x + x^2 + \ldots + x^m)$ можно отделить последний член $x^m$ и тогда ситуация будет сведена к первому случаю.

Для возведения $x$ в степень будем использовать алгоритм быстрого возведения в степень, а результат брать по модулю $m$.

Код на ideone
Задача на e-olymp

e-olymp-751. Клад

Условие

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним«. Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений ([latex]1[/latex] – север, [latex]2[/latex] – северо-восток, [latex]3[/latex]– восток, [latex]4[/latex] – юго-восток, [latex]5[/latex] – юг, [latex]6[/latex] – юго-запад, [latex]7[/latex] – запад, [latex]8[/latex] – северо-запад) (см. рис). Длина шага в любом направлении равна 1. Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).

prb751

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

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

Первая строка входного файла содержит число [latex]N[/latex] – число указаний $(1 ≤ N≤ 40)$. Последующие [latex]N[/latex] строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.

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

В выходной файл выведите координаты [latex]X[/latex] и [latex]Y[/latex] точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось [latex]Ox[/latex] направлена на восток, а ось [latex]Oy[/latex] – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с точностью [latex]10^{-3}[/latex].

Тесты

Ввод Вывод
1 6
1 3
3 1
1 1
3 3
5 2
7 1
3.000 2.000
2 1
8 10
-7.071 7.071

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

Решение

Как видно из рисунка направление 1 совпадает с осью [latex]y[/latex], а 3 — с осью [latex]x[/latex]. Допустим, направление — переменная [latex]dir[/latex], а шаг-[latex]z[/latex]. Тогда, для направления 1 можно записать $y=z\cdot\cos((45^0)\cdot(dir — 1))$ , $x=z\cdot\sin((45^0)\cdot(dir-1)) $. Выражение $\cos((45^0)\cdot(1-1))=\cos(0^0)=1$ , то есть для 1 направления [latex]y=z[/latex], а выражение $\sin((45^0)\cdot(dir-1))=\sin((45^0)\cdot(1-1))=0 $. Следовательно, для направления 1 координаты [latex]y[/latex] и [latex]x[/latex] принимают значения: [latex]y=z[/latex], а [latex]x=0[/latex] .Рассмотрите значения приведенных выражений для всех направлений и увидим, что для всех направлений можно применить данные выражения для вычисления координат. А это позволяет сократить код программы.

Ссылки

e-olymp 4752.  Кинотеатр

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

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

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

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

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

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

Тесты

Входные данные Вывод программы
3 3 3
3 2 2
231 543 3

Continue reading

e-olymp 1501. Конусное расстояние

Задача

Конус расположен в трехмерном пространстве так, что его основание радиуса [latex] r [/latex] лежит в плоскости [latex] z = 0 [/latex] с центром в [latex] (0,0,0) [/latex]. Вершина конуса расположена в [latex] (0, 0, h) [/latex]. На его поверхности заданы две точки в конусных координатах. Конусной координатой точки называется пара чисел [latex] (d, A) [/latex], где [latex] d [/latex] — расстояние от вершины конуса до точки [latex] p [/latex], а [latex] A (A < 360) [/latex] — угол в градусах между плоскостью [latex] y = 0 [/latex] и плоскостью, проходящей через точки [latex] (0,0,0), (0,0,h) [/latex] и [latex] p [/latex], считая против часовой стрелки от направления оси [latex] x [/latex].

На поверхности конуса заданы две точки [latex] p1 = (d1, A1) [/latex] и [latex] p2 = (d2, A2) [/latex]. Найти кратчайшее расстояние между [latex] p1 [/latex] и [latex] p2 [/latex], измеряемое по поверхности конуса.

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

Каждая строка является отдельным тестом и содержит 6 действительных чисел: [latex] r, h, d1, A1, d2 [/latex] и [latex] A2 [/latex].

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

Для каждого теста в отдельной строке вывести кратчайшее расстояние между точками [latex] p1 [/latex] и [latex] p2 [/latex] по поверхности конуса. Расстояние выводить с 2 десятичными знаками.

Тесты

Ввод Вывод
 1

 3.0 4.0 2.0 0.0 4.0 0.0

 2.00

 2

 3.0 4.0 2.0 90.0 4.0 0.0

 3.26
 3

 6.0 8.0 2.14 75.2 9.58 114.3

 7.66
 4

 3.0 4.0 5.0 0.0 5.0 90.0

 4.54

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

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

Инициализирую все нужные переменные и через поток ввода считываю все исходные данные. Затем нахожу образующую l по теореме Пифагора и угол между плоскостями — alpha . k1 это часть, которую занимает угол alpha от основания конуса. k2 — коэффициент пропорциональности между окружностями радиусами r и l . fi — величина угла развертки конуса, а beta — угол между прямыми на которых лежат точки, данные в условии. Далее находим искомое расстояние по теореме косинусов.

Ссылки

Коды Грея

Задача

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
[latex]0[/latex]
[latex]1[/latex]
Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
[latex]00[/latex]
[latex]01[/latex]
[latex]11[/latex]
[latex]10[/latex]
Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
[latex]000[/latex]
[latex]001[/latex]
[latex]011[/latex]
[latex]010[/latex]
[latex]110[/latex]
[latex]111[/latex]
[latex]101[/latex]
[latex]100[/latex]
При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

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

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Тесты

Входные данные Выходные данные
1 3 2
14 9
5 7
12 10
2 0 0
72 108
265 397
4781 7163
50642 42811
3 1010234 581415
96721758 119682801
640214927 893162568
2456987013 3679188807
51027963402 60418988303
1000000000000000000 797398725282889728

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

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

Объявляем переменную [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) типа unsigned long int для считывания чисел из входного потока. Цикл while работает столько раз, сколько чисел во входном потоке (по условию задачи их количество [latex]\le 10^5[/latex]). В цикле вычисляется Код Грея числа [latex]k[/latex] путем побитовой операции «исключающее ИЛИ», применимого к [latex]k[/latex] и к результату побитового сдвига [latex]k[/latex] на [latex]1[/latex] бит вправо ([latex]k \gg 1[/latex]).
Ссылка на алгоритм ниже.

Ссылки

Code Gray: theory
e-olymp
ideone

e-olymp 8377. Стойкое число


Задача

По числу $x$ определим $p(x)$ как произведение его цифр. Рассмотрим последовательность $x$, $p(x)$, $p(p(x))$… Стойкостью $x$ назовем индекс (начиная с $0$) первого однозначного числа в этой последовательности. Например, из $99$ получим последовательность $99$, $9 · 9 = 81$, $8 ·  1 = 8$. Стойкость числа $99$ равна $2$. По заданному числу $n$ определите его стойкость.

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

Каждая строка содержит одно целое число $n (0 \leqslant n \leqslant 2 · 10^9)$.

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

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

Решение

Опишем функцию $p(x)$, которая будет считать произведение цифр числа $x$. Для этого в функции заводим дополнительную переменную, например, $t$, равную единице, которую будем циклично домножать на остаток от деления $x$ на $10$, а $x$ уменьшать на разряд до тех пор, пока $x$ не попадёт в разряд единиц. Получившееся значение $t$ снова передаём в функцию $p(x)$ в качестве аргумента. Продолжим действия, описанные выше, до тех пор пока значение $t$ не будет находиться в разряде единиц. Индекс последней итерации функции и будет искомой стойкостью числа $x$.

Тесты

Ввод Вывод
1 99
268
6
2
4
0
2 796
1
100
5
0
1
3 2356951
53
9892
2
2
3

Код

Код для считывания строками

Код c-string

 

Ссылки

Continue reading

e-olymp 971. Задача Иосифа Флавия

Задача Иосифа Флавия

Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из $41$ иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.

В нашем варианте мы начнем с того, что выстроим в круг $N$ человек, пронумерованных числами от $1$ до $N$, и будем исключать каждого $k$-ого до тех пор, пока не уцелеет только один человек. (Например, если $N=10$, $k=3$, то сначала умрет $3$-й, потом $6$-й, затем $9$-й, затем $2$-й, затем $7$-й, потом $1$-й, потом $8$-й, за ним — $5$-й, и потом $10$-й. Таким образом, уцелеет $4$-й.)

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

Во входном файле даны натуральные числа $N$ и $k$. $1≤N≤500$, $1≤k≤100$.

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

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

Тесты

Ввод Вывод
1 10 3 4
2 500 100 480
3 50 10 36
4 1 1 1
5 41 3 31

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

Решение

Все люди в кругу пронумерованы от $0$ до $N-1$, началом будет person = 0 . Нужно исключить $person+(k-1)$ человека. Начальная позиция следующего раунда $person + k$. Но если номер исключенного человека $N-1$, следующая начальная позиция $N$, что выходит за пределы круга, по-этому мы берем остаток от деления на количество оставшихся в живых людей: (person + k) % count .

Таким образом круг уменьшается на одного человека, при этом номер уцелевшего в круге размера $N$ равняется номеру в получившемся круге размера $N-1$. Предполагаем, что это работает и в обратную сторону: берем круг размером  count = 2, высчитываем, кто будет в начальной позиции в следующем раунде. count в таком случае количество не убитых, а живых, и оно увеличивается с каждым раундом до $N$. В конце прибавляем $1$, потому что в начале все значения были сдвинуты.

Ссылки

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

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

e-olymp 6264. Энергетический магнат

Задача

Маленький Вася играет в новую компьютерную игру — пошаговую стратегию «Энергетический магнат».

Правила игры достаточно просты:

    • Доска содержит [latex]n[/latex] слотов, расположенных в линию.
    • Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
    • Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
    • После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.

Пример №1.

Вася уже знает все типы электростанций, которые он сможет построить на каждом шаге игры. Он хочет знать, какое максимальное количество очков он сможет получить в игре. Можете ли Вы ему помочь?

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

Первая строка содержит число [latex]n \left(1\leqslant n\leqslant 1000 \right)[/latex] — количество слотов на доске. Вторая строка содержит строку [latex]s[/latex]. [latex]i[/latex]-ый символ строки равен [latex]1[/latex], если Вы можете построить однослотовую электростанцию в [latex]i[/latex]-ом раунде, и символ [latex]2[/latex], если Вы можете построить двуслотовую электростанцию в [latex]i[/latex]-ом раунде. Количество раундов в игре не превосходит [latex]100000[/latex].

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

Вывести одно число — наибольшее количество очков, которое можно достичь.

Тесты

Вхлодные данные Выходные данные
1 3

21121

10
2 2

12

2
3 2

211

4

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

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

Будем увеличивать num на 1, если встречается двуслотовая электростанция. Если нет свободных слотов [latex]temp — c\lt0[/latex] и [latex]num\geqslant1[/latex], то вместо двуслотовой ставим станцию, которая в этом ходе должна быть [latex]temp += (2 — c)[/latex] и вычитаем одно очко. В итоге смотрим, если двуслотовых электростанций нет [latex]num\gt 1[/latex], то считаем однослотовые: [latex]n — temp[/latex], а если они есть, то: [latex]n — temp — num[/latex].

Ссылки

  • Условие задачи на e-olymp
  • Код программы ideone

e-olymp 1215. Камень, ножницы или бумага?

Задача

Условие

Камень > ножницы > бумага > камень > ножницы > ...

Камень > ножницы > бумага > камень > ножницы > …


В игру Камень, Ножницы, Бумага играют двое. Каждый игрок на счет три одновременно выбирает один из трех предметов. Игра длится определенное наперед установленное количество раундов. Игрок, который выиграет большую часть раундов, объявляется победителем. По заданному количеству раундов и их исходам следует определить победителя.
Следующие правила описывают правила победы:

  • Камень всегда побеждает Ножницы (Камень раздавливает Ножницы)
  • Ножницы всегда побеждают Бумагу (Ножницы режут Бумагу)
  • Бумага всегда бьет Камень (Бумага покрывает Камень)

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

Первая строка содержит количество тестов $t$ ($0 < t < 1000$). Первая строка каждого теста содержит количество раундов $n$ ($0 < n < 100$), сыгранных в игру Камень, Ножницы, Бумага. Каждая из следующих $n$ строк содержит одну из заглавных букв $R$ (Камень), $P$ (Бумага) или $S$ (Ножницы), пробел и снова заглавную букву $R$, $P$ или $S$. Первая буква обозначает выбор первого игрока, вторая буква — выбор второго игрока.

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

Для каждого теста в отдельной строке вывести имя победителя (Player 1 или Player 2). Если игра заканчивается вничью, вывести TIE.

Тесты

Входные данные Выходные данные
1 3
2
R P
S R
3
P P
R S
S R
1
P R
Player 2
TIE
Player 1
2 1
1
S P
Player 1
3 2
3
S P
P S
R R
2
P R
S R
TIE
TIE
4 4
1
R P
2
R P
S R
3
R P
S R
P S
4
P R
R S
P S
S S
Player 2
Player 2
Player 2
Player 1

Решение

Для решения задачи необходимо сравнить выбор первого и второго игрока в каждом раунде каждого теста.
Подсчитываем количество побед для игроков во всех раундах теста. Получаем победителя для каждого теста.
В данной реализации используем вложенные циклы. Вводим переменную $t$ — количество тестов. Затем задаём цикл, в котором вводим новую переменную $n$ — количество раундов для каждого теста. Этот цикл будет работать, пока не проверим все тесты. Так же заводим два счётчика sum1 и sum2, которые будут подсчитывать победы первого и второго игрока. Задаём ещё один цикл, который будет выполняться, пока не проверим все раунды для каждого теста. В нём вводим выбор первого игрока и выбор второго игрока. Сравниваем данные значения согласно правилам победы, которые описаны в условии. В случае победы первого игрока увеличиваем переменную sum1 на единицу, в случае победы второго — sum2 на единицу. После завершения циклов сравниваем переменные sum1 и sum2, выводим соответствующие результаты.

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

Ссылки

e-olymp 908. Те, что делятся на 6

Задача: Те, что делятся на 6

Для [latex]N[/latex] целых чисел определить сумму и количество положительных чисел, которые делятся на 6 без остатка.

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

В первой строке задано количество чисел [latex]N[/latex]$\left(1 \leq N \leq 100\right)$, в следующей строке через пробел заданы сами числа, значения которых по модулю не превышают $10000$.

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

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

Тесты

Ввод Вывод

3

12 15 18

2 30
4

-10 -15 42 -24

1 42
2

6 0

1 6
3

-6 -12 -32

0 0

Решение

Заводим 2 переменные: сумму и количество. Каждый раз, когда мы читаем число, проверяем положительно ли оно и делится ли на 6 (Обычно желательно сначала проверять наимение вероятное условие, т.к. программа реже будет лишний раз проверять второе условие и, как следствие, сделает меньше действий, но в этой задачи это особой роли не играет из-за малого ввода), если оба условия выполняются, добавляем к счетчику 1, а к сумме введенное число. По окончанию ввода выводим сумму и количество через пробел.

Ссылки

e-olymp 3766. Тысячелетие

Задача

Мудрый король решил ввести новый календарь. «Завтра будет первый день календаря, то есть день [latex]1[/latex] месяца [latex]1[/latex] года [latex]1[/latex]. Каждый год состоит из [latex]10[/latex] месяцев, с [latex]1[/latex] по [latex]10[/latex], и начинается с большого месяца. Обычный год начинается с большого месяца, за которым следует малый месяц, затем большой месяц и так далее один за другим. То есть первый месяц большой, второй малый, третий большой, …, десятый, он же последний, малый. Большой месяц состоит из [latex]20[/latex] дней, а малый месяц из [latex]19[/latex] дней. Однако годы, кратные трем, то есть год [latex]3[/latex], год [latex]6[/latex], год [latex]9[/latex] и так далее, состоит из [latex]10[/latex] больших месяцев и ни одного малого.»

Много времени прошло со дня введения календаря, и для празднования дня тысячелетия [latex]([/latex]год [latex]1000[/latex], месяц [latex]1[/latex], день [latex]1[/latex][latex])[/latex] решено было организовать королевскую лотерею, победителями которой станут те, кто прожил столько же дней, какое число выпадет в лотерее. Напишите программу, которая поможет людям вычислить количество дней от их дня рождения до дня тысячелетия.

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

Входные данные имеют следующий формат:

n
Y1 M1 D1
Y2 M2 D2

Yn Mn Dn

Первая строка задает количество тестов [latex]n, \left ( n \leq 100 \right )[/latex]. Далее следуют n тестов, каждый из которых представляет собой одну строку с тремя натуральными числами [latex]Y_{i}\left ( Y_{i}< 1000 \right ), M_{i} \left ( M_{i}< 10 \right )[/latex] и [latex]D_{i} \left ( D_{i}\leq 20 \right )[/latex], задающих соответственно год, месяц и день рождения некоторого человека в нотации королевского календаря.

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

Для каждой даты рождения следует вывести в отдельной строке количество дней, прошедших со дня рождения (включительно) до дня тысячелетия (не включительно).

Тесты

Ввод Вывод
1 2
1 1 1
344 3 1
196470
128976
2 3
696 5 1
182 9 5
998 8 7
59710
160715
252
3 2
344 2 19
696 4 19
128977
59712
4 1
999 10 20
1

Код

Решение

Запишем большой месяц (20 дней) и малый месяц (19 дней) соответственно в константы bigMonth и smallMonth, а также большой год (200 дней) и малый год (195 дней) соответственно в bigYear и smallYear. Затем проходим по циклу for n раз. Проверяем, если год, в котором родился человек,  кратен 3, считаем количество полных прожитых человеком месяцев (каждый месяц — 30 дней) первого после рождения года, а также дни месяца, в котором он родился. В противном случае ( else) прибавляем дни каждого полного месяца, проверяя, большой он, и малый. Затем добавляем дни первого прожитого человеком месяца, так же учитывая его длительность. После этого проходим по циклу for, начальной итерацией которого является ( Y + 1), потому что дни года рождения мы посчитали ранее. За каждый год, номер которого кратен 3, добавляем 200 дней, а за некратный — 195. В конце выводим количество полученных дней +1, так как должны посчитать их количество включительно с днем рождения.

Решение

Снова проходим по циклу for n раз. Однако, теперь считаем дни без помощи циклов. В переменную lifeYears записываем годы жизни -1 , так как дни года рождения мы посчитаем далее. Затем, в if проверяем, находится ли количество прожитых лет в диапазоне от 1 до 3. Если да, то в переменную multipleThree записываем 1 — количество лет, кратных трем, то есть 999 год. В else multipleThree приравниваем к lifeYears, деленую на 3. В следующем if проверяем, больше ли количество лет трех. Если да, прибавляем 5 дней за больший 999 год. Затем, в переменную notMultipleThree записываем количество лет, не кратных трем. В следующей строке прибавляем ко дням жизни годы, умноженные на соответствующие им количества в каждом. После, в if проверяем, кратен ли год рождения 3. Если да, Находим количество полных прожитых месяцев, и умножаем его на bigMonth. Далее, находим дни, прожитые в месяц рождения. В else проверяем, родился ли человек в нечетном месяце. Если да, добавляем к дням количество дней, вычисляющееся по формуле, записанной в коде, если нет — аналогично. В конце, выводим количество дней +1, так как должны посчитать их количество включительно с днем рождения.

Ссылки

e-olymp 4192. Олимпиада

Задача

На олимпиаду по информатике прибыло $n$ команд, каждая из которых состоит из $a_i$ мальчиков и $b_i$ девочек $(1 ≤ i ≤ n)$. Для проживания имеются одинаковые комнаты по $m$ мест в каждой. Какое наименшее количество комнат достаточно для размещения участников олимпиады, если мальчиков с девочками селить вместе запрещено?

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

Первая строка содержит числа $n$ и $m$. Каждая следующая из $n$ строк содержит пару чисел $a_i$ , $b_i$ $(1 ≤ i ≤ n)$. Все числовые значения целые неотрицательные и не превышают $100$.

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

Вывести наименьшее необходимое количество комнат.

Тесты

Входные данные Выходные данные
1 2 3
2 1
3 2
3
2 3 5
5 8
2 3
6 1
6
3 2 2
1 1
1 3
3
4 4 2
1 3
5 1
2 7
3 1
12
5 7 2
5 6
3 4
2 5
1 3
9 3
8 7
6 4
33

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

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

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

Ссылки

e-olymp 75. Пираты и монеты

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

 #  ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
 1  5 25  3
 2  3 24  4
 3  4 38  5
 4  5 55  6
 5  6 75  7

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

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

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

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

e-olymp 8373. Перевернутая башня

Задача

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

prb8373.gif

Эту башню решили оборудовать лифтом — и вот задача: нужно научится по номеру комнаты определять, на каком этаже она находится и какая она по счету слева на этом этаже.

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

Номер комнаты [latex]n (1\leqslant n \leqslant 2\cdot10^{9})[/latex].

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 1 1
2 5 3 2
3 35 11 5
4 31 11 1
5 2000000000 1650964 845

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

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

Для решения данной задачи я воспользовался циклом while, в котором на каждой итерации, проверял будет ли значение выражения n-rooms_per_floor больше нуля. Если оно было больше нуля, то из n вычиталось количество комнат на текущем этаже, а если меньше нуля, то цикл прерывался. После изменений, выполненных в цикле, переменная n соответствует номеру комнату на этаже, а переменная floor, которая равна количеству вычитаний из n, соответствует этажу, на котором находится комната. К ней в конце необходимо добавить единицу, так как в этой переменной не учитывается «текущий» этаж.

Ссылки

e-olymp 1519. Коды Грея

Задача

Френк Грей. Bell Lab 1930

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

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

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

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

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

Входные данные Выходные данные
1 14
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
0
1
0
1
3
2
0
1
3
2
6
7
5
4
2 3
2 1
1 2
3 3
1
1
2
3 1
0 0
0
4 2
2 3
1 3
2
1

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

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone

e-olymp 8653. Прибавить вычесть и умножить

Задача

Пусть x — переменная, изначально равная 0. Промоделируйте выполнение следующих операций над ней:

  • add a: прибавить значение a к x;
  • subtract a: вычесть значение a из x;
  • multiply a: умножить x на a;

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

Каждая строка содержит операцию и значение. Промоделируйте все операции. Значение переменной x при выполнении каждой операции не превышает по модулю $10^9$.

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

Выведите результирующее значение переменной x.

Тесты

Ввод Вывод
1 add 2
subtract 5
subtract 1
multiply -3
12
2 subtract 5
multiply -5
add 5
30
3 add 6
add 543
multiply 23
12627
4 multiply 45678
add 3
3
5 subtract 58
add 38
multiply -1
add 100
120

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

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

Инициализировав основную переменную x, через поток ввода считываем все действия, которые неоходимо применить по отношению к переменной. Во время этого ничего не выводим, дожидаясь, пока поток команд закончится. Заметим, что процесс ввода может длиться сколько угодно долго. В конце концов, на выходе получаем уже «преобразованный» x — результат проделанных дейсвтий.

Ссылки

e-olymp 273. Возведение в степень

Задача

По трем натуральным числам [latex]a[/latex], [latex]b[/latex] и [latex]m[/latex] вычислить значение [latex]a^b\mod m[/latex].

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

Три натуральных числа [latex]a[/latex], [latex]b[/latex], [latex]m[/latex] [latex]\left(1 \leqslant a, m \leqslant 10^9, 2 \leqslant b \leqslant 10^7\right)[/latex].

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

Вывести [latex]a^b\mod m[/latex].

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 2 100 1
2 100 2 1000000 10000
3 2 3 50 8
4 9 2 1 0
5 9 2 25 6

Код с циклом

Код с ветвлением

Решение

Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.

Запустить код с циклом (ideone) можно здесь
Запустить код с ветвлением (ideone) можно здесь
Задача на E-olymp

e-olymp 7228. Сколько шестерок?

Задача

Сколько раз будет использована цифра $6$, если записать подряд последовательные натуральные числа от $a$ до $b$?

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

Два натуральных числа $a$ и $b$ [latex](1 ≤ a, b ≤ 10^9)[/latex].

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

Количество цифр $6$ в последовательных натуральных числах от $a$ до $b$.

Тесты

Ввод Вывод
1 5 256 46
2 56 110 16
3 27357 43577 5852
4 368325775 56 296285528
5 584937543 984938576 420000314

Код

Решение

Выписав и посчитав количества шестёрок от $1$ до [latex]10, 100, 1000, …[/latex] Мы обнаружим закономерность, они равны [latex]1, 20, 300, …[/latex] соответственно.

Доказательство проведем по математической индукции.

  1. Для [latex]n = 1[/latex] [latex]countSix(10^1) = 1[/latex].
  2. Для [latex]n ≤ k[/latex] $countSix(10^{k}) = k \cdot 10^{k-1}$
  3. Для [latex]n = k+1[/latex] $countSix(10^{k+1}) = k\cdot10^{k-1}\cdot10+10^k = (k+1)\cdot10^k$

Разберёмся, как их нужно комбинировать. Для этого в цикле пройдёмся по каждой из цифр числа и полученные результаты просуммируем. В ответ мы выдадим разность количества шестерок без внешней границы.

Ссылки