Problem 327

[carkiller]

Hi,

I'm a bit irritated about the 40 in the maximal limit. It seems not to complicate things too much, but my solution is rejected. The examples from the Problem are easily reproduced. For R=20 rooms and 3 <= C <= 30 I get 581498558 needed cards.

Any special hint?

Thanks - Marco.

[stijn263]

Do you use 32 bit integers perhaps?

What do you get when you try to print:
1000 * 1000 * 1000 * 1000 ?
1000000000000? or some random looking integer?

If that's the problem, then you need 64 bit integers. (__int64 or long long in C++ )

[carkiller]

Do you use 32 bit integers perhaps?
If that's the problem, then you need 64 bit integers. (__int64 or long long in C++ )

Oh thanks a lot! Most of the operations were already arbitrary precision, but in between two or three "normal" floating point operations.

What a silly mistake for a level 3...

Still using php, so bcadd is my favourite. But sometimes I still fall into the trap of "floor".

Now done, Marco.

[mdean]

This might be a nitpick, but I assume there is a place to store/dispose of used security cards? The scenario as described will cause the doors to permanently lock as you are holding 5 security cards at one point: 2 used and 3 unused.

[rayfil]

nitpick

The security card that you use to enter a room is inserted into a slot and then recycled through a complex system of conveyor belts under the floor back to the dispenser at the entrance. That's why you can't use it again. It has been removed from your possession.

That complex system of conveyor belts was too complicated to explain in detail in the description of the problem. It was simply assumed that members would figure it out while working on solving the problem.

[mdean]

Works for me.

[Ramiel]

I'm having a problem with this question . My algorithm is as follows: To reach the end of r rooms with c cards, the first (r-c+1) rooms must have a card stored (I call it 'seeded' for some reason) in them. That way, you take c cards at the start, and in each room retrieve the seeded card, and you have enough to get through. In the example this works, because the (3-3+1) room is seeded. So, to find the number of cards needed to travel through the rooms, first sum up all the costs of seeded each room up till (r-c+1), then add c for the final pass.

To seed a room n, I realized that you would need at LEAST 3 cards in hand at room n-1, so you need to seed the appropriate number of rooms such that you have >= 3 cards in hand at n-1, but then you also need to seed the rooms so that you can get back to the start. Mathwise, that is: Seed all rooms < n once, and <= (n-c+2) once. Using that first algorithm, given say 5 cards to seed the 6th room, the 1-3 rooms would need to be seeded to have 3 in hand at 5 (6-1) room, and then rooms 1-5 would need to be seeded in able to return to start. Then I realized it would probably be more efficient to seed 1-4 twice rather than 1-3 once and 1-5 once, so I said if c odd: seed rooms n-(c-1)/2 twice and if c even: seed rooms n-(c-1)/2 twice and room n-((c-1)/2)+1 once.

So in all, I find all the costs to seed each room <(r-c+1), then take c cards and walk through. It works for M(3,6) AND M(3,3), but it DOESN'T work for M (4, 6). Any help would be appreciated because this is bugging me a lot. Thank you!

(I would post code but it would just get deleted)

EDIT: More specifically, can anyone detail the sequence to solve M (4, 6) with only 23 cards? (I get 31). Thanks!

[mpiotte]

... My algorithm is as follows: To reach the end of r rooms with c cards, the first (r-c+1) rooms must have a card stored (I call it 'seeded' for some reason) in them. ...
It works for M(3,6) AND M(3,3), but it DOESN'T work for M (4, 6)...

Seeding each of the first (r - c + 1) room with exactly one card is one way to cross, but not the only one, and it probably isn't always the optimal way.

[Ramiel]

Seeding each of the first (r - c + 1) room with exactly one card is one way to cross, but not the only one, and it probably isn't always the optimal way.

hmmmm thank you. (That makes it a bit harder)