Задача
Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».
Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью.
В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.
Входные данные: в одной строке заданы числа $k, n, m, d (1 ≤ k, n, m, d ≤ 1000)$.
Выходные данные: вывести количество участников олимпиады $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 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); float k = in.nextInt(), n = in.nextInt(), m = in.nextInt(), d = in.nextInt(), s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n); if ((1 / k + 1 / n + 1 / m >= 1) | (Math.floor(s / k) != s / k | Math.floor(s / n) != s / n | Math.floor(s / m) != s / m) | !(Math.floor(s) == s)) System.out.println(-1); else System.out.println(Math.round(s)); } } |
Решение задачи
Пусть $x$ — количество учеников Пифагора. Тогда $\displaystyle\frac{x}{2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\displaystyle\frac{x}{4}$ — ученики, которые изучают природу, а $\displaystyle\frac{x}{7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.
Получили уравнение вида $\displaystyle\frac{x}{2} + \frac{x}{4} + \frac{x}{7} + 3 = x$, в общем виде $\displaystyle\frac{x}{k} + \frac{x}{m} + \frac{x}{n} + d = x$.
Отсюда выходит, что $\displaystyle\frac{1}{k} + \frac{1}{m} + \frac{1}{n} + dx = 1;$
$\displaystyle\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$
$\displaystyle(mn + kn + km)x + kmnd = kmnx;$
Отсюда получаем формулу $\displaystyle x = \frac{kmnd} {kmn — mn — kn — km}$.
Следовательно, если мы получаем целое число, то секретарь оказался прав, а если число дробное, то секретарь ошибся.
Для того, чтобы проверить, является ли переменная x целым числом или нет, используем метод floor() из класса Math.
Помимо этого делаем проверку для суммы чисел $\displaystyle\frac{1}{k}$, $\displaystyle\frac{1}{n}$ и $\displaystyle\frac{1}{m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\displaystyle\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.
Так же делаем проверку, которая определяет, не являются ли числа $\displaystyle\frac{q}{k}$, $\displaystyle\frac{q}{n}$ и $\displaystyle\frac{q}{m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).
Если условие не проходит проверки, то выводится «$-1$».
Ссылки
Условие задачи на e-olymp.com
Решение задачи на ideone.com