yl-9/probench huggingface dataset:
# Grid Game

## Problem Description

Claire loves drawing lines. She receives a sheet of paper with an $ n \times n $ grid and begins drawing "lines" on it. Well—the concept of a "line" here is not what we usually think of. Claire refers each line to be a set of consecutive vertical grid cells. When she draws a line, these cells are all covered with black ink. Initially, all the cells are white, and drawing lines turns some of them black. After drawing a few lines, Claire wonders: how many ways she can color an additional white cell black so that the remaining white cells do not form a single connected component.

Two cells are directly connected if they share an edge. Two cells $ x $ and $ y $ are indirectly connected if there exists a sequence of cells $ c_0, c_1, \ldots, c_k $ with $ k > 1 $ such that $ c_0 = x $ , $ c_k = y $ , and for every $ i \in \{1, 2, \ldots, k\} $ the cells $ c_i $ and $ c_{i-1} $ are directly connected. A set of cells forms a single connected component if each pair of cells in the set is either directly or indirectly connected.

The grid has $ n $ rows and $ n $ columns, both indexed from $ 1 $ to $ n $ . Claire will draw $ q $ lines. The $ i $ -th line is drawn in the $ y_i $ -th column, from the $ s_i $ -th row to the $ f_i $ -th row, where $ s_i \leq f_i $ for each $ i \in \{1, 2, \ldots, q\} $ . Note that the cells that are passed by at least one of the $ q $ lines are colored black. The following figure shows an example of a $ 20\times 20 $ grid with $ q=67 $ lines. The grid cells marked with red star symbols refer to the cells such that, if Claire colors that cell black, all white cells no longer form a single connected component.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041G/34528cf71cdc006466f176fdbe6936874dda2994.png)You may assume that, after drawing the $ q $ lines, the remaining white cells form a single connected component with at least three white cells.

## Input Format

The first line contains exactly one integer $ t $ , indicating the number of test cases. For each test case, it begins with a line containing exactly two integers $ n $ and $ q $ . This indicates that the grid is $ n $ by $ n $ and that Claire draws $ q $ lines on it. Then $ q $ lines follow. For each $ i \in \{1, 2, \ldots, q\} $ , the $ i $ -th line among the $ q $ lines contains exactly three integers $ y_i $ , $ s_i $ , and $ f_i $ .

- $ 1\le t \le 125 $
- $ 2\leq n \leq 10^9 $
- $ q\ge 1 $ ; the sum of all $ q $ values is at most $ 10^5 $ .
- $ 1\leq y_i \leq n $
- $ 1\leq s_i \leq f_i \leq n $
- There are at least three white cells and all white cells form a connected component.

## Output Format

Print an integer on a line, indicating how many ways Claire can color an additional white cell black so that the remaining white cells do not form a single connected component.

## Sample #1

### Sample Input #1

```
2
3 1
2 1 2
5 2
2 1 4
4 2 5
```

### Sample Output #1

```
5
15
```

## Limit



Time Limit
4.00s

Memory Limit
1000.00MB

Difficulty: 3100
# Segmentation Folds

## Problem Description

Peter loves folding segments. There is a segment on a number line occupying the interval $ [\ell, r] $ . Since it is the prime time for folding the segments, Peter decides to fold the segment carefully. In each step, he chooses one of the two following operations whenever possible:

1. Operation $ \tt{LTR} $ : he folds the segment from left to right, where $ \ell $ coincides with a point $ x $ ( $ \ell < x \le r $ ) such that $ \ell+x $ is a prime number $ ^{\text{∗}} $ . When Peter chooses this operation, he always chooses the largest possible value $ x $ . Note that the segment occupies the interval $ [\frac{1}{2}(\ell+x), r] $ afterwards.
2. Operation $ \tt{RTL} $ : he folds the segment from right to left, where $ r $ coincides with a point $ x $ ( $ \ell \le x < r $ ) such that $ r+x $ is a prime number. When Peter chooses this operation, he always chooses the smallest possible value $ x $ . Note that the segment occupies the interval $ [\ell, \frac{1}{2}(r+x)] $ afterwards.

A folding sequence refers to a sequence of operations specified above. Peter wants to fold the segment several times, resulting in the shortest possible interval whose length that cannot be further reduced. The length of an interval $ [\ell, r] $ is defined naturally to be $ r-\ell $ . Let's consider the following example. Suppose that we are folding a segment initially occupying the interval $ [1, 30] $ . There are three folding sequences that lead to the shortest possible resulting interval, as shown in the following figure.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041F/be032bc113ac39f401b84d34f2c5f31947b110d1.png)Please help Peter determine the number of folding sequences such that the resulting interval has a shortest possible length. Output the number modulo $ 998244353 $ .

 $ ^{\text{∗}} $ Recall that an integer $ p>1 $ is a prime number if there do not exist integers $ a, b>1 $ such that $ p=ab $ .

## Input Format

The first line contains an integer $ t $ , denoting the number of test cases. In each of the following $ t $ lines, there are two integers $ \ell $ and $ r $ .

- $ 1 \le t \le 10 $
- $ 1 \le \ell < r \le 10^{12} $
- $ r - \ell \le 10^5 $

## Output Format

For each test case, please output a line denoting the number of ways to fold the given segment such that the resulting segment has the shortest possible length, modulo $ 998244353 $ .

## Sample #1

### Sample Input #1

```
3
1 30
16 18
142857 240135
```

### Sample Output #1

```
3
1
63
```

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: brute force, dfs and similar, number theory
Difficulty: 2400
# Beautiful Array

## Problem Description

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041E/123e9f2378be455eca9fba5ff4bfa308ab2b1a77.png) Image generated by ChatGPT 4o.A-Ming's birthday is coming and his friend A-May decided to give him an integer array as a present. A-Ming has two favorite numbers $ a $ and $ b $ , and he thinks an array is beautiful if its mean is exactly $ a $ and its median is exactly $ b $ . Please help A-May find a beautiful array so her gift can impress A-Ming.

The mean of an array is its sum divided by its length. For example, the mean of array $ [3, -1, 5, 5] $ is $ 12 \div 4 = 3 $ .

The median of an array is its middle element after sorting if its length is odd, or the mean of two middle elements after sorting if its length is even. For example, the median of $ [1, 1, 2, 4, 8] $ is $ 2 $ and the median of $ [3, -1, 5, 5] $ is $ (3 + 5) \div 2 = 4 $ .

Note that the mean and median are not rounded to an integer. For example, the mean of array $ [1, 2] $ is $ 1.5 $ .

## Input Format

The only line contains two integers $ a $ and $ b $ .

- $ -100 \leq a, b \leq 100 $ .
- The length of the array must be between $ 1 $ and $ 1000 $ .
- The elements of the array must be integers and their absolute values must not exceed $ 10^6 $ .

## Output Format

In the first line, print the length of the array.

In the second line, print the elements of the array.

If there are multiple solutions, you can print any. It can be proved that, under the constraints of the problem, a solution always exists.

## Sample #1

### Sample Input #1

```
3 4
```

### Sample Output #1

```
4
3 -1 5 5
```

## Sample #2

### Sample Input #2

```
-100 -100
```

### Sample Output #2

```
1
-100
```

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: constructive algorithms, math
Difficulty: 1200
# Drunken Maze

## Problem Description

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041D/ac90366c626ba21a7610cf55d06b2398a53105ff.png) Image generated by ChatGPT 4o.You are given a two-dimensional maze with a start and end position. Your task is to find the fastest way to get from the start to the end position. The fastest way is to make the minimum number of steps where one step is going left, right, up, or down. Of course, you cannot walk through walls.

There is, however, a catch: If you make more than three steps in the same direction, you lose balance and fall down. Therefore, it is forbidden to make more than three consecutive steps in the same direction. It is okay to walk three times to the right, then one step to the left, and then again three steps to the right. This has the same effect as taking five steps to the right, but is slower.

## Input Format

The first line contains two numbers $ n $ and $ m $ , which are the height and width of the maze. This is followed by an ASCII-representation of the maze where $ \tt{\#} $ is a wall, $ \tt{.} $ is an empty space, and $ \tt S $ and $ \tt T $ are the start and end positions.

- $ 12 \leq n\times m \leq 200000 $ .
- $ 3\leq n,m \leq 10000 $ .
- Characters are only $ \tt{.\#ST} $ and there is exactly one $ \tt{S} $ and one $ \tt{T} $ .
- The outer borders are only $ \tt{\#} $ (walls).

## Output Format

The minimum number of steps to reach the end position from the start position or -1 if that is impossible.

## Sample #1

### Sample Input #1

```
7 12
############
#S........T#
#.########.#
#..........#
#..........#
#..#..#....#
############
```

### Sample Output #1

```
15
```

## Sample #2

### Sample Input #2

```
5 8
########
#......#
#.####.#
#...T#S#
########
```

### Sample Output #2

```
14
```

## Sample #3

### Sample Input #3

```
5 8
########
#.#S...#
#.####.#
#...T#.#
########
```

### Sample Output #3

```
-1
```

## Limit



Time Limit
2.00s

Memory Limit
1000.00MB

Tags: brute force, dfs and similar, graphs, shortest paths
Difficulty: 1700
# Cube

## Problem Description

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041C/83a685de6f3f0e2c5499a1f04f05272c24e66bde.png)You are given an $ n\times n\times n $ big three-dimensional cube that contains $ n^3 $ numbers. You have to choose $ n $ of those numbers so that their sum is as small as possible. It is, however, forbidden to choose two numbers that are located in the same plane. That is, if we identify the positions in the cube by three Cartesian coordinates, then choosing two numbers from positions $ (x,y,z) $ and $ (x',y',z') $ is forbidden if $ x=x' $ , $ y=y' $ , or $ z=z' $ .

## Input Format

The input consists of the number $ n $ followed by $ n^3 $ numbers in the cube. The numbers are presented as $ n $ two-dimensional matrices, one for each layer of the cube. More precisely, there will be $ n^2 $ lines follow, each having $ n $ numbers. For each $ x, y, z $ ( $ 1\le x, y, z\le n $ ), the number at the position $ (x, y, z) $ is listed as the $ z $ -th number in the $ ((x-1)\times n+y) $ -th line.

- $ 2 \leq n \leq 12 $
- All numbers in the cube are integers between $ 0 $ and $ 2\times 10^7 $ .

## Output Format

The output consists of a single number. It is the minimum sum of $ n $ numbers chosen from the cube according to the above rules.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
5
```

## Limit



Time Limit
3.00s

Memory Limit
1000.00MB

Tags: bitmasks, dfs and similar, dp
Difficulty: 2000
# The Bento Box Adventure

## Problem Description

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041A/6724e41fa1b725d06db3c22a7057ae0e507a6d98.png) Image generated by ChatGPT 4o.Boxed meals in Taiwan are very common, offering convenient and affordable nutrition-balanced choices for students and office workers. These meals typically include a variety of vegetables, protein, and rice, providing a well-rounded diet. With numerous options available at local self-service restaurants, they are a popular choice for those looking for a quick, healthy lunch.

There are five Taiwanese self-service restaurants numbered from 1 to 5. You plan to visit a different restaurant each day from Monday to Friday to pack a boxed meal for lunch. You've already visited one restaurant from Monday to Thursday, each time visiting a different one. Now, it's Friday, and you want to visit the last remaining restaurant that you haven't been to yet this week.

Write a program that takes as input the four restaurants you've already visited (one for each day from Monday to Thursday) and outputs the restaurant you should visit on Friday.

## Input Format

A single line of input containing four integers $ a, b, c, d $ , each between 1 and 5 (inclusive), representing the restaurant numbers you visited from Monday to Thursday, in order.

- $ 1\le a, b, c, d\le 5 $
- All four numbers will be different.

## Output Format

Output the restaurant number you should visit on Friday.

## Sample #1

### Sample Input #1

```
1 3 2 5
```

### Sample Output #1

```
4
```

## Sample #2

### Sample Input #2

```
2 5 4 3
```

### Sample Output #2

```
1
```

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: implementation, sortings
Difficulty: 1300
# Number of Cubes

## Problem Description

Consider a rectangular parallelepiped with sides $ a $ , $ b $ , and $ c $ , that consists of unit cubes of $ k $ different colors. We can apply cyclic shifts to the parallelepiped in any of the three directions any number of times $ ^{\text{∗}} $ .

There are $ d_i $ cubes of the $ i $ -th color ( $ 1 \le i \le k $ ). How many different parallelepipeds (with the given sides) can be formed from these cubes, no two of which can be made equal by some combination of cyclic shifts?

 $ ^{\text{∗}} $ On the image:

- Top left shows the top view of the original parallelepiped. Lower layers will shift in the same way as the top layer.
- Top right shows the top view of a parallelepiped shifted to the right by $ 1 $ .
- Bottom left shows the top view of a parallelepiped shifted down by $ 2 $ .
- Bottom right shows the top view of a parallelepiped shifted to the right by $ 1 $ and down by $ 2 $ .

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2040F/de74a785103946b144cfadd0ee59410c014cc2b0.png)

## 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 four integers: $ a $ , $ b $ , $ c $ , and $ k $ ( $ 1 \le a, b, c \le 3 \cdot 10^6 $ ; $ a \cdot b \cdot c \le 3 \cdot 10^6 $ ; $ 1 \le k \le 10^6 $ ) — three sides of the parallelepiped and the number of colors of unit cubes.

The second line of each test case contains $ k $ integers $ d_1, d_2, \ldots, d_k $ ( $ 1 \le d_1 \le d_2 \le \ldots \le d_k \le 3 \cdot 10^6 $ ) — the elements of the array $ d $ : the number of cubes of a given color.

It is guaranteed that in each test case the sum of the elements of the array $ d $ is equal to $ a \cdot b \cdot c $ .

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

## Output Format

For each test case, print one integer — the number of different parallelepipeds modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
6
1 1 1 1
1
6 1 1 3
1 2 3
12 1 1 3
2 4 6
3 3 1 2
3 6
2 3 3 2
6 12
72 60 96 4
17280 86400 120960 190080
```

### Sample Output #1

```
1
10
1160
12
1044
231490207
```

## Hint

In the first test case, there is only one parallelepiped, which consists of one unit cube.

 Possible parallelepipeds in the second test case ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2040F/08e71e514c2bef1117926cff78006b523e092098.png)

## Limit



Time Limit
5.00s

Memory Limit
250.00MB

Tags: combinatorics, dp, math, number theory
Difficulty: 2700
# Non Prime Tree

## Problem Description

You are given a tree with $ n $ vertices.

You need to construct an array $ a_1, a_2, \ldots, a_n $ of length $ n $ , consisting of unique integers from $ 1 $ to $ 2 \cdot n $ , and such that for each edge $ u_i \leftrightarrow v_i $ of the tree, the value $ |a_{u_i} - a_{v_i}| $ is not a prime number.

Find any array that satisfies these conditions, or report that there is no such array.

## 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 first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree.

The next $ n - 1 $ lines contain the edges of the tree, one edge per line. The $ i $ -th line contains two integers $ u_i $ and $ v_i $ ( $ 1 \le u_i, v_i \le n $ ; $ u_i \neq v_i $ ), denoting the edge between the nodes $ u_i $ and $ v_i $ .

It's guaranteed that the given edges form a tree.

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, if an array that satisfies the conditions exists, print its elements $ a_1, a_2, \ldots, a_n $ . Otherwise, print $ -1 $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Hint

The possible answers are shown below. Instead of the vertex numbers, the corresponding elements of the array $ a $ are written in them.

 The image of the tree in the first test case ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2040D/d6a56c20ebd42ea20ac170d596c01c0583a1b831.png)  The image of the tree in the second test case ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2040D/8328682bcf4d0da5fcbe8de4a0054b43d22d093e.png)

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, dfs and similar, greedy, number theory, trees, two pointers
Difficulty: 1900
# Paint a Strip

## Problem Description

You have an array of zeros $ a_1, a_2, \ldots, a_n $ of length $ n $ .

You can perform two types of operations on it:

1. Choose an index $ i $ such that $ 1 \le i \le n $ and $ a_i = 0 $ , and assign $ 1 $ to $ a_i $ ;
2. Choose a pair of indices $ l $ and $ r $ such that $ 1 \le l \le r \le n $ , $ a_l = 1 $ , $ a_r = 1 $ , $ a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil $ , and assign $ 1 $ to $ a_i $ for all $ l \le i \le r $ .

What is the minimum number of operations of the first type needed to make all elements of the array equal to one?

## 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 one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array.

Note that there is no limit on the sum of $ n $ over all test cases.

## Output Format

For each test case, print one integer — the minimum number of needed operations of first type.

## Sample #1

### Sample Input #1

```
4
1
2
4
20
```

### Sample Output #1

```
1
2
2
4
```

## Hint

In the first test case, you can perform an operation of the $ 1 $ st type with $ i = 1 $ .

In the second test case, you can perform the following sequence of operations:

1. Operation of $ 1 $ st type, $ i = 1 $ . After performing this operation, the array will look like this: $ [1, 0] $ .
2. Operation of $ 1 $ st type, $ i = 2 $ . After performing this operation, the array will look like this: $ [1, 1] $ .

 The sequence of operations in the second test case ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2040B/08c860ca61c18c2cea946aa6a8dc785c3721c9f1.png)In the third test case, you can perform the following sequence of operations:

1. Operation of $ 1 $ st type, $ i = 1 $ . After performing this operation, the array will look like this: $ [1, 0, 0, 0] $ .
2. Operation of $ 1 $ st type, $ i = 4 $ . After performing this operation, the array will look like this: $ [1, 0, 0, 1] $ .
3. Operation of $ 2 $ nd type, $ l = 1 $ , $ r = 4 $ . On this segment, $ a_l + \ldots + a_r = a_1 + a_2 + a_3 + a_4 = 2 $ , which is not less than $ \lceil\frac{r - l + 1}{2}\rceil = 2 $ . After performing this operation, the array will look like this: $ [1, 1, 1, 1] $ .

 The sequence of operations in the third test case ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2040B/145510fed0c2c1fc91c16be016c113ca0ca5bb2f.png)

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, math
Difficulty: 1000
# Game of Division

## Problem Description

You are given an array of integers $ a_1, a_2, \ldots, a_n $ of length $ n $ and an integer $ k $ .

Two players are playing a game. The first player chooses an index $ 1 \le i \le n $ . Then the second player chooses a different index $ 1 \le j \le n, i \neq j $ . The first player wins if $ |a_i - a_j| $ is not divisible by $ k $ . Otherwise, the second player wins.

We play as the first player. Determine whether it is possible to win, and if so, which index $ i $ should be chosen.

The absolute value of a number $ x $ is denoted by $ |x| $ and is equal to $ x $ if $ x \ge 0 $ , and $ -x $ otherwise.

## Input Format

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

The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 100 $ ; $ 1 \le k \le 100 $ ) — the length of the array and the number $ k $ .

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

## Output Format

For each test case, if it is impossible for the first player to win, print "NO" (without quotes).

Otherwise, print "YES" (without quotes) and on the next line the appropriate index $ 1 \le i \le n $ . If there are multiple solutions, print any of them.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer.

## Sample #1

### Sample Input #1

```
7
3 2
1 2 3
4 2
1 2 4 5
5 3
10 7 3 4 5
5 3
1 31 15 55 36
2 1
17 17
2 2
17 18
1 3
6
```

### Sample Output #1

```
YES
2
NO
YES
3
NO
NO
YES
2
YES
1
```

## Hint

In the first test case, the first player can choose $ a_2 = 2 $ . Then:

- If the second player chooses $ a_1 = 1 $ , the resulting difference is $ |2 - 1| = 1 $ which is not divisible by $ k = 2 $ .
- If the second player chooses $ a_3 = 3 $ , the resulting difference is $ |2 - 3| = 1 $ which is not divisible by $ k = 2 $ .

In the second test case:

- If the first player chooses $ a_1 = 1 $ and then the second player chooses $ a_4 = 5 $ , the resulting difference is $ |1 - 5| = 4 $ which is divisible by $ k = 2 $ .
- If the first player chooses $ a_2 = 2 $ and then the second player chooses $ a_3 = 4 $ , the resulting difference is $ |2 - 4| = 2 $ which is divisible by $ k = 2 $ .
- If the first player chooses $ a_3 = 4 $ and then the second player chooses $ a_2 = 2 $ , the resulting difference is $ |4 - 2| = 2 $ which is divisible by $ k = 2 $ .
- If the first player chooses $ a_4 = 5 $ and then the second player chooses $ a_1 = 1 $ , the resulting difference is $ |5 - 1| = 4 $ which is divisible by $ k = 2 $ .

 In any case, the second player wins.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: games, math
Difficulty: 800