d040. 11207 - The easiest way
標籤 :
通過比率 : 436人/575人 ( 76% ) [非即時]
評分方式:
Tolerant

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

內容

背景

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

 

問題

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
20491 tommy1232343 ... (星雨) d040
1345 2020-01-30 17:35