The year is 2077, everyone lives in the Cyberpunk era and Laser Aim is the most popular sport of the decade.
In the classic mode, the player is put in a corner of a square-shaped field and must shoot the target, which is placed at the opposite corner of the square. The fun comes from the walls being made out of mirrors, so a laser can hit the wall and be reflected with the same angle of incidence.
In order to earn the most points, a shot must hit the target after the most reflections possible. The problem is that each time the laser hits a wall, it loses a bit of intensity, until it disappears after $$$N+1$$$ reflections.
Lami wants to become the best Laser Aim athlete and promises he's able to find all angles that maximize his score. And in order to practice, he asked for your help!
Given a Laser Gun, described by the maximum number of times its laser can be reflected, determine how many angles Lami must find.
An integer $$$N$$$, the maximum number of times the laser can be reflected before disappearing.
$$$0 \le N \le 10^{14}$$$
An integer $$$M$$$, the amount of angles Lami must find.
1
1
2
2
In the first case, it's impossible to shoot the target with a single reflection, therefore, he can only shoot it directly.
In the second case, it's possible to shoot at 1/3 of the height or 1/3 of the width, totalizing 2 angles.
The Among Us game was famous during the pandemic. The game consists of two groups of space travelers: crew and imposters. Crew members do not know who the imposters are, but each imposter knows who all the other imposters are.
The objective of the game is for all the crew to find out who the imposters are. Kinho loves to be an imposter, and has fun with his friends using only "facts and logic". However, after a certain period of the game, all players have opinions and think they can find out all the imposters.
Each player's opinion consists of a list of no more than five other players. It is guaranteed that, for each crew member, the opinion given contains at least one impostor. However, the opinion of each imposter does not contain any other imposter. Your task is simple, given the number of players, and for each player, their opinion, decide how many different combinations of imposters can exist so that there is no contradiction with the opinions given.
The input consists of several lines. The first line will be an integer $$$N$$$, $$$1 \lt = N \lt = 20$$$, indicating the number of players. Then $$$N$$$ lines, the $$$i$$$-th line consists of an integer $$$S$$$, $$$0 \lt = S \lt =5$$$,indicating the opinion of the $$$i$$$-th player, followed by $$$S$$$ integers $$$j$$$ indicating that the $$$j$$$-th player is suspicious. $$$1 \lt = j \lt = N$$$.
The output must contain only an integer. The total number of different combinations of imposters, so that there is no contradiction in any combination found.
5 2 2 3 2 1 4 3 2 4 5 0 2 1 2
1
Loureiro is fond of observing and creating patterns. One day, he discovered a device, named unidimensional cellular automaton. Observing his operation, Loureiro found out that this device receives an equally divided tape of size $$$N$$$ as input, numbered from $$$1$$$ to $$$N$$$, where each cell is either a digit $$$0$$$ or $$$1$$$, and outputs a new tape of the same size. The device works as follow: for each position we take the number formed by the binary representation of $$$s_i$$$ concatenated with its neighbours $$$(s_{i-1}s_{i}s_{i+1})$$$, consider the tape is circular $$$(s_{0} = s_{N})$$$. From a set of rules defined by the device, this number could produce a cell with digit $$$0$$$ or $$$1$$$ for the resulting tape on position $$$i$$$.
Loureiro made modifications on this machine, now he can regulate its set of rules, defined as:
- $$$K$$$ : The size of the neighborhood (originally $$$1$$$), that defines the number of cells to the left and to the right to be analyzed.
- $$$M$$$ : A binary number with $$$(2^{2*k+1})$$$ bits, where the $$$i$$$th bit defines the mapping for number $$$i$$$.
For example, if $$$K = 1$$$ and $$$M = 00011110$$$ we have the following correspondence:
Loureiro has a tape, and after adjusting the device, he wonders what would be the final state of the tape after passing it $$$Q$$$ times on the machine. As Loureiro is very lazy, he asked you to finish this task.
The first line contains 3 integers $$$N$$$, $$$K$$$ and $$$Q$$$, $$$(1 \leq N \leq 1000, 1 \leq K \leq 5, 1 \leq Q \leq 100)$$$, representing the tape size, neighborhood size and the amount of repetitions respectively. It's guaranteed that $$$2*K+1 \leq N$$$. The second line contains a binary string $$$m$$$ of size $$$2^{2*k+1}$$$, the mapping of the rule set. The third line has a binary string $$$s$$$ of size $$$N$$$, representing the tapes's initial state.
A binary string representing the final state of the tape after $$$Q$$$ repetitions.
11 1 1 00011110 00000100000
00001110000
15 1 25 01101110 010110101100101
011000011111010
12 2 42 00000000000000000000000000011110 111010001011
000000000110
12 2 23 11000101010001001001011101001100 010011111001
101010101010
This is an interactive problem.
Galdino downloaded his favorite game on his computer, but he can't remember in which folder he put it. In his computer there is a total of $$$N$$$ folders numbered from $$$1$$$ to $$$N$$$ and in only one of them he can find his favorite game. Fortunately, his friend Clippy promised to help.
Clippy offers Galdino the following game: you can choose two integers $$$L, R$$$ and I will tell you whether the game is in any of the folders in the interval $$$[L, R]$$$. However, you only have up to 25 tries and if you can't find your game until there, I will eat all of your files!
Feeling confident, Galdino decided to accept Clippy's risky game. Help him!
The first line of input will contain a single integer $$$N$$$ ($$$1 \le N \le 10^6$$$) indicating the number of folders in Galdino's computer.
When you feel that you found the right folder, print the string "! x", where $$$x$$$ is the index of the game's folder. After that, terminate your program.
To ask Clippy a question, print two integers $$$L, R$$$ ($$$1 \le L \le R \le N$$$) and flush the output. After flushing it, the answer for this query can be read from input.
After every query, it will be printed to input 0 if the game can't be found in any folder in $$$[L, R]$$$ or 1 otherwise.
To flush you can use:
- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
- see the documentation for other languages.
1 1
1 1 ! 1
4 0 0 1
1 1 2 2 3 3 ! 3
The death star is the dreadful symbol of the Galactic Empire war machine. It's a space station with spherical format, big as a moon and armed with a superlaser capable of destroying planets.
Originally, its laser mechanism operated with a single shot, demanding a lot of time and energy to be reloaded. But recent research introduced a new technology of continuous radiation emission, enabling the destruction of multiple planets in sequence.
Grand Moff Tarkin is conducting the test phase of this new system. He would like to take this opportunity to eliminate some of the Rebel's Alliance bases that could be located in nearby planets. But this attack must be planned with caution, as several planets are occupied by imperial troops that would be exterminated.
The planets nearby are represented as coordinates on a cartesian plane, with the death star located on the origin. The superlaser is modeled as a semi-straight line starting on the origin, that sweeps the plane in an uninterrupted rotation movement. The region covered must always be continuous (as a pizza slice). Notice that the region could englobe no planet.
Determine the largest advantage in the number of troops that the Galactic Empire could acquire with this attack.
The first line of the input contains a single integer $$$N$$$, $$$(1 \leq N \leq 10^5)$$$, the number of planets.
It follows $$$N$$$ lines, with information about the problem. Each of them has four integers $$$x_i$$$, $$$y_i$$$, $$$a_i$$$ and $$$s_i$$$ $$$(-10^9 \leq x_i, y_i \leq 10^9, 0 \leq a_i, s_i \leq 10^9)$$$ — the cartesian coordinates of the i-th planet and the garrisons's sizes of the Rebel's Alliance and the Galactic Empires located on the planet.
It's guaranteed that no planet is positioned on the origin and no pair of them have the same coordinates.
Output a single integer – the maximum possible difference between the number of losses of the Rebel's Alliance and the Galactic Empire after the attack of the new superlaser.
8 -5 4 10 4 7 -8 3 2 -12 -3 4 7 5 4 12 7 -7 13 1 2 2 9 5 8 10 -4 6 10 -7 -7 5 4
7
Bini is a student from UFPE that lives a very busy life, as he studies during the day and works as a DJ during the night. One day, he was called by a famous song producer in Recife to participate in an interview with "ULULU", the biggest record label in Brazil.
Determined to impress the label in his big day, Bini decided to write a song with $$$n$$$ words to add to his playlist and make it less repetitive.
Because he is a very busy guy, Bini asked you to help him analyze and modify his song. To do this, he will ask $$$m$$$ queries of 3 types:
- $$$1$$$ $$$i$$$ $$$j$$$ $$$c$$$ : change the j-th letter of the i-th word to charater c;
- $$$2$$$ $$$i$$$ $$$j$$$ $$$L_i$$$ $$$R_i$$$ $$$L_j$$$ $$$R_j$$$ : answer if substring $$$[L_i, R_i]$$$ of the i-th word is equal to substring $$$[L_j, R_j]$$$ of the j-th word;
- $$$3$$$ $$$i$$$ $$$j$$$ $$$L_i$$$ $$$R_i$$$ $$$L_j$$$ $$$R_j$$$ : answer if substring $$$[L_i, R_i]$$$ of the i-th word concatenated with substring $$$[L_j, R_j]$$$ of the j-th word forms a palindrome.
Your task is to answer all of Bini's queries, to help him in his big day, guaranteeing that he signs a big DJ contract.
The first line of input contains two integers $$$n$$$ ans $$$q$$$ ($$$1 \le n, q \le 10^5$$$), the number of words in the song and the number of queries asked by Bini.
The next $$$n$$$ lines contain one word each, with the $$$i+1$$$ line containing the i-th word.
The next $$$q$$$ lines contain one query each, in the format specified above. It is guaranteed that all queries are valid and that at least one query will not be of type 1.
All the strings will consist only of lowercase Latin letters, and it's guaranteed that the sum of lengths of all the words in the input will not exceed $$$2*10^5$$$.
For queries of type 2, print one line with the word "equal" if the substrings are equal and "different" if they are not.
For queries of type 3, print one line with the word "cool" if the resulting string is a palindrome and "not so cool" if it isn't.
6 7 pao de batata hummta que delicia 2 2 6 2 2 2 2 2 3 3 3 4 5 6 3 3 6 2 4 6 7 3 3 3 2 4 5 6 1 6 6 t 3 3 6 2 4 6 7 2 1 2 1 1 1 1
equal equal not so cool cool cool different
A palindrome is a word that can be read both from right to left and from left to right without change, such as the words "ululu", "cc" and "o".
André is a person that loves trees... In his backyard, he has a plantation of several mystical and beautiful trees. But one tree stands out among the others ... The fruits of that tree are colorless.
This tree has $$$N$$$ fruits and each fruit is numbered from $$$0$$$ to $$$N-1$$$.
Each fruit connects to at least one other fruit through magical branches.
Initially, there are $$$N-1$$$ magical branches on the tree.
Since André finds the tree with colorless fruit unsightly, he decided to paint each fruit with a specific color.
However, every season of the year, there is a magical event in this tree, where each fruit later painted by André loses its color, and becomes colorless again. In addition, in this event, two fruits are temporarily connected, through a new magical branch. It is guaranteed that the first fruit is ancestor of the second fruit, considering the tree being rooted at the node 0. It is also guaranteed that these fruits are different. That connection is broken in the next season.
Since André is stubborn, he decides to paint the tree again each season. In each event, André has $$$Ki$$$ different colors at his disposal to paint the fruits of the tree, where $$$i$$$ is the index of each event. At each event, André wants to find out how many ways he can paint the tree, with the following condition: fruits connected by magical branches cannot have the same color. Since André is very busy playing Counter-Strike, he decided to ask for your help in calculating how many ways he can paint the fruits of the tree in the next $$$Q$$$ events.
Since there can be many ways to paint the tree, André is only interested in the remainder of the division of the quantity of ways to paint the tree by $$$1000000007$$$.
Be $$$X$$$ a node in a tree rooted on the node $$$R$$$, $$$Y$$$ is called ancestral of $$$X$$$, if $$$Y$$$ is contained in the path from $$$R$$$ to $$$X$$$.
An integer number $$$N$$$, indicating the number of fruits in the tree, followed by another integer $$$Q$$$, indicating the number of events. ($$$3 \le N, Q \le 10^5 $$$).
Then, $$$N-1$$$ lines, each line containing two integers, $$$U$$$ and $$$V$$$, indicating that exists a magical branch connecting fruit $$$U$$$ and fruit $$$V$$$( $$$0 \le U , V \le N-1$$$ ).
Then, $$$Q$$$ lines, where each line contains three integers: $$$U$$$, $$$V$$$, $$$K$$$, indicating that a new temporary magical branch will connect the fruits $$$U$$$ and $$$V$$$, and André has $$$K$$$ colors to paint the fruits of the tree ( $$$0 \le U , V \le N-1$$$ ) ( $$$3 \le K \le 10^9 $$$ ).
$$$Q$$$ lines, each line containing one integer, indicating the number of different ways André has to paint the fruits of the tree on each event, mod $$$1000000007$$$.
4 1 0 1 1 3 2 1 0 2 3
12
Before the first event, the colorless tree looks like this:
After the first event, the colorless tree looks temporarily like this:
The 8 game consists of a 3x3 matrix. Each cell has a distinct number between 1 and 8 or a white space.
Let $$$M$$$ be the given matrix, if $$$M_{i,j} == 0$$$, then you can do four operations:
- Swap $$$M_{i,j}$$$ with $$$M_{i,j+1}$$$, if $$$j \lt 3$$$
- Swap $$$M_{i,j}$$$ with $$$M_{i,j-1}$$$, if $$$j \gt 1$$$
- Swap $$$M_{i,j}$$$ with $$$M_{i+1,j}$$$, if $$$i \lt 3$$$
- Swap $$$M_{i,j}$$$ with $$$M_{i-1,j}$$$, if $$$i \gt 1$$$
Let's assume you swapped $$$M_{i,j}$$$ with $$$M_{i',j'}$$$, and let $$$x == M_{i',j'}$$$, then this operation has $$$Cost_x$$$ of cost.
$$$Cost_x$$$ is the swap cost for each number $$$x$$$, $$$1 \lt = x \lt = 8$$$.
Kinho loves the 8 game, but now he is very busy developing his 3D game library, so he asks you to solve this problem.
Given the initial matrix and the cost to move each number, say what is the minimum cost necessary to order the matrix in the requested way.
The input consists of four lines. The three initial lines contains three distincts integers each. $$$0 \lt = M_{i,j} \lt = 8$$$, where $$$0$$$ represents a white space cell. The fourth line contains eight integers, where the $$$i$$$-th integer represents the cost $$$Cost_i$$$ to swap the cell with the number $$$i$$$. $$$1 \lt = Cost_i \lt = 10^9, 1 \lt = i \lt = 8$$$
Print a single integer, the minimum cost to reorganize the matrix. In the given input, there is always a valid answer.
5 4 0 6 1 8 7 3 2 1 1 1 1 1 1 1 1
22
1 2 3 4 5 6 7 8 0 1 1 1 1 1 1 1 1
0
Covid cases are surging in the Country of NLogônia, the Prime Minister has fired all health and statistics officials and now he needs your help. Each day you'll receive two types of queries:
$$$\textit{1}, \textit{id}, \textit{x}$$$
You receive the city's id and how many new cases it has.
$$$\textit{2}, \textit{k}$$$
You have to answer how many cities have more than k cases. Initially all cities have zero cases.
The first line contains two integers $$$(1\leq\textit{q}\leq10^5;1 \leq \textit{n}\leq 10^5)$$$, the number of queries and the number of cities.
$$$\textit{q}$$$ queries follow, each query is in the formats:
1 id x where $$$(0\leq\textit{id} \lt n;1 \leq \textit{x}\leq 10^{13})$$$
2 k where $$$(0\leq\textit{k}\leq 10^{18})$$$
For the second type of query print how many cities have more than $$$\textit{k}$$$ cases.
6 10 1 0 10 1 1 9 2 2 2 8 2 9 2 10
2 2 1 0
4 5 1 0 10 2 10 1 0 1 2 10
0 1
You and your group of friends went to the Café at Area II to have a coffee between classes. As usual the group makes a circle and starts to chat and you want to seize this opportunity to impress your friends! However, the risk of you being embarrassed must be taken into account. In order to do this, you need to know in a timely manner if it is possible to solve a 2x2x2 magic cube within 5 moves, since more than this would make you look like a goofy.
A 2x2x2 cube can be flattened by cutting its edges. The result would look like this:
You'll receive 8 line where each one of them represents a line of the cube printed into a 2D plan.
..NO..
..MP..
..JK..
..IL..
BCFGVW
ADEHUZ
..RS..
..QT..
Replace every letter with a digit between 1 and 6, representing the color. It's guaranteed that each colors appears exactly 4 times.
For the single test case:
"YES", if you can impress your friends; "NO", otherwise.
You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).
..13.. ..25.. ..46.. ..66.. 145253 342251 ..13.. ..46..
NO
..33.. ..55.. ..66.. ..66.. 112233 551122 ..44.. ..44..
YES