You are given $$$n$$$ ($$$1 \leq n \leq 100$$$) pieces of bronze. Each piece of bronze has a distinct weight ranging from $$$1$$$ to $$$n$$$. The nearby pawn shop has interesting criteria for determining whether or not they will take a piece of bronze. They will weigh the piece of bronze, take the sum of the squares of all digits in the weight, and repeat this process with the new sum. If this number eventually reaches $$$1$$$, they will accept the piece of bronze. Otherwise, they will reject it. How many pieces of bronze will the pawn shop accept?
The first and only line of input will contain $$$n$$$ ($$$1 \leq n \leq 100$$$).
Output the number of pieces of bronze the pawn shop will accept.
5
1
1
1
20
5
The only differences between the first and second versions are constraints on the number and length of strings given as input. This problem has smaller upper bounds.
Edward and Alphonse Elric are exploring a recently discovered branch of alchemy created by the people of Xerxes. Rather than using transmutation circles, Xerxians used spoken phrases to facilitate alchemic reactions. Each phrase that can be used to perform Xerxian alchemy can be written as a string comprised of only lowercase alphabetical characters.
The primary property of interest when it comes to Xerxian alchemy is the theory behind creating multiple simultaneous reactions. A single phrase can kickstart any reaction whose written form is contained as a substring within the phrase string.
Remembering many phrases is difficult for the Elric brothers, so they would instead like to remember a single, potentially longer phrase that can perform all of the $$$N$$$ alchemic reactions that they know. To help with memorization, the Elrics want to minimize the length of the new phrase string. You, an expert programmer, (an alchemist in your own right), must help the Fullmetal Alchemist find the minimal length of such phrase.
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 2$$$), representing the number of phrases that the Elric brothers know. The next $$$N$$$ lines of input each contain a string $$$s_i$$$ ($$$1 \leq |s_i| \leq 100$$$), representing a reaction the Elric brothers want to incorporate into their new phrase. Note that these reactions do not necessarily have distinct written forms.
Output a single integer representing the minimal length of the single phrase containing all the given phrases.
1 pupperdoggo
11
2 lovely lycoris
11
You are the president of the micronation of Steelistan and as a result, you are responsible for handling the monthly exports of steel to other countries.
There are $$$N$$$ countries in the world and $$$M$$$ border crossings between pairs of countries that share a border (countries may share a border but not have a crossing due to geographical reasons). Every country has a distinct code number between $$$1$$$ and $$$N$$$, and Steelistan is denoted as country $$$1$$$. Each border crossing is between two different countries $$$A_i$$$ and $$$B_i$$$ and requires a customs fee $$$C_i$$$ to cross in either direction. Although shipping free within a country, exported steel may need to pass through several countries and thus several border crossings.
Understandably, these customs fees add up over time, so all the countries made a trade agreement to reduce costs for everyone: instead of paying the full sum of customs fees over multiple border crossings, a shipment is allowed to instead pay a separate fee $$$F$$$ at a single border crossing (but must still pay the full amount at all others). Steelistan is conveniently allowed to to exercise this right once a month for one steel shipment to each other country.
With this trade agreement in place, can you determine the minimal cost to export steel to every other nation?
The first line of input contains three integers $$$N$$$ ($$$2 \leq N \leq 10^5$$$), $$$M$$$ ($$$1 \leq M \leq 10^5$$$), and $$$F$$$ ($$$1 \leq F \leq 10^5$$$), representing the number of countries in the world, border crossings, and fixed cost of a border crossing under the trade agreement. The next $$$M$$$ lines of input each have three integers $$$A_i$$$ ($$$1 \leq A_i \leq N$$$, $$$A_i \neq B_i$$$), $$$B_i$$$ ($$$1 \leq B_i \leq N$$$, $$$B_i \neq A_i$$$), and $$$C_i$$$ ($$$1 \leq C_i \leq 10^5$$$), which describe a single border crossing. It is possible for there to be multiple border crossings between the same pair of countries.
Output $$$N - 1$$$ lines with a single integer each, the $$$i$$$-th of which represents the minimal cost to export from Steelistan to nation with code number $$$i+1$$$ (or $$$-1$$$, if it is not possible to reach that nation from Steelistan).
4 4 2 1 2 3 2 4 2 4 3 8 1 3 1
2 1 3
NASA has been exploring the galaxy and they've found a very interesting celestial arrangement. They hope to study it further by placing an observation station.
They have found $$$N$$$ neodymium spheres arranged at distinct points along a straight line. Each of these spheres can be described as a location $$$l_i$$$ and a mass $$$m_i$$$.
Given the high mass of these spheres, NASA's observation satellites will be accelerated by gravity towards sphere $$$i$$$ according to the formula $$$\frac{g m_i}{r^2}$$$, where $$$g$$$ is the gravitational constant and $$$r$$$ is the distance between the satellite and sphere. For some strange, unexplained reason the spheres themselves are guaranteed to never move.
NASA wants to place its observation satellites in stable locations (where the gravitational forces should cancel out). Specifically, they would like to know every stable location (besides where the spheres themselves are located).
Given the mass and locations of all the spheres, tell NASA all the stable points, listed in increasing order. You can assume that the radius of the spheres is negligible and forces from objects outside this formation are also negligible.
The first line will contain a single integer $$$2 \leq N \leq 500$$$.
The next $$$N$$$ lines contain a pair of integers, the location $$$l_i$$$, followed by the mass, $$$m_i$$$ ($$$1 \leq l_i, m_i \leq 5000$$$).
A list of all stable points, in increasing order. Answers within $$$10^{-6}$$$ will be tolerated.
3 1 1 4 8 2 1
1.46165446 2.54537408
Fo has been folding foil for years now, in the hopes of making their own ingot out of foil!
The foil forms an $$$n$$$ by $$$m$$$ rectangle of metal. Due to human error though, a few air bubbles and other imperfections have accumulated throughout the layers of foil. Thankfully, Fo has diligently marked out where each imperfection is.
To qualify as an ingot, a piece of metal must have one of its dimensions be exactly $$$k$$$. Additionally, Fo has some standards for their ingot, namely that it can only contain at most $$$x$$$ imperfections. Can you help Fo find the biggest ingot?
The first line contains four integers, $$$n$$$, $$$m$$$, $$$k$$$, and $$$x$$$ ($$$1 \leq nm \leq 10^5$$$, $$$1 \lt k \lt max(n,m)$$$, $$$k \leq x \leq nm$$$), denoting the size of the sheet of foil.
Then, $$$n$$$ lines follow, each containing $$$m$$$ characters. "X" represents an imperfection in the foil, and "." represents a perfect section of foil.
Output a single integer, the maximum length of an ingot that contains at most $$$x$$$ imperfections. Note that length here corresponds to the dimension that is not $$$k$$$. (A $$$k$$$ by $$$k$$$ ingot has length $$$k$$$).
5 5 3 3 ...X. XX... ..X.. X...X .X.X.
4
Allie is making an alluring amalgamation of aluminum, actinium, and all other alloys!
The recipe for creating an alloy can be represented by a string of lowercase letters, where each letter denotes a metal. Allie is fulfilling such a recipe. However, she has a quota to meet by 11 pm tonight, so she wants to use more metals than the recipe calls for.
Allie knows that you can add twice as much metal at any point and the resulting alloy will be unchanged. That is, you can duplicate any original letter (leaving both copies of the letter in the same place) without changing the result of the recipe. Note that you can only duplicate an original letter once, and you cannot duplicate existing duplicates.
What's the lexicographically smallest string that can be created by applying the above operation any number of times?
The first line contains a single string ($$$1 \le |S| \le 10^6$$$), denoting the alloy recipe. Each character in $$$S$$$ will be a lowercase English letter.
Output a single string, the lexicographically smallest string that can be created by duplicating any original letters at most once.
silversurfer
siillveerrssurfeer
Pure meteoric iron (or star iron) is one of the rarest metals in the universe, and crafting tools out of it is a ludicrous business that requires a lifetime of training. In fact, only 11 people in the universe are trained to forge star iron.
Bob from Sandy Springs, GA is one such tradesman, and he has recently received an order for $$$K$$$ meteoric swords. Because of how valuable meteoric iron is, each sword he sells must be identical (made from the same amount of meteoric iron), so people don't fight over which sword they get.
Bob has $$$N$$$ pre-crafted swords. In one operation, he can take any sword and either add a unit of meteoric iron to it, or remove a unit of meteoric iron.
Can you help Bob solve this problem: given that he needs to sell $$$K$$$ swords, what's the minimum number of operations he needs to perform so that some set of $$$K$$$ swords contain the same amount of meteoric iron?
The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le K \le N$$$), representing the number of total swords and the number of swords Bob needs to sell, respectively.
The second line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^9$$$), representing the amount of meteoric iron currently contained in each sword.
Output a single integer, the minimum number of operations Bob needs to perform so that some set of $$$K$$$ swords all contain the same amount of meteoric iron.
6 3 8 1 2 5 9 3
2
In the example, we can select swords 2, 3, and 6 ([8, 1, 2, 5, 9, 3]). Then if we add 1 unit of iron to the 2nd sword and remove 1 unit of iron from the 6th sword (so that all 3 swords have 2 units of iron), we have performed 2 total operations. It can be shown that this is the minimum number of operations possible.
Note that this is problem is an easier version of Knight in Shining Armor 2. There are significant differences between the two problems, so please read both carefully.
Charles is a chess prodigy, but his parents are worried that he spends too much time indoors. So, they have decided to create an exercise for him that will allow him to train his chess skills while also getting some vitamin D. Charles's parents have drawn an $$$N \times N$$$ chess board using chalk and provided Charles with a giant knight chess piece made out of tungsten. To keep him busy for a while, his parents tell him to place the knight on a certain square of the board and then repeatedly make knight moves until the knight ends up back on the square it started. Charles is a really indecisive chess player, so at each step, he will choose uniformly randomly from the legal moves available for his knight (note that there will always be at least one legal move, and that Charles will never move the knight off of the board).
Since the knight is made of tungsten, its quite heavy, and Charles would like to be done as soon as possible. At the very least, he would like some kind of estimate as to when he will be done moving the knight. Since he isn't great with mathematics, he's tasked you with coming up with this value. Given the starting square and the board size, please report back to Charles with the expected number of knight moves he will have to make before he ends up back where he started on the chess board.
The only line of input will consist of three space-separated integers, $$$N\ (8 \leq N \leq 20)$$$, $$$X\ (0 \leq X \lt N)$$$, and $$$Y\ (0 \leq Y \lt N)$$$ denoting the board size ($$$N \times N$$$) as well as the starting square ($$$(X, Y)$$$, where $$$X$$$ denotes the $$$X$$$-th row from the top and $$$Y$$$ denotes the $$$Y$$$-th column from the left).
Your output should consist of a single floating point number denoting the expected number of knight moves that Charles will have to make until the knight reaches the starting square again. Your answer will be correct if it has absolute error less than or equal to $$$10^{-9}$$$.
8 0 0
168.000000000000
The only differences between the first and second versions are constraints on the number and length of strings given as input. This problem has larger upper bounds.
Edward and Alphonse Elric are exploring a recently discovered branch of alchemy created by the people of Xerxes. Rather than using transmutation circles, Xerxians used spoken phrases to facilitate alchemic reactions. Each phrase that can be used to perform Xerxian alchemy can be written as a string comprised of only lowercase alphabetical characters.
The primary property of interest when it comes to Xerxian alchemy is the theory behind creating multiple simultaneous reactions. A single phrase can kickstart any reaction whose written form is contained as a substring within the phrase string.
Remembering many phrases is difficult for the Elric brothers, so they would instead like to remember a single, potentially longer phrase that can perform all of the $$$N$$$ alchemic reactions that they know. To help with memorization, the Elrics want to minimize the length of the new phrase string. You, an expert programmer, (an alchemist in your own right), must help the Fullmetal Alchemist find the minimal length of such phrase.
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10$$$), representing the number of phrases that the Elric brothers know. The next $$$N$$$ lines of input each contain a string $$$s_i$$$ ($$$1 \leq |s_i| \leq 10^4$$$), representing a reaction the Elric brothers want to incorporate into their new phrase. Note that these reactions do not necessarily have distinct written forms.
Output a single integer representing the minimal length of the single phrase containing all the given phrases.
3 abcd defg fghi
9
4 woofer floofer error two
17
Twilight has been mistaken for a real forger, and now must work in a metal factory to conceal his identity.
For his job, Twilight needs to melt down metals in a smeltery. Each smeltery can be set to a specific temperature, and each metal has a temperature range that the smeltery must satisfy for the metal to melt properly.
To speed up the process, multiple metals can be placed into the smeltery at the same time. However, some metals will alloy together when melted, so those cannot be melted together.
Due to his extensive background, Twilight has been given access to two smelteries which he can use. Since Twilight is busy and has spy things (a family) to attend to, he'd like to set the temperature for the smelteries and place the metals in all at once. Help Twilight!
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 10^5$$$).
Then, $$$n$$$ lines follow. The $$$i$$$th line contains two integers, $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$), signifying that the temperature of the smeltery for metal $$$i$$$ must be in the range $$$[l_i, r_i]$$$.
Finally, $$$m$$$ lines follow, each containing two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq n$$$, $$$a \not= b$$$), meaning that metals $$$a$$$ and $$$b$$$ will alloy together when placed in the same smeltery.
If it is not possible for Twilight to smelt all metals at once, output "No".
Otherwise, output "Yes" on the first line.
On the second line, you should output two integers $$$t_1$$$ and $$$t_2$$$, representing the temperature settings of the first and second smeltery, respectively.
On the third line, you should output $$$n$$$ integers, representing which smeltery each metal should go in. Specifically, if the $$$i$$$th integer is $$$1$$$, then metal $$$i$$$ should be placed in the first smeltery. Similarly, if the $$$i$$$th integer is $$$2$$$, then metal $$$i$$$ should be placed in the second smeltery.
3 1 5 15 10 20 10 40 1 3
Yes 12 30 1 1 2
3 0 10 20 30 40 50 60
No
Note that this is problem is a harder version of Knight in Shining Armor 1. There are significant differences between the two problems, so please read both carefully.
Charles is a chess prodigy, but his parents are worried that he spends too much time indoors. So, they have decided to create an exercise for him that will allow him to train his chess skills while also getting some vitamin D. Charles's parents have drawn an $$$N \times N$$$ chess board using chalk and provided Charles with a giant knight chess piece made out of tungsten. To keep him busy for a while, his parents tell him to place the knight on any square of the board he likes and then repeatedly make knight moves until the knight ends up back on the square it started. Charles is a really indecisive chess player, so at each step, he will choose uniformly randomly from the legal moves available for his knight (note that there will always be at least one legal move, and that Charles will never move the knight off of the board).
To incentivize his learning and exercise, Charles's parents have decided to reward him for each knight move that he makes. When he moves the knight to the square $$$(i, j)$$$ ($$$i$$$-th row from the top, $$$j$$$-th column from the left), he will earn $$$d_{ij}$$$ gold nuggets. Note that he will earn this reward every single time his knight lands on square $$$(i, j)$$$, not just the first time.
Charles wants to earn as many gold nuggets as possible, so he would like to choose the starting square that gives him the highest likelihood of earning the most nuggets. However, he yet again faces the dilemma that he is super indecisive. Because of this, he asks you to calculate the expected number of nuggets he will collect if he chooses his starting position uniformly randomly.
The first line of input will consist of a single integer $$$N\ (8 \leq N \leq 1000)$$$ denoting the size of the chess board. The next $$$N$$$ lines of the input will consist of an $$$N \times N$$$ grid of positive integers representing the $$$d_{ij}\ (1 \leq d_{ij} \leq 100)$$$ in row-major order.
Your output should consist of a single floating point number, the expected number of nuggets that Charles will collect if he chooses of of the starting squares of the chess board uniformly randomly and then performs repeated knight moves until reaching that starting square again. Your answer will be considered correct if it has absolute error less than or equal to $$$10^{-9}$$$.
8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
75.25
8 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1
112.875