4532 . B1. 情報とお釣りとラーメン

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

AaW 最喜歡拉麵了，no ramen no life！

身為一個專業的拉麵廚，全世界的拉麵他都吃過，而除了有豐富的拉麵品嚐經驗和感想外，AaW 還有腎臟病！但 AaW 的腎臟病該如何解決不是一個非醫生的人可以解決的問題，所以我們暫且不談。

故事是這樣子的：
2023 年 3 月 5 號是一個風和日麗的周末，除了一部分的人要考臺灣國際資訊奧林匹亞初選外，大家都過得相當愉快，但很不巧的 AaW 剛好是那一部份的人，作為建國中學數理資優班的電神，以及建國中學電子計算機研習社萬中選一的學術長，不去考個資奧初選好像說不過去？
於是 AaW 和他的快樂夥伴們就去資奧初選好好燒了一波雞，為了撫平他的朋友沒進選訓營受傷的心情，AaW 決定和他的快樂夥伴一起去附近的拉麵店吃拉麵！但在點餐時，AaW 發現了一個大問題，他的錢包裡面有太多零錢了，如果在零錢數量超過 22504 枚前沒有把它們處理掉的話，AaW 的錢包就會因為質量過大坍塌成黑洞！為了解決這個問題，AaW 希望能夠把他的錢包裡面的錢花掉越多越好。
雖然說只是要把錢包中的錢花掉越多越好，但其實沒有想像中的那麼簡單。一大問題是菜單上的拉麵太多了，菜單上有各種不同價位的拉麵，而 AaW 想要找到可以讓他用掉最多硬幣的拉麵，但他身上帶了太多錢，拉麵的種類也太多了，他不知道要買哪一個可以解決他的問題，於是他想到了可以用寫程式的方法來解決他的問題，但 AaW 又發現自己的電腦因為跑火車專題燒起來了！雖然你可以借他電腦但你怕被他盜帳號，所以你決定自己寫一個程式來幫吳亞倫解決他的問題。

Input Format

首先，AaW 會告訴你兩個數字 n 和 m，分別代表拉麵的數量和 AaW 錢包中錢幣的數量，接下來一行會有 n 個數字，代表每碗拉麵的價錢 p1∼pn，最後一行則會有 m 個數字，分別代表 AaW 擁有的錢幣面額 c1∼cm。

Output Format

在同一行輸出兩個數字，可以花費最多硬幣的拉麵編號以及花費的硬幣數量，如果買不了，幫 AaW 輸出 −1，如果有多碗拉麵同時為花費最多硬幣的拉麵，請輸出編號最小的；不考慮可以找錢的情況，因為你也不知道店家找給你的硬幣面額會是什麼，如果他找給你的都是一塊就糟糕了。

Sample Input 1

2 5
225 27
2 2 5 2 7

Sample Output 1

-1

Sample Input 2

4 8
170 190 200 240
100 100 10 10 10 10 10 10

Sample Output 2

4 6

Hints

對於 19% 的測試資料 n=1 m∈[1,10] p≤500 c≤50

對於 13% 的測試資料 n≤5 m∈[1,20] p≤500 c≤2000

對於 11% 的測試資料 n∈[1,225] m∈[1,25] p≤1000 c≤2048

對於 26% 的測試資料 n∈[1,25×103] m∈[1,105] p≤103 c≤210

對於 31% 的測試資料 n∈[1,105] m∈[1,104] p≤104 c≤230

Subtasks

No. Testdata Range Constraints Score
1 0~6 n=1 m∈[1,10] p≤500 c≤50 19
2 7~11 n≤5 m∈[1,20] p≤500 c≤2000 13
3 12~16 n∈[1,225] m∈[1,25] p≤1000 c≤2048 11
4 17~30 n∈[1,25×103] m∈[1,105] p≤103 c≤210 26
5 31~35 n∈[1,105] m∈[1,104] p≤104 c≤230 31

TopCoder

807
學長對不起

User's AC Ratio

80.0% (4/5)

Tags

111學術上機考 學術上機考

Problem Source

111學年度建北電資指定科目考試【資訊科上機考】

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2
10 1000 65536 65536 2
11 1000 65536 65536 2
12 1000 65536 65536 3
13 1000 65536 65536 3
14 1000 65536 65536 3
15 1000 65536 65536 3
16 1000 65536 65536 3
17 1000 65536 65536 4
18 1000 65536 65536 4
19 1000 65536 65536 4
20 1000 65536 65536 4
21 1000 65536 65536 4
22 1000 65536 65536 4
23 1000 65536 65536 4
24 1000 65536 65536 4
25 1000 65536 65536 4
26 1000 65536 65536 4
27 1000 65536 65536 4
28 1000 65536 65536 4
29 1000 65536 65536 4
30 1000 65536 65536 4
31 1000 65536 65536 5
32 1000 65536 65536 5
33 1000 65536 65536 5
34 1000 65536 65536 5
35 1000 65536 65536 5
Submit
Back to Top