0

Нужно подсчитать количество потраченых ударов для убийства монстра. На вход поступают: начальный урон [d], увеличение урона при каждом ударе (арифметическая прогрессия, an=a1+d*n) [k], и количество жизней у монстра [hp]. Нужно найти максимально быстро количество ударов.

Ограничение по времени: 1с.

Ограничение по памяти: 256Мб.

Входные данные: 1≤K≤10^3, 1≤D≤10^5, 1≤hp≤10^15

У меня есть набросок кода, но он по времени не успевает обрабатывать.. Данные подаются с Файла (input.txt), выход в другой файл (output.txt);

#include <fstream>
using namespace std;
int main()
{   
    ifstream fin ("input.txt");
    unsigned long long  res = 0,dn,res_n;
    long double hp;
    int k, d;
    fin >> k >> d >> hp;
    res_n = 0;
    while (hp>0){
        hp = hp - d;
        d = d + k;
        res_n++;
    }
    res =res_n;
    ofstream fout;
    fout.open("output.txt");
    fout << res;
    fout.close();
    return 0;
}
8
  • А формулу суммы арифметической прогрессии применить не судьба?...
    – Harry
    27 ноя 2018 в 19:08
  • а как из нее выразить n?? 27 ноя 2018 в 19:15
  • решить уравнение (точнее - неравенство)
    – MBo
    27 ноя 2018 в 19:18
  • 2
    Элементарно, Ватсон :) Если бы я вообще понимал, что у вас считывается (читает n, прибавляете k, говорите в тексте об a1, пишете "количество" с двумя л :)), я бы даже написал формулу. Но у вас настолько неаккуратно все написано... Привели бы исходное условие или URL.
    – Harry
    27 ноя 2018 в 19:21
  • Можете пояснить? Я не до конца понял, что вы хотите сказать.. 28 ноя 2018 в 16:24

1 ответ 1

0

сумма арифм. прогрессии: сумма арифм. прогрессии

d*n^2 +(2*a - d)*n - 2*Sn = 0

дискриминант: D = (2*a - d)^2 + 8*d*Sn

n = (sqrt(D) - 2*a + d) / 2*d

"n" округлить в верхнюю сторону

P.S. тут указаны общие формулировки, вот названия из твоего проекта
мои переменные -- переменные из кода
a == d
d == k
Sn == hp

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.