Задача

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

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

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

Завдання

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

Вхідні дані

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

Вихідні дані

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

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

Оцінювання

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

$0$ Тести з умови —
$41$ Точнiсть $R$ не бiльш нiж $1$ знак пiсля коми —
$33$ Точнiсть $R$ не бiльш нiж $6$ знаків пiсля коми $0,$ $1$
$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)

#include <iostream>
#include <string> 
using namespace std;
 
unsigned long long GCD (unsigned long long a, unsigned long long b) {
    while (b) {
        a %= b;
        swap (a, b);
    }
    return a;
}
 
int main() {
    string str;
    cin >> str;
    int length = str.length();
    unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;
    for (int i = 0; i < length; i++) {
        if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');
    }
    while (--length > 1) denominator *= 10;
    gcd = GCD (numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
    remainder =  numerator % denominator;
    numerator -= remainder;
    fraction = numerator / denominator;
    cout << denominator << endl;
    for (int i = 1; i <= 5; i++) {
        if (i == fraction) {
            i++;
            cout << denominator - remainder << " ";
            if (fraction != 5) cout << remainder << " ";
        }
        else cout << 0 << " ";
    }
}

#include <iostream>

#include <string>

using namespace std;

unsigned long long GCD (unsigned long long a, unsigned long long b) {

while (b) {

a %= b;

swap (a, b);

}

return a;

}

int main() {

string str;

cin >> str;

int length = str.length();

unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;

for (int i = 0; i < length; i++) {

if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');

}

while (--length > 1) denominator *= 10;

gcd = GCD (numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

for (int i = 1; i <= 5; i++) {

if (i == fraction) {

i++;

cout << denominator - remainder << " ";

if (fraction != 5) cout << remainder << " ";

}

else cout << 0 << " ";

}

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

#include <iostream>
#include <cstring> 
using namespace std;

unsigned long long GCD (unsigned long long a, unsigned long long b) {
    if (b == 0) return a;
    else return GCD (b, a % b);
}

int main() {
    char str[20];
    int length = 0;
    while (cin >> str[length]) length++;
    unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;
    for (int i = 0; i < length; i++) {
        if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');
    }
    while (--length > 1) denominator *= 10;
    gcd = GCD(numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
    remainder =  numerator % denominator;
    numerator -= remainder;
    fraction = numerator / denominator;
    cout << denominator << endl;
    for (int i = 1; i <= 5; i++) {
        if(i == fraction) {
            i++;
            cout << denominator - remainder << " ";
            if(fraction != 5) cout << remainder << " ";
        }
        else cout << 0 << " ";
    }
}

#include <iostream>

#include <cstring>

using namespace std;

unsigned long long GCD (unsigned long long a, unsigned long long b) {

if (b == 0) return a;

else return GCD (b, a % b);

}

int main() {

char str[20];

int length = 0;

while (cin >> str[length]) length++;

unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;

for (int i = 0; i < length; i++) {

if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');

}

while (--length > 1) denominator *= 10;

gcd = GCD(numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

for (int i = 1; i <= 5; i++) {

if(i == fraction) {

i++;

cout << denominator - remainder << " ";

if(fraction != 5) cout << remainder << " ";

}

else cout << 0 << " ";

}

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

Спочатку зазначимо, що для рейтингу з точністю $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)

Related Images:

Задача:

Даны действительные числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] ([latex]a[/latex]≠0). Выяснить, имеет ли уравнение [latex]ax^2 + bx + c = 0[/latex] действительные корни. Если корни имеются, то найти их. В противном случае ответом должно служить сообщение, что корней нет.

Тесты:

Ввод:			Вывод:	Результат
a	b	c
0	ввод не доступен	ввод не доступен	неверный ввод	Нарушено первоначальное условие, дальнейший ввод не доступен
1	-3	2	уравнение имеет два действительных корня:x1=1.00×2=2.00	уравнение обладает двумя действительными корнями, которые были найдены
9	54	81	уравнение имеет один действительный корень:x0=-3.00	уравнение обладает единственным действительным корнем, который был найден
3	11	19	уравнение не имеет действительных корней	корни уравнения отсутствуют
4	21	24	уравнение имеет два действительных корня:x1=-6.73×2=-14.27	уравнение обладает двумя действительными корнями, которые были найдены
-2	-3.7	5	уравнение имеет два действительных корня:x1=5.51×2=-1.81	уравнение обладает двумя действительными корнями, которые были найдены

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

#include <iostream>
#include <math.h>
using namespace std;
int main() {
	double a, b, c, D, d, x0, x1, x2; //Параметры, дискриминант и его корень, возможные корни уравнения
	printf("ax^2+bx+c=0 \n");
	printf("введите параметр 'a': \n");
	scanf("%lf", &a);
	if(a == 0)
	{
		printf("неверный ввод \n"); 
	}
	else
	{
		printf("введите параметр 'b': \n");
		scanf("%lf", &b);
		printf("введите параметр 'c': \n");
		scanf("%lf", &c);
		D=(b*b)-4*(a*c);
		if(D<0)
		{
			printf("уравнение не имеет действительных корней");
		}
		else if(D==0)
		{
			printf("уравнение имеет один действительный корень:' \n");
			x0 = -b/(2*a);
			printf("x=%5.2lf \n", x0);
		}
		else
		{
			printf("уравнение имеет два действительных корня: \n");
			d=sqrt(D);
			x1= (-b + d )/2;
			x2= (-b - d)/2;
			printf("x1=%5.2lf \n",x1);
			printf("x2=%5.2lf \n",x2);
		}
	}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double a, b, c, D, d, x0, x1, x2; //Параметры, дискриминант и его корень, возможные корни уравнения

printf("ax^2+bx+c=0 \n");

printf("введите параметр 'a': \n");

scanf("%lf", &a);

if(a == 0)

{

printf("неверный ввод \n");

}

else

{

printf("введите параметр 'b': \n");

scanf("%lf", &b);

printf("введите параметр 'c': \n");

scanf("%lf", &c);

D=(b*b)-4*(a*c);

if(D<0)

{

printf("уравнение не имеет действительных корней");

}

else if(D==0)

{

printf("уравнение имеет один действительный корень:' \n");

x0 = -b/(2*a);

printf("x=%5.2lf \n", x0);

}

else

{

printf("уравнение имеет два действительных корня: \n");

d=sqrt(D);

x1= (-b + d )/2;

x2= (-b - d)/2;

printf("x1=%5.2lf \n",x1);

printf("x2=%5.2lf \n",x2);

}

return 0;

}

Отчёт:

В случае, если параметр a не равен нулю, программа позволяет ввести последующие параметр b и константу c. После этого программа ищет дискриминант D по формуле [latex]b^2-4ac[/latex]. Если дискриминант меньше нуля, то программа выдаст сообщение об отсутствии действительных корней в уравнении. Если же дискриминант равен нулю, тогда получим сообщение о наличии единственного корня уравнения x0, который будет посчитан по формуле [latex]\frac{-b}{2a}[/latex]. В случае, когда дискриминант больше нуля, программа сообщит, что у уравнения есть два действительных корня, после чего будет посчитан корень от дискриминанта d для удобства нахождения первого корня x1: [latex]\frac{-b+d}{2a}[/latex], а затем второго x2: [latex]\frac{-b-d}{2a}[/latex]. Оба корня будут выведены на экран.

Ссылка на дубликат кода в Ideone: http://ideone.com/ZQv9AS

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: дробь

e-olymp 8367. Таксі

Задача

Завдання

Вхідні дані

Вихідні дані

Оцінювання

Тести

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

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

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

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

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

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

Посилання

Related Images:

А48

Related Images: