Finn loves Fours and Fives. In fact, he loves them so much that he wants to know the number of ways a number can be formed by using a sum of fours and fives, where the order of the fours and fives does not matter. If Finn wants to form the number \(14\), there is one way to do this which is \(14 = 4 + 5 + 5\). As another example, if Finn wants to form the number \(20\), this can be done two ways, which are \(20 = 4+4+4+4+4\) and \(20 = 5+5+5+5\). As a final example, Finn can form the number 40 in three ways: \(40=4+4+4+4+4+4+4+4+4+4\), \(40=4+4+4+4+4+5+5+5+5\), and \(40=5+5+5+5+5+5+5+5\).
Your task is to help Finn determine the number of ways that a number can be written as a sum of fours and fives.
The input consists of one line containing a number \(N\).
The following table shows how the available 15 marks are distributed.
| Marks Awarded | Bounds on \(N\) | Additional Constraints |
|---|---|---|
| 3 marks | \(1 \leq N \leq 10\) | None |
| 2 marks | \(1 \leq N \leq 100\ 000\) | \(N\) is a multiple of \(4\) |
| 2 marks | \(1 \leq N \leq 100\ 000\) | \(N\) is a multiple of \(5\) |
| 8 marks | \(1 \le N \leq 1\ 000\ 000\) | None |
Output the number of unordered sums of fours and fives which form the
number \(N\). Output
0 if there are no such sums of fours and
fives.
141This is one of the examples in the problem description.
403This is one of the examples in the problem description.
60There is no way to use a sum of fours and fives to get \(6\).
A class has been divided into groups of three. This division into groups might violate two types of constraints: some students must work together in the same group, and some students must work in separate groups.
Your job is to determine how many of the constraints are violated.
The first line will contain an integer \(X\) with \(X \geq 0\). The next \(X\) lines will each consist of two different names, separated by a single space. These two students must be in the same group.
The next line will contain an integer \(Y\) with \(Y \geq 0\). The next \(Y\) lines will each consist of two different names, separated by a single space. These two students must not be in the same group.
Among these \(X+Y\) lines representing constraints, each possible pair of students appears at most once.
The next line will contain an integer \(G\) with \(G \geq 1\). The last \(G\) lines will each consist of three different names, separated by single spaces. These three students have been placed in the same group.
Each name will consist of between 1 and 10 uppercase letters. No two students will have the same name and each name appearing in a constraint will appear in exactly one of the \(G\) groups.
The following table shows how the available 15 marks are distributed at the Junior level.
| Marks Awarded | Number of Groups | Number of Constraints |
|---|---|---|
| 4 marks | \(G \leq 50\) | \(X \leq 50\) and \(Y = 0\) |
| 10 marks | \(G \leq 50\) | \(X \leq 50\) and \(Y \leq 50\) |
| 1 mark | \(G \leq 100\,000\) | \(X \leq 100\,000\) and \(Y \leq 100\,000\) |
The following table shows how the available 15 marks are distributed at the Senior level.
| Marks Awarded | Number of Groups | Number of Constraints |
|---|---|---|
| 3 marks | \(G \leq 50\) | \(X \leq 50\) and \(Y = 0\) |
| 5 marks | \(G \leq 50\) | \(X \leq 50\) and \(Y \leq 50\) |
| 7 marks | \(G \leq 100\,000\) | \(X \leq 100\,000\) and \(Y \leq 100\,000\) |
Output an integer between \(0\) and \(X+Y\) which is the number of constraints that are violated.
1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE0There is only one constraint and it is not violated: ELODIE and CHI are in the same group.
3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L3The first constraint is that A and B must be in the same group. This is violated.
The second constraint is that G and L must be in the same group. This is violated.
The third constraint is that J and K must be in the same group. This is not violated.
The fourth constraint is that D and F must not be in the same group. This is violated.
The fifth constraint is that D and G must not be in the same group. This is not violated.
Of the five constraints, three are violated.
You are composing music for the Cool Clarinet Competition (CCC). You have been instructed to make a piece of music with exactly \(N\) notes. A note is represented as a positive integer, indicating the pitch of the note.
We call a non-empty sequence of consecutive notes in the piece a sample. For instance, \((3, 4, 2)\), \((1, 2, 3, 4, 2)\) and \((4)\) are samples of \(1, 2, 3, 4, 2\). Note that \((1, 3)\) is not a sample of \(1, 2, 3, 4, 2\). We call two samples different if they start or end at a different position in the piece.
We call a sample good if no two notes in the sample have the same pitch.
The clarinet players are picky in two ways. First, they will not play any note with pitch higher than \(M\). Second, they want a piece with exactly \(K\) good samples.
Can you construct a piece to satisfy the clarinet players?
The first and only line of input will contain \(3\) space-separated integers, \(N\), \(M\) and \(K\).
The following table shows how the available 15 marks are distributed.
| Marks Awarded | Bounds on \(N\) | Bounds on \(M\) | Bounds on \(K\) |
|---|---|---|---|
| 3 marks | \(1 \le N \le 16\) | \(M=2\) | \(1 \leq K \leq 1\ 000\) |
| 3 marks | \(1 \leq N \leq 10^6\) | \(M=2\) | \(1 \leq K \leq 10^{18}\) |
| 4 marks | \(1 \leq N \leq 10^6\) | \(M=N\) | \(1 \leq K \leq 10^{18}\) |
| 5 marks | \(1 \leq N \leq 10^6\) | \(1 \le M \le N\) | \(1 \leq K \leq 10^{18}\) |
If there is a piece of music that satisfies the given constraints, output \(N\) integers between \(1\) and \(M\), representing the pitches of the notes of the piece of music. If there is more than one such piece of music, any such piece of music may be outputted.
Otherwise, output \(-1\).
3 2 51 2 1Notice that the piece is composed of \(N=3\) notes, each of which is one of \(M=2\) possible pitches, 1 and 2. That piece of music has a total of 6 samples, but only \(K=5\) good samples: \((1)\), \((1, 2)\), \((2)\), \((2, 1)\), \((1)\). Notice that the two good samples of \((1)\) are different since they start at two different positions.
Note that the piece 2 1 2 is the only other
valid output for this input.
One example of an output that would be incorrect is
3 2 3, since it has notes with pitches larger
than 2. Another incorrect output would be
1 1 2, since it only has four good samples:
\((1)\), \((1)\), \((2)\) and \((1,2)\).
5 5 141 5 3 2 1The 14 good samples are: \((1)\), \((1,5)\), \((1,5,3)\), \((1,5,3,2)\), \((5)\), \((5,3)\), \((5,3,2)\), \((5,3,2,1)\), \((3)\), \((3,2)\), \((3,2,1)\), \((2)\), \((2,1)\), \((1)\).
5 5 50-1There are no pieces with 5 notes that can produce 50 different good samples.
Andrew is a very curious student who drew a circle with the center at \((0,0)\) and an integer circumference of \(C \geq 3\). The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.
Andrew drew \(N \geq 3\) points at integer locations. In particular, the \(i\)th point is drawn at location \(P_i\) \((0 \le P_i \le C-1)\). It is possible for Andrew to draw multiple points at the same location.
A good triplet is defined as a triplet \((a,b,c)\) that satisfies the following conditions:
\(1 \le a < b < c \le N\).
The origin \((0,0)\) lies strictly inside the triangle with vertices at \(P_a\), \(P_b\), and \(P_c\). In particular, the origin is not on the triangle’s perimeter.
Lastly, two triplets \((a,b,c)\) and \((a',b',c')\) are distinct if \(a \ne a'\), \(b \ne b'\), or \(c \ne c'\).
Andrew, being a curious student, wants to know the number of distinct good triplets. Please help him determine this number.
The first line contains the integers \(N\) and \(C\), separated by one space.
The second line contains \(N\) space-separated integers. The \(i\)th integer is \(P_i\) \((0 \le P_i \le C-1)\).
The following table shows how the available 15 marks are distributed.
| Marks Awarded | Number of Points | Circumference | Additional Constraints |
|---|---|---|---|
| 3 marks | \(3 \le N \leq 200\) | \(3 \le C \leq 10^6\) | None |
| 3 marks | \(3 \le N \leq 10^6\) | \(3 \le C \leq 6\ 000\) | None |
| 6 marks | \(3 \le N \leq 10^6\) | \(3 \le C \leq 10^6\) | \(P_1, P_2, \ldots, P_N\) are all distinct (i.e., every location contains at most one point) |
| 3 marks | \(3 \le N \leq 10^6\) | \(3 \le C \leq 10^6\) | None |
Output the number of distinct good triplets.
8 10
0 2 5 5 6 9 0 06Andrew drew the following diagram.
The origin lies strictly inside the triangle with vertices \(P_1\), \(P_2\), and \(P_5\), so \((1,2,5)\) is a good triplet. The other five good triplets are \((2,3,6)\), \((2,4,6)\), \((2,5,6)\), \((2,5,7)\), and \((2,5,8)\).
There are \(N\) (\(N \ge 2\)) students in a computer science class, with distinct student IDs ranging from \(1\) to \(N\). There are \(N-1\) friendships amongst the students, with the \(i\)th being between students \(A_i\) and \(B_i\) (\(A_i \not= B_i\), \(1 \le A_i \le N\) and \(1 \le B_i \le N\)). Each pair of students in the class are either friends or socially connected. A pair of students \(a\) and \(b\) are socially connected if there exists a set of students \(m_1, m_2, \ldots, m_k\) such that
\(a\) and \(m_1\) are friends,
\(m_i\) and \(m_{i+1}\) are friends (for \(1 \leq i \leq k-1\)), and
\(m_k\) and \(b\) are friends.
Initially, each student \(i\) either
intends to write the CCC (if \(P_i\) is
Y) or does not intend to write the CCC (if
\(P_i\) is
N). Initially, at least one student intends to
write the CCC, and at least one student does not intend to write the
CCC.
The CCC has allocated some funds to pay some students to be influencers for the CCC. The CCC will repeatedly choose one student \(i\) who intends to write the CCC, pay them \(C_i\) dollars, and ask them to deliver a seminar to all of their friends, and then all of their friends will intend to write the CCC.
Help the CCC determine the minimum cost required to have all of the students intend to write the CCC.
The first line contains the integer \(N\).
The next \(N-1\) lines each contain two space-separated integers, \(A_i\) and \(B_i\) (\(1 \leq i \leq N-1\)).
The next line contains \(N\)
characters, \(P_{1}\ldots P_{N}\), each
of which is either Y or
N.
The next line contains \(N\) space-separated integers, \(C_{1}\ldots C_{N}\).
The following table shows how the available 15 marks are distributed.
| Marks Awarded | Number of students | Payment | Additional Constraints |
|---|---|---|---|
| 5 marks | \(2 \le N \leq 2\ 000\) | \(1 \le C_i \le 1\ 000\) | \(A_i = i\) and \(B_i = i+1\) for each \(i\) |
| 7 marks | \(2 \le N \leq 2\ 000\) | \(1 \le C_i \le 1\ 000\) | None |
| 3 marks | \(2 \le N \leq 200\ 000\) | \(1 \le C_i \le 1\ 000\) | None |
Output the minimum integer number of dollars required to have all of the students to intend to write the CCC.
4
1 2
2 3
3 4
YNYN
4 3 6 26The CCC should pay $6 to student 3 to deliver a seminar to their friends (students 2 and 4), after which all 4 students will intend to write the CCC.
15
1 5
5 2
2 15
15 4
2 10
8 3
3 1
1 6
11 6
12 6
11 9
11 14
12 7
13 7
NNYYYNYYNNNNNNN
1 1 1 1 1 1 1 1 1 1 1 1 1 1 16One optimal strategy is for the CCC to ask students 5, 1, 6, 11, 7, and 2 to deliver seminars, in that order, paying them $1 each.