E is climbing a multi-level gyroscopic tower with $$$n$$$ circular levels. There is a rare musical note at the top of the tower she wants to obtain. Each $$$i$$$th level can rotate independently, and has a known starting angle $$$a_i$$$ (measured in degrees starting from the North, where $$$0^\circ \leq a_i \lt 360^\circ$$$).
E starts at the bottom level, and can only climb to the next level after aligning her current level. We say a level has been aligned when the angle of the level matches the angle of all levels below it, either by moving it clockwise or counterclockwise (which is trivially satisfied if it is the bottom level). Furthermore,
- The rotations between angles should be treated as the shortest linear distance (not wrapping around the circle).
- For example, aligning from 359$$$^\circ$$$ to 0$$$^\circ$$$ would require a full 359 degree rotation, rather than a 1 degree rotation.
E is lazy, and wants to reach the top of the tower with minimum effort. Please help her determine the fewest total degrees of rotation needed to align all levels of the tower.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^3$$$), the number of levels in the tower.
The next line contains $$$n$$$ integers, $$$a_1,a_2,\cdots, a_n$$$ for $$$0 \leq a_i \lt 360$$$.
Please output the fewest total degrees of rotation needed to align all levels of the tower.
34 6 270
266
1418 291 230 140 24 293 29 53 359 20 1 39 200 49
1386
In the first sample test case, rotating all levels to exactly 6$$$^\circ$$$ from North gives $$$|4-6| + |6-6| + |270-6|$$$ = 266 degrees, which is also the minimum possible degrees of rotation.
Nancy is learning about pianos and music theory!
Her piano looks like the above, and it consists of various black and white keys. The white keys are indexed by number-letter pairs, starting at C1 and ending at C8. The indexing system begins C1, D1, E1, F1, G1, A1, B1, C2, D2, and so on until A7, B7, C8. Nancy wonders, between a particular pair of white keys, how many black keys are there? Can you help her out with various queries?
The input will consist of a single line containing a pair of white key indices (each represented by a letter between A and G and a number between 1 and 8), separated by a space. It is guaranteed that the first white key index is smaller than or equal to the second one, based on the indexing scheme mentioned above. It is also guaranteed that both of the indices appear between the range of C1 and C8.
The output should consist of a single line containing a single integer, the number of black keys that appear on Nancy's piano between the two white keys specified in the input.
C1 C8
35
A5 D6
2
In the first sample test case, the range of keys is the entire piano, so all of the black keys are counted, for a total of 35.
Maggie has a piano keyboard of length $$$n$$$, and she wants to know how many white keys and black keys it contains. The length of the keyboard is the distance from the left of the leftmost key to the right of the rightmost key.
- The width of the keys is as follows:
- White keys are 4 units wide.
- Black keys are 2 units wide.
- The keyboard pattern starts with a white key labeled "F" and follows a repeating arrangement. Each black key is centered between two white keys, extending 1 unit over each neighboring white key.
- Occasionally, Maggie might encounter a "weird" keyboard where a black key extends beyond the edge of a white key without any white key underneath. An example is shown below.
The goal is to determine the number of white and black keys on a keyboard of length $$$n$$$ that follows this pattern. If the keyboard cannot have length $$$n$$$, output $$$-1$$$.
The first integer will contain $$$n$$$ ($$$1\leq n\leq 1000$$$) — the length of the piano Maggie was given.
The output is two integers, $$$a, b$$$ which are the number of white and black keys.
1
-1
4
1 0
10
-1
9
2 2
This is the easy version of the problem. The only difference is that in this version, $$$n, w, b \leq 10^6$$$.
As you may know a standard piano has $$$88$$$ keys ($$$52$$$ white and $$$36$$$ black keys). Burt is quirky and wants to build a piano with $$$n$$$ keys, where the number of white keys is a multiple of $$$w$$$ and the number of black keys is a multiple of $$$b$$$.
Help Burt count the number of valid configurations of black/white keys for his custom piano given the constraints:
- The total number of keys is $$$n$$$,
- The number of white keys is a multiple of $$$w$$$,
- The number of black keys is a multiple of $$$b$$$,
- The number of white keys is between $$$0$$$ and $$$n$$$ inclusive, and similarly for the number of black keys.
The input contains three space-separated integers $$$n, w, b$$$ ($$$0 \leq n, w, b \leq 10^6$$$) — the total number of keys, the required divisor for the number of white keys, and the required divisor for the number of black keys, respectively.
Please output one integer, the total number of different ways Burt can configure his piano.
156 24 60
1
72 9 15
2
81 3 3
28
10 2 1
6
Explanation for first two sample cases:
First sample case: The only valid piano with $$$156$$$ keys satisfying the constraints is one with $$$96$$$ white keys (multiple of $$$24$$$) and $$$60$$$ black keys (multiple of $$$60$$$).
Second sample case: the possible valid $$$72$$$-key pianos are:
- $$$72$$$ white keys (multiple of $$$9$$$) and $$$0$$$ black keys (multiple of $$$15$$$)
- $$$27$$$ white keys (multiple of $$$9$$$) and $$$45$$$ black keys (multiple of $$$15$$$)
A curious trend is taking place among pirates that sail the seven seas. To add a touch of sophistication to their rallying cries, the most notorious pirate ships have begun to play piano melodies before they hoist their flag and officially mount their attack.
Captain Beethoven is an expert sea-farer that has memorized $$$n$$$ pirate melodies. He is lawfully enjoying his trip across the second sea when he makes out a piano tune on the wind...
Beethoven would like to identify the ship from the melody he heard. Please find which pirate ship is approaching Captain Beethoven.
–
A pirate melody is a list of $$$m$$$ integers. Beethoven hears a melody with length $$$m$$$. The melody he hears matches a pirate ship's melody if all the notes he hears appear in the ship's melody in the same order. Pirate melodies repeat after $$$m$$$ notes, and the sequence Beethoven hears may start at a place that's different than what he memorized.
Return the index of the ship that has a matching melody to the song Beethoven hears. If there are two possible ships, return the ship with the earlier index. If there is no matching ship, return $$$-1$$$.
The first line contains $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^3$$$) — the number of pirate melodies and the length of each melody (including the melody that Beethoven hears) respectively.
The next line contains $$$m$$$ space-separated integers $$$s_1, s_2, ... s_m$$$ ($$$0 \leq s_i \leq 10^3$$$) — the $$$i$$$-th note in the melody that Beethoven hears.
The next $$$n$$$ lines each contain $$$m$$$ space-separated integers $$$a_{i,1}, a_{i,2}, ..., a_{i,m}$$$ ($$$0 \leq s_{i,j} \leq 10^3$$$) — the $$$j$$$-th note in the melody of the $$$i$$$-th ship.
A single integer representing the index of the first matching ship or $$$-1$$$ if no ships match.
3 41 2 3 44 1 2 31 1 2 31 2 3 1
1
This is the hard version of the problem. The only difference is that in this version, $$$n, w, b \leq 10^9$$$.
As you may know a standard piano has $$$88$$$ keys ($$$52$$$ white and $$$36$$$ black keys). Burt is quirky and wants to build a piano with $$$n$$$ keys, where the number of white keys is a multiple of $$$w$$$ and the number of black keys is a multiple of $$$b$$$.
Help Burt count the number of valid configurations of black/white keys for his custom piano given the constraints:
- The total number of keys is $$$n$$$,
- The number of white keys is a multiple of $$$w$$$,
- The number of black keys is a multiple of $$$b$$$,
- The number of white keys is between $$$0$$$ and $$$n$$$ inclusive, and similarly for the number of black keys.
The input contains three space-separated integers $$$n, w, b$$$ ($$$0 \leq n, w, b \leq 10^9$$$) — the total number of keys, the required divisor for the number of white keys, and the required divisor for the number of black keys, respectively.
Please output one integer, the total number of different ways Burt can configure his piano.
156 24 60
1
72 9 15
2
81 3 3
28
10 2 1
6
Explanation for first two sample cases:
First sample case: The only valid piano with $$$156$$$ keys satisfying the constraints is one with $$$96$$$ white keys (multiple of $$$24$$$) and $$$60$$$ black keys (multiple of $$$60$$$).
Second sample case: the possible valid $$$72$$$-key pianos are:
- $$$72$$$ white keys (multiple of $$$9$$$) and $$$0$$$ black keys (multiple of $$$15$$$)
- $$$27$$$ white keys (multiple of $$$9$$$) and $$$45$$$ black keys (multiple of $$$15$$$)
Sergei Rachmaninoff is hosting a competition — which if his students can best play his latest composition - Opus 18 Piano Concerto No. 2. He has $$$n$$$ students, numbered $$$1, 2, ... n$$$, each of which is also part of various circles in the Russian mafia. The students all have a rival who they want to target — student $$$i$$$ wants to shoot down student $$$s_i$$$. Note that it is possible for $$$i = s_i$$$ (the nerves ... ).
You, Rachmaninoff's assistant, want to minimize the bloodshed. Therefore, you want to order the students in such a way so as to minimize the bloodshed — you don't like violence. The students play sequentially, and if its a student's turn but they are already dead, the competition moves on to the next in line. Each students best opportunity to shoot their assigned rival is as they are exiting the stage, therefore, student $$$i$$$ only attempts to shoot $$$s_i$$$ once they have finished performing, before the next performance starts. Find the minimum number of casualties across all possible permutations of students at this event.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 200,000$$$) — the number of students.
The second line contains $$$n$$$ space separated integers $$$s_1, s_2, ... s_n$$$ ($$$1 \le s_i \le n$$$) — the student who the $$$i$$$th student wants to shoot down, respectively.
A single integer that gives the minimum number of casualties in the competition across all permutations of students.
82 3 2 2 6 7 8 5
3
51 2 3 4 5
5
62 3 4 5 6 1
3
52 3 1 2 4
3
In the first sample, we can achieve 3 deaths (and no better) from the order of performances - 1 2 3 4 5 6 7 8.
In the second sample, everyone is able to target themself, so .
The third sample is a cycle - the order 1 2 3 4 5 6 ensures only 3 deaths.
In the fourth sample, the order 5 1 2 3 4 targets 3 people, with students 3 and 5 surviving at the end.
You are an avid osu!mania player, a piano-style rhythm game where you press notes that appear on the screen at the right time. You live in a neighborhood of osu!mania players, conveniently shaped in a grid. To prepare for the tournament, you decide to collect some beatmaps from other people in the neighborhood.
Your house is in the first row and first column. To walk around in the neighborhood, you can only increase your row number, decrease your row number, or increase your column number. You also do not want to visit a house that you have already visited before. Your walk will end immediately once you have visited all the houses with beatmaps. In order to decide which path to take, you want to compute how many paths visit every house with a beatmap. Since there may be many paths, output the answer mod $$$998244353$$$.
The first line contains three integers $$$r$$$, $$$c$$$, and $$$k$$$ ($$$1 \leq r, c \leq 10^9$$$, $$$1 \leq k \leq 10^5$$$) — the number of rows, columns, and beatmaps, respectively.
The following $$$k$$$ lines contain two integers $$$a, b$$$ ($$$1 \leq a \leq r$$$, $$$1 \leq b \leq c$$$) — denoting that the person living in the house at row $$$a$$$ and column $$$b$$$ has a beatmap. It is guaranteed that no $$$(a, b)$$$ pair appears twice in this list.
Output the number of walks that visit every house with a beatmap, mod $$$998244353$$$.
1 2 11 2
1
2 2 11 2
2