ADWFNSNW - A Dwarf - N Snow Whites

no tags 

Hôm nay RomanD3 trên đường đua về Đồ Sơn với hai nhóc lớp 10 bỗng nổi hứng phán một bài như sau:

Trên chặng đường đạp xe vất vả về Đồ Sơn, đội đua do chú lùn RomanD3 dẫn đầu gồm N nàng Bạch tuyết đi trên N chiếc xe đạp khác nhau, nhưng các nàng không ai chịu đi một mình cả :| Biết rằng nàng Bạch Tuyết thứ i muốn được chàng lùn nhà ta chở trong Ti phút, sau đó nàng có thể tự đi được trong Di phút, sau đó mà không được chở tiếp là nàng sẽ khóc :((; tuy vậy tình yêu đích thực của chàng RomanD3 lại là nàng Bạch Tuyết trên chiếc xe bus hồng Thịnh Hưng, để gặp được nàng, chàng ta phải chở mỗi nàng đi xe đạp đúng một lần, sau đó cần ít nhất 1 phút để lên bus!

Hãy giúp RomanD3 tính toán xem có kịp hay không!

Dữ liệu

- Dòng đầu tiên chứa số N.
- Trong N dòng tiếp theo, dòng thứ i chứa hai số Ti, Di.

Kết quả

- In ra -1 nếu chàng lùn không thể kịp, hoặc in ra thứ tự chở N nàng Bạch Tuyết trên cùng một dòng.

Ví dụ

Dữ liệu:
2
2 11
11 30

Kết quả:
2 1

Giới hạn

- 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

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?

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.

Re:
I don't understand your comment very much :|

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

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 :))