Mila is baking a traditional pastry, baklava! Now that she has layered many strips of thin dough, butter, and nuts, she wants to cut the baklava in an ornate way (even if it isn't optimal for sharing the dish fairly.
Namely, her baklava begins as a square of side length $$$l$$$, and Mila is going to perform $$$k$$$ rounds of cutting. In the first round, she will make four cuts that inscribe a smaller square into the original baklava square; the cuts will be from the midpoints of each side to the midpoints of the sides which are not directly across from them. In each subsequent round, she will perform the same four cuts except with the midpoints of the previous round's smaller inscribed square. A visual depiction of this process is shown below for $$$k = 2$$$, with the first round's cuts depicted in red and the second round's cuts depicted in blue:
Mila wants to see just how unfair this cutting scheme is for sharing the baklava, so she wants to calculate the size of the final square which is inscribed in the baklava after the final round of cuts. Can you help her calculate this area?
The input will consist of a single line containing two space-separated integers $$$l\ (1 \leq l \leq 10^9)$$$ and $$$k\ (1 \leq k \leq 25)$$$, denoting the initial side length of Mila's baklava and the number of rounds of cutting, respectively.
The output should consist of a single floating-point number denoting the size of the smallest inscribed square in Mila's baklava. A competitor's output will be considered correct if it has absolute or relative error less than or equal to $$$10^{-6}$$$ with respect to the judge's solution's output.
2 1
2.00000000000000000000
10 25
0.00000298023223876953
Janise is baking a honey baklava with $$$N$$$ layers. She knows that if she reverses $$$N$$$, she will get a number divisible by $$$5$$$. Janise wants to know how many possible baklavas with $$$9$$$-digit $$$N$$$ satisfy this property that have a layer count $$$N$$$ that is divisible by $$$K$$$. Can you help her calculate this?
The first line contains $$$T$$$ ($$$1 \leq T \leq 10^5$$$), the number of test cases. The next $$$T$$$ lines each contain a single integer $$$K$$$ ($$$1 \leq K \leq 10^5$$$).
For each of the $$$T$$$ test cases, output the total number of possible baklavas Janise could bake on a new line.
5 1 2 3 4 5
100000000 50000000 33333333 25000000 20000000
It's baklava night at Hell's Kitchen, and the teams are struggling to get their dishes out. Customers have already placed $$$N$$$ orders for baklava, and they're getting impatient!
Specifically, each order specifies a quantity $$$a_i$$$, denoting how many baklavas the customer wants. The cooks have already prepared $$$N$$$ batches of baklava, but these batches may not have the correct quantity of orders for baklavas; the $$$i$$$th batch consists of $$$b_i$$$ baklavas.
In one operation, the cooks can move one baklava from any batch to any other batch (and these batches may be different between operations). In order to prevent the customers from walking out or rioting, they need to get an order out as quickly as possible. What is the minimum number of operations required to complete any order? An order is considered completed if the number of baklavas requested is equal to the quantity of baklavas in any batch.
The first line consists of a single integer $$$N$$$, the number of orders and the number of batches. ($$$1 \le N \le 2 \cdot 10^5$$$).
The second line consists of $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the number of baklavas ordered by the $$$i$$$th customer.
The third line consists of $$$N$$$ integers $$$b_1,...,b_N$$$ ($$$1 \le b_i \le 10^9$$$), where $$$b_i$$$ denotes the number of baklavas in the $$$i$$$th batch.
Print out a single integer, the minimum number of operations required to complete any order, or -1 if it is not possible.
4 1 2 3 4 5 6 7 8
1
4 5 6 7 8 1 2 3 4
1
Around the world, folks celebrate Baklava Baking day. However, landwellers are not the only ones with a sweet tooth. Beneath the waves, the majestic Kraken prepares to feast, and seeks the help of Vonce Nutty the Wrasse Cleaner to clean its teeth.
A Kraken is an animal with $$$t$$$ one-meter long teeth (1-indexed) arranged in a circle, with $$$n$$$ non-intersecting segments of retainer wire, where going clockwise, each segment spans a tooth range $$$[a_{i},b_{i}]$$$, inclusive. Whole tooth gaps must be cleaned by string. Tooth gaps split by a retainer wire must have the top 0.5m cleaned by string and bottom 0.5m cleaned by pick. Each toothpick has a string end and a pick end. The string end can clean $$$s$$$ meters of teeth before breaking, and the pick end can clean $$$p$$$ meters of teeth before breaking.
Vonce Nutty adheres to the following procedure: He may start at any tooth holding a toothpick, and cleans the tooth gaps in order of either CW or CCW fashion. His current toothpick must completely clean the tooth gap he is working on (i.e. when his current toothpick cannot completely clean the tooth gap, he must get a new toothpick.) He may not use more than one toothpick for a tooth gap; i.e he cannot "borrow" another toothpick to finish cleaning the tooth gap. Additionally, he must finish cleaning the current tooth gap before moving on to the next one (i.e. he can't skip cleaning a tooth gap, cycle around the entire mouth one time, and then finish cleaning this tooth gap with another toothpick).
The first line contains two integers $$$1\leq t \leq 10^3$$$ and $$$1\leq n \leq 10^3$$$, the number of teeth and retainer wires the Kraken has, respectively.
The next $$$n$$$ lines contain two integers $$$1 \leq a_i \leq b_i\leq t$$$, denoting the start and end of each retainer wire $$$1 \leq i \leq n$$$.
The next line contains an integer $$$1\leq s \leq 10^3$$$, how many meters of teeth a toothpick's string end can clean.
The last line contains an integer $$$1\leq p \leq 10^3$$$, how many meters of teeth a toothpick's pick end can clean.
Please output the minimum number of toothpicks Vonce Nutty needs to clean all the Kraken's teeth.
17 21 810 1321
8
On the sample test case, label the teeth gap as 1,2,$$$\cdots$$$,17 going CW. Then it is optimal to start cleaning from tooth gap 0, going CW.
Zeynep has been craving baklava to satisfy her major sweet tooth. As she's pouring the syrup over the baklava, she wonders: given the locations where she has poured syrup, which piece ends up the sweetest?
Formally, each baklava piece is located at some index $$$(i,j)$$$ on a $$$n \times m$$$ grid, and has some height $$$h_{i,j}$$$. Due to the way the baklava is sliced, the syrup flows at an angle; the syrup can either flow directly up or down to $$$(i \pm 1, j)$$$, or it can flow at a diagonal to either $$$(i-1, j-1)$$$ or $$$(i+1, j+1)$$$. The syrup can only flow to a piece with the same or lower height.
Zeynep pours the syrup on $$$q$$$ locations, and lets the syrup flow completely before pouring again. Can you identify which piece is covered by syrup the most number of times?
The first line contains $$$n, m$$$ and $$$q$$$ ($$$1 \leq n,m \leq 100$$$, $$$1 \leq q \leq 1000$$$), the dimensions of the baklava grid and the number of syrup pours.
The next $$$n$$$ lines each contain $$$m$$$ integers, where the $$$i$$$th line contains the heights $$$h_{i,1}, \ldots, h_{i,m}$$$ ($$$0 \leq h_{i,j} \leq 10^9$$$) of each baklava piece.
The next $$$q$$$ lines contain two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i \leq n, 1 \leq j \leq m$$$), the coordinates of the piece where the $$$i$$$th syrup pour starts.
Output three integers, the coordinates of the sweetest piece $$$(i,j)$$$, as well as the number of times that piece gets covered by syrup. If there are multiple sweetest pieces, pick the one with the smallest row coordinate $$$i$$$, and break further ties with the smallest column $$$j$$$.
5 5 3 7 9 9 9 9 6 6 9 2 8 5 9 5 2 8 4 3 5 2 8 3 9 5 2 8 1 1 3 3 1 5
2 4 3
You and an arbitrary number of friends are standing on a grid of baklava of size $$$N \times M$$$, all at coordinate $$$(0, 0)$$$.
Each piece of baklava at coordinate $$$(i, j)$$$ has a limited durability $$$K_{ij}$$$, meaning it can only be stepped on $$$K_{ij}$$$ times. The baklava pieces at $$$(0, 0)$$$ and $$$(N-1, M-1)$$$ both have infinite durability.
You and your friends walk through the baklava grid one by one. At any step, you may travel to a piece that is one step up, down, left, or right from your current piece, but you may not leave the grid. Given the durability across the baklava grid, at most how many friends can make it across to coordinate $$$(N-1, M-1)$$$ until the grid has become too deteriorated to allow anyone past?
Constraints:
$$$2 \leq N \leq 100$$$
$$$2 \leq M \leq 100$$$
$$$0 \leq K_{ij} \leq 100,000$$$
Two integers $$$N$$$, and $$$M$$$, on the first line.
$$$N$$$ lines follow, going from row index $$$i=0$$$ to $$$i=N-1$$$. For each line, $$$M$$$ values follow, going from value index $$$j=0$$$ to $$$j=M-1$$$, each one representing the durability $$$K_{ij}$$$.
Note that the values $$$K_{(0, 0)}$$$ and $$$K_{(N-1, M-1)}$$$ are not needed to solve the problem, as the pieces have infinite durability.
One integer representing the number of friends that can make it across.
2 2 0 1000 2000 0
3000
Baklava has a baklava with $$$N$$$ layers. Each layer has a flavor level, $$$f_i$$$, where $$$1 \leq f_i \leq N$$$. A "baklava interval" is defined as a contiguous sequence of layers. Two intervals are different if their start or end layer positions are different.
Baklava wants you to find the number of unique intervals in the baklava that satisfy the properties:
1. $$$f_i == f_j$$$ where $$$i$$$ and $$$j$$$ are the start and end layer positions of the interval.
2. For every layer $$$k$$$ where $$$i \lt k \lt j$$$, either $$$f_k == f_i == f_j$$$ or $$$f_k$$$ appears only once between the layers $$$[i, j]$$$.
The first line of input will have an integer $$$N$$$. $$$(2 \leq N \leq 100,000)$$$
The next line of input will have $$$N$$$ integers where the $$$i^{th}$$$ integer depicts $$$f_i$$$. $$$(1 \leq f_i \leq N)$$$
Please output one integer, the number of intervals that satisfy Baklava's defined properties above.
51 2 3 1 3
2
101 3 4 5 1 5 4 2 2 2
5
21 1
1