Photons have a unique property called "polarization" that determines how they orient themselves, but what about eggs? Bobo the chicken has just placed some eggs in the incubator and wants to know which ones are oriented vertically. To solve this problem, she invents a special machine that can measure the "polarization" of eggs.
When Bobo presses a button, the solid floor of the incubator shifts, revealing a set of egg-shaped holes. These holes are shaped to allow only eggs that are facing upwards to fall through into a (soft) nest below. Eggs that aren't correctly oriented will remain on the solid parts of the floor.
Each egg can start in one of six possible orientations: horizontal, vertical, diagonal, anti-diagonal, right, and left. We label these orientations as "states" from 0 to 5 respectively. The first egg is always vertical, denoted by $$$X_1 := 1$$$, and the state of the $$$(n+1)^{\text{th}}$$$ egg (for $$$n \geq 1$$$) is represented by $$$X_{n+1} := ((4 \cdot X_{n}) \oplus n)\: \text{mod} \: 6$$$, where $$$\oplus$$$ is the XOR operator. Can you help Bobo figure out how many vertical-facing eggs are in the incubator?
The first line contains an integer $$$x\ \left(0 \lt x \leq 10^3\right)$$$ — the number of eggs in the incubator.
Please output the number of vertical-facing eggs in the incubator.
4
2
In the sample test case, the states of the first four eggs are 1, 5, 4, 1. Thus, egg #1 and egg #4 are facing upwards, so the answer is 2.
Jacob is trying to produce as many hard boiled eggs as humanly possible before the annual hard boiled egg production competition!
However, he only has a single egg-sized pot, meaning that he can only cook a single egg at a time. For some reason, since Jacob is using supernatural eggs (they are worth extra points), each of his eggs has a different cooking time (given in minutes).
Based on his remaining time and the cooking time of the eggs Jacob has, can you figure out the number of eggs he can hard boil if he acts optimally?
The input will begin with a single line containing two space-separated integers, $$$n$$$ and $$$t$$$ ($$$1 \leq n \leq 10^5, 1 \leq t \leq 2 \cdot 10^9$$$) — the number of raw supernatural eggs Jacob has and his remaining time (in minutes), respectively.
The next line will contain $$$n$$$ space-separated integers, $$$c_1, c_2, \dots, c_n$$$ ($$$1 \leq c_i \leq 2 \cdot 10^9$$$) — the $$$i^{\text{th}}$$$ of which, $$$c_i$$$, denotes the number of minutes it takes Jacob to hard boil the $$$i^{\text{th}}$$$ egg in his possession.
The output should consist of a single non-negative integer representing the number of eggs which Jacob can hard boil with his remaining time.
3 103 5 9
2
5 102 2 2 2 2
5
In the first example test case, Jacob can hard boil the first two eggs in 8 minutes, but he will not have time to hard boil the last egg.
In the second example test case, Jacob can hard boil all of the eggs in exactly the time he has remaining.
Eggo has $$$n$$$ eggs, one of each size from $$$1$$$ to $$$n$$$. He wants to figure out what order to place the eggs. A powerful subarray is one where each element is one size greater than the previous. More formally, if $$$b_1, b_2, \dots, b_k$$$ are the sizes of the eggs in the subarray, then the subarray is powerful if $$$b_i - b_{i - 1} = 1$$$ for $$$2 \leq i \leq k$$$. The power of a configuration of eggs is the size of the largest powerful subarray.
You want the power of the configuration to exactly equal $$$k$$$. Can you place the eggs such that the power equal $$$k$$$? If multiple answers exist, print any.
An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Note that an array is a subarray of itself.
The first and only line of input consists of two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — the number of eggs and the desired power, respectively.
Print $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ — the order of eggs that gives the desired power.
5 3
5 2 3 4 1
Oh goodness... Sean accidentally mixed up his eggs with a can of alphabet soup, and now everything's all scrambled together! Now he needs your help to rearrange the letters in the alphabet soup and restore peace to the egg-iverse.
Sean's suspicious egg-soup mixture can be represented as a series of $$$n$$$ spaghetti letters. He knows that two conditions used to be true of his letters before they got scrambled into the eggs:
- When put in a row, his letters would form a palindrome, a string which is read the same forwards and backwards. Put more formally, if his letters were labelled $$$s_1, s_2, \dots, s_n$$$, then it is the case that $$$s_i = s_{n - i + 1}$$$ for each $$$i \in \{1, 2, \dots, n\}$$$.
- Of all possible palindromes, his letters would form the lexicographically smallest one.
Sean knows for certain that it is possible for him to arrange the scrambled up spaghetti letters to fulfill both constraints simultaneously, but he's busy at the moment researching possible egg-spaghetti hybrids, and needs your help to unscramble his soup!
The input will consist of a single line containing a single string of length $$$n$$$ ($$$1 \leq n \leq 10^5$$$) consisting exclusively of lowercase English letters — the scrambled-up spaghetti letters found in Sean's egg soup.
The output should consist of a single line containing a single string representing the unscrambled contents of Sean's egg soup as described by the rules above.
racecar
acrerca
aabbccdde
abcdedcba
ajcvoiwqnexajcvoiwqnex
aceijnoqvwxxwvqonjieca
- In the first sample test case, "racecar" itself is a palindrome, but not the lexicographically smallest palindrome which can be created using the same set of letters.
- In the second sample test case, the letters are already arranged in lexicographical order, but they do not immediately form a palindrome.
Sierra lives in the mountains where it occasionally rains egg yolk. During these storms, yolk pools in the valleys between mountain peaks. Sierra is curious about these pools and would like to know the total volume of the pool with the highest surface elevation.
The topology of the mountain range can be represented by $$$n$$$ integers, where $$$h_i$$$ describes the elevation of the $$$i$$$th location in this range. Some space above a location is considered "part of a pool" if there exist locations to the left and the right of the space with higher or equal elevations. A pool's surface height is defined by the minimum elevation of its immediate neighbors. In cases where there are ties, return the sum of the volumes of all highest pools.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of locations in the range.
The next line contains the array $$$h_1, h_2, \dots, h_n$$$ ($$$1 \leq h_i \leq 10^9$$$) — the heights of the locations in the range.
Output the volume of the highest pool. If there are multiple pools at the same height, print the sum of their volumes.
81 4 8 2 2 8 1 7
12
There are two pools in the input: one above locations 4 and 5 at a height of 8, and one above location 7 with a height of 7. The first pool is higher, and it has a volume of 12.
Eggward is working on a hobby project and recently acquired $$$n$$$ eggs that he wants to try and hatch that are stuck at fixed positions along a number line. He has some heat lamps, and he wants to keep the eggs close to the heat lamps in order to ensure they receive the warmth they need. Unfortunately, he only has $$$k$$$ heat lamps to incubate these eggs with. His goal is to minimize the maximum distance from any egg to its nearest heat lamp. Help him find this distance. The lamps are hung above the eggs so they can be at the same position on the number line, and all lamps must be at integer positions.
The first line will contain two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — the number of eggs and the number of heat lamps respectively.
The following line will contain $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) indicating the position of the $$$i^{\text{th}}$$$ egg. Furthermore, the $$$a_i$$$ are guaranteed to be distinct, that is, if $$$i \neq j$$$, then $$$a_i \neq a_j$$$.
Output one integer indicating the minimal possible max distance from any egg to its nearest heat lamp.
3 20 5 7
1
5 2-2 1 0 -1 4
2
Sample 1 Explanation: We can place one heat lamp at 0, and another at 6. The distance from the 0 egg to its nearest lamp is 0. The distance from the 5 and 7 eggs to their nearest lamp is 1. Thus, the minimum max distance we can achieve is 1.
Sample 2 Explanation: We can place one heat lamp at 0, and one heat lamp at 2. Then every egg is at most 2 away from the nearest lamp.
What came first, the chicken or the egg? This is one of life's biggest mysteries, but your friend Chris thinks he can solve it.
He hypothesizes that whichever came first should have had more time to evolve and should thus be faster.
To test this, he has made a maze. The maze can be represented as a directed graph with $$$n$$$ nodes and $$$m$$$ edges. Among these $$$n$$$ nodes, there are $$$a$$$ entrances and $$$b$$$ exits. Because chickens and eggs are shaped differently, they take $$$c_i$$$ and $$$e_i$$$ time to traverse edge $$$i$$$, respectively.
First, Chris will test a chicken. He will uniformly randomly pick an entrance to place the chicken and time how long it takes for the chicken to reach any exit. He will then similarly pick a random entrance for the egg and time it. He plans to let the chicken and egg study the maze beforehand so that they both take their respective fastest routes to any exit.
If a chicken or egg starts at a node that can't reach an exit, it can never finish. If they both never finish, it is a tie.
Knowing you are a mathematician, Chris wants to know who you think will win.
The first line contains 4 space-separated integers $$$n$$$, $$$m$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$, $$$1 \leq a, b \leq n$$$, $$$2 \leq a + b \leq n$$$) — the number of nodes, number of edges, the number of entrances, and the number of exits, respectively.
The following $$$m$$$ lines each contain four integers $$$u$$$, $$$v$$$, $$$c$$$, and $$$e$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq c, e \leq 10^9$$$) – denoting a directed edge between nodes $$$u$$$ and $$$v$$$ that will take chickens and eggs time $$$c$$$ and $$$e$$$ to traverse, respectively.
The next line contains $$$a$$$ distinct space-separated integers $$$s_1, \dots, s_a$$$ ($$$1 \leq s_i \leq n$$$) – the nodes that are entrances.
The next line contains $$$b$$$ distinct space-separated integers $$$t_1, \dots, t_b$$$ ($$$1 \leq t_i \leq n$$$) – the nodes that are exits.
It is guaranteed that no node is both an entrance and an exit. There can be double edges.
Output "chicken" if it is more likely for the chicken to win, "egg" if it is more likely for the egg to win, and "tie" if they have equal probability of winning.
3 3 1 12 1 1 11 3 2 12 3 3 323
egg
5 6 3 21 2 1 21 3 3 12 3 2 21 4 1 103 4 3 23 5 1 31 2 34 5
chicken
4 2 2 21 3 2 12 4 1 21 23 4
tie
Alice is playing a popular block game, and has $$$n$$$ days to collect as many eggs as she can. Alice initially has 1 chicken that lays an egg every day and needs 1 night of sleep. Every day, she can throw as many eggs as she wants to hatch more chickens.
Alice knows the seed of her game generated world, which gives her some additional information. In fact, she knows how many eggs she must throw to hatch another chicken, and how many nights of sleep each chicken needs before laying an egg. In fact, these values follow a predictable pattern. Help Alice find the maximum amount of eggs that she can have in $$$n$$$ days.
Note that throwing an egg requires that you have at least 1 egg, and the act of throwing an egg decreases the amount of eggs you have by 1.
The first line of input will contain the integers $$$n$$$ ($$$1 \leq n \leq 60$$$) and $$$m$$$ ($$$1 \leq m \leq 10^4$$$), the number of days Alice has to collect eggs and the length of the arrays containing each chicken's information.
The second line of input will contain $$$m$$$ integers $$$c_1, c_2, ..., c_m$$$ ($$$1 \leq c_i \leq n$$$), where $$$c_i$$$ represents the hatching cost of chickens $$$i, i + m, i + 2m, ...$$$.
The third line of input will contain $$$m$$$ integers $$$r_1, r_2, ..., r_m$$$ ($$$1 \leq r_i \leq n$$$), where $$$r_i$$$ represents the number of nights of sleep needed by chickens $$$i, i + m, i + 2m...$$$ beforing laying an egg.
Note that Alice may hatch more than $$$m$$$ chickens. The pattern repeats once the $$$m-th$$$ chicken is hatched, and the $$$m+1th$$$ chicken has the same hatching cost and sleep requirement as the first hatched chicken.
8 31 2 11 2 3
23
7 111
64
10 21 22 1
37