## 10840 - Multi-stage Compressor

Moderator: Board moderators

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am

### 10840 - Multi-stage Compressor

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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10840 WA ?

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks Darko for clearing this out. This kind of insane problems really should be banned from UVA...
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am

### Re: 10840 - Multi-stage Compressor

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.