Problem Statement
Quang and Nam are playing a game.
Nam has N stones.
Quang has secretly chosen two integers L and R such that 1 <= L <= R <= N. The integers between L and R, inclusive, are called good. All other integers are called bad.
Nam's task is to determine the values L and R.
Nam can ask Quang an abitrary number of questions. For each question, Nam will partition all N stones into one or more non-empty piles. He will then show the partition to Quang and ask: "Are all these pile sizes good?" Quang will always truthfully answer "yes" or "no".
Nam is very smart, so he can deduce all information contained in Quang's answers. On the other hand, he does not want to guess, so he will only announce the pair (L, R) if he is 100% sure what the two numbers are.
Given N, count all admissible pairs (L, R) such that Nam can win the game.
Definition
- Class:
- QuangAndNam
- Method:
- count
- Parameters:
- int
- Returns:
- long
- Method signature:
- long count(int N)
- (be sure your method is public)
Constraints
- N will be between 1 and 10^6, inclusive.
Examples
2
Returns: 3
For N = 2 there are 3 possible pairs (L, R) Quang can choose: (1, 1), (1, 2) and (2, 2). Nam can play the game as follows: Partition the stones into two piles, each containing a single stone. Show the configuration to Quang. If he gets the answer "no", he can deduce that L = R = 2, and he wins the game. Leave both stones on the same pile. Show the configuration to Quang. If he gets the answer "yes" in both cases, Quang chose L = 1 and R = 2. If the second answer was "no", we must have L = R = 1. Thus, for N = 2 Nam can always win the game.
3
Returns: 4
Nam can only win the game if the pair (L, R) chosen by Quang is one of the pairs (1, 1), (1, 2), (1, 3) and (2, 2). If Quang chooses one of the pairs (2, 3) or (3, 3), Nam will not be able to win the game. In both situations, Nam will get the answer "yes" if he shows Quang all three stones on the same pile, and the answer "no" for all other partitions of stones. In more detail, suppose (L, R) = (2, 3) and Nam produces the partition with two stones on one pile and one stone on the other pile. When Quang looks at this partition, he sees pile sizes 2 and 1. The number 2 is good, but the number 1 is bad. Hence, the correct answer to the question "Are all these pile sizes good?" is "no".
10
Returns: 23
1
Returns: 1
4
Returns: 6
5
Returns: 6
6
Returns: 10
7
Returns: 11
8
Returns: 15
9
Returns: 17
11
Returns: 25
12
Returns: 33
13
Returns: 34
14
Returns: 42
15
Returns: 47
16
Returns: 53
17
Returns: 58
18
Returns: 70
19
Returns: 73
20
Returns: 83
21
Returns: 91
22
Returns: 101
23
Returns: 105
24
Returns: 121
25
Returns: 124
26
Returns: 138
27
Returns: 150
28
Returns: 161
29
Returns: 166
30
Returns: 189
31
Returns: 194
32
Returns: 208
33
Returns: 222
34
Returns: 235
35
Returns: 246
36
Returns: 269
37
Returns: 275
38
Returns: 293
39
Returns: 309
40
Returns: 327
41
Returns: 335
42
Returns: 364
43
Returns: 372
44
Returns: 394
45
Returns: 412
46
Returns: 430
47
Returns: 442
48
Returns: 475
49
Returns: 485
50
Returns: 507
1000000
Returns: 205138958927
999999
Returns: 205138533612
999998
Returns: 205138046754
999997
Returns: 205137651796
999996
Returns: 205137385009
999995
Returns: 205136779329
999994
Returns: 205136451170
999993
Returns: 205136083918
999992
Returns: 205135622848
999991
Returns: 205135178181
999990
Returns: 205134907429
999989
Returns: 205134316940
999988
Returns: 205134018497
999987
Returns: 205133608558
999986
Returns: 205133130789
999985
Returns: 205132744451
999984
Returns: 205132458248
999983
Returns: 205131842507
999982
Returns: 205131530918
999981
Returns: 205131164995
999980
Returns: 205130704950
999979
Returns: 205130250126
999978
Returns: 205129973336
999977
Returns: 205129398652
999976
Returns: 205129100281
999975
Returns: 205128695501
999974
Returns: 205128200329
999973
Returns: 205127805538
999972
Returns: 205127539642
999971
Returns: 205126927605
999970
Returns: 205126618901
999969
Returns: 205126233499
999968
Returns: 205125769756
999967
Returns: 205125329887
999966
Returns: 205125050828
999965
Returns: 205124486406
999964
Returns: 205124173587
999963
Returns: 205123760726
999962
Returns: 205123280512
999961
Returns: 205122885560
999960
Returns: 205122629135
999959
Returns: 205121994403
999958
Returns: 205121682840
999957
Returns: 205121318579
999956
Returns: 205120847692
999955
Returns: 205120418471
999954
Returns: 205120122356
999953
Returns: 205119550237
999952
Returns: 205119253121
999951
Returns: 205118841186
197723
Returns: 8019726211
897596
Returns: 165275999111
812037
Returns: 135269439881
204741
Returns: 8599166621
422750
Returns: 36661860081
106756
Returns: 2337918534
776557
Returns: 123707067831
129191
Returns: 3423796382
445299
Returns: 40677198105
357328
Returns: 26192773675
589993
Returns: 71407089378
558854
Returns: 64068453059
594306
Returns: 72454985382
580633
Returns: 69159370242
354348
Returns: 25757745388
75203
Returns: 1160138873
67792
Returns: 942756569
50673
Returns: 526737856
41137
Returns: 347137002
30109
Returns: 185961654
31682
Returns: 205900019
44918
Returns: 413882285
28923
Returns: 171601501
86636
Returns: 1539712515
41665
Returns: 356105872
57464
Returns: 677378695
66010
Returns: 893843615
91874
Returns: 1731520424
81741
Returns: 1370641665
41418
Returns: 351900395
9867
Returns: 19969999
9228
Returns: 17467833
3178
Returns: 2071156
1029
Returns: 217036
1748
Returns: 626389
1295
Returns: 343637
4325
Returns: 3835994
6494
Returns: 8649395
8059
Returns: 13321089
5926
Returns: 7202686
840
Returns: 144682
888
Returns: 161672
344
Returns: 24202
979
Returns: 196353
584
Returns: 69829
727
Returns: 108226
219
Returns: 9800
290
Returns: 17184
302
Returns: 18639
487
Returns: 48528