AtCoder Beginner Contest #085 C問題 - Otoshidama

Source

AtCoder Beginner Contest #085
問題文

問題概要

この問題では紙幣は $10000$ 円札,$5000$ 円札,$1000$ 円札のみを考える.
お年玉は $N$ 枚の紙幣で合計金額が $Y$ 円だったという情報が与えられる.
実際に,$N$ 枚の紙幣で合計が $Y$ 円になる紙幣の組み合わせを $1$ つ出力する問題.
矛盾しているならそれを指摘する.

解法

$1000$ 円札の枚数,$5000$ 円札の枚数を全探索する.
残りの $10000$ 円札の枚数は合計が $N$ 枚であることから求まる.
それで,合計金額が $Y$ になっているかどうかを判定すれば良い.
時間計算量は $O(N^2)$ 程度.
$1000$ 円札の枚数を $x$ としたとき,$Y - 1000x$ が $5000$ の倍数になっていなければ枝刈り,などをやっても良い ($5$ 倍程度速くなる,以下のコードも参照).
オーダーを改善したければ,どれか $1$ つの紙幣の枚数を全探索し,残りは方程式を解いて求める,などとしても良い.

cLayversion 20180107-1)のコード

C++に変換後のコードはこちら

int N, Y;
{
  int i, j, k;
  
  rd(N,Y);
  Y /= 1000;

  for(i=Y%5;i<=N;i+=5) rep(j,N+1-i){
    k = N - i - j;
    if(i+5j+10k==Y){
      wt(k,j,i);
      return 0;
    }
  }
  wt(-1,-1,-1);
}

Current time: 2021年09月18日04時31分41秒
Last modified: 2018年01月07日23時02分01秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC085 ABC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: