-
April 2nd, 2010, 01:00 PM
#1
telephone call problem
Hello, could someone help me to solve the following problem?
A conversation time consists of N parts. Each of first N-1 parts last for K[i] minutes, the N-th part is considered to be infinite. Each minute of a part i costs E[i]. Parts are consecutive, i.e. part N+1 always goes right after the end of part N. The pay is per-minute (you pay at the beginning of a new minute for entire minute). If you have no enough money for a new minute, the conversation is interrupted.
You are given integers N and M. N-1 integers K[i] and N integers E[i]. The task is to find the maximal possible number of minutes that you can speak over the telephone (it is possible to make several calls).
constraints:
1 <= N <= 77,
1 <= M, K[i], E[i] <= 1000000 (10^6)
time: 5 sec
memory: 64 mb
If you need a link to the problem to submit, it is here:
http://acm.lviv.ua/fusion/viewpage.p...=4b9bd89bef4d4
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|