概要

N枚のカードから2枚以上を選ぶとき、選んだカードの表面の数の積と裏面の数の積が等しくなる組み合わせが存在するかを判定し、存在すればその最小の枚数を求めます。

考察

各カードには表に整数 \(P_i\)、裏に整数 \(Q_i\) が書かれており、ある部分集合 \(S\)（\(|S| \geq 2\)）について、
$\( \prod_{i \in S} P_i = \prod_{i \in S} Q_i \)$
が成り立つかどうかを調べる必要があります。

素朴な方法として、すべての部分集合を試すことを考えますが、Nが最大22なので、部分集合の個数は \(2^N\) で最大約400万通りあります。さらに各部分集合に対して積を計算するので、全体で計算量が非常に大きくなります。しかし、Nが小さいことを利用して、全探索を行うことが現実的です。

重要なのは、「選ぶカードの枚数」を2枚から順に増やしていき、初めて条件を満たすものが見つかった時点でその枚数を出力することです。これにより最小のサイズを求めることができます。

また、\(P_i, Q_i \leq 100\) であることから、積がオーバーフローしない範囲であり、Pythonのように任意精度の整数を持つ言語を使えばそのまま計算できます。

アルゴリズム

1. 入力からカード情報を読み込みます。
2. 選ぶカードの枚数 size を 2 から N まで順に増やしていきます。
3. 各 size に対して、N枚の中から size 枚を選ぶすべての組み合わせを生成します（combinationsを使用）。
4. 各組み合わせに対し、選ばれたカードの \(P_i\) の積と \(Q_i\) の積をそれぞれ計算します。
5. 両者が一致すればその size を出力し、終了します。
6. 全ての組み合わせを試しても見つからない場合は -1 を出力します。

例

例えば、カードが以下の場合：

3
2 3
6 4
3 2

size=2で (2,3) と (6,4) を選ぶと、 - 表の積：\(2 \times 6 = 12\) - 裏の積：\(3 \times 4 = 12\)

となり、条件を満たすので答えは 2 になります。

計算量

• 時間計算量: \(O(N \cdot 2^N \cdot N) = O(N^2 \cdot 2^N)\)
  • 各sizeに対して組み合わせを生成し（最大 \(O(2^N)\)）、各組み合わせ内で積を計算するのに最大 \(O(N)\) かかる。
• 空間計算量: \(O(N)\)
  • カード情報の保存と、組み合わせ生成時に一時的に使用するメモリ。

実装のポイント

• Pythonの itertools.combinations を使うことで、指定した枚数の組み合わせを簡単に列挙できます。

• 積の計算はループ内で逐次的に行い、途中でオーバーフローする言語では注意が必要です（ただしPythonでは問題ありません）。

• 最小のsizeを探すために、sizeを昇順に処理し、最初に条件を満たした時点でreturnするようにしましょう。

  ソースコード

from itertools import combinations

def main():
    N = int(input())
    cards = [tuple(map(int, input().split())) for _ in range(N)]
    
    # 部分集合を要素数が小さい順に探索
    for size in range(2, N + 1):
        for subset in combinations(range(N), size):
            prod_p = 1
            prod_q = 1
            for i in subset:
                prod_p *= cards[i][0]
                prod_q *= cards[i][1]
            if prod_p == prod_q:
                print(size)
                return
    print(-1)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。