In the year 1928, Otto Frederick Rohwedder invented the first single loaf bread-slicing machine, a technological advancement which would propel America forward decades, nay, centuries into the future–an invention on par with that of the wheel. Ever since Rohwedder's incredible breakthrough, historians have utilized the invention of sliced bread as a reference point for greatness against which all subsequent inventions can be compared. For instance, the invention of FM radio by Edwin H. Armstrong in 1933 rates at about a $$$0.65$$$ on the sliced bread scale, meaning that it was about $$$65\%$$$ as great as the invention of sliced bread.
Given a list of $$$N$$$ historical inventions, with the dates that they were invented and their ratings on the sliced bread scale, determine once and for all what objectively is the greatest thing since sliced bread?
The first line of input contains the integer $$$N$$$ ($$$1\leq N \leq 10^4$$$) which is the number of invention descriptions to follow. Then, each invention description consists of three lines. The first line gives the title of the invention. The second line gives the date that the invention was made, in the format 'MMM DD, YYYY' where the month is a three-letter abbreviation (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec) and the day value (between 1 and 31) is one or two digits long. The third line of an invention description gives the invention's sliced bread score as a decimal value between 0 and 1 (clearly no invention could exceed the greatness of sliced bread).
Print out the title of the greatest invention since sliced bread, which is the one with the highest sliced bread score. Consider sliced bread to have been invented on Jul 7, 1928, such that any invention made after that date was invented 'since sliced bread.' Note that there will always be at least one invention made since sliced bread, and there will never be ties for greatest invention.
5 FM Radio Dec 26, 1933 0.65 Ballpoint Pen Oct 30, 1888 0.7442 Penicillin Sep 28, 1928 0.0036 The Hovercraft Dec 12, 1955 0.896 Fireworks Apr 20, 960 0.99999
The Hovercraft
Sylvia has been fascinated with Ancient Egypt and used her brand-new time machine to go back in time to the era of her favorite king, Ramses II. While King Ramses II was a highly successful leader, he was also highly eccentric and during her adventures, Sylvia found out that he had a very particular property that all hieroglyph sequences should follow in order for him to read it.
Each hieroglyph in the alphabet was assigned a unique number and King Ramses only accepted the message if the bit-wise XOR of all the numbers in the sequence was equal to $$$0$$$. Unfortunately, Sylvia did not know this before traveling back in time so she doesn't know if the message that she wrote for him satisfies his eccentric request. She also doesn't have too much time before her meeting with the King. Thus, she decides she will replace the minimum hieroglyphs possible in order to make the sequence fit his constraints. Given the numerical representation of the hieroglyphs that Sylvia has written, help her figure out the minimum number of elements in the sequence that need to be replaced in order to make the bitwise XOR of the sequence equal to $$$0$$$.
Note: The XOR between two bits is defined as a function that returns 1 if exactly one of the bits is a 1 and 0 otherwise. The bitwise XOR between two numbers is applying the XOR function on each of the corresponding bits (the last bit of the output is the XOR between the last bits of each of the input numbers and the second-to-last bit of output is the XOR of second-to-last bits of input and so on).
The first line of input will be a single integer $$$n$$$ (where $$$2 \leq n \leq 10^4$$$).
The second line of input will contain $$$n$$$ space-separated integers representing the elements in the sequence where $$$1 \leq h_i \leq 10^9$$$.
Output a single integer representing the minimum number of elements in the sequence that need to be replaced in order to make the bitwise XOR of the sequence equal to 0.
3 2 4 8
1
4 1 1 1 1
0
In the first sample test case, we can replace the first element with a 12 and then the bitwise XOR of the elements in the sequence is zero so the answer is 1. In the second test case, the bitwise XOR of the elements is already zero so the answer is 0.
Alice has traveled back in time to Ancient Greece to meet one of her greatest idols, the famous inventor Daedulus. When Alice visits, Daedulus is analyzing a few maze passageways that he is considering including in his latest creation, the soon-to-be famous Labyrinth. Alice jumps at the opportunity to help Daedulus and needs to build a solver that determines if a given maze passageway is solvable or not.
A maze passageway consists of $$$3$$$ rows that each have $$$n$$$ positions. Each position can either be blocked, which means that Alice cannot move through that position, or open, which means that Alice can move through that position. To solve a particular maze passageway, a person can move in any of the cardinal directions, as long as they don't move into a blocked position or go out of bounds of the passageway. Alice can start in any of the $$$3$$$ rows at the first position and can successfully solve the maze if she can reach the final position at any of the $$$3$$$ rows.
Given a particular maze passageway that meets these criteria, you must output Solvable! if Alice can solve the maze passageway and Unsolvable! otherwise.
The first line will consist of a single integer $$$n$$$ ($$$2 \leq n \leq 10^4$$$), which gives the number of positions per row. The next $$$3$$$ lines consist of a string, $$$s$$$, with $$$n$$$ characters that are either 0 or 1, representing a row of the maze passage way. If $$$s_i = $$$ 0, then the $$$i$$$th position in that row is open, and if $$$s_i = $$$ 1, then the $$$i$$$th position in that row is blocked.
Output Solvable! if the maze passageway is solvable and Unsolvable! otherwise.
2 00 10 00
Solvable!
2 01 10 10
Unsolvable!
Gloria is a ravenous reader and has recently been enraptured by Shakespeare's 'Othello'. Lucky for her, this new time travel device provided her the perfect opportunity to go back in time to November 1, 1604, and watch her favorite play in person. Gloria dresses up in her finest Shakespearean-era attire and zooms back in time. To prevent the time travel machine from ending up in the wrong hands, each user is given a specific numeric password and a set of recovery codes in case they forget the password.
Gloria reaches the Whitehall Palace just in time for the show and after an enthralling three and a half hours, she returned to her time travel machine only to realize that she has forgotten her password! Luckily, she had the foresight to bring her tablet with the recovery codes on her. However, the effect of time travel on such electronics was unfortunately still not completely mitigated so some of the bits in the tablet got shifted around. Fortunately, Gloria knows that each of the recovery code numbers was rearranged in the exact same way and that her password is the smallest possible difference between the maximum recovery code and the minimum recovery code. Help Gloria recover her password!
That is, given the list of $$$n$$$ rearranged recovery codes, each of which is exactly $$$k$$$ digits, permute all of the numbers in the exact same way in order to get the minimum possible difference between the maximum and minimum recovery code after the permutation.
The first line of the input will contain two space-separated integers, $$$n$$$ and $$$k$$$ (where $$$2 \leq n \leq 100$$$ and $$$1 \leq k \leq 9$$$).
$$$n$$$ lines of input will then follow, each line containing a single integer $$$x_i$$$ ($$$0 \leq x_i \leq 10^{k} - 1$$$) which will have exactly $$$k$$$ digits (the number can contain leading zeros).
A single integer representing Gloria's password aka the minimum difference between the maximum and minimum recovery code after the permutation.
2 2 12 32
2
4 4 1842 0141 5581 1581
1017
Armed with a small canoe and a mental map of the stars, Kiana embarks upon a voyage to a distant island from her own, where she suspects she may find valuable resources that can be brought back to her village community. Unfortunately, the seas can be unforgiving, and Kiana knows that her feeble canoe may not be sturdy enough to survive the extent of the voyage. However, Kiana's island lies within the Polynesian Triangle, and there are hundreds of other islands nearby, $$$N$$$ to be precise, where Kiana should be able to find more boat-building wood and construct a hardier vessel. Each island, located at $$$(x_i, y_i)$$$ miles in the Pacific Ocean, contains $$$s_i$$$ "units" of boat-building supplies, whereby each supply unit allows Kiana to upgrade her boat to be capable of traveling 1 additional mile of distance at one time without sinking.
For example, Kiana starts at the $$$0^{th}$$$ island with $$$s_0$$$ supplies that she has already used to build her canoe, and until she upgrades her boat, she can travel a maximum of $$$s_0$$$ continuous miles in any direction before her canoe fails. If the distance between say the $$$0^{th}$$$ and $$$1^{st}$$$ island is less than $$$s_0$$$, then Kiana could sail to the $$$1^{st}$$$ island and upgrade her boat with $$$s_1$$$ supply units, so that going forward she could sail to any island within $$$s_0 + s_1$$$ of her current position.
Given the locations of the Polynesian islands and the amount of wood supplies at each island, determine whether or not Kiana can make it to her destination.
The first line of input contains the integer $$$N$$$ ($$$2 \leq N \lt 10^3$$$), denoting the number of neighboring islands known to Kiana. The next $$$N$$$ lines each contain three integers, $$$x_i$$$, $$$y_i$$$, and $$$s_i$$$ ($$$0 \leq x_i, y_i, s_i \lt 10^6$$$), where $$$(x_i, y_i)$$$ is the location of the $$$i^{th}$$$ Polynesian island and $$$s_i$$$ is the number of wood supply units available at the island for Kiana to harvest for canoe improvements. The $$$0^{th}$$$ island, described in the first line of input, is Kiana's starting location, and the last line of input, for the $$$N-1^{th}$$$ island, describes Kiana's target destination.
Output "YES" if it is possible for Kiana to reach her destination and "NO" otherwise.
7 50 50 3 50 52 0 50 55 0 50 58 10 50 49 1 50 35 10 74 50 0
YES
In the distant future, Ellen works as a musician for the Willbeington D.C. Philharmonic. However, frequent use of time travel has caused the Fabric of Space and Time to weaken considerably, to the extent that certain melodies can cause severe vibrations and harm the musician playing them, as well as the Fabric itself. To prevent such harm, the Ministry of Music has created a handy guidebook for composing melodies, which details which instruments can follow which other instruments, as well as how many notes can be played on any given instrument.
Unfortunately, this guidebook was greeted by large amounts of backlash from people that believed that the Ministry of Music was suffocating their creative spirit in making music, and was just a power grab on the part of the Minister for Music. In response to concerns that the guidebook was limiting the supply of fresh melodies, Ellen decides to enumerate all the possible melodies that can be written that still follow the guidebook.
Since the guidebook has no restrictions on length of melody, this number is possibly infinite. So, Ellen restricts her count to only consider melodies of length $$$K$$$, and ones starting with the $$$S$$$'th instrument.
Given the guidebook, the starting instrument, and the number of notes, find the answer for Ellen. Because the number of possible melodies might be very large, output the answer$$$\mod{10^9 +7}$$$.
The first line of input contains four integers, $$$N, M, K, S$$$ ($$$1 \le N \le 50$$$, $$$1\le M \le N^2$$$, $$$1\le K \le 10^6$$$, $$$0\le S\le N-1$$$) - the number of distinct instruments, the number of ordered pairs of instruments that can follow each other, the number of notes in the melody being constructed, and the index of the starting instrument.
The second line contains $$$N$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$) — the number of notes the $$$i$$$th instrument can play.
Finally, $$$M$$$ lines follow, where the $$$j$$$th line is of the form $$$x_j\ y_j$$$ ($$$0\le x_j, y_j \le N-1$$$), indicating that the $$$y_j$$$'th instrument can follow the $$$x_j$$$'th instrument.
Output a single integer equal to the number of total melodies that can be created following the rules of the guidebook that start with instrument $$$S$$$ and last exactly $$$K$$$ notes, mod $$$10^9 + 7$$$
2 1 10 0 2 3 0 1
0
3 4 3 0 1 2 3 0 1 1 2 1 0 2 1
8
In the first example, the only way to make a melody is to use a note from instrument $$$0$$$ and then a note from instrument $$$1$$$. After this second note, no further notes can be added to the melody, since no instrument is allowed to follow instrument $$$1$$$. So, there are no melodies of length $$$10$$$.
In the second example, there are two ways to make a melody: use instruments $$$0, 1, 2$$$, in that order, or $$$0, 1, 0$$$, in that order. In the first case, there are $$$1\cdot2\cdot3 = 6$$$ ways to choose the notes, and in the second, there are $$$1\cdot 2\cdot 2 = 2$$$, for a total of $$$8$$$.
The Terracotta Army is a collection of terracotta sculptures depicting the armies of Qin Shi Huang, the first Emperor of China. It is a form of funerary art buried with the emperor in 210–209 BCE with the purpose of protecting the emperor in his afterlife.
Aang has been commissioned to create these fearsome warriors, and observes that the requested designs share many similarities. In fact, Aang has been able to narrow down the list of features shared by the statues to a list of only $$$K$$$ different features. For example, statues with feature #$$$1$$$ might hold a sword, statues with feature #$$$2$$$ might have a unique insignia, and so on.
Aang has even devised a concise way to describe each statue in terms of its "feature ID", a single $$$K$$$-bit integer whose binary representation tells us the set of features exhibited by the statue. As an example, suppose a statue has feature ID $$$13$$$. Since $$$13$$$ written in binary is $$$1101$$$, this means our statue exhibits features $$$1$$$, $$$3$$$, and $$$4$$$ (reading right to left), but not feature $$$2$$$. As a more general rule of thumb, we find a $$$1$$$ in the $$$2^{i-1}$$$ place if a statue exhibits feature $$$i$$$.
Always the curious fellow, Aang lined up statues $$$1 \dots N$$$ in a long row and noticed that certain ranges of statues are somewhat "majestic" in terms of the features they exhibit. A contiguous range of statues $$$i \dots j$$$ is majestic if each of the $$$K$$$ possible features is exhibited by the same number of statues in the range. Aang would like to find the largest majestic range of statues, but it is quite difficult for him to keep track of an entire army. Can you give our protagonist a hand?
The first line of input for each test case contains two integers $$$N$$$ ($$$1 \leq N \leq 100000$$$) and $$$K$$$ ($$$1 \leq K \leq 30$$$) representing the number of terracotta sculptures Aang has lined up and the number of features Aang has found, respectively. The next $$$N$$$ lines of input each contain a single integer $$$f_i$$$ ($$$0 \leq f_i \leq 2^{K}-1$$$) specifying the features present in statue $$$i$$$ using the encoding format described above.
Output a single integer representing the longest majestic range within the $$$N$$$ selected sculptures.
7 3 7 6 7 2 1 4 2
4
In the sample input, statues 3 through 6 (inclusive) form a majestic sequence of length 4.