e-olymp 75. Пираты и монеты

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

 #  ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
 1  5 25  3
 2  3 24  4
 3  4 38  5
 4  5 55  6
 5  6 75  7

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

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]\sqrt{b^{2} — 4c}[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + d}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

Код программы (с условным оператором)

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

11 thoughts on “e-olymp 75. Пираты и монеты

    • Или можно бы отрицание условия из самого «if» внести в условие «while», а в конце просто добавить один «n++». Тогда вообще пропадает необходимость в ветвлении

  1. Даниил, если задача находится в разделе «Линейные вычисления», её нужно попытаться решить без использования условных операторов либо циклов. Ты ведь сам сначала вспомнил про арифметическую прогрессию, а потом зачем-то делаешь цикл)
    И ещё, нужно добавить метки к отчёту и убрать кириллицу из постоянной ссылки.

    • Пробелы ставят после запятой, а не перед.
    • Не надо использовать * в качестве умножения в математических формулах — либо точка, либо ничего.
    • Нужно объяснить, почему отбрасываете второй корень квадратного уравнения.
      По первому коду

    • В чем логика написания -1*b?
    • В строке 6 Вы заводите переменную q = 1 и в строке 10 постоянно что-то на эту единицу умножаете. Зачем?
      По первому коду

    • Вечный цикл (7) с брейком (8) это на самом деле обычный цикл с условием.
    • Чтобы проверить два числа на равенство (8) нет необходимости вычитать и сравнивать с нулем.
    • Начинать с (5) и в конце увеличивать на 1 (9) означает просто начинать с 1.
    • Подумайте, как обойтись вообще без условных операторов внутри цикла — все пираты берут монеты, а не по некоторому условию. Значит и уменьшать сумму приходится всегда
  2. Да, такими темпами это будет дого продолжаться.
    — У Вас были замечания по первому коду. Вы его сохранили и сделали третий. Зачем сохранять этот ужасный код? Уберите его, пожалуйста. Вместе с объяснением.
    — Вы устранили замечания по второму коду. Я бы сказал, молодец. Но Вы вдруг решили все испортить. Простое умножение зачем-то заменили приближенными вычислениями нецелой степени действительного числа разложением в ряд тейлора. Это юмор такой?
    — По последнему коду. Вам нужно вывести n+1. Любой интилигентый одесский мальчик, так бы и сделал — cout << n + 1; Но нет! Вы это делаете в два приема, зачем-то перед самым концом программы увеличивая n.
    — Вы ведь вычисляете дискриминант? почему не написать формулу? Вместо этого у Вас смеси тумана с очевидностью: «В коде задаем чему равно b, c и d. Они нужны для нахождения корня нашего уравнения».
    Ну, и раз уже все равно переделывать, то
    — посмотрите, как в latex кодируют меньше либо равно
    — поставьие пробелы перед открывающими скобками.

    • Вы пишите «способ решения… осуществляется». Так в этом языке говорить нельзя. Можно найти способ осуществить решение. Можно просто сказать, что задача решается таким-то способом. Можно осуществить идею и получить способ решения. Старайтесь использовать витиеватые речевые обороты, только если абсолютно в них уверены. Неверное словоупотребление или сочетание слов в вычурных фразах выглядит смешно и претенциозно, как мещанин во дворянстве.
      Не хатите просто сказать «Для решения задачи воспользуемся формулой арифметической прогрессии»?
    • Пожалуйста, выбросьте все «нашего», «наше», «данное» и даже «мы». Если очень хочется вставить что-то вроде этих слов, прочтите фразу без них. Если они ничег не добавляют к смыслу, то смело удаляйте.
    • «создаем цикл» — эти слова не сочетаются. Вы максимум можете использовать цикл, но не создать.
    • Зачем вы поставили пустой оператор после фигурной скобки закрывающей цикл? Он ничего плохого не делает, он же пустой. Но смысл? Закрадывается подозрение, что вы не знаете где нужно ставить точки с запятой. Но нет, не может такого быть.

    Я зачту эту работу. Будет время, исправьте недостатки.
    И хотя я не пониаю, зачем тут циклы, но зачту и это решение.
    Просто у меня давно уже закончились задачи за сентябрь прошлого года.
    Теперь Вам нужно решить задачу на условный оператор 🙂 Предлагаю решить эту же самую.

    • Все сделал. А пустой оператор после фигурной скобки , закрывающей цикл , это я не доглядел 🙂 Все недостатки исправил. Решение с условными операторами добавил.

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