ABC085 C - お年玉

Calendar Clock iconCalendar Clock icon

atcoder

目次

# 問題

https://atcoder.jp/contests/abc085/tasks/abc085_c

2つの整数NNYYが与えられて、10000円、5000円、1000円のお札を合計NN枚使ってYYが作れるか.
また作れるならその組み合わせの1例をあげる問題.

# 解説

10000円札、5000円札、1000円札の枚数をそれぞれaabbccとおく.
2つの方程式が得られる.
また、お札の枚数なので(3)が得られる.

{a+b+c=N(1)10000a+5000b+1000c=Y(2)0a,b,cN(3)\begin{cases} a + b + c = N (1) \\ 10000a + 5000b + 1000c = Y (2) \\ 0 \leq a, b, c \leq N (3) \end{cases}

(1)より、aabbが決まればccは一意に定まる.

c=Nabc = N - a - b

このときこのaabbccについて(2) (3)を満たす組み合わせを初めて見つけた時、出力して終了.

# 計算量

O(N2)O(N^2)

aabbの組み合わせの全列挙に2重ループ.

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
#define MAX_N 2001
#define MAX_Y 20000001

Int N, Y;

void input() {
  cin >> N >> Y;
}

void solve() {
  loop(a,0,N+1) {
    loop(b,0,N+1) {
      Int c = N - a - b;
      if (a + b > N || c < 0) continue;
      if (a * 10000 + b * 5000 + c * 1000 == Y) {
        cout << a << ' ' << b << ' ' << c << endl;
        return;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}

リモートフリーランス。ウェブサービス、スマホアプリエンジニア。
東アジアを拠点に世界を移動しながら活動してます!

お仕事のご依頼・お問い合わせはこちら

コメント