ABC085 C - Otoshidama

備忘録

問題

atcoder.jp

回答

"use strict"
function Main(input) {
  input = input.trim().split(' ').map(Number);
  let N = input[0];
  let Y = input[1];

  const h = 1e4;
  const m = 5e3;
  const l = 1e3;

  let rx = -1;
  let ry = -1;
  let rz = -1;
  for(let x=0; x<=N; ++x){
    for(let y=0; y<=N-x; ++y){
      let lz = (N-x-y)*l;
      let total = h*x + m*y + lz;
      if(total === Y) {
        rx = x;
        ry = y;
        rz = N-x-y;
      }
    }
  }


  console.log(rx,ry,rz);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

単純に3つのforループで計算を行うと制限時間を超過する。
xを1万円札の枚数、yを5000円札の枚数としたとき、
1000円札の枚数についてはN-x-y枚と求めることが出来るので、
forを一つ減らすことで制限時間内に答えを出せる。