11079 - What's the Time?

[Nazmul Quader Zinnuree]

Input will be terminated with N=0 and K=0.

The people who solved it. did you consider it? The sample does not say so.
How to solve it? I'm getting TLE, but no reason to get it. it may be WA. Someone plz clarify whether it is just some math or anything other to solve it?

[sclo]

Input will be terminated with N=0 and K=0.

The people who solved it. did you consider it? The sample does not say so.
How to solve it? I'm getting TLE, but no reason to get it. it may be WA. Someone plz clarify whether it is just some math or anything other to solve it?

I haven't solved it yet, but i think you have to simulate for lcm of periods, then find how many periods are needed, then solve for the time. It shouldn't tle because that number shouldn't be too big. Some optimization may be needed.

[Nazmul Quader Zinnuree]

First, I simulate for the first period & for the last period. which loops for at most 30000. I think it must be done. coz, situation may change in every second in a period. Then, if it is possible to reach, then O(1) calculation, to get the time.

only three cases may occur:
i. reached within the first period.
ii. never reach.
iii. reached after a some period, but within the next one.

I matched all the cases.

Second, is there such a input so that

Code: Select all

desired amount < initial amount

?

Thanks.

[Adrian Kuegel]

I think you should loop for at most 55440 (lcm of (p * 2)), because each period consists of actually 2 * p seconds before it repeats.
Then, my solution would handle such cases where the desired amount is smaller than the current amount. In this case I simply switch desired amount with current amount and change the sign of all capacity values, so then it becomes an equivalent problem with desired amount > current amount.

[Nazmul Quader Zinnuree]

Thanks Adrian,
I have worked to minimize my time. & now I'm getting WA after 5.660 sec. So, would you please give me some tricky samples?

[EfEr]

Adrian, I see you solution to this problem is the fastest. Did you use the approach of simulating over the LCM of the periods? I can't make it to run in the time limit.
Thanks.

[fh]

I don't understand sample case 2:

The input is

2 0
3 4
3 -3
100

Which mean there are:
1 inlet that will give 4 units in 3 secs and then idle 3 secs, etc..
1 outlet that will subtract 3 units in 3 secs and then idle 3 sec, etc..

So :
in time = 6, the processing unit will have 1 unit
in time = 12, the processing unit will have 2 unit
in time = 18, the processing unit will have 3 unit
in time = 24, the processing unit will have 4 unit
...
in time = 199, the processing unit will have 33.1667 unit

The minimum time according to the output is 199, but when you see above, in time = 199, the processing unit only has less than 34 unit (not even close to the desired amount 100).

Can anybody explain the sample case 2? how to get 199?

[little joey]

No, your interpretation is wrong:
3 4 means the inlet will give 4 units per second during the first 3 seconds and then be idle for 3 seconds
3 -3 means the outlet will take 3 units per second during the first 3 seconds and then be idle for 3 seconds

So in each in each 6 second period:
during 1st second: gain is 4 -3 = 1 unit
during 2nd second: gain is 4 -3 = 1 unit
during 3rd second: gain is 4 -3 = 1 unit
during 4th, 5th and 6th second: idle

So the tank gains 3 units in every 6 second period.
After 198 seconds it has gained 198/6 * 3 = 99 units, and in the next second an additional one to make 100.

[Cho]

[quote]Now a peculiar incident can occur