e-olymp 43. Количество участников олимпиады

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$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

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

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

Пусть $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

5 thoughts on “e-olymp 43. Количество участников олимпиады

    • Объяснение не объясняет самого главного — как получена эта волшебная формула. Как Вы рассуждали, как выводили. Можно только догадаться, что общее количество участников Вы обозначили $q.$ Что это количество разбито на четыре не пересекающиеся группы с численностью $d, \frac{q}{n}, \frac{q}{m}$ и $\frac{q}{k}.$ Суммируя Вы получаете некоторое соотношение и как-то из него находите $q.$
    • Теперь по ситуации, когда решения нет. И почему это происходит только в случае, когда $\frac{1}{n} + \frac{q}{m} + \frac{q}{k} > 1$? А если эта сумма равна 1 и $d$ > 0?
    • И еще один случай, который Вы не учитываете — расчленение участников соревнование совершенно не соответствует жанровой направленности Вашей публикации. Например, если $n=6, m=6, k=6, d=1,$ Ваша программа говорит, что участников соревнования было 2. Но тогда получается, что 1 участник думает с чего начать, а второго разделили на 3 равные части. Согласитесь, это несколько необычно.

    Да, я согласен, что задача прошла все тесты. Но прохождение всех тестов не гарантирует правильности решения. Т.е. тесты отсеивают ошибочные решения, но не гарантируют правильности. Наш пример 6 6 6 1 стоило бы добавить к тестам для того, чтобы отсеять еще один тип ошибок в программе.
    Тесты, прохождение которых не гарантирует правильности решения, принято называть «слабыми» или «неполными».

    • floor(s/k) != s/k — это расплата за использование действительного типа данных. Для целого типа обошлись бы s % k. Но уж как есть.
    • На будущее, лучше использовать тип double для действительных чисел.
    • Использовать return вместо else неправильно. Логически, у Вас два случая — нужно либо вывести s, либо -1. Это означает, что у Вас должен быть один условный оператор.
      Возможно условие будет довольно сложным, но такое случается.
      • Сделайте, пожалуйста, правильные отступы.

        По пояснению. Вы пишите «при подстановке в нашу формулу, получается, что в знаменателе мы получаем 0, что невозможно, а значит…» Вы путаете причину и следствие. У Вас четыре категории. Первые три заданы в долях, а четвертая количеством. Если три доли дают 1, то в четвертую не попадает никто. Если же по условию задачи в этой четвертой категории кто-то есть, то получаем противоречие. Ваша задача описать эту ситуацию формулой и запрограммировать.
        Если Вы придумали какую-то формулу и она в каком-то случае приводит к делению на 0 или другой некорректной ситуации, то это говорит только о том, что в этой ситуации формула неприменима.

  1. Ну, хорошо. Исправил сам и зачел.
    Тем не менее мне некоторые вещи не нравятся, хоть я и не требую их исправления.
    Во-первых, термин дробное число» не является однозначно принятым. Дробными иногда называют все рациональные числа, а иногда все действительные не целые, а иногда все рациональные не целые. У Вас всего два случая — целое число и остальное. Можно было и не придумывать название для этого случая.
    Во-вторых, Вы используете в программе действительные числа и «кучу» округлений. Можно было бы поступить проще:

Добавить комментарий