a003: 不能Brute Force的糖果問題
標籤 : Level1700 數論
通過比率 : 67% (2 人 / 3 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-11-22 20:40

內容 :

阿軒走到了新化市集,想幫她女朋友買慶生糖果

首先,新化市集是一個圓環狀的市集,這個市集有些店家會供應糖果

而阿軒想著,如果我繞著順時鐘轉,我要繞多少次才能買到最大想要的糖果數量(設阿軒的錢無限,因為阿軒的爸是郭台銘)

請注意,由於阿軒想要多走點路有益身體健康,他一次只會買一包,而且經過如果可以買,就一定要買。

 

若阿軒想買38顆糖果,新化市集有三家店,都是一包五顆糖果

則阿軒最多可以買35顆,因為剩下三顆沒有任何一家店肯提供

若阿軒想要買40顆糖果,新化市集有三家店,都是一包100顆糖果

則阿軒不能在新化市集買任何的糖果

 

例如第一筆測資

她可以先去第一家買五顆,剩下32顆要買

第二家買兩顆,剩下30顆要買

第三家買五顆,還有25顆要買

又繞回了第一家,買了五顆,剩下20顆要買,以此類推

直到最後,他總共逛了10家才買完剛好38顆糖果

 

請問阿軒最少需要在新化市集逛多少家,才能買到最大不超過的糖果數量?

 

輸入說明

輸入只有一筆

第一行有兩個數字N,M,第一個數字N為新化市集有多少家賣糖果的店(1<=N<=200000)

第二個數字M為阿軒最多想要買的糖果數量(1<=N<=10¹⁸)

接下來第二行有N個數字,代表每家市集一次供應的糖果數量(1<= 供應之糖果數量 <= 2³²-1)

輸出說明

請輸入阿軒需要逛多少家才能買到最大不超過的糖果數量

範例輸入
範例測資一
3 38 
5 2 5

範例測資二
5 21
2 4 100 2 6
範例輸出
測資一解答
10

測資二解答
6
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (16%): 2.0s , <1K
公開 測資點#1 (16%): 2.0s , <1K
公開 測資點#2 (17%): 2.0s , <1M
公開 測資點#3 (17%): 2.0s , <10M
公開 測資點#4 (17%): 2.0s , <1M
公開 測資點#5 (17%): 2.0s , <10M
提示 :

第0、1個測資點是範例測資

 

第0個測資點,阿軒可以這樣買:5→2→5→5→2→5→5→2→5→2

第1個測資點,阿軒可以這樣買:2→4→2→6→2→4

標籤:
Level1700 數論
出處:
Educational Codeforces Round 53 [編輯: han910625 (賤萌兔CutieRabbit) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」