English · Original
Chinese · Translation
Formal · Original
The last stage of Football World Cup is played using the play-off system.
There are _n_ teams left in this stage, they are enumerated from 1 to _n_. Several rounds are held, in each round the remaining teams are sorted in the order of their ids, then the first in this order plays with the second, the third — with the fourth, the fifth — with the sixth, and so on. It is guaranteed that in each round there is even number of teams. The winner of each game advances to the next round, the loser is eliminated from the tournament, there are no draws. In the last round there is the only game with two remaining teams: the round is called the Final, the winner is called the champion, and the tournament is over.
Arkady wants his two favorite teams to play in the Final. Unfortunately, the team ids are already determined, and it may happen that it is impossible for teams to meet in the Final, because they are to meet in some earlier stage, if they are strong enough. Determine, in which round the teams with ids _a_ and _b_ can meet.
## Input
The only line contains three integers _n_, _a_ and _b_ (2 ≤ _n_ ≤ 256, 1 ≤ _a_, _b_ ≤ _n_) — the total number of teams, and the ids of the teams that Arkady is interested in.
It is guaranteed that _n_ is such that in each round an even number of team advance, and that _a_ and _b_ are not equal.
## Output
In the only line print "_Final!_" (without quotes), if teams _a_ and _b_ can meet in the Final.
Otherwise, print a single integer — the number of the round in which teams _a_ and _b_ can meet. The round are enumerated from 1.
[samples]
## Note
In the first example teams 1 and 2 meet in the first round.
In the second example teams 2 and 6 can only meet in the third round, which is the Final, if they win all their opponents in earlier rounds.
In the third example the teams with ids 7 and 5 can meet in the second round, if they win their opponents in the first round.
足球世界杯的最后一阶段采用淘汰赛制。
目前剩下 #cf_span[n] 支球队，编号从 #cf_span[1] 到 #cf_span[n]。比赛进行若干轮，每轮中剩余的球队按其编号排序，然后第 1 名与第 2 名比赛，第 3 名与第 4 名比赛，第 5 名与第 6 名比赛，依此类推。保证每轮球队数量均为偶数。每场比赛的胜者晋级下一轮，败者被淘汰，没有平局。最后一轮只有两支球队参赛：这一轮称为决赛，胜者称为冠军，赛事至此结束。
阿尔卡迪希望他最喜欢的两支球队能在决赛中相遇。但球队编号已经确定，如果这两支球队在更早的轮次中就可能相遇（如果他们都足够强大），那么他们可能无法在决赛中相遇。请确定编号为 #cf_span[a] 和 #cf_span[b] 的两支球队将在第几轮相遇。
输入仅一行，包含三个整数 #cf_span[n]、#cf_span[a] 和 #cf_span[b]（#cf_span[2 ≤ n ≤ 256]，#cf_span[1 ≤ a, b ≤ n]）——球队总数以及阿尔卡迪感兴趣的两支球队的编号。
保证 #cf_span[n] 的取值使得每轮晋级的球队数均为偶数，且 #cf_span[a] 和 #cf_span[b] 不相等。
若两支编号为 #cf_span[a] 和 #cf_span[b] 的球队能在决赛中相遇，请在唯一一行输出 "_Final!_"（不含引号）。
否则，请输出一个整数——两支球队可能相遇的轮次编号。轮次从 #cf_span[1] 开始编号。
在第一个示例中，编号为 #cf_span[1] 和 #cf_span[2] 的球队在第一轮相遇。
在第二个示例中，编号为 #cf_span[2] 和 #cf_span[6] 的球队只有在赢得此前所有比赛的情况下，才可能在第三轮（即决赛）相遇。
在第三个示例中，编号为 #cf_span[7] 和 #cf_span[5] 的球队若在第一轮均获胜，则可能在第二轮相遇。
## Input
仅一行包含三个整数 #cf_span[n]、#cf_span[a] 和 #cf_span[b]（#cf_span[2 ≤ n ≤ 256]，#cf_span[1 ≤ a, b ≤ n]）——球队总数以及阿尔卡迪感兴趣的两支球队的编号。保证 #cf_span[n] 的取值使得每轮晋级的球队数均为偶数，且 #cf_span[a] 和 #cf_span[b] 不相等。
## Output
仅一行输出：若编号为 #cf_span[a] 和 #cf_span[b] 的球队能在决赛中相遇，则输出 "_Final!_"（不含引号）；否则输出一个整数，表示两支球队可能相遇的轮次编号。轮次从 #cf_span[1] 开始编号。
[samples]
## Note
在第一个示例中，编号为 #cf_span[1] 和 #cf_span[2] 的球队在第一轮相遇。
在第二个示例中，编号为 #cf_span[2] 和 #cf_span[6] 的球队只有在赢得此前所有比赛的情况下，才可能在第三轮（即决赛）相遇。
在第三个示例中，编号为 #cf_span[7] 和 #cf_span[5] 的球队若在第一轮均获胜，则可能在第二轮相遇。
Let $ n $ be the number of teams, and let $ a, b $ be the IDs of two distinct teams, with $ 1 \leq a, b \leq n $, $ a \neq b $.
The tournament proceeds in rounds $ r = 1, 2, \dots, \log_2 n $, where in round $ r $, $ \frac{n}{2^{r-1}} $ teams remain, paired as $ (1,2), (3,4), \dots $ in sorted order by ID.
Two teams $ a $ and $ b $ can meet in round $ r $ if and only if they are in the same bracket of size $ 2^r $, but in different sub-brackets of size $ 2^{r-1} $.
Define the bracket index of a team $ x $ in round $ r $ as:
$$
\text{bracket}_r(x) = \left\lfloor \frac{x - 1}{2^{r-1}} \right\rfloor
$$
Then, teams $ a $ and $ b $ meet in round $ r $ if:
$$
\text{bracket}_r(a) = \text{bracket}_r(b) \quad \text{and} \quad \text{bracket}_{r-1}(a) \neq \text{bracket}_{r-1}(b)
$$
For $ r = 1 $, define $ \text{bracket}_0(x) = -1 $ (or any value different from all others), so the condition reduces to $ \text{bracket}_1(a) = \text{bracket}_1(b) $.
Let $ R $ be the smallest round $ r \in \{1, 2, \dots, \log_2 n\} $ such that $ \text{bracket}_r(a) = \text{bracket}_r(b) $.
Then:
- If $ R = \log_2 n $, output `"Final!"`.
- Otherwise, output $ R $.
---
**Formal Output:**
Let $ k = \log_2 n $.
Let $ r = \min \left\{ i \in \{1, 2, \dots, k\} \ \middle|\ \left\lfloor \frac{a - 1}{2^{i-1}} \right\rfloor = \left\lfloor \frac{b - 1}{2^{i-1}} \right\rfloor \right\} $.
If $ r = k $, output `"Final!"`.
Else, output $ r $.
API Response (JSON)
{
"problem": {
"name": "A. World Cup",
"description": {
"content": "The last stage of Football World Cup is played using the play-off system. There are _n_ teams left in this stage, they are enumerated from 1 to _n_. Several rounds are held, in each round the remaini",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF944A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The last stage of Football World Cup is played using the play-off system.\n\nThere are _n_ teams left in this stage, they are enumerated from 1 to _n_. Several rounds are held, in each round the remaini...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "足球世界杯的最后一阶段采用淘汰赛制。\n\n目前剩下 #cf_span[n] 支球队，编号从 #cf_span[1] 到 #cf_span[n]。比赛进行若干轮，每轮中剩余的球队按其编号排序，然后第 1 名与第 2 名比赛，第 3 名与第 4 名比赛，第 5 名与第 6 名比赛，依此类推。保证每轮球队数量均为偶数。每场比赛的胜者晋级下一轮，败者被淘汰，没有平局。最后一轮只有两支球队参赛：这一轮称为决赛...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ be the number of teams, and let $ a, b $ be the IDs of two distinct teams, with $ 1 \\leq a, b \\leq n $, $ a \\neq b $.\n\nThe tournament proceeds in rounds $ r = 1, 2, \\dots, \\log_2 n $, where ...",
"is_translate": false,
"language": "Formal"
}
]
}