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 910. Среднее арифметическое положительных

Задача

Задана последовательность вещественных чисел. Найти среднее арифметическое положительных чисел.

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

В первой строке задано количество чисел $n$ ($0 < n ≤ 100$). В следующей строке заданы $n$ действительных чисел, значения которых не превосходят по модулю $100$.

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

Вывести среднее арифметическое положительных чисел с двумя десятичными знаками. В случае отсутствия положительных чисел вывести сообщение $Not$ $Found$.

Тесты

Входные данные Выходные данные
3
5.2 -2 4
4.60
3
-5.2 -2 -4
Not Found
5
16 -78 56 1 -3
24.33
1
17.33
17.33
1
-17.33
Not Found

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

Решение

В начале читаем из потока общее количество чисел n . Затем с помощью цикла остальные числа, одновременно проверяя положительные ли они. Если число положительное, то прибавляем его к общей сумме и увеличиваем счетчик k++ . В конце s!=0 означает, что в потоке есть хотя бы одно положительное число — тогда мы высчитываем и выводим $\frac{s}{k}$ с двумя знаками после запятой. В противном случае — $Not$ $Found$.

Код программы (Тернарная операция)

Решение

Для вывода ответа с помощью тернарной операции необходимо, чтобы выходные данные были одного типа. Используем метод to_string, предварительно округлив $s$ до двух знаков после запятой. Так как при использовании метода  double переводится с шестью знаками после запятой, то используем erase, чтобы удалить лишние четыре.

Ссылки

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

Код программы на IdeOne (1)

Код программы на IdeOne (2)

 

КМ.72

Задача из журнала «Квант» №72

Условие:
Пусть p — произвольное вещественное число. Найдите все такие x, что сумма кубических корней из чисел 1 – x и 1 + x равна p.

Тесты:

Входные данные Выходные данные
1 0.6 No solutions
2 1.4 x1 = -0.997217
x2 = 0.997217
3 2 x=0
4 1.79 x1 = -0.814516
x2 = 0.814516

Код

Решение:
Рассмотрев условие, приходим к такому уравнению [latex] \sqrt[3]{\left(1+x \right)}+\sqrt[3]{\left(1-x \right)}=p [/latex] , где p — параметр, который будет задаваться на входе.Ответы для р будут существовать на промежутке [latex] \left[\sqrt[3]{2}; 2\right] [/latex] . Если р не входит в промежуток, то выводим «нет решений». Если р=2, то оба корня совпадут, по этому выводим один «х=0». Для остальных случаев ответом будет два корня.

Ссылки:
Решение на ideone http://ideone.com/A8DXC9
Условие http://www.kvant.info/zkm_1971.htm
Решение wolfram http://www.wolframalpha.com/input/?i=(1%2Bx)%5E(1%2F3)+%2B+(1-x)%5E(1%2F3)+%3D+p