[NOIP 2004 提高组] 津津的储蓄计划

知识点

模拟、余额管理、整数运算

解题思路

每月加入300元并扣除预算。若余额不足，立即输出负的月份编号；否则将整百金额存入银行，仅保留不足100的余额。年末将存款按1.2倍返还后与余额相加。

正确性说明

每月不变量为手中零钱等于按规则操作后的余额，银行存款等于此前每月存入的总额。依次模拟即得到真实过程；首次不足时当月必然失败，年末利息按总存款计算。

易错点

判断不足要在存钱之前；输出的是-month；利息不是每月复利。存款为100的倍数，用saved*12/10可精确得到整数结果。

复杂度

时间O(12)=O(1)，空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int cash=0,saved=0;
    for(int month=1;month<=12;++month){int cost;cin>>cost;cash+=300;
        if(cash<cost){cout<<-month<<'\n';return 0;}
        cash-=cost;saved+=cash/100*100;cash%=100;
    }
    cout<<cash+saved*12/10<<'\n';
}