You're trying to make several banners that say "coderams" on them, for an upcoming in-person coding competition. However, you have a limited number of letter stickers that you can use. All you have is a long string of $$$n$$$ lowercase letter stickers. Given this, your task is to figure out the maximum possible number of complete banners (that say "coderams" on them, not just part of the string), given the letter stickers that you have.
The first line of input consists of a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 10^5)$$$: the number of letter stickers that you have.
The next line consists of a single $$$n$$$-character string, each character representing the letter of one sticker that you have. All stickers will have lowercase letters on them.
Output the number of complete banners that you can make with the letter stickers you have.
Full problem: 6 points
18 arcmodessmarcodarc
1
4 code
0
32 ramscodecoderamsramscodecoderams
4
You have an array $$$a$$$ consisting of $$$n$$$ positive integers. You decide to "condense" this array. In one operation, you can replace any $$$m$$$ elements of the array with a single element consisting of their sum.
For example, if you had the array $$$a = [2, 7, 1, 8, 2, 8]$$$ and $$$m = 3$$$, you could, for example, do the operation on the second, third, and fifth elements, making the array $$$[2, 10, 8, 8]$$$ (note that the order of the array elements doesn't matter for this problem).
Given this information, your task is to figure out the maximum possible largest element in the array that could exist after $$$k$$$ operations.
The first line of input contains three space-separated positive integers $$$n$$$ $$$(1 \lt = n \lt = 10^5)$$$, $$$m$$$ $$$(1 \lt = m \lt = n)$$$, and $$$k$$$ $$$(1 \lt = k \lt = n, k * m \lt = n)$$$: the length of the array, the number of elements that you can change in a single operation, and the number of operations you can make, respectively.
The next line of input contains the array $$$a$$$ $$$(1 \lt = a_i \lt = 10^9)$$$.
Output a single positive integer, representing the maximum possible largest element in the array, after applying exactly $$$k$$$ of the operations described above.
Note that the answer may overflow traditional 32-bit integers.
Full problem: 9 points
6 3 1 2 7 1 8 2 8
23
9 2 3 1 5 4 9 8 6 3 5 7
30
You have a tree, or an undirected connected graph with no cycles, with $$$n$$$ vertices and $$$n - 1$$$ edges. Vertex 1 is the root.
You define a "leaf vertex" to be a vertex on the tree, other than the root, that is adjacent to exactly one branch vertex.
You also define a "branch vertex" to be a vertex on the tree other than the root, that is adjacent to exactly two other vertices, and adjacent to at least one leaf vertex.
You define a tree to be more of a "taiga tree" the more branch vertices that it has. Given a tree, figure out how many branch vertices it has.
The first line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 10^5)$$$: the number of vertices on the tree.
The next $$$n - 1$$$ lines each contain two space-separated integers, each representing an edge on the tree.
Output a single positive integer: the number of branch vertices on the tree, as defined above.
Full problem: 15 points
6 1 2 2 3 1 4 4 5 5 6
2
8 1 2 2 3 1 4 4 5 5 6 6 7 6 8
1
Here is a visual representation of the first example case (the branch vertices are circled):
You go to a school with $$$n$$$ students, all of which can be identified by a unique student ID from 1 to $$$n$$$, inclusive. The school has $$$m$$$ classes, each consisting of $$$k$$$ students.
Unfortunately, $$$c$$$ students just tested positive for COVID-19, and the school is figuring out which other students need to go into quarantine due to the $$$c$$$ students testing positive.
Since the school is being very cautious, they decide to have any students in at least one class with the $$$c$$$ students quarantine, but the school decides to extend the rule and have any students in a class with a quarantined student quarantine as well. This continues in a "chain reaction" process, until there are no more additional students that have to quarantine.
Given the $$$c$$$ students that just tested positive, figure out the ID's of any additional students that have to quarantine (not including the original $$$c$$$ students).
The first line of input consists of three space-separated integers $$$n$$$ $$$(1 \lt = n \lt = 10^5)$$$, $$$m$$$ $$$(1 \lt = m \lt = 10^5)$$$, and $$$k$$$ $$$(1 \lt = k \lt = 10^5)$$$, $$$m * k \lt = 10^5$$$: the number of students in the school, the number of classes in the school, and the number of students in each class, respectively.
The next $$$m$$$ lines each contain $$$k$$$ distinct space-separated integers: the student ID's of each student in each class.
The next line contains a single positive integer $$$c$$$ $$$(1 \lt = c \lt = n)$$$: the number of students that recently tested positive for COVID-19.
The next line contains $$$c$$$ distinct space-separated positive integers: the student ID's of the students that recently tested positive.
Output a single positive integer $$$q$$$: the number of additional students that have to quarantine.
Then, output a single line consisting of $$$q$$$ space-separated integers in ascending order: the number of students that will have to quarantine (not including the students that already tested positive).
Subtask 1 (14 points): $$$(1 \lt = n, m, k, m*k \lt = 1000)$$$
Subtask 2 (9 points): no additional constraints
13 4 5 1 3 5 6 7 3 5 8 6 1 2 9 11 10 4 4 11 9 13 2 3 1 5 8
3 3 6 7
13 4 5 1 3 5 6 7 3 5 8 6 1 2 9 10 11 4 4 11 9 13 2 4 1 5 8 4
8 2 3 6 7 9 10 11 13
30 10 5 18 5 2 20 15 7 18 16 9 17 23 26 15 24 21 8 29 10 23 7 29 17 10 2 21 2 14 20 7 11 21 20 4 15 23 10 18 6 16 9 20 12 11 8 2 18 6 20 16 19 1 29
21 2 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 23 24 26
You consider a number to be "magic" if it has an even number of digits (not counting leading zeros), and if the first half of the number is equal to the second half of the number. For example, $$$13151315$$$, $$$878878$$$, and $$$9999$$$ are magic numbers, while $$$35353$$$, $$$12345$$$, and $$$3663$$$ are not.
You really like magic numbers, and you decide to play a game given a starting number $$$n$$$.
In one turn, you change the number $$$n$$$ depending on the following instructions:
- If $$$n$$$ consists entirely of an odd number of nines (i.e. $$$99999$$$ or $$$9$$$), the game ends.
- Otherwise, if $$$n$$$ is a magic number (as described above), you replace $$$n$$$ by the first half of its digits (so $$$13151315$$$ would become $$$1315$$$), which takes one turn.
- Otherwise, you increase $$$n$$$ by $$$1$$$, which takes one turn.
It can be proven that the game will always end eventually.
Given these rules, figure out how many turns the game will take before the game ends.
The only line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt 10^{12})$$$: the number you start out with.
Output a single positive integer $$$t$$$: the number of turns you will end up taking before the game ends.
Subtask 1 (6 points): $$$n$$$ <= $$$10^5$$$
Subtask 2 (18 points): no additional constraints
86
4
7977
14
982490834438
148563
You have an array $$$a$$$ consisting of $$$n$$$ integers. Your favorite number is $$$k$$$, and you want to see if you can find any triple of distinct indices with a product of $$$k$$$. In other words, you're looking for three distinct indices $$$x$$$, $$$y$$$, and $$$z$$$, such that $$$a_x * a_y * a_z = k$$$.
The first line of input contains two space separated integers $$$n$$$ $$$(1 \lt = n \lt = 10^5)$$$ and $$$k$$$ $$$(1 \lt = k \lt = 10^5)$$$.
The next line consists of $$$n$$$ space-separated integers: the array $$$a$$$ $$$(1 \lt = a_i \lt = 10^4)$$$.
Output a single positive integer representing the number of triples of distinct indices in $$$a$$$ that have a product of $$$k$$$.
Subtask 1 (4 points): $$$n \lt = 100$$$
Subtask 2 (8 points): $$$n \lt = 2000$$$
Subtask 3 (26 points): no additional constraints
5 24 6 2 3 4 1
2
7 7 1 1 1 7 7 7 8
9
6 27 1 3 3 3 3 9
8
You have an $$$n$$$ by $$$n$$$ 2D grid consisting of $$$n^2$$$ integers. You're trying to find the "plus sign" in the grid with the maximum sum.
You define a "plus sign" to be any contiguous segment of rows (including at least one row), and any contiguous segment of columns (including at least one column). For example, the cells highlighted in blue in the image below are a plus sign:
Your task is to find the sum of the elements of the 2D grid in the plus sign with the maximum sum. For example, the plus sign shown above has a sum of elements of 15.
Note that a valid plus sign doesn't necessarily have to look like a plus sign if it fits the definition above, i.e. the entire grid (a rectangle) would be considered a valid plus sign, as well as a T-shape (if the plus sign included the top row).
The first line of input contains a single positive integer $$$n$$$ $$$(4 \lt = n \lt = 400)$$$: the width and height of the 2D grid.
The next $$$n$$$ lines each contain $$$n$$$ space-separated positive integers: the grid. Each grid element will be between $$$-10^9$$$ and $$$10^9$$$, inclusive.
Output a single integer, representing the sum of the elements on the plus sign with the maximum sum in the 2D grid, as defined above.
Subtask 1 (15 points): $$$n \lt = 40$$$
Subtask 2 (27 points): no additional constraints
5 3 7 -9 8 2 1 -5 3 -4 1 -3 2 0 3 6 -1 -8 5 6 2 4 5 -1 -3 5
34
4 -9 -1 -3 -2 -4 -6 -8 -1 -1 -1 -3 -2 -10 -12 -4 -5
-15
You have a house consisting of several rooms, which can be represented as an $$$n$$$ by $$$n$$$ top-down floor plan (showing both walls and open space in the house).
You are trying to give each open space in the house a certain number. However, you decide that to avoid repetition, all pairs of numbers in the same room must have a GCD of 1.
Given these restrictions, your task is to figure out the minimum possible sum of numbers you can assign to in the open spaces of the house, if you have to assign a number to every open space.
The first line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 800)$$$: the width and height of the house.
The next $$$n$$$ lines each contain an $$$n$$$-character string representing the floor plan of the house. An "x" character represents a wall, while a "." character represents open space.
Output a single positive integer: the minimum possible sum of numbers in the open spaces in your house, per the rules outlined above.
Full problem: 58 points
4 xxxx x..x x..x xxxx
11
10 xxxxxxxxxx x...x....x x...x....x x.xxxxxxxx xxx......x x.x.xxxxxx x.x.x....x xxx.xxx..x x.....x..x xxxxxxxxxx
402
In the first example case, you can place the numbers 1, 2, 3, and 5 in the four open spaces.
You work for the CIA, and take the subway to work every day. The subway consists of $$$n$$$ stations, connected by $$$m$$$ lines. You live near station $$$a$$$, and work near station $$$b$$$. Each line consists of a specified route of $$$k_i$$$ stations (where each train goes either from the first to the last in order, or from the last to the first in order). You are guaranteed to be able to travel between any pair of stations by going on one or more subway lines.
Unfortunately, you've just received word that an enemy agent is hiding in one of the stations in the subway. You're not sure which one the enemy agent is hiding in, but you do know that they're going to stay in the same station for the whole day.
You still need to get to and from work, but you want to avoid ever being in the same station with the enemy agent. Thus, your task is to figure out, for each station, whether you can still travel from home to work (and back), if the enemy agent is in that station.
The first line of input contains four space-separated integers $$$n$$$, $$$m$$$, $$$a$$$, and $$$b$$$ $$$(1 \lt = n, m \lt = 10^5)$$$, $$$(1 \lt = a, b \lt = n)$$$, $$$(1 \lt = \sum_{}{k_i} \lt = 10^5)$$$: the number of stations in the subway, the number of subway lines, the station that you live near, and the station that you work near, respectively.
Additionally, the subway system has at most 1000 "hub stations" (stations that more than one line go through).
The next $$$m$$$ line pairs each contain a single positive integer $$$k_i$$$, representing the number of stations that the line services, and a line consisting of the $$$k_i$$$ stations that the line services, in order.
Output a single binary string of length $$$n$$$, where a "1" character represents a station where, if the enemy agent was in the station, you could still go to work (and back), and a "0" character if not.
Full problem: 73 points
15 3 1 10 6 1 2 3 4 5 6 5 2 7 8 9 10 8 11 2 12 13 9 14 15 6
001111110011111
18 3 3 5 8 1 2 3 18 4 5 6 7 7 10 9 8 2 11 12 13 7 15 14 9 4 13 16 17
110001111111111111
Here is a visual representation of the first example case:
