Overview

Given N cards, we determine whether there exists a combination of selecting 2 or more cards such that the product of the numbers on the front sides equals the product of the numbers on the back sides. If such a combination exists, we find the minimum number of cards.

Analysis

Each card has an integer \(P_i\) written on the front and an integer \(Q_i\) written on the back. We need to check whether there exists a subset \(S\) (\(|S| \geq 2\)) such that: $\( \prod_{i \in S} P_i = \prod_{i \in S} Q_i \)$

A naive approach would be to try all subsets, but since N is at most 22, the number of subsets is \(2^N\), which is approximately 4 million at most. Furthermore, computing the product for each subset adds to the overall computation. However, since N is small, performing a brute-force search is practical.

The key idea is to incrementally increase the number of selected cards starting from 2, and output the count as soon as we find the first combination that satisfies the condition. This ensures we find the minimum size.

Also, since \(P_i, Q_i \leq 100\), the products stay within a manageable range, and using a language with arbitrary-precision integers like Python allows us to compute them directly without overflow concerns.

Algorithm

1. Read the card information from input.
2. Incrementally increase the number of selected cards size from 2 to N.
3. For each size, generate all combinations of choosing size cards from the N cards (using combinations).
4. For each combination, compute the product of \(P_i\) values and the product of \(Q_i\) values of the selected cards.
5. If both products are equal, output that size and terminate.
6. If no valid combination is found after trying all possibilities, output -1.

Example

For instance, given the following cards:

3
2 3
6 4
3 2

With size=2, selecting cards (2,3) and (6,4): - Product of fronts: \(2 \times 6 = 12\) - Product of backs: \(3 \times 4 = 12\)

The condition is satisfied, so the answer is 2.

Complexity

• Time complexity: \(O(N \cdot 2^N \cdot N) = O(N^2 \cdot 2^N)\)
  • For each size, we generate combinations (at most \(O(2^N)\)), and computing the product for each combination takes at most \(O(N)\).
• Space complexity: \(O(N)\)
  • For storing the card information and temporary memory used during combination generation.

Implementation Notes

• By using Python’s itertools.combinations, we can easily enumerate combinations of a specified size.

• Products are computed iteratively within loops. In languages where overflow can occur, extra care is needed (though this is not an issue in Python).

• To find the minimum size, process sizes in ascending order and return as soon as the condition is satisfied for the first time.

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.