Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Задача на бинарный поиск 
V
    Опции темы
Dmi3ev
Дата 8.10.2013, 04:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 1
Всего: 41
Всем привет, давно меня не было, нужна помощь...
вот задача
вот исполнение 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 с(

Это сообщение отредактировал(а) Dmi3ev - 8.10.2013, 14:45


--------------------
PM MAIL   Вверх
xvr
Дата 8.10.2013, 12:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223
Цитата(Dmi3ev @  8.10.2013,  04:12 Найти цитируемый пост)
    n=ceil(double(hpall)/double(hp));

Это зачем? Чем просто деление не угодило?
PM MAIL   Вверх
Dmi3ev
Дата 8.10.2013, 14:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 1
Всего: 41
Какое деление???


--------------------
PM MAIL   Вверх
volatile
Дата 8.10.2013, 15:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
Цитата(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;
Но суть не в этом, а в алгоритме.





Это сообщение отредактировал(а) volatile - 8.10.2013, 15:11
PM MAIL   Вверх
Dmi3ev
Дата 8.10.2013, 15:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 1
Всего: 41
Цитата

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


Цитата

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


Цитата

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

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


--------------------
PM MAIL   Вверх
baldina
Дата 8.10.2013, 17:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101
Цитата(Dmi3ev @  8.10.2013,  04:12 Найти цитируемый пост)
r=ceil(double(hd)/double(dp));

тут оно небыстро работает
PM MAIL   Вверх
Dmi3ev
Дата 10.10.2013, 01:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 1
Всего: 41
Код

#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.
Думаю подвох в больших числах или еще чего, алгоритм верный, тут сомнений нет... 


--------------------
PM MAIL   Вверх
Grost
Дата 10.10.2013, 11:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 65
Регистрация: 26.8.2010
Где: Москва

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

Этот ответ добавлен с нового Винграда - http://vingrad.com
PM MAIL ICQ   Вверх
Dmi3ev
Дата 10.10.2013, 19:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 1
Всего: 41
Цитата

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

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


--------------------
PM MAIL   Вверх
Dmi3ev
Дата 10.10.2013, 21:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

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



--------------------
PM MAIL   Вверх
o2n3e
Дата 12.10.2013, 14:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.8.2011

Репутация: -4
Всего: -5

Модератор: Сообщение скрыто.
PM MAIL   Вверх
o2n3e
Дата 14.10.2013, 16:11 (ссылка) | (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.8.2011

Репутация: -4
Всего: -5

Модератор: Сообщение скрыто.
PM MAIL   Вверх
Dmi3ev
Дата 14.10.2013, 19:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 1
Всего: 41
Цитата

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

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


--------------------
PM MAIL   Вверх
o2n3e
Дата 15.10.2013, 15:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.8.2011

Репутация: -4
Всего: -5

Модератор: Сообщение скрыто.
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0940 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.