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

24/12/2018 by Даниил Мозгунов

Задача

[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

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double a, m, n, b, c, d;
    cin>>a>>m; 
    b = 2 * a + 1;
    c = 2 * a - 2 - 2 * m;
    d = b * b - 4 * c;
    n = ( -b + sqrt(d) ) / 2;
    cout<<n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, m, n, b, c, d;

cin>>a>>m;

b = 2 * a + 1;

c = 2 * a - 2 - 2 * m;

d = b * b - 4 * c;

n = ( -b + sqrt(d) ) / 2;

cout<<n;

return 0;

}

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [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]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

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

#include <iostream>
using namespace std;

int main() {
    unsigned int a, m, n = 0;
    cin>>a>>m;
    while (m - 2 * a != 0){
            m -= a;
            a ++;
            n ++;
    }
    cout<<n + 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int a, m, n = 0;

cin>>a>>m;

while (m - 2 * a != 0){

m -= a;

a ++;

n ++;

}

cout<<n + 1;

return 0;

}

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [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]. И получаем ответ на нашу задачу.

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

#include <iostream>
using namespace std;
 
int f(int a, int m, int n = 0) {
    if (m - 2*a == 0) {
        return n + 1;
    }
    else {
        return f(a + 1, m - a, n + 1);
    }
}
 
int main() {
    int a, m;
    cin >> a >> m;
    cout << f(a, m);
    return 0;
}

#include <iostream>

using namespace std;

int f(int a, int m, int n = 0) {

if (m - 2*a == 0) {

return n + 1;

}

else {

return f(a + 1, m - a, n + 1);

}

int main() {

int a, m;

cin >> a >> m;

cout << f(a, m);

return 0;

}

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

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

Ссылки

Related Images:

Похожее

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

Руслан Масальский says: 24/12/2018 at 18:20

Советую избавиться от break, лучше какой-то флаг поставить while(flag) , а вместо break написать flag = false

Войдите, чтобы ответить
- Кирилл Веремйов says: 24/12/2018 at 18:34
  
  Или можно бы отрицание условия из самого «if» внести в условие «while», а в конце просто добавить один «n++». Тогда вообще пропадает необходимость в ветвлении
Никита Семерня says: 24/12/2018 at 18:28

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

Войдите, чтобы ответить
- Даниил Мозгунов says: 25/12/2018 at 19:54
  
  Спасибо , метки добавил и кириллица убрана.

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

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

int main() {
    double a ,m ,n, b, c, q = 1;
    cin>>a>>m; 
    b = 2*a + 1; // нам все это нужно для того чтобы найти корень квадратного
    c = 2*a - 2 - 2*m; // уравнения вида n*n + 2 * n * a + n + 2 * a - 2 = 2*m
    n = ( -1*b + sqrt(b*b - 4*q*c) ) / (2 * q);// корень которого равен:...
    cout<<n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a ,m ,n, b, c, q = 1;

cin>>a>>m;

b = 2*a + 1; // нам все это нужно для того чтобы найти корень квадратного

c = 2*a - 2 - 2*m; // уравнения вида n*n + 2 * n * a + n + 2 * a - 2 = 2*m

n = ( -1*b + sqrt(b*b - 4*q*c) ) / (2 * q);// корень которого равен:...

cout<<n;

return 0;

}

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

#include <iostream>
using namespace std;
 
int main() {
    unsigned int a ,m ,n = 0;
    cin>>a>>m;
    while (true){
        if (m-2*a == 0) {
            n++; 
            break;
        }
        else if (m -= a != 0) {
            m -= a-1;
            a++;
            n++;
        }
    }
    cout<<n;
}

#include <iostream>

using namespace std;

int main() {

unsigned int a ,m ,n = 0;

cin>>a>>m;

while (true){

if (m-2*a == 0) {

n++;

break;

}

else if (m -= a != 0) {

m -= a-1;

a++;

n++;

}

cout<<n;

}

Вечный цикл (7) с брейком (8) это на самом деле обычный цикл с условием.
Чтобы проверить два числа на равенство (8) нет необходимости вычитать и сравнивать с нулем.
Начинать с (5) и в конце увеличивать на 1 (9) означает просто начинать с 1.
Подумайте, как обойтись вообще без условных операторов внутри цикла — все пираты берут монеты, а не по некоторому условию. Значит и уменьшать сумму приходится всегда

Даниил Мозгунов says: 11/03/2019 at 14:34

Хорошо, сейчас все будет сделано и исправлено с учетом максимального количества ошибок.
Мазурок Игорь Евгеньевич says: 14/03/2019 at 21:48

Вы что-то путаете. Я не ставил вам задачу сделать максимальное количество ошибок. Это Вы сами…

Мазурок Игорь Евгеньевич says: 14/03/2019 at 23:00

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

Войдите, чтобы ответить
- Даниил Мозгунов says: 21/03/2019 at 22:38
  
  Все исправил.
Мазурок Игорь Евгеньевич says: 25/03/2019 at 21:47
- Вы пишите «способ решения… осуществляется». Так в этом языке говорить нельзя. Можно найти способ осуществить решение. Можно просто сказать, что задача решается таким-то способом. Можно осуществить идею и получить способ решения. Старайтесь использовать витиеватые речевые обороты, только если абсолютно в них уверены. Неверное словоупотребление или сочетание слов в вычурных фразах выглядит смешно и претенциозно, как мещанин во дворянстве.
  Не хатите просто сказать «Для решения задачи воспользуемся формулой арифметической прогрессии»?
- Пожалуйста, выбросьте все «нашего», «наше», «данное» и даже «мы». Если очень хочется вставить что-то вроде этих слов, прочтите фразу без них. Если они ничег не добавляют к смыслу, то смело удаляйте.
- «создаем цикл» — эти слова не сочетаются. Вы максимум можете использовать цикл, но не создать.
- Зачем вы поставили пустой оператор после фигурной скобки закрывающей цикл? Он ничего плохого не делает, он же пустой. Но смысл? Закрадывается подозрение, что вы не знаете где нужно ставить точки с запятой. Но нет, не может такого быть.
Я зачту эту работу. Будет время, исправьте недостатки.
И хотя я не пониаю, зачем тут циклы, но зачту и это решение.
Просто у меня давно уже закончились задачи за сентябрь прошлого года.
Теперь Вам нужно решить задачу на условный оператор 🙂 Предлагаю решить эту же самую.

Войдите, чтобы ответить
- Даниил Мозгунов says: 04/04/2019 at 21:08
  
  Все сделал. А пустой оператор после фигурной скобки , закрывающей цикл , это я не доглядел 🙂 Все недостатки исправил. Решение с условными операторами добавил.
- Мазурок Игорь Евгеньевич says: 28/04/2019 at 21:42
  
  Хорошо, Молодец.
  Только поправьте пожалуйста в описании — вы обозначили через d не дискриминант, а корень из него.
- Даниил Мозгунов says: 02/05/2019 at 16:08
  
  Надеюсь я Вас правильно понял, и исправил то, что нужно 🙂

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

Для отправки комментария вам необходимо авторизоваться.

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

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

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

Задача

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

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

Тесты

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

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

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

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

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

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

Ссылки

Related Images:

Понравилось это:

Похожее

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

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

Задача

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

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

Тесты

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

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

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

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

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

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

Ссылки

Related Images:

Share this:

Понравилось это:

Похожее

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

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