Magikarp dreams of becoming a jumping champion and eventually evolving into a Gyarados! For now, he is practicing on a row of $$$n$$$ spots, numbered $$$1$$$ through $$$n$$$. The height of spot $$$i$$$ is $$$h_i$$$.
Magikarp starts at spot $$$1$$$ and wants to reach spot $$$n$$$. From spot $$$i$$$, he can jump to spot $$$i+1$$$, $$$i+2$$$, or $$$i+3$$$, as long as the destination does not exceed $$$n$$$. A jump from spot $$$i$$$ to spot $$$j$$$ costs $$$$$$ (h_i-h_j)^2 $$$$$$ energy. The total energy cost is the sum of the costs of all his jumps.
What is the minimum total energy cost for Magikarp to reach spot $$$n$$$?
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of spots.
The second line contains $$$n$$$ integers $$$h_1,h_2,\ldots,h_n$$$ ($$$0 \le h_i \le 10^6$$$) — the heights of the spots.
Output a single integer — the minimum total energy cost for Magikarp to reach spot $$$n$$$.
610 30 20 40 10 20
100
70 1000000 1000000 0 1000000 1 1000000
999998000002
41 100 100 1
0
17
0
In the first sample, Magikarp can jump from spot $$$1$$$ to spot $$$3$$$, then to spot $$$6$$$. The total cost is $$$(10-20)^2+(20-20)^2=100$$$, which is the minimum possible.
In the second sample, one optimal route visits spots $$$1,4,6,7$$$, using jumps of lengths $$$3,2,1$$$. The total cost is $$$$$$ (0-0)^2+(0-1)^2+(1-10^6)^2=999998000002. $$$$$$
In the third sample, Magikarp can jump directly from spot $$$1$$$ to spot $$$4$$$. Both spots have height $$$1$$$, so the cost is $$$0$$$.
In the fourth sample, Magikarp is already at spot $$$n$$$, so he does not need to jump. The total cost is $$$0$$$.
Magikarp is a cashier at Hudson River Trader Joe's (HRTJ). HRTJ has some weirdly valued coins, and the available coin values can change from day to day!
On a day with parameters $$$b$$$ and $$$k$$$, HRTJ has coins worth $$$b^0,b^1,\ldots,b^k$$$ cents. Magikarp has an unlimited number of coins of each of these values. He must give a customer exactly $$$x$$$ cents in change.
For each of $$$t$$$ days, find the minimum number of coins Magikarp needs. Each day is independent.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of days.
Each of the next $$$t$$$ lines contains three integers $$$b$$$, $$$k$$$, and $$$x$$$ ($$$2 \le b \le 10^9$$$, $$$0 \le k \le 29$$$, $$$1 \le x \le 10^9$$$) — the base of the coin values, the largest exponent, and the amount of change in cents for that day, respectively.
It is guaranteed that $$$b^k \le 10^9$$$ for each day.
For each day, output a single integer on its own line — the minimum number of coins needed to give exactly $$$x$$$ cents in change.
13 3 35
5
510 2 12342 0 10000000001000000000 1 12 29 53687091210 9 1000000000
19 1000000000 1 1 1
32 3 205 1 2010 0 20
3 4 20
11000000000 1 999999999
999999999
In the first sample, the coin values are $$$1$$$, $$$3$$$, $$$9$$$, and $$$27$$$. Magikarp can give $$$35$$$ cents using five coins: $$$27+3+3+1+1=35$$$.
In the second sample:
- On the first day, the coin values are $$$1$$$, $$$10$$$, and $$$100$$$. Magikarp needs twelve $$$100$$$-cent coins, three $$$10$$$-cent coins, and four $$$1$$$-cent coins, for a total of $$$19$$$ coins.
- On the second day, $$$k=0$$$, so only $$$1$$$-cent coins are available. Magikarp needs $$$10^9$$$ coins.
- On the third day, the change is $$$1$$$ cent, so one $$$1$$$-cent coin is enough.
- On the fourth day, one coin worth $$$2^{29}$$$ cents is enough.
- On the fifth day, one coin worth $$$10^9$$$ cents is enough.
In the third sample, the change is $$$20$$$ cents on every day, but the coin values change. Magikarp can use $$$8+8+4$$$ on the first day and $$$5+5+5+5$$$ on the second day. On the third day, he must use twenty $$$1$$$-cent coins.
In the fourth sample, the only coin values are $$$1$$$ and $$$10^9$$$. The larger coin exceeds the required change, so Magikarp must use only $$$1$$$-cent coins.
In a trail race, there is no shame in walking for part of the race! Walking up a steep hill can save energy and allow a runner to achieve a better overall time.
You are running a trail race this weekend, and you know that your body can expend a total of $$$E$$$ units of energy before you'll be too exhausted to finish the race. For each mile of the race, you can choose to either walk or run. Each strategy consumes a certain amount of energy and takes a certain amount of time.
Compute the fastest you can finish the race.
The first line of input contains two space-separated integers $$$N$$$ $$$(1 \leq N \leq 50)$$$ and $$$E$$$ $$$(1 \leq E \leq 1\,000)$$$, the number of miles in the race and the maximum energy you can consume, respectively.
Each of the next $$$N$$$ lines contains four space-separated integers $$$e_1$$$, $$$t_1$$$, $$$e_2$$$, and $$$t_2$$$ $$$(0 \leq e_1, e_2 \leq 1\,000; 1 \leq t_1, t_2 \leq 10\,000)$$$: the amount of energy it costs to walk the mile, how many seconds doing so takes, the amount of energy it costs to run the mile instead, and how many seconds running the mile takes.
Note that it is not necessarily the case that $$$e_1 \lt e_2$$$ or $$$t_1 \gt t_2$$$.
Print a single integer: the fastest time (in seconds) you can complete the race. If it is impossible to finish the race no matter the strategy, print $$$-1$$$ instead.
3 1001 600 50 4501 650 50 4001 500 50 500
1500
3 10040 125 35 10035 200 35 18050 500 31 430
-1
In the first sample, Magikarp can walk the first and third miles and run the second. This uses $$$52$$$ energy and takes $$$600+400+500=1500$$$ seconds, which is the minimum time possible.
In the second sample, even the least-energy choice on each mile uses $$$35+35+31=101$$$ energy, more than the limit of $$$100$$$. Therefore finishing is impossible.
Some CS 314 students have asked you for help on a problem from their first homework assignment. You didn't get all of the details about the problem bounds, so you've set some limits that seem reasonable to you. Can you help them solve the problem?
You are given a rectangular $$$N \times M$$$ grid $$$g$$$ of integers, and the homework problem asks you to compute the maximum possible sum of entries in a contiguous rectangular sub-grid of the given grid. (A $$$0 \times 0$$$ sub-grid is a valid sub-grid and its entries sum to $$$0$$$. The entire grid $$$g$$$ also counts as a sub-grid of itself.)
In other words, compute $$$$$$\max_{0 \leq l \leq r \leq M \\ 0 \leq t \leq b \leq N} \sum_{i=l}^{r-1} \sum_{j=t}^{b-1} g_{ji}$$$$$$ where $$$g_{ji}$$$ is the grid entry in row $$$j$$$, column $$$i$$$.
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$ $$$(1 \leq N, M \leq 500)$$$, the number of rows and columns in the grid $$$g$$$, respectively.
The next $$$N$$$ lines each contain $$$M$$$ space-separated integers each and describe the entries of $$$g$$$. All entries are in the range $$$[-10^6, 10^6]$$$.
Print a single integer: the sum of the entries in the contiguous sub-grid of $$$g$$$ that maximizes this sum.
4 47 -3 4 2-1 8 -5 63 0 -9 10-4 5 1 -8
22
2 3-3 -1 -4-1 -5 -9
0
4 5-108793 -29395 -608138 -722622 407621702232 -619216 391815 -778753 568439426028 69966 885259 624653 -531945887849 -702803 -494114 655225 155269
2352063
In the first sample, the sub-grid using rows $$$1$$$ through $$$3$$$ and columns $$$1$$$ through $$$4$$$ has sum $$$22$$$, which is maximum.
In the second sample, every entry is negative, so the valid empty sub-grid has the maximum sum, $$$0$$$.
In the third sample, the sub-grid using rows $$$3$$$ and $$$4$$$ and columns $$$1$$$ through $$$4$$$ has the maximum sum, $$$2352063$$$.
A UTPC Code is similar to a QR code: it is a square bitmap of white and black pixels that encodes data. Not any bitmap is a valid UTPC Code, though. Valid codes must satisfy the following parity constraint: in any $$$2\times 2$$$ contiguous block of pixels, the number of black pixels in the block must be even. In other words, the following $$$2\times 2$$$ blocks cannot appear anywhere inside a valid UTPC Code:
WB BW BB BB BW WB WW WW
BB BB WB BW WW WW BW WB
where W and B represent white and black pixels, respectively.
You are given an $$$N \times N$$$ grid with some pixel colors already filled in. Is it possible to complete the rest of the UTPC Code in a way that satisfies the parity constraint?
First line of input contains a single integer $$$N$$$ $$$(1 \leq N \leq 10)$$$: the size of the grid. Then follow $$$N$$$ lines of exactly $$$N$$$ characters each. Each character will be one of W, B, or ., representing a white or black pixel already given at that location in the grid, or a blank spot that you need to fill in, respectively.
Print POSSIBLE if it is possible to fill in all remaining . cells with a black or white pixel in a way that satisfies the UTPC parity constraint, and IMPOSSIBLE otherwise.
3W.WBBB...
POSSIBLE
5WWBWBW....B...B..W...W...
IMPOSSIBLE
In the first sample, one valid completion is
WWW
BBB
WWW
In the second sample, it is impossible to fill in the unknown pixels so that the completed grid satisfies the parity rule.