Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Задача на бинарный поиск

Автор: Dmi3ev 8.10.2013, 19:11

создал тему, похоже не там вот собственно задача и реализация на с++
http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=2969&run_id=1710r1537#1
вот моя реализация

Код


#include <iostream>
#include <math.h>
using namespace std;
long long hd, ur, now, n, dd, hp, dp, hpall,l,r;
int main()
{
cin>>hd>>dd>>hp>>dp;
l=1;
r=ceil(double(hd)/double(dp));
while (l!=r)
{
  now=(l+r)/2;
  n=now;
  ur=0;
  hpall=now*hp;
  while ((ur<hd) && (hpall>0))
{
    ur+=dp*n;
    hpall-=dd;
    n=ceil(double(hpall)/double(hp));
}
  if (ur<hd)
    l=now+1;
  else
    r=now;
  }
cout<<r;
return 0;
}

проходит 17/18 тестов, есть недоработки... в основном не выходит за пределы 0,012 с, а в 18-ом тесте от 2,04 до 2,08 с

Автор: ФедосеевПавел 9.10.2013, 16:46

Может быть 18-й тест проходит на больших числах, когда hpall имеет порядок 10^18. И при конвертации в double происходит потеря точности. Попробуй реализоать всё в целочисленной арифметике.
-------------------
Сейчас изменил две строки в твоём варианте - заменил ceil на целочисленное деление и инкремент - и для hd=987654321; dd=500; hp=12345678; dp=3; время работы изменилось с 2,6 с на 1,4 с.

Автор: Dmi3ev 9.10.2013, 19:24

как именно изменил? может быть это меняет правильность решения...

Автор: ФедосеевПавел 9.10.2013, 21:45

Я плохо говорить на C++, но таки по смыслу

Код


            n=hpall / hp;
            if ((hpall % hp)!=0)
                n++;

Автор: Dmi3ev 9.10.2013, 23:52

Цитата

n=hpall / hp;
if ((hpall % hp)!=0)
n++;

так не проходит еще один тест(((

Автор: Mirkes 10.10.2013, 00:39

Я не уверен, но по моему от действительной арифметики легко избавиться считая не число выживших копейщиков, а число убитых smile

если мы поделим суммарный урон, нанесенный драконом на запас жизни одного копейщика, то целочисленное деление даст точно нужный результат! Я никогда не писал на С но думаю, что правильно исправил программу

Код


#include <iostream>
#include <math.h>
using namespace std;
long long hd, ur, now, n, dd, hp, dp, hpall,l,r,dpall;
int main()
{
cin>>hd>>dd>>hp>>dp;
l=1;
r=ceil(double(hd)/double(dp));
while (l!=r)
{
  now=(l+r)/2;
  n=now;
  ur=0;
  hpall=now*hp;
  while ((ur<hd) && (hpall>dpall))
{
    ur+=dp*n;
    dpall+=dd; //Суммарный урон нанесенный драконом
    n= now- dpall/hp; //число оставшихся в живых есть число тех, кто был до того минус число убитых
}
  if (ur<hd)
    l=now+1;
  else
    r=now;
  }
cout<<r;
return 0;
}

Автор: Dmi3ev 10.10.2013, 16:09

послушал вас всех и оптимизировал:

Код


#include <iostream>
#include <math.h>
using namespace std;
long s,hd, ur, now, n, dd, hp, dp, hpall,l,r,k,ost,o,f;

int main()
{
cin>>hd>>dd>>hp>>dp;
l=1;
r=ceil(double(hd)/double(dp));
f=r;
k=dd/hp;
o=dd%hp;
while (l!=r)
{
  now=(l+r)/2;
  n=now;
  ur=0;
  ost=0;
  s=f;
  while ((s>0) && (n>0))
    {
        s-=n;
        n-=k;
        ost+=o;
        if (ost>=hp) {n--; ost-=hp;}
    }
  if (s>0)
    l=now+1;
  else
    r=now;
}
cout<<r;
return 0;
}

теперь все тесты летают за 0,003 с, а тот все еще не проходит...
есть идеи???

Автор: Dmi3ev 10.10.2013, 18:00

Цитата

Я не уверен

Так задача не решается!!! Данная замена неправильная...

Автор: ФедосеевПавел 10.10.2013, 19:16

А может и правильная.
Теперь мне кажется другое.
1) Тип long long целочисленный со знаком - не происходит ли переполнение разрядной сетки с изменением знака. Может попробовать unsigned long.
2) Кроме того, у Mirkes в коде присутствует маленькая ошибка - нет инициализации dpall, что приводит к неверным результатам
3) твой последний вариант не находит решения для hd=987654321; dd=500; hp=12345678; dp=3; - зависает.

Предлагаю улучшить вариант Mirkes

Код


.............
unsigned long hd, ur, now, n, dd, hp, dp, hpall,l,r,dpall;
..........................
   while (l!=r)
    {
        now=(l+r)/2;
        n=now;
        ur=0;
        dpall=0;                                                                                            <---  не хватало
        hpall=now*hp;
        while ((ur<hd) && (hpall>dpall))
        {
            ur+=dp*n;
            dpall+=dd; //Суммарный урон нанесенный драконом
            if (now>(dpall/hp))                                                                       <--- у нас теперь беззнаковые числа
                n= now- dpall/hp; //число оставшихся в живых есть число тех, кто был до того минус число убитых
            else
                n=0;

Автор: Dmi3ev 10.10.2013, 21:45

все, решил, ура)))
надо три цикла просто а не два... все ок, спасибо за помощь... посмотрел чуть с другой стороны на нее...

Цитата

А может и правильная.

неправильная, я же на тестах проверяю... им можно верить...
PS
теперь даже при самых худших раскладах задача решается за 0,006 с))) победа

Автор: ФедосеевПавел 10.10.2013, 21:52

Если это возможно, покажи решение или расскажи, что за цикл добавляется.
--------------
Также интересно, тест 18 не проходил по времени или по некорректным результатам?

Автор: Dmi3ev 10.10.2013, 22:26

Цитата

Также интересно, тест 18 не проходил по времени или по некорректным результатам?

По времени не проходил, решение изначально верное... после оптимизации стало еще больше похоже...
В третий цикл запихнул случай, когда дракон не каждый раз кого-то убивает... т. е. отдельно рассмотрел к=0.
Сейчас уже вижу, что можно вывести формулу, но... задача уже решена) ср. время работы 0,002 с.

Цитата

твой последний вариант не находит решения для hd=987654321; dd=500; hp=12345678; dp=3; - зависает.

там ограничение до 10^9 в задаче... проверил кстати, у меня все работает в том варианте...
ты что юзаешь???

Добавлено @ 22:31
PascalABC

Код


program ex1;

var
  s, hd, ur, now, n, dd, hp, dp, hpall, l, r, k, ost, o, f,i: longint;

begin
  readln(hd, dd, hp, dp);
  l := 1;
  r := hd div dp;
  if (hd mod dp > 0) then r := r + 1; 
  f := r;
  k := dd div hp;
  o := dd mod hp;
  while (l <> r) do
  begin
    now := (l + r) div 2;
    n := now;
    ost := 0;
    s := f;
    if (k=0) then 
    i := hp div o;
    if k > 0 then
      while ((s > 0) and (n > 0)) do
      begin
        s := s - n;
        n := n - k;
        ost := ost + o;
        if (ost >= hp) then
        begin
          n := n - 1; 
          ost := ost - hp;
        end;
      end
    else
      while ((s > 0) and (n > 0)) do
      begin
        s := s - n * (i+1);
        ost := ost + o * (i+1);
        n := n - 1; 
        ost := ost - hp;
        i := (hp - ost) div o;
      end;
    
    if (s > 0) then
      l := now + 1
    else
      r := now
  end; 
  writeln(r)
end.

GNU C++

Код


#include <iostream>
#include <math.h>
using namespace std;
long s,hd, now, n, dd, hp, dp,l,r,k,ost,o,f,i;

int main()
{
cin>>hd>>dd>>hp>>dp;
l=1;
r=ceil(double(hd)/double(dp));
f=r;
k=dd/hp;
o=dd%hp;
while (l!=r)
{
  now=(l+r)/2;
  n=now;
  ost=0;
  s=f;
  if (!k) i=hp/o;
  if (k>0)
  while ((s>0) && (n>0))
    {
        s-=n;
        n-=k;
        ost+=o;
        if (ost>=hp) {n--; ost-=hp;}
    }
    else
    while ((s>0) && (n>0))
    {
        s-=n*(i+1);
        ost+=o*(i+1);
        n--;
        ost-=hp;
        i=(hp-ost)/o;
    }
  if (s>0)
    l=now+1;
  else
    r=now;
}
cout<<r;
return 0;
}

Автор: ФедосеевПавел 10.10.2013, 22:54

Про зависание - наверное. я поторопился и где-то ошибся.
Баловался Code::Block+MinGW == gnu c++

Поздравляю с найденым решением!

Автор: Mirkes 10.10.2013, 23:10

Вообще-то задачу решал не я smile

По поводу идей - есть. Скорее всего программа слишком долго ищет решение потому, что оценка нужного числа копейщиков слишком грубая от 1 до hd/dp. Если дракон слабенький но очень живучий (dh большое а dd маленькое) и копейщики тоже живучие но слабые, то число обменов ударами будет большое (много времени на проверку одного предполагаемого числа копейщиков)
Учитывая заданный в задаче диапазон чисел вы вполне можете получить оценку типа 10^9: dh=10^9; dp=1; dd=10; hp=10;
При этих условиях вы будете гонять порядка 30 рассчетов, причем при большом числе копейщиков каждый рассчет будет весьма долгим. Я посмотрел на правильный ответ потребуется 14142 тура. Представьте время, которое вам для этого потребуется smile

Можно поробовать идти от числа туров при обмене ударами. [] - взятие целой части
1 тур N*dp=hd
2 тура 2N*dp-[dd/hp]*dp=hd
3 тура 3N*dp-[dd/hp]*dp-[2*dd/hp]*dp=hd
и т.д.
В каждом из этих уравнений нужно вычислить N и [k*dd/hp]
Если второе значение станет больше первого, то проскочили и правильным ответом является N с предыдущего шага
Если правильно организуете расчеты, то на каждом шаге нужно будет выполнить пару умножений и делений. Все операции только с целочисленными переменными.
Полученный ответ может быть на 1 меньше, чем правильный. Это прийдется проверить путем прямого рассчета.
Однако в этом случае число прямых рассчетов будет всего 2-3. А первичное вычисление N будет достаточно быстрым, поскольку в нем нет внутренних циклов.

Успеха!

Автор: Dmi3ev 11.10.2013, 18:08

Цитата

Mirkes, я уже решил задачу и выложил решение давно, смотри выше )