yl-9/probench huggingface dataset:
# Digital Village (Hard Version)

## Problem Description

This is the hard version of the problem. In the three versions, the constraints on $ n $ and $ m $ are different. You can make hacks only if all the versions of the problem are solved.

Pak Chanek is setting up internet connections for the village of Khuntien. The village can be represented as a connected simple graph with $ n $ houses and $ m $ internet cables connecting house $ u_i $ and house $ v_i $ , each with a latency of $ w_i $ .

There are $ p $ houses that require internet. Pak Chanek can install servers in at most $ k $ of the houses. The houses that need internet will then be connected to one of the servers. However, since each cable has its latency, the latency experienced by house $ s_i $ requiring internet will be the maximum latency of the cables between that house and the server it is connected to.

For each $ k = 1,2,\ldots,n $ , help Pak Chanek determine the minimum total latency that can be achieved for all the houses requiring internet.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2000 $ ). The description of the test cases follows.

The first line of each test case contains three integers $ n $ , $ m $ , $ p $ ( $ 2 \le n \le 5000 $ ; $ n-1 \le m \le 5000 $ ; $ 1 \le p \le n $ ) — the number of houses, the number of cables, and the number of houses that need internet.

The second line of each test case contains $ p $ integers $ s_1, s_2, \ldots, s_p $ ( $ 1 \le s_i \le n $ ) — the houses that need internet. It is guaranteed that all elements of $ s $ are distinct.

The $ i $ -th of the next $ m $ lines of each test case contains three integers $ u_i $ , $ v_i $ , and $ w_i $ ( $ 1 \le u_i < v_i \le n $ ; $ 1 \le w_i \le 10^9 $ ) — the internet cable connecting house $ u_i $ and house $ v_i $ with latency of $ w_i $ . It is guaranteed that the given edges form a connected simple graph.

It is guaranteed that the sum of $ n $ and the sum of $ m $ do not exceed $ 5000 $ .

## Output Format

For each test case, output $ n $ integers: the minimum total latency that can be achieved for all the houses requiring internet for each $ k = 1,2,\ldots,n $ .

## Sample #1

### Sample Input #1

```
2
9 8 5
2 5 6 8 9
1 2 1
1 3 2
3 4 10
4 5 3
4 6 5
1 7 10
7 8 4
7 9 2
3 3 2
3 1
1 2 1
2 3 3
1 3 2
```

### Sample Output #1

```
34 19 9 4 0 0 0 0 0
2 0 0
```

## Hint

In the first test case for $ k=3 $ , a possible optimal solution is to install servers at vertices $ 2 $ , $ 6 $ and $ 8 $ and obtain the following latency:

- $ \text{latency}(2) = 0 $
- $ \text{latency}(5) = \max(3, 5) = 5 $
- $ \text{latency}(6) = 0 $
- $ \text{latency}(8) = 0 $
- $ \text{latency}(9) = \max(2, 4) = 4 $

So the total latency is $ 9 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: data structures, dp, dsu, graphs, math, trees
Difficulty: 2500
# Digital Village (Easy Version)

## Problem Description

This is the easy version of the problem. In the three versions, the constraints on $ n $ and $ m $ are different. You can make hacks only if all the versions of the problem are solved.

Pak Chanek is setting up internet connections for the village of Khuntien. The village can be represented as a connected simple graph with $ n $ houses and $ m $ internet cables connecting house $ u_i $ and house $ v_i $ , each with a latency of $ w_i $ .

There are $ p $ houses that require internet. Pak Chanek can install servers in at most $ k $ of the houses. The houses that need internet will then be connected to one of the servers. However, since each cable has its latency, the latency experienced by house $ s_i $ requiring internet will be the maximum latency of the cables between that house and the server it is connected to.

For each $ k = 1,2,\ldots,n $ , help Pak Chanek determine the minimum total latency that can be achieved for all the houses requiring internet.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows.

The first line of each test case contains three integers $ n $ , $ m $ , $ p $ ( $ 2 \le n \le 400 $ ; $ n-1 \le m \le 400 $ ; $ 1 \le p \le n $ ) — the number of houses, the number of cables and the number of houses that need internet.

The second line of each test case contains $ p $ integers $ s_1, s_2, \ldots, s_p $ ( $ 1 \le s_i \le n $ ) — the houses that need internet. It is guaranteed that all elements of $ s $ are distinct.

The $ i $ -th of the next $ m $ lines of each test case contains three integers $ u_i $ , $ v_i $ , and $ w_i $ ( $ 1 \le u_i < v_i \le n $ ; $ 1 \le w_i \le 10^9 $ ) — the internet cable connecting house $ u_i $ and house $ v_i $ with latency of $ w_i $ . It is guaranteed that the given edges form a connected simple graph.

It is guaranteed that the sum of $ n^3 $ and the sum of $ m^3 $ do not exceed $ 10^8 $ .

## Output Format

For each test case, output $ n $ integers: the minimum total latency that can be achieved for all the houses requiring internet for each $ k = 1,2,\ldots,n $ .

## Sample #1

### Sample Input #1

```
2
9 8 5
2 5 6 8 9
1 2 1
1 3 2
3 4 10
4 5 3
4 6 5
1 7 10
7 8 4
7 9 2
3 3 2
3 1
1 2 1
2 3 3
1 3 2
```

### Sample Output #1

```
34 19 9 4 0 0 0 0 0
2 0 0
```

## Hint

In the first test case for $ k=3 $ , a possible optimal solution is to install servers at vertices $ 2 $ , $ 6 $ and $ 8 $ and obtain the following latency:

- $ \text{latency}(2) = 0 $
- $ \text{latency}(5) = \max(3, 5) = 5 $
- $ \text{latency}(6) = 0 $
- $ \text{latency}(8) = 0 $
- $ \text{latency}(9) = \max(2, 4) = 4 $

So the total latency is $ 9 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, data structures, dfs and similar, dp, dsu, fft, graphs, greedy, implementation, math, trees
Difficulty: 2300
# Maximize Mex

## Problem Description

You are given an array $ a $ of $ n $ positive integers and an integer $ x $ . You can do the following two-step operation any (possibly zero) number of times:

1. Choose an index $ i $ ( $ 1 \leq i \leq n $ ).
2. Increase $ a_i $ by $ x $ , in other words $ a_i := a_i + x $ .

Find the maximum value of the $ \operatorname{MEX} $ of $ a $ if you perform the operations optimally.

The $ \operatorname{MEX} $ (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:

- The $ \operatorname{MEX} $ of $ [2,2,1] $ is $ 0 $ because $ 0 $ is not in the array.
- The $ \operatorname{MEX} $ of $ [3,1,0,1] $ is $ 2 $ because $ 0 $ and $ 1 $ are in the array but $ 2 $ is not.
- The $ \operatorname{MEX} $ of $ [0,3,1,2] $ is $ 4 $ because $ 0 $ , $ 1 $ , $ 2 $ and $ 3 $ are in the array but $ 4 $ is not.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ x $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le x \le 10^9 $ ) — the length of the array and the integer to be used in the operation.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the given array.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer: the maximum $ \operatorname{MEX} $ of $ a $ if you perform the operations optimally.

## Sample #1

### Sample Input #1

```
3
6 3
0 3 2 1 5 2
6 2
1 3 4 1 0 2
4 5
2 5 10 3
```

### Sample Output #1

```
4
6
0
```

## Hint

In the first test case, the $ \operatorname{MEX} $ of $ a $ is $ 4 $ without performing any operations, which is the maximum.

In the second test case, the $ \operatorname{MEX} $ of $ a $ is $ 5 $ without performing any operations. If we perform two operations both with $ i=1 $ , we will have the array $ a=[5,3,4,1,0,2] $ . Then, the $ \operatorname{MEX} $ of $ a $ will become $ 6 $ , which is the maximum.

In the third test case, the $ \operatorname{MEX} $ of $ a $ is $ 0 $ without performing any operations, which is the maximum.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, greedy, math, number theory
Difficulty: 1200
# Meaning Mean

## Problem Description

Pak Chanek has an array $ a $ of $ n $ positive integers. Since he is currently learning how to calculate the floored average of two numbers, he wants to practice it on his array $ a $ .

While the array $ a $ has at least two elements, Pak Chanek will perform the following three-step operation:

1. Pick two different indices $ i $ and $ j $ ( $ 1 \leq i, j \leq |a| $ ; $ i \neq j $ ), note that $ |a| $ denotes the current size of the array $ a $ .
2. Append $ \lfloor \frac{a_i+a_j}{2} \rfloor $ $ ^{\text{∗}} $ to the end of the array.
3. Remove elements $ a_i $ and $ a_j $ from the array and concatenate the remaining parts of the array.

For example, suppose that $ a=[5,4,3,2,1,1] $ . If we choose $ i=1 $ and $ j=5 $ , the resulting array will be $ a=[4,3,2,1,3] $ . If we choose $ i=4 $ and $ j=3 $ , the resulting array will be $ a=[5,4,1,1,2] $ .

After all operations, the array will consist of a single element $ x $ . Find the maximum possible value of $ x $ if Pak Chanek performs the operations optimally.

 $ ^{\text{∗}} $ $ \lfloor x \rfloor $ denotes the floor function of $ x $ , which is the greatest integer that is less than or equal to $ x $ . For example, $ \lfloor 6 \rfloor = 6 $ , $ \lfloor 2.5 \rfloor=2 $ , $ \lfloor -3.6 \rfloor=-4 $ and $ \lfloor \pi \rfloor=3 $

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 50 $ ) — the length of the array $ a $ .

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array $ a $ .

Do note that the sum of $ n $ over all test cases is not bounded.

## Output Format

For each test case, output a single integer: the maximum possible value of $ x $ after all numbers have been picked.

## Sample #1

### Sample Input #1

```
3
5
1 7 8 4 5
3
2 6 5
5
5 5 5 5 5
```

### Sample Output #1

```
6
4
5
```

## Hint

In the first test case, the array is initially $ a=[1,7,8,4,5] $ . Pak Chanek will perform the following operations:

1. Pick $ i=1 $ and $ j=2 $ , then $ a=[8,4,5,4] $ .
2. Pick $ i=3 $ and $ j=2 $ , then $ a=[8,4,4] $ .
3. Pick $ i=2 $ and $ j=3 $ , then $ a=[8,4] $ .
4. Pick $ i=1 $ and $ j=2 $ , then $ a=[6] $ .

After all the operations, the array consists of a single element $ x=6 $ . It can be proven that there is no series of operations that results in $ x $ greater than $ 6 $ in the end.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: data structures, greedy, math, sortings
Difficulty: 800
# Count Leaves

## Problem Description

Let $ n $ and $ d $ be positive integers. We build the the divisor tree $ T_{n,d} $ as follows:

- The root of the tree is a node marked with number $ n $ . This is the $ 0 $ -th layer of the tree.
- For each $ i $ from $ 0 $ to $ d - 1 $ , for each vertex of the $ i $ -th layer, do the following. If the current vertex is marked with $ x $ , create its children and mark them with all possible distinct divisors $ ^\dagger $ of $ x $ . These children will be in the $ (i+1) $ -st layer.
- The vertices on the $ d $ -th layer are the leaves of the tree.

For example, $ T_{6,2} $ (the divisor tree for $ n = 6 $ and $ d = 2 $ ) looks like this:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2020F/fe3509981f0e7cfbf5fabd59d7e6e5b6182b6f65.png)Define $ f(n,d) $ as the number of leaves in $ T_{n,d} $ .

Given integers $ n $ , $ k $ , and $ d $ , please compute $ \sum\limits_{i=1}^{n} f(i^k,d) $ , modulo $ 10^9+7 $ .

 $ ^\dagger $ In this problem, we say that an integer $ y $ is a divisor of $ x $ if $ y \ge 1 $ and there exists an integer $ z $ such that $ x = y \cdot z $ .

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The only line of each test case contains three integers $ n $ , $ k $ , and $ d $ ( $ 1 \le n \le 10^9 $ , $ 1 \le k,d \le 10^5 $ ).

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^9 $ .

## Output Format

For each test case, output $ \sum\limits_{i=1}^{n} f(i^k,d) $ , modulo $ 10^9+7 $ .

## Sample #1

### Sample Input #1

```
3
6 1 1
1 3 3
10 1 2
```

### Sample Output #1

```
14
1
53
```

## Hint

In the first test case, $ n = 6 $ , $ k = 1 $ , and $ d = 1 $ . Thus, we need to find the total number of leaves in the divisor trees $ T_{1,1} $ , $ T_{2,1} $ , $ T_{3,1} $ , $ T_{4,1} $ , $ T_{5,1} $ , $ T_{6,1} $ .

- $ T_{1,1} $ has only one leaf, which is marked with $ 1 $ .
- $ T_{2,1} $ has two leaves, marked with $ 1 $ and $ 2 $ .
- $ T_{3,1} $ has two leaves, marked with $ 1 $ and $ 3 $ .
- $ T_{4,1} $ has three leaves, marked with $ 1 $ , $ 2 $ , and $ 4 $ .
- $ T_{5,1} $ has two leaves, marked with $ 1 $ and $ 5 $ .
- $ T_{6,1} $ has four leaves, marked with $ 1 $ , $ 2 $ , $ 3 $ , and $ 6 $ .

The total number of leaves is $ 1 + 2 + 2 + 3 + 2 + 4 = 14 $ .

In the second test case, $ n = 1 $ , $ k = 3 $ , $ d = 3 $ . Thus, we need to find the number of leaves in $ T_{1,3} $ , because $ 1^3 = 1 $ . This tree has only one leaf, so the answer is $ 1 $ .

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: dp, math, number theory
Difficulty: 2900
# Connect the Dots

## Problem Description

One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a twist.

To play the game, Alice draws a straight line and marks $ n $ points on it, indexed from $ 1 $ to $ n $ . Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs $ m $ operations of the following type:

- She picks three integers $ a_i $ , $ d_i $ ( $ 1 \le d_i \le 10 $ ), and $ k_i $ .
- She selects points $ a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i $ and connects each pair of these points with arcs.

After performing all $ m $ operations, she wants to know the number of connected components $ ^\dagger $ these points form. Please help her find this number.

 $ ^\dagger $ Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le m \le 2 \cdot 10^5 $ ).

The $ i $ -th of the following $ m $ lines contains three integers $ a_i $ , $ d_i $ , and $ k_i $ ( $ 1 \le a_i \le a_i + k_i\cdot d_i \le n $ , $ 1 \le d_i \le 10 $ , $ 0 \le k_i \le n $ ).

It is guaranteed that both the sum of $ n $ and the sum of $ m $ over all test cases do not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output the number of connected components.

## Sample #1

### Sample Input #1

```
3
10 2
1 2 4
2 2 4
100 1
19 2 4
100 3
1 2 5
7 2 6
17 2 31
```

### Sample Output #1

```
2
96
61
```

## Hint

In the first test case, there are $ n = 10 $ points. The first operation joins the points $ 1 $ , $ 3 $ , $ 5 $ , $ 7 $ , and $ 9 $ . The second operation joins the points $ 2 $ , $ 4 $ , $ 6 $ , $ 8 $ , and $ 10 $ . There are thus two connected components: $ \{1, 3, 5, 7, 9\} $ and $ \{2, 4, 6, 8, 10\} $ .

In the second test case, there are $ n = 100 $ points. The only operation joins the points $ 19 $ , $ 21 $ , $ 23 $ , $ 25 $ , and $ 27 $ . Now all of them form a single connected component of size $ 5 $ . The other $ 95 $ points form single-point connected components. Thus, the answer is $ 1 + 95 = 96 $ .

In the third test case, there are $ n = 100 $ points. After the operations, all odd points from $ 1 $ to $ 79 $ will be in one connected component of size $ 40 $ . The other $ 60 $ points form single-point connected components. Thus, the answer is $ 1 + 60 = 61 $ .

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: brute force, dp, dsu, graphs, math, trees
Difficulty: 1800
# Bitwise Balancing

## Problem Description

You are given three non-negative integers $ b $ , $ c $ , and $ d $ .

Please find a non-negative integer $ a \in [0, 2^{61}] $ such that $ (a\, |\, b)-(a\, \&\, c)=d $ , where $ | $ and $ \& $ denote the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR) and the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND), respectively.

If such an $ a $ exists, print its value. If there is no solution, print a single integer $ -1 $ . If there are multiple solutions, print any of them.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). The description of the test cases follows.

The only line of each test case contains three positive integers $ b $ , $ c $ , and $ d $ ( $ 0 \le b, c, d \le 10^{18} $ ).

## Output Format

For each test case, output the value of $ a $ , or $ -1 $ if there is no solution. Please note that $ a $ must be non-negative and cannot exceed $ 2^{61} $ .

## Sample #1

### Sample Input #1

```
3
2 2 2
4 2 6
10 2 14
```

### Sample Output #1

```
0
-1
12
```

## Hint

In the first test case, $ (0\,|\,2)-(0\,\&\,2)=2-0=2 $ . So, $ a = 0 $ is a correct answer.

In the second test case, no value of $ a $ satisfies the equation.

In the third test case, $ (12\,|\,10)-(12\,\&\,2)=14-0=14 $ . So, $ a = 12 $ is a correct answer.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, hashing, implementation, math, schedules, ternary search
Difficulty: 1400
# Brightness Begins

## Problem Description

Imagine you have $ n $ light bulbs numbered $ 1, 2, \ldots, n $ . Initially, all bulbs are on. To flip the state of a bulb means to turn it off if it used to be on, and to turn it on otherwise.

Next, you do the following:

- for each $ i = 1, 2, \ldots, n $ , flip the state of all bulbs $ j $ such that $ j $ is divisible by $ i^\dagger $ .

After performing all operations, there will be several bulbs that are still on. Your goal is to make this number exactly $ k $ .

Find the smallest suitable $ n $ such that after performing the operations there will be exactly $ k $ bulbs on. We can show that an answer always exists.

 $ ^\dagger $ An integer $ x $ is divisible by $ y $ if there exists an integer $ z $ such that $ x = y\cdot z $ .

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The only line of each test case contains a single integer $ k $ ( $ 1 \le k \le 10^{18} $ ).

## Output Format

For each test case, output $ n $ — the minimum number of bulbs.

## Sample #1

### Sample Input #1

```
3
1
3
8
```

### Sample Output #1

```
2
5
11
```

## Hint

In the first test case, the minimum number of bulbs is $ 2 $ . Let's denote the state of all bulbs with an array, where $ 1 $ corresponds to a turned on bulb, and $ 0 $ corresponds to a turned off bulb. Initially, the array is $ [1, 1] $ .

- After performing the operation with $ i = 1 $ , the array becomes $ [\underline{0}, \underline{0}] $ .
- After performing the operation with $ i = 2 $ , the array becomes $ [0, \underline{1}] $ .

In the end, there are $ k = 1 $ bulbs on. We can also show that the answer cannot be less than $ 2 $ .

In the second test case, the minimum number of bulbs is $ 5 $ . Initially, the array is $ [1, 1, 1, 1, 1] $ .

- After performing the operation with $ i = 1 $ , the array becomes $ [\underline{0}, \underline{0}, \underline{0}, \underline{0}, \underline{0}] $ .
- After performing the operation with $ i = 2 $ , the array becomes $ [0, \underline{1}, 0, \underline{1}, 0] $ .
- After performing the operation with $ i = 3 $ , the array becomes $ [0, 1, \underline{1}, 1, 0] $ .
- After performing the operation with $ i = 4 $ , the array becomes $ [0, 1, 1, \underline{0}, 0] $ .
- After performing the operation with $ i = 5 $ , the array becomes $ [0, 1, 1, 0, \underline{1}] $ .

In the end, there are $ k = 3 $ bulbs on. We can also show that the answer cannot be smaller than $ 5 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: binary search, math
Difficulty: 1200
# Find Minimum Operations

## Problem Description

You are given two integers $ n $ and $ k $ .

In one operation, you can subtract any power of $ k $ from $ n $ . Formally, in one operation, you can replace $ n $ by $ (n-k^x) $ for any non-negative integer $ x $ .

Find the minimum number of operations required to make $ n $ equal to $ 0 $ .

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The only line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 10^9 $ ).

## Output Format

For each test case, output the minimum number of operations on a new line.

## Sample #1

### Sample Input #1

```
6
5 2
3 5
16 4
100 3
6492 10
10 1
```

### Sample Output #1

```
2
3
1
4
21
10
```

## Hint

In the first test case, $ n = 5 $ and $ k = 2 $ . We can perform the following sequence of operations:

1. Subtract $ 2^0 = 1 $ from $ 5 $ . The current value of $ n $ becomes $ 5 - 1 = 4 $ .
2. Subtract $ 2^2 = 4 $ from $ 4 $ . The current value of $ n $ becomes $ 4 - 4 = 0 $ .

It can be shown that there is no way to make $ n $ equal to $ 0 $ in less than $ 2 $ operations. Thus, $ 2 $ is the answer.

In the second test case, $ n = 3 $ and $ k = 5 $ . We can perform the following sequence of operations:

1. Subtract $ 5^0 = 1 $ from $ 3 $ . The current value of $ n $ becomes $ 3 - 1 = 2 $ .
2. Subtract $ 5^0 = 1 $ from $ 2 $ . The current value of $ n $ becomes $ 2 - 1 = 1 $ .
3. Subtract $ 5^0 = 1 $ from $ 1 $ . The current value of $ n $ becomes $ 1 - 1 = 0 $ .

It can be shown that there is no way to make $ n $ equal to $ 0 $ in less than $ 3 $ operations. Thus, $ 3 $ is the answer.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: bitmasks, brute force, greedy, math, number theory
Difficulty: 800