d040. 11207 - The easiest way
Tags :
Accepted rate : 441人/583人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 15:00

Content

背景

身為 Murcia 奧林匹亞程式競賽的選手,你的目標就是要拿到越多的紙鳥越好。但是今年的題目好難… 所以你決定要用最簡單的方法:自己做紙鳥。

 

問題

你要做 4 隻相同大小的紙鳥來假裝你已做出了 4 題——這樣就可以晉級 SWERC 2007 了。現在有 N 張不同大小的長方形紙張可用。每張紙,i,的寛度為 w 高度為 h。你的工作就要選一張可以做出最大的 4 隻鳥的紙張。你需要考慮到,做一隻鳥需要一張正方形的紙。紙張可以截切,但不可以黏接。如果有多個最佳選擇,你要顯示第一個。

Input
輸入中會有多組測試。每組測試的第一行為紙張的張數,N。接下來的 N 行包含了紙張的尺寸;每一行有兩個整數:w 和 h。當 N = 0 時輸入結束。
Output
對於每組測試 (N = 0 的那組除外),要輸出能做出最大的紙鳥的那張紙的號碼。第一張為 1,第二張為 2,以此類推。如果有好幾個解,輸出第一個。
Sample Input #1
3
10 20
40 8
12 12
3
140 122
122 140
100 170
2
120 170
71 500
0
Sample Output #1
2
1
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
出處:
UVa11207 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
20491 tommy1232343 ... (星雨) d040
1493 2020-01-30 17:35