Overview

Given N cards, the problem asks to determine whether there exists a way to select 2 or more cards such that the product of the front-side numbers equals the product of the back-side numbers, and if so, find the minimum number of cards.

Analysis

Since the constraint is \(N \leq 22\), which is relatively small, we can consider examining all combinations (subsets) of cards. The front and back numbers of each card are at most 100, and the product can become extremely large — even selecting all 22 cards could yield an astronomically large value of \(100^{22}\). However, due to the nature of the problem, we need to directly compare whether the products of the front and back sides are equal.

A straightforward approach is to examine all subsets (\(2^N - 1\) possibilities) and check whether the product of the front sides equals the product of the back sides. For N=22, the number of subsets is approximately 4.2 million, which is well within the range that modern computers can handle.

Algorithm

We adopt a brute-force algorithm using bitmasks. Specifically:

1. Generate all bitmasks from 0 to \(2^N - 1\) (each bit represents the selection state of a card)
2. For each bitmask, count the number of selected cards (skip if fewer than 2)
3. Calculate the product of the front-side numbers and the product of the back-side numbers for the selected cards
4. If both products are equal and the number of cards is smaller than the current minimum, update the minimum
5. After examining all combinations, output the minimum number of cards if a valid combination exists, otherwise output -1

Complexity

• Time complexity: \(O(2^N \cdot N)\)
  • There are \(2^N\) subsets
  • For each subset, we check N bits and compute the products
• Space complexity: \(O(N)\)
  • Only memory for storing card information is used

Implementation Notes

• Each bit of the bitmask corresponds to the selection state of a card (1< selects the i-th card)

• Care should be taken regarding integer overflow when computing products, but in Python this is not an issue since it automatically handles arbitrary-precision integers

• The initial value for the minimum is set to infinity (float('inf')), and it is updated only when a valid combination is found

• As a pruning optimization, combinations with more cards than the current minimum are skipped to improve efficiency

  Source Code

import sys
from math import gcd
from functools import reduce

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    cards = []
    index = 1
    for i in range(n):
        p = int(data[index]); q = int(data[index+1]); index += 2
        cards.append((p, q))
        
    if n < 2:
        print(-1)
        return
        
    min_size = float('inf')
    
    for bitmask in range(1, 1 << n):
        size = bin(bitmask).count('1')
        if size < 2:
            continue
            
        if size >= min_size:
            continue
            
        prod_p = 1
        prod_q = 1
        for i in range(n):
            if bitmask & (1 << i):
                prod_p *= cards[i][0]
                prod_q *= cards[i][1]
                
        if prod_p == prod_q:
            min_size = min(min_size, size)
            
    if min_size != float('inf'):
        print(min_size)
    else:
        print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.