10980 - Lowest Price in Town

[Darko]

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]

Try coming up with a DP solution.. =)

[Darko]

Grumble...

It seems I completely misunderstood the problem.

Thanks :)

Darko

[Observer]

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...

[lonelyone]

I use DP to solve it but got wrong answer.

Any test data, would appreciate you.

Thanks a lot.

[Larry]

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

[Darko]

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]

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

[Ivan]

Darko,
My AC code gives the same output.
Ivan

[little joey]

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]

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

[Darko]

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]

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]

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]

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