10840 - Multi-stage Compressor

[Quantris]

Just wondering if anyone has a hint about this one (I realise only two people have it AC anyway).

It seems like a pretty simple problem if I'm reading it right.

Perhaps something is off with the judge's data?

[Martin Macko]

Actually I don't undestand the problem statement. I've read it so many times, but nothing helped. Is there anybody who understand the problem statement? Could you, please, explain it? Thanks.

[Darko]

I think that all that introduction is there just to say "we'll make it look like a real world problem, but it won't get anywhere close to being one..."

What they say (among other things) is that you are given the pressure in front of the compressor and the pressure behind the compressor and that there are n "stages" (sets of blades? rotors? not sure what the word is...). What they are asking is "What is the pressure behind (i-1)th 'stage'?"

From what they said about everything being ideal, seems like following is true:
p_n+1/p_n = p_n/p_n-1 = ... = p_3/p_2 = p_2/p_1 = k

So, k = (p_n+1/p_1)^(1/n) ?

And p_i = k^(i-1) ?

Well, that's what I tried, but it didn't work (works on the sample input, of course). I got WA after 2.5 secs (Java) and 0.5 sec (C).

There are no bounds on any of those, and I would've tried BigDecimal if UVa allowed it, but no luck there. So, if you have a BigDecimal library handy, go for it

Darko

[little joey]

Thanks Darko for clearing this out. This kind of insane problems really should be banned from UVA...

[Quantris]

Thanks to uDebug I finally got AC on this problem.

There is a discrepancy between the data and problem statement. The statement says to output p_i, but actually what works is to output p_i / p_1. In other words we want not the output pressure after stage i but the compression ratio after stage i.

This case (just the sample case with pressures doubled) illustrates it:

3
2 2 4 1
2 2 4 2
2 2 4 3

the AC output is (same as sample output):
1.00
1.41
2.00

but the real answers following the statement should be:
2.00
2.83
4.00
[ p1 <= p_i <= p_n+1 should be true ]

I don't know if we'd prefer to correct the statement to match the data, or the other way around.