SBOOST - Need For Speed
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Bessie đang tân trang và nâng cấp chiếc xe ô tô của cô ta để chuẩn bị cho cuộc đua ô tô Grand Prix nổi tiếng. Cô ta muốn mua thêm một số linh kiện nhằm tăng tối đa khả năng của ô tô. Ban đầu xe ô tô có khối lượng M(1<= M <=1000) và lực chạy F(1<= F <=1000000). Cửa hàng có N (1<= N <=10000) loại linh kiện được đánh số từ 1..N,mỗi loại linh kiện chỉ có một chiếc duy nhất.
Loại thứ i nếu được sử dụng, sẽ làm cho khối lượng ô tô tăng M[i] và lực tăng F[i]. Định luật thứ II của Newton cho biết, a=f/m , trong đó là f là lực, m là khối lượng, và a là gia tốc vật đạt được . Bessie muốn chọn một số loại linh kiện để bổ sung vào cho ô tô, sau cho Gia tốc đạt được là lớn nhất, đồng thời khối lượng ô tô càng bé càng tốt. Cô ta nên chọn loại những linh kiện nào ?
Input
-Dòng đầu tiên là 3 số tự nhiên f,m,n.
-Dòng thứ 2..N+1 , dòng thứ i là hai số f[i], m[i] , cách nhau bởi ít nhất một dấu cách.
Output
-Nếu không cần thêm linh kiện nào, in ra "NONE", ngược lại in ra các loại linh kiện được chọn, mỗi loại in trên một dòng. Bạn cần phải in ra theo thứ tự tăng dần.
Example
Input:
1500 100 4
250 25
150 9
120 5
200 8
Output:
2
3
4
- Người up: company_1
- Nguồn bài: USACO Mar 10 - Silver division