ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1648. Яхты

Asyamov Igor What is a right algorithm to that problem? [15] // Задача 1648. Яхты 26 окт 2008 11:53
Tell me please!
Is it greedy???
Ivan Yes (-) // Задача 1648. Яхты 26 окт 2008 12:14
svr Re: What is a right algorithm to that problem? [12] // Задача 1648. Яхты 26 окт 2008 19:56
Greedy only? I think.
I don't solve else but think that next algo is right:
1. maximal production =d in all n periods;
2. Greedy approach :satisfy first demand as fully as possible;
3. If we have residue in last period equal to k
diminish by k residues in previous periods until it is possible
4. Sum final residues along all periods.

Edited by author 26.10.2008 20:52
Asyamov Igor Re: What is a right algorithm to that problem? [11] // Задача 1648. Яхты 26 окт 2008 20:37
My algo is the same as your! (but still wa 15) :-(
Vedernikoff Sergey (HSE: EconomicsForever!) Re: What is a right algorithm to that problem? // Задача 1648. Яхты 26 окт 2008 21:07
Use DP
svr Re: What is a right algorithm to that problem? [9] // Задача 1648. Яхты 26 окт 2008 21:43
You definitely need reading math eco theory
optimal store managing(Taha  a.s.o.)
P.S.I also have WA14. First number of output I guarantee but
the second need more delicate algo.
Asyamov Igor Re: What is a right algorithm to that problem? [8] // Задача 1648. Яхты 26 окт 2008 21:47
may be your problem with the type of the second number(it should be __int64)???
Maxim Dvoynishnikov (Dnipropetrovsk SU) * [1] // Задача 1648. Яхты 27 окт 2008 01:32
I have WA49 with greedy and restroring.
double Re: * // Задача 1648. Яхты 27 окт 2008 06:17
use int64(long long) ,then you'll get AC.
svr Re: What is a right algorithm to that problem? [5] // Задача 1648. Яхты 27 окт 2008 09:21
Yuare right!
With __int 64 AC.
I didn'r recognized masked danger:100000*100000=10*1-e9.
All data seemed fitted in int type.



Edited by author 27.10.2008 09:21
Asyamov Igor Re: What is a right algorithm to that problem? [4] // Задача 1648. Яхты 27 окт 2008 18:02
Are you got AC with your algo or you had chaged it???
Asyamov Igor Re: What is a right algorithm to that problem? // Задача 1648. Яхты 27 окт 2008 18:16


Edited by author 28.10.2008 14:51
svr Re: What is a right algorithm to that problem? [2] // Задача 1648. Яхты 27 окт 2008 18:54
I considered stored values backward more attentievely
according with alg:
store[i-1]=max(store[i]+sell[i-1]-d,0)
store[n]:=0;
i=n..1
where sell[i-1] array of greedy selling on the first stage.
Asyamov Igor Re: What is a right algorithm to that problem? [1] // Задача 1648. Яхты 28 окт 2008 15:39
Accepted!!!!!!
this test help me find my bug...
in:
5 5
3 1 20 3 10
out: 25 10

and now,after accepted, could somebody, who solved this problem with DP, sent to me your solution?
my mail: asyamov@mail.ru

Edited by author 28.10.2008 16:18
lql1993 Re: What is a right algorithm to that problem? // Задача 1648. Яхты 2 дек 2008 16:30
I think greedy can work well.
Vit Demidenko Re: What is a right algorithm to that problem? // Задача 1648. Яхты 27 авг 2010 20:27
I don'n understand, how to solve this problem whith DP or greedy. I solve with RMQ.