In the Squid Game competition, each game requires different abilities to succeed. Unfortunately, you are player '$$$0$$$' and you have no abilities, and you must choose your teammates wisely to maximize your chances of winning. Each teammate will bring a set of abilities to the table, and your goal is to ensure that every one of your teammates has at least one ability required for a game.
For each game, you are given a number $$$x$$$ representing the abilities required for this game. The task is to determine how many people among $$$n$$$ players can join your team for that game, and whether it is guaranteed that your team will win.
Your team is guaranteed to win a game if, for every ability required by the game, at least one of your teammates possesses that ability.
A set of abilities isrepresented by a number . A number $$$a$$$ means a player has certain abilities, where the $$$j^{th}$$$ bit of $$$a$$$ in its binary representation is $$$1$$$ if the player masters the $$$j^{th}$$$ ability and $$$0$$$ otherwise.
Every player has at most 6 different abilities.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2.10^5$$$), the number of players numbered from $$$1$$$ to $$$n$$$ and the number of games.
The second line contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n-1},a_{n}$$$ ($$$0 \leq a_{i} \leq 2^{20}-2^{14}$$$), where $$$a_{i}$$$ is the set of abilities of player $$$i$$$.
The next q line contains an integer $$$x$$$ ($$$0 \leq x \leq 2^{20}$$$), representing the abilities required for this game.
It's guaranteed that every player has at most 6 different abilities.
For each game, print two integers:
7 20 1 2 3 2 1 013
3 1 5 1
8 21 2 3 4 5 6 7 225
5 1 6 1
Two players, Player 001 and Player 002, are trapped in a mysterious tree-shaped battleground. Their objective is to visit the least number of nodes—because in this game, the more steps you take, the closer you are to elimination.
The game is controlled by the Squid Game Dummy, who gives each second a Green Light to move and a Red Light to stop. This ensures that both players move simultaneously when the Green Light is given. Keep in mind that both players will aim to play optimally.
Game Rules
The Front Man's Twist
The Front Man noticed that with an even number of nodes, the game often ends in a tie—which he finds boring. To ensure a decisive outcome, he made sure that the number of nodes in the tree is always odd.
23 11 22 33 25 21 22 33 44 51 41 5
001 002 Remake!
This is an example of a gameplay. Let's use a black dot to represent each player's current position. Each player has their own black dot. Query 1:
test case 2 query 1. At time t=2: Player 2 must move toward the closest unvisited node, so they start walking toward Node 3. Player 1 also moves toward the closest unvisited node, which is Node 3.
At time t=3: All nodes have been colored and visited by at least one player, so the game ends.
Query 2:
test case 2 query 2.
In the Dalgona Challenge from Squid Game, players must carefully carve out a shape from a honeycomb candy using a needle. The Masked Guards have designed a new version of this challenge using laser-cut patterns on a circular honeycomb.
You are g iven a circular honeycomb with $$$n$$$ points along its boundary. The guards use laser cutters to draw a straight line between every pair of these points. That is, for every possible pair of distinct points, a straight laser cut is made, linking each point with every other point. These laser cuts create a complex pattern of intersecting lines that divide the honeycomb into multiple regions.
Your task is to determine the maximum number of regions the honeycomb can be divided into when all possible laser cuts are made.
The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{5} $$$).
Each test case contains :
A single integer $$$n$$$ ($$$0 \leq n \leq 10^{5}$$$), representing the number of points.
A single integer, the maximum number of regions formed in the honeycomb.
3146
1 8 31
In the first two testcases, the result is obvious.
In the third testcase, it can be proven that the maximum number of regions obtained after placing 6 points in the circle optimally is $$$31$$$
test case 3 .
In one of the Squid Game challenges, Seong Gi-hun (Player 456) and Oh Il-nam (Player 001) face off in a game where they start with $$$n$$$ bags of marbles. Each bag has $$$a_{i}$$$ marbles. The rules are simple:
In the first line, there is a single integer $$$t$$$ ($$$1 \leq t \leq 2.10^5$$$), representing the number of testcases.
In each testcase, there are three lines:
Output "456" if Seong Gi-hun will win the game, or "001" if Oh Il-nam will win, assuming both players play optimally.
413 4213 4423 41000000000000000000 100000000000000000023 42 4
001 456 001 456
In the Squid Game, players find themselves trapped in a massive, deadly tree-like structure with $$$n$$$ platforms (nodes). Each platform has a danger level $$$a_i$$$, representing its instability. Platforms are connected by rope bridges with different weight values $$$w_i$$$, determining the difficulty of crossing between them. Players can jump from one platform to any platform in its subtree, but each jump comes at a cost:
jump's cost $$$=a_y$$$ $$$($$$weight of the path from $$$x$$$ to $$$y$$$$$$)$$$
where $$$x$$$ is the current platform and $$$y$$$ is the destination.
The goal for each player, starting from any platform, is to find the safest escape route to a leaf platform, where the total jumping cost is minimized. However, the root platform (1) is cursed and can never be a leaf, even if it has only one connection!
Can you find the optimal escape path for each platform before the deadly Squid Game masters close in?
The first line of input contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$), the number of nodes in the tree.
The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \leq a_i \leq 10^6$$$),representing each platform danger level.
Next $$$n - 1$$$ lines contain two space-separated integers $$$u_i$$$ , $$$v_i$$$ and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq n , -10^6 \leq w_i \leq 10^6$$$) describing a rope bridge between platforms $$$u_i$$$ and $$$v_i$$$ given its weight.
Output $$$n$$$ space-separated integers, the $$$i$$$-th of which denotes the minimum cost of a path from platform $$$i$$$ to reach any leaf.
32 -1 11 2 32 3 -2
-5 -2 0
53 -1 2 -2 -41 2 31 3 -13 4 -23 5 1
-6 0 -4 0 0
71 -3 2 -4 5 -3 -11 2 -11 3 -22 4 22 5 -13 6 -23 7 1
-10 -8 -1 0 0 0 0
In the Squid Game, players must cross a dangerous glass bridge consisting of $$$n$$$ planks. Each plank has a danger value $$$a_{i}$$$ , representing how unstable it is. Players must strategically place $$$k$$$ safe planks on the bridge to divide it into $$$k+1$$$ segments, making their path safer.
The survival cost of a segment is determined by the number of divisors ($$$\tau $$$) of the product of all danger values in that segment. The total survival cost is the sum of the survival costs of all segments.
For example, for a bridge $$$[20,1,1,1] $$$ and $$$k=1$$$, an optimal way is to divide the bridge into two segments: $$$[20]$$$ and $$$[1,1,1] $$$, and the total cost $$$=6+1=7$$$.
Your task is to strategically place the $$$k$$$ dividers to minimize the total survival cost, ensuring the safest possible route across the bridge. Can you survive the Glass Bridge Challenge and reach the other side?
The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 500 $$$).
Each test case contains two lines :
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^{3} , 1 \leq k \leq min(100,n-1) $$$), representing the number of the planks and the number of safe planks .
The second line contains $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^{6})$$$ representing the danger value of the planks.
Its guaranteed that the sum of $$$n$$$ over all test cases does not exceed 1000.
Print one integer, the minimum total survival cost after optimally placing the safe planks.
It's guaranteed that the minimum total survival cost after optimally placing the safe planks does not exceed $$$10^{18}$$$.
55 120 1 1 1 15 24 6 8 2 34 12 3 4 53 14 6 85 22 12 9 24 8
7 15 10 12 25
In the second testcase, a best way is to divide the bridge into 3 segments $$$[4,6],[8,2],[3] $$$ so the total cost $$$=8+5+2=15$$$
In this challenge, $$$n$$$ players are arranged in a line with positions numbered from $$$1$$$ to $$$n$$$. The goal of the challenge is simple: only a few players will survive, and the rest will be eliminated based on their position and a mathematical property known as Euler's Totient Function.
After the players are arranged, a guard will go through each position and determine whether the player in that position should be eliminated or not. The decision to eliminate a player depends on a mathematical condition involving Euler's Totient Function, $$$\varphi(k)$$$, which is defined as the number of integers from $$$1$$$ to $$$k$$$ that are coprime with $$$k$$$. To make the decision, the guard will check each position $$$k$$$ $$$(1 \leq k \leq n)$$$ and ask, does $$$\varphi(k)$$$ divide $$$k$$$? If yes, the player survives; otherwise, the player in that position will be eliminated.
Your task is to determine how many players will survive.
A single integer $$$n$$$ $$$(1 \leq n \leq 10^{18} )$$$ — number of players.
Output a single integer representing the number of survivors.
6
4
1000000
130
Euler's totient function, denoted as $$$ \varphi(n) $$$, counts the number of positive integers from $$$ 1 $$$ to $$$ n $$$ that are coprime to $$$ n $$$, meaning they do not share any common divisor with $$$ n $$$ other than $$$ 1 $$$.
The function satisfies the following formula for any positive integer $$$ n $$$ with prime factorization:
$$$$$$ n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k} $$$$$$
where $$$ p_1, p_2, \dots, p_k $$$ are distinct prime numbers. The totient function is given by:
$$$$$$ \varphi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \dots \left( 1 - \frac{1}{p_k} \right) $$$$$$
For a prime number $$$ p $$$, we have:
$$$$$$ \varphi(p) = p - 1 $$$$$$
since all numbers less than $$$p $$$ are coprime to it.
test case 1
In one of the Squid Game challenges, a Revolving Death Clock determines the fate of the players. The clock consists of two circular gears: a smaller gear (the Death Gear) rotates around a larger circular base (the Clock Gear).
The Death Gear starts at a specific point on the Clock Gear and rotates around it. Your task is to determine the minimum number of full rotations the Death Gear completes before returning to its starting position relative to the Clock Gear. You are given two circles:
This is an example of how the gear rotates. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{6} $$$)
Each test case contains :
Two integers $$$D_{1}$$$ and $$$D_{2}$$$ ($$$1 \leq D_{2} \leq D_{1} \leq 10^{9} $$$), representing the diameters of the Clock Gear and the Death Gear, respectively.
For each test case, output a single integer, the minimum integer number of complete rotations the Death Gear makes around itself before returning to its starting position.
21 13 1
2 4
The first test case: here.
In this challenge, you are tasked with helping the players navigate through a series of binary gates. The guards have set up a system where each gate is either "open" (denoted by $$$1$$$) or "closed" (denoted by $$$0$$$). The challenge is to escape through the gates by ensuring you have a segment of open gates large enough to slip through without being caught.
You are given two integers,$$$n$$$ — the total number of gates (binary sequence length)and $$$l$$$ — the minimum number of consecutive open gates (i.e., $$$1s$$$) required to successfully escape.
Your task is to determine how many binary sequences of length $$$n$$$ contain at least one contiguous subsegment of length $$$l$$$ consisting only of $$$1s$$$. The sequence can contain any combination of $$$0s$$$ and $$$1s$$$, but to successfully escape, there must be a subsegment of $$$l$$$ consecutive $$$1s$$$ somewhere in the sequence.
Since the number of such sequences can be quite large, output the result modulo $$$10^9+7$$$.
A single line containing two integers $$$n$$$ $$$(1 \leq n \leq 10^9)$$$ and $$$l$$$ $$$(1 \leq l \leq 100)$$$ respectively representing the total number of gates and the minimum number of consecutive open gates required to successfully escape.
Output a single integer — the number of valid binary sequences of length $$$n$$$ that satisfy the condition, modulo $$$10^9+7$$$.
3 2
3
In the first test, all possible sequences of gates are :
$$$000,001,010,011,100,101,110,111$$$.
The only valid ones are :
$$$011,110,111$$$.
So the answer is 3.
In the easy version, guards can use the operations only once.
In the next round of the Squid Game, players must be arranged by their numbers from $$$1$$$ to $$$n$$$. Guards must rearrange the players that initially are shuffled in a random order. Time is crucial, so they have to minimize the time needed to do that.
A guard can do the following operations :
The goal of the guards is to rearrange the players into the correct order $$$1,2,...,n$$$, using these operations only once, while minimizing the total time. The guards can perform these operations infinitely, but they must be strategic in choosing the number of segments each time because the more segments they use, the longer it takes.
The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — the number of players.
The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le n)$$$ — the initial permutation of players.
Print a single integer, the minimum time needed to rearrange the players.
55 4 2 3 1
4
53 4 5 1 2
2
66 5 4 3 2 1
6
51 2 3 4 5
0
In the first test, you can divide the players into $$$4$$$ segments $$$[5]$$$,$$$[4]$$$,$$$[2,3]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$4$$$.
In the second test, you can divide the players into $$$2$$$ segments $$$[3,4,5]$$$ and $$$[1,2]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$2$$$.
In the third test, you can divide the players into $$$6$$$ segments $$$[6]$$$,$$$[5]$$$,$$$[4]$$$,$$$[3]$$$,$$$[2]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5,6]$$$. So the answer is $$$6$$$.
In the hard version, guards can use the operations as many times as needed
In the next round of the Squid Game, players must be arranged by their numbers from $$$1$$$ to $$$n$$$. Guards must rearrange the players that initially are shuffled in a random order. Time is crucial, so they have to minimize the time needed to do that.
A guard can do the following operations :
The goal of the guards is to rearrange the players into the correct order $$$1,2,...,n$$$, using these operations as many times as needed, while minimizing the total time. The guards can perform these operations infinitely, but they must be strategic in choosing the number of segments each time because the more segments they use, the longer it takes.
The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — the number of players.
The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le n)$$$ — the initial permutation of players.
Print a single integer, the minimum time needed to rearrange the players.
55 4 2 3 1
4
53 4 5 1 2
2
66 5 4 3 2 1
5
51 2 3 4 5
0
In the first test, you can divide the players into $$$4$$$ segments $$$[5]$$$,$$$[4]$$$,$$$[2,3]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$4$$$.
In the second test, you can divide the players into $$$2$$$ segments $$$[3,4,5]$$$ and $$$[1,2]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$2$$$.
In the third test, you can divide the players into $$$2$$$ segments $$$[6,5,4]$$$ and $$$[3,2,1]$$$ and shuffle them into $$$[3,6,2,5,1,4]$$$.Then divide the players into $$$3$$$ segments $$$[3,6]$$$,$$$[2,5]$$$ and $$$[1,4]$$$and shuffle them into $$$[1,2,3,4,5,6]$$$. So the answer is $$$2+3=5$$$.
The enigmatic owner of the Squid Games is searching for a new Front Man to take over his position and become Player 001. However, before he entrusts you with this role, he must test your intelligence.
Your first task seems simple:
Given an integer $$$ 1 \leq N \leq 10^{17} $$$, compute the sum of the digits of all numbers $$$ i $$$ for $$$ 1 \leq i \leq N $$$. That is, your answer should be:
$$$ \sum_{i=1}^{N} \text{sum_of_digits}(i) $$$
However, the owner finds this challenge too easy. To truly prove your worth, you must answer $$$ t $$$ consecutive test cases correctly.
Can you pass the test and claim the title of Player 001?
The first line contains a single integer $$$ t $$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
Each of the next $$$ t $$$ lines contains a single integer $$$ N $$$ $$$(1 \leq N \leq 10^{17})$$$.
For each test case, output a single integer — the sum of the digits of all numbers $$$ i $$$ for $$$ 1 \leq i \leq N $$$.
Print each answer on a new line.
4121011254
51 46 1 16125
Example of Sum of Digits of a Number: sum_digits(10) = 1 + 0 = 1 sum_digits(123) = 1 + 2 + 3 = 6 And so on.
Explanation of a Test Case: Let's denote the function sum_of_digits as s. For Test Case 2, we calculate the sum of digits for all integers $$$i$$$ where $$$1 \leq i \leq 10$$$: $$$s(1) + s(2) + s(3) + s(4) + s(5) + s(6) + s(7) + s(8) + s(9) + s(10)= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + (1 + 0)= 46$$$
In this round of the Squid Game, the players are presented with $$$n$$$ locked vaults, each containing a hidden number. The guards provide an interval $$$[l, r]$$$ for each vault, indicating that the number inside must be chosen from this range.
Each player must select exactly one number from each interval, forming a sequence of $$$n$$$ numbers. The objective is to maximize the MEX of this sequence.
The mex of a sequence is the smallest non-negative integer that does not appear in the sequence. For example:
Print a single integer, the maximum possible mex of the sequence obtained by selecting one integer from each interval.
310 040 10 31 20 030 10 03 3
1 4 2
In one of the Squid Game challenges, players are tasked with positioning themselves within a circular arena. The challenge is to find the number of groups of four players that can stand on the same perfect circle within the arena, such that all four points lie on the circumference of the circle. The players are scattered randomly in the arena, and your task is to calculate how many such quadrilaterals can be formed.
You are given $$$n$$$ points in a 2D plane. Each point is represented by its coordinates ($$$x_{i},y_{i}$$$) for $$$1 \leq i \leq n$$$. You are tasked with finding the number of sets of four points that lie on the same circle.
A single integer $$$n$$$ ($$$4 \leq n \leq 300$$$) representing the number of points in the plane.
The next $$$n$$$ lines contain two integers $$$x$$$ and $$$y$$$ representing the coordinates of each point($$$-1000 \leq x,y \leq 1000$$$).
A single integer, the number of distinct quadrilaterals formed by four points that lie on the same circle.
80 10 21 02 03 13 21 32 3
70
50 01 10 2-1 10 1
1
50 01 1-1 -11 -2-2 1
0
In the first test, every point is included in the same circle, so the answer is choose $$$4$$$ out of $$$8$$$, which is $$$70$$$.
test $$$1$$$. In the second test, only one quadruple of points is in the same circle, so the answer is $$$1$$$.
test $$$2$$$.
In the Squid Game, the Masked Guards are responsible for maintaining order and eliminating rebellious Players. However, the Guards have secretly grown resentful of the system and wish to overthrow the Front Man. The Guards have discovered a key insight: if a group of consecutive Guards in the circular formation is surrounded by strictly more Players, they will be overpowered and eliminated.
For example, if the initial formation is: $$$$$$11000100101$$$$$$ where 1 represents a Player and 0 represents a Masked Guard, the Players can initially attack the first three Guards, as they are surrounded by 4 Players: $$$$$$110001∗∗∗∗1$$$$$$ leaving the new formation as: $$$$$$11100101$$$$$$ The process continues until the Players take control of the entire arena.
The Guards, realizing the imminent threat, decide to swap their positions in a circular manner, attempting to find an arrangement where, after all possible attacks, the number of remaining Guards is greater than or equal to the initial number of Players.
Your task is to determine how many different valid rearrangements of the Guards and Players exist to ensure that the Guards can survive the rebellion. As these numbers can be very large, print the result modulo $$$998244353$$$.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$, representing the number of testcases.
For each testcase, you will be given two integers $$$k$$$ and $$$n$$$ $$$(1 \leq k \leq 10^6, 1 \leq n \leq 10^6)$$$, indicating the initial number of Players and the initial number of Guards.
Print the answer modulo 998244353.
52 12 23 35 88 5
0 16 216 204983294 0
In the second test case if we enumerate the $$$4$$$ positions in the circular formation from $$$1$$$ to $$$4$$$ in clockwise order and we note the two players as $$$A$$$ and $$$B$$$ and the two guards as $$$C$$$ and $$$D$$$. Each permutation of this 4 letters represent a formation.
Then all possible valid rearrangements of the Guards and Players are : $$$ABCD$$$ , $$$BACD$$$ , $$$ABDC$$$ , $$$BADC$$$ , $$$CABD$$$ , $$$CBAD$$$ , $$$DABC$$$ , $$$DBAC$$$ , $$$CDAB$$$ , $$$CDBA$$$ , $$$DCAB$$$ , $$$DCBA$$$ , $$$ACDB$$$ , $$$ADCB$$$ , $$$BCDA$$$ , $$$BDCA$$$ so the answer is 16.
In one of the Squid Game challenges, the Masked Guards randomly shuffle the players into a single line. However, only those players who remain in their original positions after the shuffle will survive. These survivors are the fixed points.
You are tasked with determining the expected number of survivors—the number of players who remain in their original positions after a random shuffle of the players.
You are given $$$t$$$ test cases. For each test case, you are given a single integer $$$n$$$, representing the number of players in the line-up. The Masked Guards shuffle the players into any possible permutations, each being equally likely. A fixed point (or survivor) is a position $$$i$$$ in the shuffled list where the player $$$i$$$ remains in the same position as their original number $$$i$$$.
Your task is to calculate the expected value of the number of survivors (fixed points) in a random shuffle of $$$n$$$ players for each test case.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^{5}$$$), the number of test cases.
Each of the next $$$t$$$ lines contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^{7}$$$), representing the number of players in the line-up.
It is guaranteed that the sum of all $$$n$$$ across the $$$t$$$ test cases does not exceed $$$10^{7}$$$.
For each test case, output a single floating-point number, the expected number of survivors (fixed points), with an absolute or relative error of at most $$$10^{-6}$$$
212
1.0000000 1.0000000