You are manufacturing sheets of copper for the Copper Corporation. Each sheet is broken up into individual units that form a square. The value that a sheet of copper will sell for is the sum of the copper amounts of the units in the top left corner, top right corner, bottom left corner, and bottom right corner. If the entire sheet is only made up of one unit, then the value of the sheet is simply the value of the one unit.
The first line of input will contain a single integer $$$s$$$ ($$$1 \leq s \leq 50$$$), representing the number of units in a single row of the copper square. The next $$$s$$$ lines will each contain $$$s$$$ space separated positive integers, representing copper amounts in all the units that form the square. Every unit has a copper amounts of at most $$$1000$$$.
Output the value of the given sheet of copper.
1 7
7
3 1 3 4 3 1 4 5 7 2
12
You've recently acquired two bars made of Foo, and want to put them on your wall for display.
You've already decided where the endpoints of each bar should be, and in particular which endpoint the bar is mounted to.
The problem is, Foo is a very light metal, and will spin around in the AC current uncontrollably! Specifically, a bar will rotate as a straight line about its endpoint.
Ideally, you'd like the bars to never have any possibility of hitting each other, as they could be damaged by the collision. Can you check if the bars will ever collide?
The first line contains four integers, $$$x_1, y_1, x_2, y_2$$$, representing the endpoints $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ of the first bar. $$$(x_1, y_1)$$$ is the mounted endpoint of the first bar.
Similarly, the second line contains four integers $$$x_3, y_3, x_4, y_4$$$, representing the endpoints $$$(x_3, y_3)$$$ and $$$(x_4, y_4)$$$ of the second bar. $$$(x_3, y_3)$$$ is the mounted endpoint of the first bar.
All coordinates have absolute value less than or equal to $$$10^9$$$.
Output "Yes" if the bars will collide, or "No" if they won't.
1 1 2 2 0 0 1 0
Yes
2 2 1 1 0 0 1 0
No
The first test case looks as follows:
The solid red line represents the initial position of the first bar. The solid green line represents the initial position of the second bar.
The highlighted points are the bars respective mounted endpoints, and the dotted lines show how the bars could be rotated to cause a collision.
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