問題一覧 > 通常問題

No.2244 Integer Complete

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : shobonvip / テスター : noya2 👑 Nachia
お気に入りにしたユーザー ProblemId : 9087 / 自分の提出
問題文最終更新日: 2023-03-10 01:22:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 380 (順位表) の他の問題:

Problem Statement

Shobon-kun is currently absorbed in a card game called "Integer Complete". In this card game, you prepare $2$ decks, deck $A$ and deck $B$, and put some cards into each deck.

Shobon-kun has put $N$ cards $A_1, A_2, \cdots, A_N$ into deck $A$ and $M$ cards $B_1, B_2, \cdots, B_M$ into deck $B$. In "Integer Complete", you battle by placing integers on the field. An integer can be placed on the field by performing the following [Action].

[Action] Choose a card $A_i ~ (1 \le i \le N)$ from deck $A$ and $1$ integer $x$ satisfying $A_i^2 \le x \lt (A_i+1)^2$. Next, choose a card $B_j ~ (1 \le j \le M)$ from deck $B$ and $1$ integer $y$ satisfying $B_j^2 \le y \lt (B_j+1)^2$. Then, place the product $xy$ of $x$ and $y$ on the field.

Find the smallest positive integer that Shobon-kun cannot place on the field.

Constraints

  • All inputs are integers
  • $1 \le N, M \le 3 \times 10^4$
  • $1 \le A_1 < A_2 < \cdots < A_N \le 3 \times 10^4$
  • $1 \le B_1 < B_2 < \cdots < B_M \le 3 \times 10^4$

Input

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$ 
$B_1$ $B_2$ $\cdots$ $B_M$

Output

Output the smallest positive integer that Shobon-kun cannot place on the field.

It can be shown that an answer exists under the constraints.

Sample

Sample 1
Input
2 1
1 2
1
Output
11

The integers that can be chosen from deck $A$ are $1, 2, 3, 4, 5, 6, 7, 8$, and the integers that can be chosen from deck $B$ are $1, 2, 3$. For example, for the positive integer $10$, you can choose $5$ from deck $A$ and $2$ from deck $B$ to place their product, $10$, on the field.

All positive integers less than or equal to $10$ can be placed on the field. However, no matter how you choose integers from deck $A$ and deck $B$, you cannot place the positive integer $11$ on the field. Therefore, output $11$.

Sample 2
Input
1 1
1
2
Output
1

The integers that can be chosen from deck $A$ are $1, 2, 3$, and the integers that can be chosen from deck $B$ are $4, 5, 6, 7, 8$. No matter how you choose integers from deck $A$ and deck $B$, you cannot place $1$ on the field, so output $1$.

Sample 3
Input
2 3
1 2
1 3 4
Output
25

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。