ADWFNSNW - A Dwarf - N Snow Whites

no tags 

Today RomanD3 wants to race his old bicycle to Do Son beach with two friends of his, on his way he thought out a problem named "A Dwarf - N Snow Whites":

On his hard way to Do Son beach, he races with N Snow White racing on N different bicycles, but none of them wants to go alone. Given that the ith Snow White wants to be taken by the dwarf RomanD3 for Ti minute(s), then she can go alone for (only) Di minute(s) (she will cry after that); RomanD3 wants to "escape" from them soon to go... by bus with the N+1th Snow White on the bus (whom he likes), so he must take each Snow White exactly one time but not let any of them cry; then he needs at least one minute to go with his lady (in dream ;)) ).

Please help him to determine whether he can do or not.


- The first line contains number N.
- Next N line(s), the ith line contains two numbers Ti, Di.


- Print out -1 whether he can not "escape" from them or print out the order of serving them before he can jump on the bus ;))


2 11
11 30

2 1


- n ≤ 105.

hide comments
Alexander: 2010-11-12 12:50:55

Ti and Di are integers (at least scanf doesn't balk).

I keep getting WA though. Am I right in surmising that when D rode all bicycles and there is still at least one minute before any snow white starts to cry, then, and only then, D has made it?

Furthermore, what's with ambiguous input? For example

1 9
2 8
3 7

should have six valid outputs:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Is one preferred over the others, or is the judge smart enough to accept any of them?

Adamax: 2010-07-02 07:20:28

Are Ti and Di integers?

[Trichromatic] XilinX: 2009-06-11 07:53:50

I don't understand the problem statement. Maybe a further example is needed.

Re: I think the prob stat is quite clear :-)
but I can explain the eg.:
If the order is 1->2: the dwarf (D) needs 2 min(s) to take the first Snow White (SW), then she can go alone for 11 min(s); while D must spend 11 min(s) more taking the 2nd SW before jumping on the bus, but after 11 min(s) the 1st SW will cry >> BAD solution

If the order is 2->1: GOOD solution, D has 11 min(s) to go on the bus before the 1st SW crys.

ok ;) sorry for my bad Eng

Last edit: 2009-05-27 01:41:51
Robert Gerbicz: 2009-06-11 07:53:50

It's a little Chinese for me.

I don't understand your comment very much :|

Last edit: 2009-05-26 01:54:22

Added by:AnhDQ
Time limit:0.100s-1.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:AnhDQ - RomanD3 :))