#想請教TOI線上練習賽的pA

1 messages · Page 1 of 1 (latest)

proper jackal
#

是這週進行嗎？

#

比賽進行中應該不能討論哦

#

可能要等禮拜五結束後再討論

clever prawn
woven tree
#

第一題我也想問

#

感覺二分搜就解決了

#

但範例測資對了，丟上去去wa

desert tangle
#

卡題目

woven tree
#

是這題八

# 
//wa
#include <bits/stdc++.h>
#define ll long long int
#define M 200005
using namespace std;
ll n,r;
ll a[M];

bool deal(ll money){
    for(int i = 0; i < n; i++){
        if(money%r!=0)money=money+(money/r)+1;
        else money=money+(money/r);
        money-=a[i];
        if(money<=0)return 1;
    }
    return (money<=0);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>r;
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    ll l=0,R=1e15,mid;
    while(R-l>1){
        mid=(l+R)/2;
        if(deal(mid))l=mid;
        else R=mid;
    }
    cout<<l<<'\n';
}
#

測測資感覺是對的

desert tangle
#

瞄了一下題目，我猜是溢位

woven tree
#

我有想過

#

可是第一子題也錯的說

#

第一子題的資料感覺怎樣都不會溢位

desert tangle
#

hmm題目說無條件進位至整數欸

woven tree
#

deal是在處理這個的

desert tangle
#

喔沒事我剛沒看懂你的處理方式

desert tangle
#

如果P=1，那每次的金額不都會是money+money/1

woven tree
#

🤨

woven tree
#

理論上最差不是100*100?

#

比較可能爆的應該只有1e15*n

desert tangle
#

我手邊沒電腦，你要不要自己試著把二分搜時的money變化印出來？

woven tree
#

阿哩

#

似乎溢蠻多的?

#

阿~它是複利阿

#

難怪長哪麼快

#

可是都用到long long了，而且money感覺是必要的

#

||用long long long||

hard oyster
#

發現之後扣不完當前金額就跳掉?

woven tree
#

嗯嗯嗯，好像可以欸