| Submit | All submissions | Best solutions | Back to list |
ADWFNSNW - A Dwarf - N Snow Whites |
| English | Tiếng Việt |
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.
Input
- The first line contains number N.
- Next N line(s), the ith line contains two numbers Ti, Di.
Output
- 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 ;))
Example
Input: 2 2 11 11 30 Output: 2 1
Limitations
- n ≤ 105.
| Added by: | AnhDQ |
| Date: | 2009-05-25 |
| 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 :)) |
hide comments
|
2010-11-12 12:50:55 Alexander
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 3 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? |
|
|
2010-07-02 07:20:28 Adamax
Are Ti and Di integers? |
|
|
2009-06-11 07:53:50 [Trichromatic] XilinX
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 |
|
|
2009-06-11 07:53:50 Robert Gerbicz
It's a little Chinese for me. Re: I don't understand your comment very much :| Last edit: 2009-05-26 01:54:22 |
RSS