Odysseus is trying to find his way home, after he got a little bit lost after going out on a journey. Sadly, he finds that he's struggling quite a bit, partly because some gods are upset at him. As it turns out, there are lots of locations in the world numbered by the positive integers, and the gods have decided the following rules for Odysseus's route. For simplicity, let us denote a location by the number it is at. If Odysseus's location $$$n$$$ is even, his next step will be location $$$\frac n2$$$. If Odysseus's location $$$n$$$ is odd, his next step will be location $$$3n + 1$$$. Now, given his starting location $$$s$$$, determine how many steps it will take for Odysseus to reach home, which is location $$$1$$$.
A single integer $$$s (1 \le s \le 100)$$$, Odysseus' starting location.
A single integer detailing the number of steps it takes to get home.
3
7
Starting at location $$$3$$$, Odysseus will take the following path: $$$$$$3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$$$$$ The path above is a total of $$$7$$$ steps.
Hercules is bored today. As he does when he is bored, he runs off into the forest to frolic around. Today, he stumbled upon a bunch of very peculiar stones. He found the lightest stone, and then noticed that for every stone except for the smallest stone, there existed another stone that was exactly half its weight, and no two stones had the same weight. Let $$$w$$$ be the weight of the lightest stone. Hercules wants to verify that he can to pick up a weight of $$$n \cdot w$$$, so he selects some subset of the stones to add up to $$$n \cdot w$$$, which is guaranteed to exist and be unique. Given $$$n$$$, determine how many stones Hercules lifted to determine that he could indeed lift a weight of $$$n \cdot w$$$.
The first line of the input will contain $$$n (1 \le n \le 10^9)$$$, the weight in terms of the lightest stone that Hercules can lift.
A single integer detailing the number of stones Hercules lifted to get a weight of $$$n$$$ times the lightest stone.
6
2
For a weight of $$$6w$$$, Hercules lifted stones with weights $$$2w$$$ and $$$4w$$$ for a total weight of $$$6w$$$, which is $$$2$$$ stones.
Metal Guy is trying to create an artificial intelligence to help him process information and act as a personal assistant, but his current program has a bug! If any pair of integers sum up to a certain bugged number, the training program crashes and he must start over.
He realizes that he could simply process the data multiple times in separate sessions to avoid running into this issue. However, he's very impatient and only wants to have at most two sessions. Can he separate his data set into two such that no two numbers will sum up to the bugged number?
On the first line, two integers: $$$1 \leq N \leq 10^6$$$ and $$$1 \leq S \leq 10^9$$$, indicating the size of the dataset and bugged number respectively. One the next line, $$$N$$$ integers $$$1 \leq a_i \leq 10^9$$$ representing the data set.
One line with yes if he can separate the set into two, each without a pair summing to $$$S$$$, no otherwise (case insensitive).
5 6 1 2 3 4 5
yes
8 6 1 1 1 1 3 3 3 3
no
Superbman is escaping from his archrival Rex Ruthor's hideout and is pursued into a large cornfield of size $$$n$$$ meters by $$$m$$$ meters. Each square meter of the cornfield is either filled with thick and tall corn stalks (noted by a '*' on the grid) or is empty (noted by '.'). Superbman is running low on energy though and needs to begin his evasive maneuver quickly.
From recent memory, he has found that Rex tends to be lost whenever he makes sharp turns so he decides to make a right triangle with his flight path in order to completely bamboozle Rex. However, he wants to make the three turns (corresponding to the vertices of the triangle) in only the squares which contain the corn stalks. Additionally, Superbman doesn't like flying diagonally so he wants two of the sides of the triangle made by his flight path to be parallel to the sides of the square.
Given Superbman's complicated escape maneuver plan, help Superbman find the number of triangles that can be made on the cornfield which fit his specifications.
The first line of input will be two space-separated integers $$$n$$$ and $$$m$$$ where $$$1 \leq n,m \leq 500$$$ and $$$n$$$ is the number of rows in the cornfield and $$$m$$$ is the number of columns.
The following $$$n$$$ lines will each contain $$$m$$$ characters (the only two possible characters are '*' and '.') to describe the field.
Output a single integer, the number of triangles that satisfy Superbman's escape maneuver plan.
2 2 ** *.
1
3 2 .* *. .*
0
Ratman is attempting to save the city from one of his most dangerous nemeses, the Puzzler! Unfortunately, the Puzzler has distributed various bombs around Ratman's hometown, Gothem city, and Ratman must solve a series of math puzzles to defuse each bomb.
Specifically, each bomb is labelled with two numbers $$$n$$$ and $$$k$$$. For each bomb, Ratman must calculate the number of pairs of integers $$$a, b$$$ with $$$0 \leq a \lt b \lt 2^k$$$ such that $$$a \oplus b = n$$$, where $$$\oplus$$$ denotes the XOR operator. After doing so, he can plug the result into his bomb-defusing machine, which will neutralize the threat if the number is calculated correctly.
Write a program to help Ratman solve the Puzzler's riddles and defuse the bombs throughout Gothem city!
The input will consist of two numbers $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$ and $$$k$$$ $$$(1 \leq k \leq 60)$$$.
Output the number of distinct pairs of integers $$$a, b$$$ such that $$$0 \leq a \lt b \lt 2^k$$$ and $$$a \oplus b = n$$$.
7777 1
0
3 2
2
In the first sample, the only possible pair is $$$a = 0, b = 1$$$ and $$$0 \oplus 1 = 1 \neq 7777$$$.
In the second sample, there are two pairs that satisfy the above property. Specifically $$$a = 0, b = 3$$$ and $$$a = 1, b = 2$$$ both work.
Dr. Stronge has a lot of superhero friends, like the Hulc and Admiral USA, and he likes to keep tabs on all of their affairs (sometimes by looking into the future). Recently, Dr. Stronge has grown concerned about a brewing feud between the heroes, that could erupt into a full-blown civil war! But in order for a civil war to break out among the superheroes, there would need to be something powerful dividing them all...
To investigate this possibility, Dr. Stronge has sent a survey out to his $$$N$$$ superhero friends, asking each of them their favorite number $$$f_i$$$, and everyone responded. Dr. Stronge believes that a civil war is imminent if there exists some $$$d=a^p$$$ where integers $$$a, p \geq 2$$$ such that $$$d$$$ divides $$$f_i$$$ for all $$$i$$$. In other words, he wants to know whether each superhero's favorite number is divisible by a common divisor that is equal to some number taken to a higher power.
Help Dr. Stronge predict whether or not there will be a civil war! Given $$$N$$$ superhero favorite numbers, output the largest value of $$$d$$$ such that it divides all of the heroes' favorite numbers and is of the form $$$a^p$$$ for some $$$a, p \geq 2$$$, or output NO CIVIL WAR if there is no such divisor $$$d$$$.
The first line of input contains an integer $$$N$$$ ($$$1 \leq N \leq 10^3$$$) denoting the number of superheroes surveyed by Dr. Stronge. The next line contains $$$N$$$ space-separated integers $$$f_1$$$ through $$$f_N$$$ ($$$1 \leq f_i \leq 10^6$$$) which are the superheroes' favorite numbers.
On a single line, print the largest $$$d$$$ satisfying Dr. Stronge's civil war requirement, or NO CIVIL WAR if none exists.
6 27 72 45 99 126 54
9
3 100 6 14
NO CIVIL WAR
Wicked Thamos is plotting to take over the universe after he becomes extremely powerful by collecting all of the legendary Eternity Rocks. However, our hero Spar-Lord refuses to let that happen without putting up a fight! Spar-Lord wants to obtain as many Eternity Rocks as possible, to keep them out of Thamos's possession.
Spar-Lord has planned out a space voyage to visit $$$N$$$ planets in order before he will finally rendezvous with the rest of his crew—the Custodians of the Galaxy. On the $$$i^{th}$$$ planet, Spar-Lord has the opportunity to obtain $$$r_i$$$ Eternity Rocks if he descends onto the planet and battles the enemies that are hoarding the rocks. However, if he does so, he will need to spend some time on his ship recovering from the battle, so he will not be able to descend onto any of the next $$$k$$$ planets, with indices $$$i+1$$$ through $$$i+k$$$. Spar-Lord also has the option to descend onto the $$$i^{th}$$$ planet for only a quick skirmish, where he will obtain $$$\frac{r_i}{2}$$$ Eternity Rocks rounded down to the nearest integer but only need to recover from the battle while passing over the next $$$\frac{k}{2}$$$ planets, also rounded down to the nearest integer. Of course, Spar-Lord can always choose not to descend onto a planet, and save his energy for a future, more critical battle.
Help Spar-Lord make the right choices to obtain as many Eternity Rocks as possible! Output the maximum number of Eternity Rocks that Spar-Lord will be able to collect.
The first line of input contains the integers $$$N$$$ and $$$k$$$ ($$$1 \leq k \leq N \leq 10^6 $$$), denoting the number of planets on Spar-Lord's voyage and his battle recovery constant respectively. The next line contains $$$N$$$ space-separated integers $$$r_0$$$ through $$$r_N$$$, where $$$r_i$$$ $$$(0 \leq r_i \leq 10^3)$$$ is the number of Eternity Rocks available on the $$$i^{th}$$$ planet.
Print the maximum number of Eternity Rocks that Spar-Lord should be able to accumulate along his space voyage.
8 2 135 466 904 575 492 259 796 317
1767
An evil supervillain has stranded some innocent civilians in an archipelago! Luckily, the legendary flying superhero Agamemnon has come to save the day!
The archipelago can be mapped in an $$$N \times N$$$ grid. The civilians are stuck at location $$$(1,1)$$$ and Agamemnon has spotted a helipad at $$$(N, N)$$$.
Agamemnon has a special ability: he can build land between these islands, effectively replacing a square of water with land. By connecting the civilians to the helipad (they can only travel in the $$$4$$$ cardinal directions), he hopes to quickly evacuate them.
However, as is common with many omnipotent individuals, he has grown incredibly lazy and despite wanting to help, wants to expend minimal effort, so he can resume feeding his addiction to competitive programming.
Given an $$$N \times N$$$ map of the region and which cells are land and water, help Agamemnon determine the smallest amount of land he must create to effectively evacuate the civilians.
The first line contains a single number, $$$1 \leq N \leq 500$$$. The next $$$N$$$ lines display the grid, containing $$$N$$$ digits each, either $$$0$$$ for water or $$$1$$$ for land.
A single integer, the smallest amount of land needed to evacuate the civilians.
5 11010 00000 01011 01000 01101
2
The civilians $$$(1,1)$$$ and helipad $$$(N, N)$$$ will always be on land.
Stephen finds a slightly defective sling ring while training at Kamar-Taj that will open portals, but going through each portal takes time rather than being instant. Portals are bidirectional so that someone on either side can get through to the other side. To practice, he opens a bunch of portals between various locations of interest. However, he isn't well trained enough yet to maintain all of the portals, so the portals begin to collapse over time.
Stephen wonders how quickly he can get between any two arbitrary locations as the portals are collapsing. Can you help him?
First line contains $$$N, M, Q$$$, the number of locations, portals, and queries. $$$ 2 \leq N \leq 300, 1 \leq M \leq Q \leq 10000$$$
The next $$$M$$$ lines are in the form $$$u_i$$$ $$$v_i$$$ $$$w_i$$$, indicating a portal from location $$$u_i$$$ to $$$v_i$$$ (0 indexed) that takes $$$w_i$$$, $$$0 \leq u_i, v_i \lt N$$$ and $$$0 \leq w_i \leq 10000$$$.
Then the next $$$Q$$$ lines are in the form $$$q$$$ $$$u_i$$$ $$$v_i$$$, where $$$q$$$ being 0 indicates a portal collapse between $$$u_i$$$ and $$$v_i$$$ and 1 for a query for fastest to get from $$$u_i$$$ to $$$v_i$$$. It is guaranteed that there will be $$$M$$$ lines where $$$q$$$ is 0, i.e. all portals will collapse.
For each query where $$$q$$$ is 1, print the quickest you can get from location $$$u_i$$$ to $$$v_i$$$. If you cannot get from $$$u_i$$$ to $$$v_i$$$, print IMPOSSIBLE.
3 3 6 0 1 1 0 2 3 1 2 1 1 0 2 0 1 2 1 0 2 0 0 1 0 0 2 1 0 2
2 3 IMPOSSIBLE