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$ つの紙幣の枚数を全探索し，残りは方程式を解いて求める，などとしても良い．

cLay（version 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: 2024年04月20日12時47分50秒
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)

ログイン：