Count all pairs of integers $$$(n, p)$$$ such that $$$0 \le p \le P$$$, $$$p \neq n \cdot p$$$, and $$$p!=n \cdot p$$$.
The input consists of a single integer $$$P$$$ ($$$1 \le P \le 10^5$$$) — the upper bound on $$$p$$$.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10}=10$$$ points.
Tests $$$1 - 5$$$ will satisfy $$$P \le 1000$$$.
The remaining tests do not satisfy any additional constraints.
Output a single integer — the number of integer values for $$$n$$$ and $$$p$$$ that satisfy the constraints.
4
2
In the sample test, the $$$2$$$ values of $$$(n,p)$$$ that work are $$$(2,3)$$$ and $$$(6,4)$$$.
—
Problem Idea: willy108
Problem Preparation: xug
Occurrences: Novice A, Advanced A
I BET IT DOES!
Ifrit is an operator in Arknights who specializes in mapwide war crimes. You are tasked to increase the efficiency with which said war crimes are committed.
A map in Arknights can be represented as an $$$n$$$ by $$$m$$$ grid with three types of tiles:
- Placeable high-ground tiles (you can place Ifrit here). These tiles are denoted with a H.
- Low ground tiles (enemies walk here). These tiles are denoted with a L.
- Unplaceable high-ground tiles (you cannot place Ifrit here). These tiles are denoted with a #.
Let the upper-left tile be $$$(1, 1)$$$ and the bottom-right tile be $$$(n, m)$$$. We say a tile $$$(x, y)$$$ is an Ifrit Tile if the following conditions hold:
- It is a placeable high-ground tile. We want to place down Ifrit.
- We can pick a direction (up, left, down, right) such that out of the $$$5$$$ tiles immediately in that direction excluding the tile Ifrit is placed on, at least two of them are low-ground tiles. We want Ifrit to hit some enemies.
For a given map, count all Ifrit Tiles.
The first line of input contains two integers $$$n$$$ and $$$m$$$ denoting the length and width of the map $$$(1 \leq n, m \leq 1000)$$$.
The following $$$n$$$ lines each contain a string of length $$$m$$$, the $$$j$$$'th character on the $$$i$$$'th row being either an H, L, or #, denoting that tile $$$(i, j)$$$ is a tile of that type as defined in the statement.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10} = 10$$$ points.
Tests $$$1 - 3$$$ satisfy that $$$n, m \leq 10$$$.
The remaining tests do not satisfy any additional constraints.
Output a single integer, denoting the number of Ifrit Tiles on the map.
5 7##HLHH##HHLHH#LLLLLLL##HHLHH##HHLH#
4
The Ifrit Tiles are $$$(1, 5)$$$, $$$(2, 5)$$$, $$$(4, 4)$$$, and $$$(5, 4)$$$. Ifrit should be placed facing down, down, up, and up respectively on these tiles to hit at least two low-ground tiles.
This map is also the stage $$$1-1$$$ in Arknights.
—
Problem Idea: willy108
Problem Preparation: willy108
Occurrences: Novice B
Given an array $$$a$$$ of length $$$n$$$, you need to answer $$$m$$$ queries.
Each query will provide $$$l$$$ and $$$r$$$, and you need to calculate the value of $$$\bigoplus\limits_{i=l}^{r}\bigoplus\limits_{j=l}^{r}(a_i+a_j)$$$, the bitwise XOR of all $$$a_i+a_j$$$ such that $$$l \le i, j \le r$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 10^6$$$) — the length of the array $$$a$$$ and the number of queries.
The second line contains $$$n$$$ integers $$$a_1,a_2 \ldots a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$ — the elements of the array $$$a$$$.
Then, there are $$$m$$$ lines, each containing two integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10}=10$$$ points.
Tests $$$1 - 2$$$ satisfy $$$1 \leq n, m \leq 100$$$.
Tests $$$3 - 5$$$ satisfy $$$1 \leq n, m \leq 3366$$$.
The remaining tests do not satisfy any additional constraints.
Output $$$m$$$ lines, each containing an integer, representing the answer to each query.
5 40 1 2 3 43 52 21 41 5
10 2 0 8
The answer to the first query of the sample test is $$$(2+2) \oplus (2+3) \oplus (2+4) \oplus (3+2) \oplus (3+3) \oplus (3+4) \oplus (4+2) \oplus (4+3) \oplus (4+4)$$$, which simplifies to $$$4 \oplus 5 \oplus 6 \oplus 5 \oplus 6 \oplus 7 \oplus 6 \oplus 7 \oplus 8=10$$$.
—
Problem Idea: willy108
Problem Preparation: willy108
Occurrences: Novice C
Given the array $$$[ 1,2, \ldots ,2 \cdot n ]$$$, partition it into $$$2$$$ subsequences $$$a$$$ and $$$b$$$ of length $$$n$$$ such that each element of the original array is present in one of $$$a$$$ or $$$b$$$. A subsequence is a sequence that can be derived from the given array by deleting zero or more elements without changing the order of the remaining elements.
For each index $$$i$$$ ($$$ 1 \le i \le n$$$), you are given one of the three following constraints: $$$a_i+b_i = v_i$$$, $$$|a_i-b_i| = v_i$$$, or $$$\text{max}(a_i, b_i) = v_i$$$. Find the number of possible subsequences $$$a$$$ and $$$b$$$, modulo $$$10^9+7$$$. It is guaranteed there exists at least one partition that satisfies the constraints.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The next $$$n$$$ lines each contain two integers $$$t_i$$$ and $$$v_i$$$ ($$$1 \le t_i \le 3, 1 \le v_i \lt 4 \cdot n$$$) — the constraints on $$$a_i$$$ and $$$b_i$$$.
If $$$t_i=1$$$, $$$v_i=a_i+b_i$$$.
If $$$t_i=2$$$, $$$v_i=|a_i-b_i|$$$.
If $$$t_i=3$$$, $$$v_i=\text{max}(a_i, b_i)$$$.
—
There are $$$10$$$ tests, not including samples. Each test is worth $$$\frac{100}{10}=10$$$ points.
Output a single integer — the number of possible ways to partition the array $$$[ 1,2, \ldots 2 \cdot n ]$$$ into $$$a$$$ and $$$b$$$ that satisfy the constraints. Output your answer modulo $$$10^9+7$$$.
51 53 53 62 21 18
4
In the sample test, the $$$4$$$ ways to partition the array are:
- $$$a=[1,2,3,7,8]$$$ and $$$b=[4,5,6,9,10]$$$
- $$$a=[1,2,3,9,10]$$$ and $$$b=[4,5,6,7,8]$$$
- $$$a=[4,5,6,7,8]$$$ and $$$b=[1,2,3,9,10]$$$
- $$$a=[4,5,6,9,10]$$$ and $$$b=[1,2,3,7,8]$$$
—
Problem Idea: superhelen
Problem Preparation: xug
Occurrences: Novice D
Given an array $$$a$$$ of $$$n$$$ integers, find the minimum sum of the array after removing two elements of $$$a$$$ and appending their bitwise XOR to the array.
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 first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 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$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1 - 5$$$ will satisfy $$$t \le 10$$$, $$$n \le 1000$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a single integer — the minimum achievable sum.
255 1 1 3 231 4 9
8 12
In the first test case of the sample test, it is optimal to choose the elements $$$2$$$ and $$$3$$$, deleting them and appending $$$1$$$ to the array. This produces a new sum of $$$8$$$.
In the second test case of the sample test, it is optimal to choose the elements $$$1$$$ and $$$9$$$, deleting them and appending $$$8$$$ to the array. This produces a new sum of $$$12$$$.
—
Problem Idea: xug
Problem Preparation: xug
Occurrences: Novice E
XORnet has created the most difficult game yet, and Little Jonny wants to be the first to beat it. He is given a matrix $$$a$$$, consisting of $$$n$$$ rows by $$$m$$$ columns. Each element of the matrix is equal to $$$0$$$ or $$$1$$$, and he needs to reach the bottom right corner starting from the top left corner by only stepping down or right. However, he may only step on $$$1$$$s. Little Jonny is also a very accomplished hacker, so he managed to give himself an XORgun, which, when used, can toggle all the values in a row, changing the $$$1$$$s to $$$0$$$s and $$$0$$$s to $$$1$$$s (unfortunately, his skills did not extend to enable toggling for columns). All uses of the XORgun must be done before he takes his first step. Find the minimum number of uses of the XORgun that allow Little Jonny to beat the game.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$) — the number of rows and the number of columns of the matrix $$$a$$$.
Each of the next $$$n$$$ lines contains a binary string of length $$$m$$$ — the description of matrix $$$a$$$. It is guaranteed that the value of the top left corner is $$$1$$$.
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.
—
There are $$$20$$$ tests, not including samples. Each test is worth $$$\frac{100}{20}=5$$$ points.
For each test case, output a single integer — the minimum number of times Little Jonny can use the XORgun for him to beat the game. If it is impossible for him to beat the game, output $$$-1$$$.
33 41110010010104 31101011100002 51001011011
2 1 -1
In the first test case of the sample test, it is optimal to use the XORgun on rows $$$2$$$ and $$$3$$$.
In the second test case of the sample test, it is optimal to use the XORgun on row $$$4$$$.
—
Problem Idea: Red0
Problem Preparation: xug
Occurrences: Novice F
Yash really likes monkeys and special arrays. Because he was curious, Curios George gave Yash an array $$$A$$$ of length $$$N$$$, and now Yash wonders how many good subarrays exist in this array.
Specifically, Yash deems a subarray good if $$$X$$$, his favorite number, is the maximum value in the subarray, $$$Y$$$, his second favorite number, is the minimum in the subarray, and $$$K$$$, his least favorite number, is not in the subarray. In other words, in a given subarray, $$$X$$$ should be the maximum value, $$$Y$$$ should be the minimum, and $$$K$$$ should not be in the subarray.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 5 \cdot 10^4)$$$ — the number of test cases.
The first line of each test case contains four integers $$$N$$$, $$$X$$$, $$$Y$$$, and $$$K$$$ ($$$1 \le N \le 5 \cdot 10^5, 1 \le Y \lt K \lt X \le 10^9$$$).
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$$$.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-5$$$ satisfy that the sum of $$$N$$$ over all test cases does not exceed $$$100$$$.
Tests $$$6-10$$$ satisfy that the sum of $$$N$$$ over all test cases does not exceed $$$1000$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a single integer — the number of good subarrays in the array $$$A$$$.
38 7 4 56 7 4 6 5 4 6 76 5 2 43 2 4 5 1 312 8 3 610 4 3 7 4 8 6 5 1 3 8 2
5 0 3
In the first test case of the sample test, the $$$5$$$ subarrays that are good are $$$[6, 7, 4]$$$, $$$[6, 7, 4, 6]$$$, $$$[7, 4]$$$, $$$[7, 4, 6]$$$, and $$$[4, 6, 7]$$$.
In the second test case of the sample test, there are no good subarrays.
—
Problem Idea: yash_9a3b
Problem Preparation: yash_9a3b, xug
Occurrences: Novice G, Advanced B
Given an integer $$$a$$$, count the number of different ways to remove exactly $$$4$$$ digits of $$$a$$$ such that the resulting integer is less than $$$b$$$.
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.
Each test case contains two integers $$$a$$$ and $$$b$$$ ($$$10^4 \le a \lt 10^{10000}, 1 \le b \lt 10^{10000}$$$). It is guaranteed that the number of digits in $$$a$$$ is exactly $$$4$$$ more than the number of digits in $$$b$$$.
—
There are $$$10$$$ tests, not including samples. Each test is worth $$$\frac{100}{10}=10$$$ points.
Output a single integer — the number of ways to make $$$a$$$ less than $$$b$$$ after removing $$$4$$$ digits.
3634272196 223505082349091 19356224211 2
1 56 2
In the first test case of the sample test, the only digits you can remove are $$$6$$$, $$$3$$$, $$$4$$$, and $$$7$$$ to make $$$22196$$$.
In the second test case of the sample test, you can remove the $$$5$$$ and then remove any three digits after the first $$$0$$$ for a total of $$$56$$$ different ways.
—
Problem Idea: CPIdeas
Problem Preparation: xug
Occurrences: Novice H
There is a chain of $$$n$$$ nodes with edges between nodes $$$u$$$ and $$$v$$$ such that $$$|v - u| = 1$$$. For each node $$$i$$$ ($$$1 \le i \le n$$$), you will keep it with probability $$$\frac{1}{i}$$$ or delete it with probability $$$1 - \frac{1}{i}$$$. Find the expected number of connected components after all the deletions, modulo $$$10^9+7$$$.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^5)$$$ — the number of test cases.
Each test case contains one line consisting of a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ — the number of nodes in the chain.
—
Tests in subtasks are numbered from $$$1-10$$$ with samples skipped. Each test is worth $$$\frac{100}{10}=10$$$ points.
Test $$$1$$$ satisfies $$$1 \leq n \leq 15$$$.
Tests $$$2-3$$$ satisfy $$$1 \leq n \leq 100$$$.
Tests $$$4-5$$$ satisfy $$$t=1$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, print a single integer — the expected number of connected components after all deletions. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{a}{b}$$$, where $$$a$$$ and $$$b$$$ are integers. Output the integer equal to $$$a \cdot b^{-1} \text{ mod } 10^9+7$$$.
41234
1 1 166666669 333333337
For the first test case in the sample test, $$$n=1$$$, so there is one node that you keep with probability $$$\frac{1}{1}=1$$$, so there can only be $$$1$$$ connected component in the final graph.
In the second test case in the sample test, $$$n=2$$$, so you keep node $$$1$$$ with probability $$$\frac{1}{1}=1$$$ and node $$$2$$$ with probability $$$\frac{1}{2}$$$. Whether node $$$2$$$ is kept or not, there will be $$$1$$$ connected component.
—
Problem Idea: willy108, Yam
Problem Preparation: Yam
Occurrences: Novice I, Advanced C
Recently, two very productive (even peakly productive) Rinbot'ers have been optimizing Rinbot. They realized that instead of buying a sentient supercomputer, they could use hangman strats instead. These two highly productive Rinbot'ers made a giant cloud-hosted database where they stored the title for every anime in Rinbot. Unfortunately, the AC turned off, marking the end of the laptop.
Can you write a program to access their database?
In this link, there is a text file with all anime titles for shows in Rinbot (up until the Spring 2024 season).
For $$$T$$$ titles, determine which line in the file the title is modulo $$$P$$$. For instance, "86" is on line $$$75$$$ and "?" is on line $$$5$$$.
The Teamscode Online Judge has a submission size limit of 50 kB.
The first line of input will contain a single integer $$$T$$$ $$$(1 \leq T \leq 2 \cdot 10^4)$$$ — the number of titles to consider.
The second line of input will contain a single integer $$$P$$$ $$$(P \in {\{2, 10, 10^5\}})$$$ — the modulus applied to the line numbers you find.
The following $$$T$$$ lines will each contain a title. It is guaranteed that the title is present character for character (including punctuation, spaces, and correct uppercase/lowercase distinction) in the above text file.
It is guaranteed that the sum of all inputted title lengths does not exceed $$$10^6$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1$$$ will only ask for titles within the second sample test.
Tests $$$2 - 3$$$ will only ask for titles within the first $$$100$$$ lines.
Tests $$$4 - 5$$$ will only ask for titles within the first $$$3366$$$ lines and satisfy $$$P = 2$$$.
Tests $$$6 - 8$$$ will only ask for titles within the first $$$3366$$$ lines and satisfy $$$P = 10$$$.
Tests $$$9 - 10$$$ will only ask for titles within the first $$$3366$$$ lines.
Tests $$$11 - 13$$$ will satisfy $$$P = 2$$$.
Tests $$$14 - 16$$$ will satisfy $$$P = 10$$$.
The remaining tests do not satisfy any additional constraints.
For each title, let $$$\texttt{line}$$$ denote the line number that the title occurs at in the text file. Output a single integer — $$$\texttt{line} \text{ mod P}$$$.
11 100000 86 ? Bakemonogatari Hayate no Gotoku! Shuumatsu Nani Shitemasuka? Isogashii Desuka? Sukutte Moratte Ii Desuka? Shoujo Shuumatsu Ryokou "Oshi no Ko" Shiguang Dailiren II Hajime no Ippo: The Fighting! - New Challenger Zombie Land Saga Lycoris Recoil
75 5 666 3535 8480 8424 17 8201 3366 10591 5553
11 100000 Bakemonogatari Nisemonogatari Nekomonogatari (Kuro): Tsubasa Family Monogatari Series: Second Season Hanamonogatari: Suruga Devil Kizumonogatari Tsukimonogatari: Yotsugi Doll Owarimonogatari (2017) Koyomimonogatari Owarimonogatari Zoku Owarimonogatari
666 6686 6576 6272 3439 4968 9549 7122 5175 7128 10577
—
Problem Idea: willy108
Problem Preparation: willy108
Occurrences: Novice J, Advanced D
Jason wants to orz Waymo! To achieve this, he can use the following operations:
1. Type "orz" in $$$A$$$ seconds.
2. Copy all the text in $$$B$$$ seconds.
3. Paste all the copied text in $$$C$$$ seconds.
Since Jason is in a hurry, please help him minimize the amount of time he spends to orz Waymo at least $$$N$$$ times.
Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of test cases.
Each test case contains one line, with four positive integers $$$A$$$, $$$B$$$, $$$C$$$, and $$$N$$$ ($$$1 \le A,B,C \le 10^6, 1 \le N \le 10^9$$$).
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfy $$$N \le 2000$$$.
Tests $$$3-6$$$ satisfy $$$N \le 5 \cdot 10^5$$$.
Tests $$$7-12$$$ satisfy $$$N \le 10^7$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a single integer — the minimum amount of time to type "orz" at least $$$N$$$ times.
41 1 1 201 2 3 1431 4 3 8903 20 7 650
9 29 51 156
In the test case of the sample test, it is optimal to type orz 3 times, then copy, paste, copy, paste, paste, paste.
—
Problem Idea: jay_jayjay
Problem Preparation: jay_jayjay
Occurrences: Novice K, Advanced E