EX17 - 果物屋さんでお買い物 / 2.02 /

Time Limit: 2 sec / Memory Limit: 256 MB

説明ページに戻る

問題文

ある果物屋では、リンゴ・パイナップルがそれぞれN個売られています。i個目のリンゴ、パイナップルはそれぞれA_i円、P_i円です。

リンゴ・パイナップルをそれぞれ1つずつ選んで購入しようとするとき、合計金額が丁度S円になるような買い方が何通りあるか求めてください。

ただし、同じ値段の同じ種類の商品でも区別します。たとえば同じ値段のリンゴが複数あった場合、それらを買う場合は別の買い方として数えます。パイナップルについても同様です。また、リンゴ・パイナップルを買う順番は考慮しないものとします。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S;
  cin >> N >> S;
  vector<int> A(N), P(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> P.at(i);
  }

  // リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
  // ここにプログラムを追記
}

制約

  • 0≦N≦100
  • 0≦S≦1000
  • 1≦A_i, P_i≦500 (1 ≦ i ≦ N)
  • A_i, P_i (1 ≦ i ≦ N)は整数

入力

入力は次の形式で標準入力から与えられます。

N S
A_1 A_2 \cdots A_N
P_1 P_2 \cdots P_N

出力

リンゴ・パイナップルをそれぞれ1つずつ購入しようとするとき、合計金額が丁度S円になるような 買い方が何通りあるかを出力してください。

出力の最後には改行が必要です。


ジャッジでは以下の入力例以外のケースに関してもテストされることに注意。

入力例1

3 400
100 100 130
270 300 250

出力例1

3

合計が400円になる買い方は以下の3通りです。
1つ目のリンゴ、2つ目のパイナップルを購入すると、100円 + 300円 = 400円となります。
2つ目のリンゴ、2つ目のパイナップルを購入すると、100円 + 300円 = 400円となります。
3つ目のリンゴ、1つ目のパイナップルを購入すると、130円 + 270円 = 400円となります。
1つ目のリンゴと2つ目のリンゴがどちらも100円ですが、別の買い方として数えることに注意してください。

入力例2

10 600
70 110 90 120 90 20 260 150 220 150
170 100 250 350 60 280 450 460 20 220

出力例2

2

入力例3

3 200
100 100 100
100 100 100

出力例3

9

入力例4

1 0
100
200

出力例4

0

合計0円で買うことはできません。


ヒント

  1. ループを使わないで書く
  2. パターンを見つける
  3. ループで書き直す

に沿って書く場合の流れをヒントで説明します。

まずは自分で考えてみて、詰まったら見てみましょう。

ヒント1 (ループを使わないで書く)

クリックでヒントを見る

合計がS円になるような買い方が何通りあるかを求めるので、 すべての組み合わせをif文で確認できれば答えが求まるはずです。

一般のNでは考えにくいので、試してみるときはNを小さい値で仮定してみるとよいです。 N = 3のケースを全て書き出してみます。(添え字として0始まりの値を使っている点に注意してください。)

  int ans = 0;

  if (A.at(0) + P.at(0) == S) {
    ans++;
  }
  if (A.at(0) + P.at(1) == S) {
    ans++;
  }
  if (A.at(0) + P.at(2) == S) {
    ans++;
  }

  if (A.at(1) + P.at(0) == S) {
    ans++;
  }
  if (A.at(1) + P.at(1) == S) {
    ans++;
  }
  if (A.at(1) + P.at(2) == S) {
    ans++;
  }

  if (A.at(2) + P.at(0) == S) {
    ans++;
  }
  if (A.at(2) + P.at(1) == S) {
    ans++;
  }
  if (A.at(2) + P.at(2) == S) {
    ans++;
  }

添え字の変化に着目するとパターン化できそうです。

ヒント2 (パターンを見つける)

クリックでヒントを見る 変数i, jを導入してi番目のリンゴ、j番目のパイナップルを買う場合を考えます。 条件式は次のようになります。

if (A.at(i) + P.at(j) == S) {
  ans++;
}

あとはi, jを網羅的に動かして上の文を実行できればよいです。

ヒント3 (ループで書き直す)

クリックでヒントを見る

変数i, jを導入してi番目のリンゴ、j番目のパイナップルを買う場合の判定文は次のようになります。

if (A.at(i) + P.at(j) == S) {
  ans++;
}

i, jはそれぞれ別々に0からN - 1までの値を取ります。
このように変数(ここではi, j)の組み合わせを列挙したい場合は、多重ループを用います。
今回の場合は変数がi, jの2つなので、次のような二重ループになります。

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      // i, jを使う
    }
  }


解答例

必ず自分で問題に挑戦してみてから見てください。

クリックで解答例を見る

解答例1

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S;
  cin >> N >> S;
  vector<int> A(N), P(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> P.at(i);
  }

  // リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
  int ans = 0;  // 買い方が何通りあるか

  // 実際に全ての買い方を試してみて、合計がS円ならカウントアップ
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (A.at(i) + P.at(j) == S) {
        ans++;
      }
    }
  }

  cout << ans << endl;
}

解答例2 (範囲for文を用いた解法)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S;
  cin >> N >> S;
  vector<int> A(N), P(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> P.at(i);
  }

  // リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
  int ans = 0;  // 買い方が何通りあるか

  // 実際に全ての買い方を試してみて、合計がS円ならカウントアップ
  for (int x : A) {
    for (int y : P) {
      if (x + y == S) {
        ans++;
      }
    }
  }

  cout << ans << endl;
}