ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1648. Yachts

What is a right algorithm to that problem?
Posted by Asyamov Igor 26 Oct 2008 11:53
Tell me please!
Is it greedy???
Yes (-)
Posted by Ivan 26 Oct 2008 12:14
Re: What is a right algorithm to that problem?
Posted by svr 26 Oct 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
Re: What is a right algorithm to that problem?
Posted by Asyamov Igor 26 Oct 2008 20:37
My algo is the same as your! (but still wa 15) :-(
Re: What is a right algorithm to that problem?
Use DP
Re: What is a right algorithm to that problem?
Posted by svr 26 Oct 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.
Re: What is a right algorithm to that problem?
Posted by Asyamov Igor 26 Oct 2008 21:47
may be your problem with the type of the second number(it should be __int64)???
*
Posted by Maxim Dvoynishnikov (Dnipropetrovsk SU) 27 Oct 2008 01:32
I have WA49 with greedy and restroring.
Re: *
Posted by double 27 Oct 2008 06:17
use int64(long long) ,then you'll get AC.
Re: What is a right algorithm to that problem?
Posted by svr 27 Oct 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
Re: What is a right algorithm to that problem?
Posted by Asyamov Igor 27 Oct 2008 18:02
Are you got AC with your algo or you had chaged it???
Re: What is a right algorithm to that problem?
Posted by Asyamov Igor 27 Oct 2008 18:16


Edited by author 28.10.2008 14:51
Re: What is a right algorithm to that problem?
Posted by svr 27 Oct 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.
Re: What is a right algorithm to that problem?
Posted by Asyamov Igor 28 Oct 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
Re: What is a right algorithm to that problem?
Posted by lql1993 2 Dec 2008 16:30
I think greedy can work well.
Re: What is a right algorithm to that problem?
Posted by Vit Demidenko 27 Aug 2010 20:27
I don'n understand, how to solve this problem whith DP or greedy. I solve with RMQ.