Problem Statement
You have just entered a knockout tournament with N competitors. The tournament is structured as follows: at the start, the competitors are written down in a list. Adjacent competitors in the list are then paired off, starting from the first competitor on the list, and each pair plays a match (competitor 1 plays against 2, 3 plays against 4, etc.). The losers of each match are eliminated and their names are crossed off the list, while the winners progress to the next round. If there are an odd number of competitors in a round, then the last competitor in the list advances to the next round automatically, without having to play a match. This process then repeats with the new list of competitors, until only a single competitor remains, who is declared the winner. Note that the ordering of the competitors is preserved between rounds.
Your arch-rival has also entered the tournament and you want to know when you might end up playing against him. Your position in the list for the first round is you and your rival's position is rival (both indexed from 1). Assuming that both you and your rival win all the matches before you play each other, return the number of the round in which you will meet (counting the rounds from 1).
Definition
- Class:
- KnockoutTourney
- Method:
- meetRival
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int meetRival(int N, int you, int rival)
- (be sure your method is public)
Constraints
- N will be between 2 and 100000, inclusive.
- you and rival will each be between 1 and N, inclusive.
- you and rival will be distinct.
Examples
16
1
2
Returns: 1
This is a 4 round tournament, with 16 players, so every player plays a match in every round. You are paired with your rival in the first round.
16
8
9
Returns: 4
Despite being adjacent in the list, you are not paired with your rival until the final round.
1000
20
31
Returns: 4
65536
1000
35000
Returns: 16
60000
101
891
Returns: 10
22179
20695
13642
Returns: 15
7470
32
3599
Returns: 12
5465
1097
2191
Returns: 12
25905
15364
13876
Returns: 12
32332
10747
25408
Returns: 15
27113
18492
3937
Returns: 15
22829
6868
17061
Returns: 15
4805
1038
3555
Returns: 12
18881
1349
8675
Returns: 14
16614
11673
4493
Returns: 14
18690
5178
9086
Returns: 14
4567
3170
2409
Returns: 11
13880
2443
10440
Returns: 14
17960
8781
281
Returns: 14
31465
19518
15883
Returns: 15
30505
8313
26107
Returns: 15
21190
3939
3334
Returns: 10
28220
19615
14928
Returns: 15
9428
8183
6497
Returns: 11
13674
5939
9232
Returns: 14
3452
325
1459
Returns: 11
11341
1633
4121
Returns: 13
20821
16283
4661
Returns: 14
23908
2998
7072
Returns: 13
32447
12872
23083
Returns: 15
20333
19357
6940
Returns: 15
6302
4373
6204
Returns: 12
27491
6132
9031
Returns: 14
20199
8501
12532
Returns: 13
6946
4552
6119
Returns: 11
6581
1775
1405
Returns: 10
19944
9204
5983
Returns: 14
4635
2967
4474
Returns: 13
26415
10463
11071
Returns: 10
12279
6076
4719
Returns: 11
4494
842
4253
Returns: 13
13931
1951
5717
Returns: 13
21156
883
3474
Returns: 12
8399
6677
275
Returns: 13
24124
951
12786
Returns: 14
24622
11206
4898
Returns: 14
22056
6127
3996
Returns: 13
15798
4549
13812
Returns: 14
12684
5073
1971
Returns: 13
20638
6531
2660
Returns: 13
16773
3253
8915
Returns: 14
13933
12521
1280
Returns: 14
634
69
203
Returns: 8
12977
2618
10958
Returns: 14
28788
507
23593
Returns: 15
35772
19909
28276
Returns: 14
85333
74710
81786
Returns: 13
92474
87470
45897
Returns: 17
72055
55469
57183
Returns: 11
89464
37596
71464
Returns: 17
23309
1441
20998
Returns: 15
675
440
152
Returns: 9
35129
25712
29707
Returns: 13
5199
4095
530
Returns: 12
70677
50736
4140
Returns: 16
100000
1
10000
Returns: 14
43532
353
2355
Returns: 12
3
3
1
Returns: 2
3
3
2
Returns: 2
5
5
1
Returns: 3
101
13
51
Returns: 6
9
1
9
Returns: 4
9
8
9
Returns: 4
1000
8
9
Returns: 4
6
5
2
Returns: 3
1000
4
3
Returns: 1
10000
10000
1
Returns: 14
10
1
9
Returns: 4
30
27
3
Returns: 5
16
2
1
Returns: 1
100000
321
99999
Returns: 17
100000
1
100000
Returns: 17
9
2
1
Returns: 1
49
20
21
Returns: 3
8
4
5
Returns: 3
1000
2
1
Returns: 1
1000
7
8
Returns: 1
2
2
1
Returns: 1
13
12
13
Returns: 3
7
6
5
Returns: 1
100000
2
3
Returns: 2
16
14
15
Returns: 2
13
2
3
Returns: 2
2
1
2
Returns: 1
4
2
1
Returns: 1
100
100
1
Returns: 7
5
4
5
Returns: 3
6
5
1
Returns: 3
100000
8
9
Returns: 4
11
5
6
Returns: 1
15
15
1
Returns: 4
100
49
51
Returns: 2
9999
5001
7
Returns: 13
16
16
14
Returns: 2
4
2
3
Returns: 2
10
10
1
Returns: 4
20
9
10
Returns: 1
10
5
6
Returns: 1
17
17
1
Returns: 5
5
2
1
Returns: 1
98997
76579
26
Returns: 17
10000
3
2
Returns: 2
65535
64
65534
Returns: 16
7
4
7
Returns: 3
16
7
9
Returns: 4
16
10
1
Returns: 4
10
7
8
Returns: 1
5
1
5
Returns: 3
3
1
3
Returns: 2
100000
5681
99999
Returns: 17