Задача
Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».
Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью. В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.
Входные данные: в одной строке заданы числа $k, n, m, d \left(1 ≤ k, n, m, d ≤ 1000 \right)$.
Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.
Тесты
|
$k$
|
$n$ | $m$ | $d$ | Выходные данные |
| 2 | 4 | 7 | 3 | 28 |
| 4 | 5 | 2 | 1 | 20 |
| 3 | 7 | 5 | 4 | -1 |
| 6 | 6 | 6 | 1 | -1 |
| 2 | 3 | 6 | 4 | -1 |
| 3 | 2 | 5 | 8 | -1 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> #include <cmath> using namespace std; int main(){ float k, n, m, d, s; cin >> k >> n >> m >> d; s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n); if((1/k + 1/n + 1/m >= 1) || (floor(s/k) != s/k || floor(s/n) != s/n || floor(s/m) != s/m) || !(floor(s) == s)){ cout << "-1"; }else{ cout << s; } return 0; } |
Решение задачи
Пусть $x$ — количество учеников Пифагора. Тогда $\frac{x} {2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\frac{x} {4}$ — ученики, которые изучают природу, а $\frac{x} {7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.
Получили уравнение вида $\frac{x} {2} + \frac{x} {4} + \frac{x} {7} + 3 = x$, в общем виде $\frac{x} {k} + \frac{x} {m} + \frac{x} {n} + d = x$.
Отсюда выходит, что $\frac{1} {k} + \frac{1} {m} + \frac{1} {n} + \frac{d} {x} = 1;$
$\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$
$(mn + kn + km)x + kmnd = kmnx;$
Отсюда получаем формулу $x = \frac{kmnd} {kmn — mn — kn — km}$.
Следовательно, если мы получаем целое число, то секретарь оказался прав, а если число дробное, то секретарь ошибся.
Для того, чтобы проверить, является ли переменная $x$ целым числом или нет, используем функцию floor() из встроенной библиотеки <cmath>.
Помимо этого делаем проверку для суммы чисел $\frac{1} {k}$, $\frac{1} {n}$ и $\frac{1} {m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.
Так же делаем проверку, которая определяет, не являются ли числа $\frac{q} {k}$, $\frac{q} {n}$ и $\frac{q} {m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).
Если условие не проходит проверки, то выводится «$-1$».
Ссылки
Условие задачи на e-olymp.com
Решение задачи на ideone.com
Да, я согласен, что задача прошла все тесты. Но прохождение всех тестов не гарантирует правильности решения. Т.е. тесты отсеивают ошибочные решения, но не гарантируют правильности. Наш пример 6 6 6 1 стоило бы добавить к тестам для того, чтобы отсеять еще один тип ошибок в программе.
Тесты, прохождение которых не гарантирует правильности решения, принято называть «слабыми» или «неполными».
Возможно условие будет довольно сложным, но такое случается.
Игорь Евгеньевич, исправил.
Сделайте, пожалуйста, правильные отступы.
По пояснению. Вы пишите «при подстановке в нашу формулу, получается, что в знаменателе мы получаем 0, что невозможно, а значит…» Вы путаете причину и следствие. У Вас четыре категории. Первые три заданы в долях, а четвертая количеством. Если три доли дают 1, то в четвертую не попадает никто. Если же по условию задачи в этой четвертой категории кто-то есть, то получаем противоречие. Ваша задача описать эту ситуацию формулой и запрограммировать.
Если Вы придумали какую-то формулу и она в каком-то случае приводит к делению на 0 или другой некорректной ситуации, то это говорит только о том, что в этой ситуации формула неприменима.
Ну, хорошо. Исправил сам и зачел.
Тем не менее мне некоторые вещи не нравятся, хоть я и не требую их исправления.
Во-первых, термин дробное число» не является однозначно принятым. Дробными иногда называют все рациональные числа, а иногда все действительные не целые, а иногда все рациональные не целые. У Вас всего два случая — целое число и остальное. Можно было и не придумывать название для этого случая.
Во-вторых, Вы используете в программе действительные числа и «кучу» округлений. Можно было бы поступить проще: