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

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

Форум программистов > C/C++: Общие вопросы > Задача на бинарный поиск

Автор: Dmi3ev 8.10.2013, 04:12

Всем привет, давно меня не было, нужна помощь...
http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=2969&run_id=1710r1537#1
вот исполнение GNU C++ 4.7.2

Код


#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;
}

проходит все тесты кроме одного...
В этом тесте задачу решает, но выходит за временные рамки на 0,08 с(

Автор: xvr 8.10.2013, 12:45

Цитата(Dmi3ev @ 8.10.2013, 04:12

)

n=ceil(double(hpall)/double(hp));

Это зачем? Чем просто деление не угодило?

Автор: Dmi3ev 8.10.2013, 14:44

Какое деление???

Автор: volatile 8.10.2013, 15:02

Цитата(Dmi3ev @ 8.10.2013, 04:12

)

Задача на бинарный поиск

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

Цитата(Dmi3ev @ 8.10.2013, 04:12

)

выходит за временные рамки на 0,08 с(

т.е. алгоритм изначально не оптимальный, поэтому время большое.

Добавлено @ 15:05

Цитата(Dmi3ev @ 8.10.2013, 14:44

)

Какое деление???

Цитата(Dmi3ev @ 8.10.2013, 04:12

)

r=ceil(double(hd)/double(dp));

Добавлено @ 15:07
Короче так:
r=(hd-1)/dp +1;
Но суть не в этом, а в алгоритме.

Автор: Dmi3ev 8.10.2013, 15:51

Цитата

r=(hd-1)/dp +1;

Цитата

Это зачем? Чем просто деление не угодило?

Цитата

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

а воз и ныне там)
PS если нет советов и идей, то...
все тесты укладываются в 2 с, а этот нет... большинство (16/17) за 0,012 не выходят...

Автор: baldina 8.10.2013, 17:49

Цитата(Dmi3ev @ 8.10.2013, 04:12

)

r=ceil(double(hd)/double(dp));

тут оно небыстро работает

Автор: Dmi3ev 10.10.2013, 01:30

Код


#include <iostream>
#include <math.h>
using namespace std;
signed 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 кроме одного теста...
там все еще 2,08.
Думаю подвох в больших числах или еще чего, алгоритм верный, тут сомнений нет...

Автор: Alex Feat 10.10.2013, 11:25

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

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Задача-на-бинарный-поиск-id52535c96ae20152446000000#findElement_E7045_52566482ae2015390900039a_0

Автор: Dmi3ev 10.10.2013, 19:15

Цитата

Подвох возможен в большом количестве жизней дракона и маленьком количестве урона копейщиков

Да, я тоже так думаю, получается, что если у дракона и у копейщика много жизней и маленький урон, то долгое время никто никого не убивает((( а это значит, поединок продолжается...

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

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

Автор: o2n3e 12.10.2013, 14:42

Модератор: Сообщение скрыто.

Автор: o2n3e 14.10.2013, 16:11

Модератор: Сообщение скрыто.

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

Цитата

Ну так даже не интересно. Пройдя не интересные, тупые тесты жалкого подобия - вы уже забили на то, для чего они предназначались.
Для прохода тестов даже задача не нужна, как и её решение. Вы бы могли поучится устроив топик-батл, аля "кто понтовей запилет это ###", но вам не интересно.
Ой ладно - фу на вас, страдайте дальше фигнёй.

Да нормально всё, тесты летают за 0,003. Можно оптимизировать, но и так время хорошее... Не понимаю, что тебе не нравится??? Покажи свою шикарную версию решения, умник...

Автор: o2n3e 15.10.2013, 15:04

Модератор: Сообщение скрыто.