10980 - Lowest Price in Town

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

10980 - Lowest Price in Town

Post by Darko » Wed Dec 28, 2005 9:52 pm

Ok, I have no idea what I'm missing here, it sounds simple.

Just divide k with number of items in each combo (including single item "combo"), if not even, add one, multiply that number with the price of the combo (or "combo")... print out the minimum of those?

I thought that one was the easiest in the set, and I see a lot of people got it, but I didn't.

Any tricky input that someone can think of?

Darko

P.S. I was doing it in Java, so I suspect something with I/O, but doesn't have to be

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Dec 28, 2005 10:17 pm

Try coming up with a DP solution.. =)

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Dec 28, 2005 10:21 pm

Grumble...

It seems I completely misunderstood the problem.

Thanks :)

Darko

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Dec 29, 2005 4:30 am

Once again I'm sorry if the word "buy" in output confuses you... The last sample test case is added to make things clearer.

Clearly "Get 3 for $40.00" looks clearer than "Buy 3 for $40.00", but I can do little to change now... :-?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Thu Dec 29, 2005 6:17 am

I use DP to solve it but got wrong answer.

Any test data, would appreciate you.

Thanks a lot.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Dec 29, 2005 9:04 am

Sometimes you need to buy more than 100 items for cheaper..

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Dec 29, 2005 11:51 am

I ran out of ideas...

Code: Select all

22.00 2
2 22.00
4 60.00
2 4
25.00 2
2 48.00
2 46.00
2
22.00 2
2 22.00
4 40.00
1 2 3
10.00 3
2 15.00
3 20.00
50 334.00
1 2 3 4 5 17 49 50 51 53 99 100
100.00 3
2 0.01
100 0.00
17 10.00
1 100
12.00 0
1 2 100
999.99 1
51 999.99
1 50 51 52 99 100

Code: Select all

Case 1:
Buy 2 for $22.00
Buy 4 for $44.00
Case 2:
Buy 2 for $46.00
Case 3:
Buy 1 for $22.00
Buy 2 for $22.00
Buy 3 for $40.00
Case 4:
Buy 1 for $10.00
Buy 2 for $15.00
Buy 3 for $20.00
Buy 4 for $30.00
Buy 5 for $35.00
Buy 17 for $115.00
Buy 49 for $330.00
Buy 50 for $334.00
Buy 51 for $340.00
Buy 53 for $354.00
Buy 99 for $660.00
Buy 100 for $668.00
Case 5:
Buy 1 for $0.00
Buy 100 for $0.00
Case 6:
Buy 1 for $12.00
Buy 2 for $24.00
Buy 100 for $1200.00
Case 7:
Buy 1 for $999.99
Buy 50 for $999.99
Buy 51 for $999.99
Buy 52 for $1999.98
Buy 99 for $1999.98
Buy 100 for $1999.98
Darko

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 29, 2005 12:35 pm

Would anybody give an idea how to form the dynamic relation here?

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Thu Dec 29, 2005 1:08 pm

Darko,
My AC code gives the same output.
Ivan

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Dec 29, 2005 1:25 pm

mamun wrote:Would anybody give an idea how to form the dynamic relation here?
Its a spoiler:
Calculate the array cheapest[], where cheapest[n] is the best price to buy n items, and calculate this array for n=1, 2, 3, etc. (increasing n).
Now there are many ways to buy n items:
- buy them for n times the unit price;
- buy k times an offer (m for the price of p), where k*m >= n, for k*p;
- buy a items and then b items for cheapest[a]+cheapest, where a+b = n, 0 < a,b <n;
but one of these ways is the cheapest, so store that in cheapest[n].

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 29, 2005 3:41 pm

Thanks little joey. I'll try to implement it now.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Dec 29, 2005 9:22 pm

Can someone tell me (or give me a hint) WHEN this doesn't work ("comboSize" is N (1 for the single item) and "price" is P from the input). I really can't figure it out.

Code: Select all

cost = new long[110];
for (int i = 1; i < 110; i++) {
	if (i == 2 && cost[1] == 0)
		break;
	long min = Long.MAX_VALUE;
	for (int j = 0; j < prices.length; j++) {
		if (prices[j].price == 0) {
			min = 0;
			break;
		}
		int q = i / prices[j].comboSize;
		int r = i % prices[j].comboSize;
		if(r == i || i == 1){
			q = 1;
			r = 0;
		}
		long c = q * prices[j].price + cost[r];
		if (c < min)
			min = c;
	}
	cost[i] = min;
}
Darko

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 29, 2005 9:44 pm

What's prices.length?
What are you doing in

Code: Select all

int q = i / prices[j].comboSize; 
int r = i % prices[j].comboSize; 
You mat try this I/O
Input

Code: Select all

10.00 2
3 25.00
4 32.00
3 4 5 6 7
Output

Code: Select all

Case 1:
Buy 3 for $25.00
Buy 4 for $32.00
Buy 5 for $42.00
Buy 6 for $50.00
Buy 7 for $57.00

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Dec 29, 2005 10:16 pm

Sometimes you need to buy more than 100 items for cheaper..
Looking up to 110 isn't enough. Also, there's a simplier recurrence..

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Dec 30, 2005 1:50 am

Thanks for the responses, guys.

prices.length is the length of the array holding the (comboSize,price) pairs (M+1 of them).

I increased 101 to 110 just in desperation, those are K's (that are never larger than 100) (I just tried 200 in another desperate attempt...)

I know that that method is slow, I keep dividing the same things and use only already calculated values for the remainders. But it runs in one second, so it's fine. I don't understand why I'm getting WA.

Yes, q is quotient and r is reminder. As in:
K = 10
N = 3, P = 10.00
I calculate the cost as:
q = 10/3 = 3
r = 1
c = q*price+cost[r] = 3*10.00 + cost[1]
Then I get minimum of those c's for all (N,P)'s (and I consider the initial one as (1, unitPrice)).

Even if you buy more than 100 items, it doesn't matter, I consider only the cost of the deal, not if there are more than 100 (if K<comboSize, I set q to 1 and r to 0).

If you think that 100 is the key, can you please provide some input, as I said, I ran out of ideas.

Darko

Post Reply

Return to “Volume 109 (10900-10999)”