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
Alice, a talented pianist, just composed a perfect melody! A melody is a sequence of $$$n$$$ notes $$$a_1, a_2, ..., a_n$$$, represented as integers. This melody is cyclic, meaning that the $$$n$$$th note is adjacent to the first note. Further, a perfect melody is one such that each pair of adjacent notes different in value by exactly $$$1$$$. (Formally, $$$|a_i - a_{(i \bmod n) + 1}| = 1$$$ for all $$$i \in \{1, 2, ..., n\}$$$)
Alice was just about to play the melody when Bob showed up and scrambled all the notes! Given an arbitrary ordering of the notes, help Alice determine the number of perfect melodies she can form by rearranging the notes. Two rearrangements are considered unique if for some $$$i$$$, the $$$i$$$-th element in the original ordering ends up in different positions between the two rearrangements.
The first line of input will contain $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of notes in the melody.
The next line of input will contain $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the (unordered) sequence of notes in the melody.
Output a single integer, representing the number of ways that the notes can be arranged into a perfect melody. Since this number may be very large, output it modulo $$$998244353$$$.
42 2 1 3
8
31 2 3
0
81 2 3 2 3 4 3 2
576
Aria, a composer, is trying to create the perfect chord for her orchestra of $$$k$$$ musicians. She wants the chord to contain exactly $$$k$$$ notes, and the sum of the values of each note should be exactly $$$n$$$. Each note is represented by a positive integer indicating its pitch.
In a chord, the order of notes doesn't matter, but the same pitch can be used multiple times (multiple instruments can play the same note). For example, a chord with notes $$$\{1, 3\}$$$ is the same as $$$\{3, 1\}$$$, and a chord with $$$\{2, 2\}$$$ is also valid.
For each valid chord with pitches $$$\{ p_1, p_2, \dots, p_K \}$$$ that sum to $$$n$$$, Aria wants to calculate the harmony level of the chord, which is defined as the sum of the squares of each pitch: $$$$$$ p_1^2 + p_2^2 + \dots + p_k^2 $$$$$$
Your task is to compute the total harmony level for all unique chords that can be formed with these conditions, then output this value modulo $$$10^9 + 7$$$.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 5 \cdot 10^3$$$) — the target sum of pitches and the exact number of notes in the chord, respectively.
Output a single number representing the total harmony level across all valid chords, modulo $$$10^9 + 7$$$.
5 3
20
There are two valid chords: $$$\{1,1,3\}$$$, and $$$\{1, 2, 2\}$$$. Their values are $$$11$$$ and $$$9$$$ which sum up to $$$20$$$.