Einstein has a calculator and a list of numbers that he wants to put into his calculator! More specifically, Einstein has an array $$$a$$$ of $$$n$$$ $$$(2 \leq n \leq 100)$$$ numbers that he will put into his calculator. And one of Einstein's favorite equations is $$$6 + 7 + 6 + 7 + 41 + 0 = 67$$$, so every number in $$$a$$$ is guaranteed to be one of $$${0, 6, 7, 41, 67}$$$.
Einstein wants to put an operator $$$+$$$, $$$-$$$, $$$/$$$, or $$$\cdot$$$ between each number in order to make a valid expression to put into the calculator. He also wants to maximize the value of the expression that he forms and ensure that it is not undefined (there is never $$$0/0$$$). Note that there is no limit on how many of any operator Einstein uses, and that he is allowed to use operators more than once.
If Einstein chooses the operators in his expression optimally, what is the maximum value of the expression that he can achieve? In other words, what is Einstein doing on that calculator? Because the value may be very large, print it modulo $$$10^9 + 7$$$.
The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 100)$$$ where $$$n$$$ the size of $$$a$$$.
The second line contains $$$n$$$ integers, $$$[a_1, a_2, ... a_n]$$$ ($$$a_i \in \{0, 6, 7, 41, 67\}$$$), the elements in $$$a$$$.
Output one number, the maximum value of Einstein expression modulo $$$10^9 + 7$$$.
4 6 7 41 0
1722
In the sample test case, we need to fill in the operators for:
$$$6$$$ _ $$$7$$$ _ $$$41$$$ _ $$$0$$$
One possible way we can maximize the value of the expression is by assigning the operators as follows:
$$$6 \cdot 7 \cdot 41 - 0 = 1722$$$
It can be proven that 1722 is the maximum value that can be achieved.
Edward isn't just a gamer — he's the gamer. The man, the myth, the MLG legend. His KD ratio is higher than your GPA, his scope sensitivity defies the laws of physics, and his Wi-Fi connection? Blessed by the gods of low latency themselves.
He's dropped into a digital warzone — a chaotic grid where enemies spawn like lag spikes in a ranked match. There are $$$N$$$ poor souls scattered across the map, blissfully unaware that Edward "NoScopeKing420" is about to go absolutely feral.
He locks in. His avatar faces one of eight sacred gamer directions: North, Northeast, East, Southeast, South, Southwest, West, or Northwest.
He will perform this MLG move by spinning 360 degrees, and then firing his rifle. His rifle will shoot a bullet that travels straight in the direction he is facing after he turns 360 degrees, and will hit the first entity it encounters. Please find out which poor soul Edward hits.
The first line contains $$$n, e_x, e_y$$$, the amount of enemies, and the $$$x, y$$$ coordinates that Edward is at. $$$1 \leq n, e_x, e_y \leq 10^5$$$
The second line contains $$$s$$$ a string representing the direction Edward is facing. This string will be in full caps, matching one of the directions specified in the statement.
The next $$$n$$$ lines will contains $$$2$$$ integers each $$$x_i, y_i$$$ representing the coordinates of the $$$i$$$th enemy. $$$1 \leq x_i, y_i \leq 10^5$$$
Output $$$2$$$ integers, $$$x, y$$$, the coordinates of the enemy Edward hit. Output $$$-1$$$ if Edward does not hit anyone.
1 1 1 NORTHEAST 3 3
3 3
2 1 1 NORTHEAST 3 4 4 3
-1
1 1 1 NORTH 1 1
1 1
Input
1 1 1
NORTHEAST
3 3
- There is one enemy.
- Edward's position is $$$(1, 1)$$$.
- Edward is facing NORTHEAST, meaning the bullet travels diagonally upward to the right, increasing both $$$x$$$ and $$$y$$$ equally.
The bullet travels along the line: [ (1, 1) , (2, 2) , (3, 3) ... ] The only enemy is located at $$$(3, 3)$$$, which lies directly along this path.
—
Input
2 1 1
NORTHEAST
3 4
4 3
- There are two enemies.
- Edward's position is $$$(1, 1)$$$.
- Edward is facing NORTHEAST, so the bullet moves along the diagonal line $$$y = x$$$.
The bullet's path is: [ (1, 1) , (2, 2) , (3, 3) , (4, 4) ... ]
Check the enemies: $$$$$$ (3, 4): \text{ not on } y = x \qquad (4, 3): \text{ not on } y = x $$$$$$
Neither enemy lies on Edward's line of fire, so he hits no one.
—
Aftermath
As the smoke clears and the echoes of the shot fade, Edward lowers his rifle. In the first match, he lands a perfect 360 no-scope — chat goes wild, airhorns blast, and the killfeed lights up. In the second? A clean miss. The enemies live to tell the tale, but only barely. Somewhere, a dubstep remix begins to play as Edward reloads, ready for the next highlight reel moment.
The only difference between the easy version and the hard version of the problem is the constraints on $$$n$$$, $$$k$$$, and $$$a_i$$$.
It's the year 2125, and e-archaeologists have uncovered remnants of what they believe was known as the "troll face". They believe that the troll face was represented by a non-degenerate $$$k$$$-sided polygon that could be inscribed in a circle. Note that for this problem, $$$k$$$ is always 3.
So far, the e-archaeologists have discovered $$$n$$$ line segments, each of which has a length $$$a_i$$$. Now, the e-archaeologists are wondering: how many $$$k$$$-size subsets of their $$$n$$$ line segments could be used to create a troll face?
Consider all line segments to be unique, even if 2 have the same length.
The first line of input contains 2 integers, $$$n$$$ and $$$k$$$ ($$$3\le n\le 5000, \mathbf{k=3}$$$) — the number of line segments and the number of sides in a troll face, respectively.
The second line of input contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — the lengths of the $$$n$$$ line segments.
Output a single integer, the number of $$$k$$$-size subsets that could be used to create a troll face.,
5 31 2 3 3 3
7
In the first test case, there are 7 unique subsets (Note that all the 3's are considered to be distinct):
Bob would like to buy a trading card pack today, but his local game store has some strange rules:
Firstly, they do not provide change, so he must come up with the exact amount of money to buy a trading card pack.
Secondly, they only accept $$$\textit{clean}$$$ coins, and unfortunately, all of Bob's coins are $$$\textit{dirty}$$$.
Thirdly, the $$$\textit{unluckiness}$$$ of the trading card pack you get is equal to the number of coins you pay with.
Finally, the store closes once midnight arrives.
Bob has an unlimited amount of $$$n$$$ types of dirty coins, each of which are worth $$$w_i$$$ cents and takes $$$t_i$$$ seconds to clean. Bob knows a trading card pack costs exactly $$$m$$$ cents, and midnight arrives in $$$k$$$ seconds. Bob needs to clean enough coins to buy a pack by the time midnight arrives, and minimize the unluckiness of his card pack. Find the minimum unluckiness of Bob's card pack if he spends his time wisely, or output $$$-1$$$ if Bob can not get a card pack!
The first line of input will contain the integers $$$n$$$ $$$(1 \leq n \leq 500)$$$, $$$m$$$ $$$(n \leq m \leq 500)$$$, and $$$k$$$ $$$(1 \leq k \leq 500)$$$, the number of coin values, the cost of the card pack, and how soon midnight will arrive.
The second line of input will be the array $$$w$$$ $$$(1 \leq w_i \leq m)$$$, consisting of $$$n$$$ space-separated integers indicating the value of the $$$i^\text{th}$$$ coin.
The third line of input will be the array $$$t$$$ $$$(1 \leq t_i \leq 500)$$$, consisting of $$$n$$$ space-separated integers indicating the time it takes to clean the $$$i^\text{th}$$$ coin.
Output the minimum unluckiness of a card pack that Bob can get, or $$$-1$$$ if he cannot clean enough coins in time to get a card pack.
3 10 10 1 2 5 2 4 5
2
3 10 9 1 2 5 2 1 5
4
In the first test case, you should clean two of the 5-cent coins. You will finish just as midnight arrives.
In the second case, you should clean one 5-cent coin, two 2-cent coins, and one 1-cent coin.
After recruiting for months, you finally score a SWE intern position at Sunnyside Daycare. Unfortunately, you didn't really do your research, so when you show up for the summer, you realize you're actually gonna be babysitting (what were you thinking?).
Bored and unsure how to deal with children, you decide to screenmaxx them instead. You study the daycare layout and luckily, it's a tree (seems the Leetcode is paying off). Each room has at most one TV, each of which you have configured to display meaningless brainrot at some level $$$a[i]$$$.
To truly screenmaxx though, the babies need access to as many TVs as possible. If they can walk from one TV to another, the total brainrot value of the daycare (and your subsequent enjoyment) increases by the product of those two TVs.
Unfortunately, your senior SWE catches on. They aren't paid nearly enough to deal with it though, so they'll lock exactly one door for the rest of the day, minimizing the total brainrot value. Given the daycare layout and each TV's brainrot level, what will be the total brainrot value for the day?
The first line of input contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of rooms.
The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^2$$$) — the brainrot levels of the TVs.
Each of the next $$$n - 1$$$ lines contains two integers $$$u, v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — representing a door between rooms $$$u$$$ and $$$v$$$.
It is guaranteed that the given doors form a tree.
Print a single integer — the minimum possible total brainrot value after the senior SWE locks one door.
The brainrot value is the sum of $$$a_u \cdot a_v$$$ over all pairs of different rooms $$$u$$$ and $$$v$$$ that are connected.
5 1 2 0 3 4 1 2 2 3 1 4 4 5
11
Certain numbers are funny on their own, but next to other numbers, their funniness changes. In particular, the funniness $$$f(x_1, x_2)$$$ of a pair of numbers $$$x_1$$$ and $$$x_2$$$ is the number of common divisors between their respective funniness values $$$y_1$$$ and $$$y_2$$$. The funniness of a sequence is the sum of the funniness of every adjacent pair of numbers, or more formally:
Note that this sequence must contain at least two elements, so the funniness of a single number $$$x_1$$$ is not defined.
Given $$$n$$$ distinct numbers and their funniness values, find the funniness of the funniest possible sequence that can be constructed.
The first line of input contains $$$n$$$ ($$$2 \le n \le 18$$$), the number of funny numbers.
The second line contains $$$n$$$ integers, $$$x_1, x_2, ..., x_n$$$ ($$$1 \le x_i \le 10^9$$$), the distinct funny numbers.
The third line contains $$$n$$$ integers, $$$y_1, y_2, ..., y_n$$$ ($$$1 \le y_i \le 10^9$$$), the funniness value of each funny number.
The output should be one line containing the maximum possible funniness of any sequence that consists of the given funny numbers.
441 42 67 6912 20 24 16
13
One sequence with the maximum funniness is $$$42, 41, 67, 69$$$, which has a funniness of $$$f(42, 41) + f(41, 67) + f(67, 69) = 3 + 6 + 4 = 13$$$.
The only difference between the easy version and the hard version of the problem is the constraints on $$$n$$$, $$$k$$$, and $$$a_i$$$.
It's the year 2125, and e-archaeologists have uncovered remnants of what they believe was known as the "troll face". They believe that the troll face was represented by a non-degenerate $$$k$$$-sided polygon that could be inscribed in a circle.
So far, the e-archaeologists have discovered $$$n$$$ line segments, each of which has a length $$$a_i$$$. Now, the e-archaeologists are wondering: how many $$$k$$$-size subsets of their $$$n$$$ line segments could be used to create a troll face? Output your answer in mod $$$10^9+7$$$.
Consider all line segments to be unique, even if 2 have the same length.
The first line of input contains 2 integers, $$$n$$$ and $$$k$$$ ($$$3\le k\le n\le 100$$$) — the number of line segments and the number of sides in a troll face, respectively.
The second line of input contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^4$$$) — the lengths of the $$$n$$$ line segments.
Output a single integer in mod $$$10^9+7$$$, the number of $$$k$$$-size subsets that could be used to create a troll face.
5 31 2 3 3 3
7
6 41 5 2 3 4 1
12
In the first test case, there are 7 unique subsets (Note that all the 3's are considered to be distinct):
In another universe, Adam's Ark is filled with many wonderful animals, from Tralalero Tralala to Chimpanzini Bananini. To keep things organized, Adam has a log of all the data related to the ship's architectural details and any info related to the ship's occupants. Weirdly enough, this log contains a lot of ratios, and in fact only ratios! From calculating the output:input force ratio to how many hours Lirili Larila sleeps per cactus on its head, these ratios are crucial for maintaining the ship.
In the midst of his trip, a typhoon caused Adam to drop his log into the ocean! With no way to recover it, Adam realizes he is in deep trouble. He has a series of $$$q$$$ checkpoints coming up, and checkpoint $$$i$$$ will ask Adam for the $$$q_i$$$-th smallest fraction $$$\frac{a}{b}$$$ in his log. Adam doesn't have enough time to recalculate all these fractions in time for the first checkpoint. What he does remember is that his log only consisted of positive reduced fractions. More specifically, it contained every positive reduced fraction whose numerator was at most $$$n$$$ and denominator at most $$$m$$$.
Time is ticking down, so Adam has to act quickly. Can you help him answer the $$$q$$$ checkpoints and save brainrot?
The first line of input contains the numbers $$$n$$$ $$$m$$$ $$$q$$$. $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^4$$$) are the upper limits on the numerator and denominator respectively. $$$q$$$ is the number of checkpoints.
After this, $$$q$$$ ($$$1 \le q \le 100$$$) lines follow. If the $$$i$$$-th number is $$$q_i$$$, then checkpoint $$$i$$$ is curious about the $$$q_i$$$-th smallest fraction in Adam's log. Each query $$$q_i$$$ satisfies $$$1 \le q_i \le nm$$$.
Output $$$q$$$ lines. The $$$i$$$th line should contain the $$$q_i$$$-th smallest fraction in Adam's log in the format $$$a$$$/$$$b$$$ (if $$$b=1$$$ you should still maintain this format). If $$$q_i$$$ exceeds the number of fractions in Adam's log, print "Trick".
3 3 41693
1/3 2/1 Trick 2/3
In the sample, we have the following list of ratios in sorted order:
$$$$$$\left [ \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1} \right ]$$$$$$