You go to bed early on Friday the $$$13^{th}$$$ because you are feeling kind of eepy, only to wake up in the middle of the night to a loud sound. You look around and find yourself in an creepy, abandoned mansion. Beside you is an old map of the mansion. The map indicates $$$n$$$ mysterious points scattered throughout the mansion. Each point is represented by a pair of coordinates $$$(x_i, y_i)$$$, and you are currently standing at a point $$$(x_0, y_0)$$$.
You decide to investigate the point on the map closest to your current location (by Euclidean distance), hoping to find some kind of exit.
The first line contains $$$n$$$, the number of points on the map $$$(1 \leq n \leq 10^5)$$$.
The second line contains two integers, $$$x_0$$$ and $$$y_0$$$, representing your current coordinates $$$(0 \leq x_0, y_0 \leq 10^6)$$$.
Each of the next $$$N$$$ lines contains two integers, $$$x_i$$$ and $$$y_i$$$, representing the coordinates of the $$$i^{th}$$$ point $$$(0 \leq x_i, y_i \leq 10^6)$$$.
It is guaranteed that all points, including your current coordinates, are pairwise distinct.
Print two space-separated integers, $$$x_i$$$ $$$y_i$$$, the coordinates of the point $$$(x_i, y_i)$$$ that is closest to your current location $$$(x_0, y_0)$$$. If there are multiple points at the same minimum distance, output the point with the smallest x-coordinate. If there is still a tie, output the point with the smallest y-coordinate.
42 31 15 210 104 5
1 1
25 01 07 0
7 0
25 07 03 0
3 0
20 01 11000000 1000000
1 1
In the first sample test case, you are currently standing at point (2,3).
The distance from each point to your location is as follows:
(1, 1): $$$\sqrt{(2-1)^2 + (3-1)^2} = 2.24$$$
(5, 2): $$$\sqrt{(2-5)^2 + (3-2)^2} = 3.16$$$
(10, 10): $$$\sqrt{(2-10)^2 + (3-10)^2} = 10.63$$$
(4, 5): $$$\sqrt{(2-4)^2 + (3-5)^2} = 2.83$$$
Thus, the point on the map that is closest to you is (1, 1) because it has the smallest Euclidean distance.
Vitya woke up from his nightmare and turned on his laptop in yet another boring day as a mid-career software engineer. Then, in horror, he noticed that his computer has turned ternary — in addition to $$$0$$$ and $$$1$$$, he now notices $$$2$$$ in the data flow too. This is indeed worse than any nightmare he could have ever expected — essential programs he wrote were based on the seemingly unshakable assumption that binary "bits" would be received, not ternary "trits" (this is a real word: see the Wikipedia article).
Fortunately, Vitya built his programs with resilience in mind: within a data stream, it can withstand a certain number of unexpected values (in this case, '2'), $$$k$$$, before it starts behaving unpredictably. Since his laptop has just turned ternary, he needs your help finding the maximum length of the continuous sub-stream from his data stream of length $$$n$$$ that can be run through the programs without causing unexpected behavior.
The first line consists of two integers, $$$n$$$ and $$$k\ (1\leq n \leq 10^5, 0\leq k \leq n)$$$ — the length of the data stream and the maximum allowed unexpected values.
The second line consists of a single string $$$s$$$, representing the ternary data stream, made up of exclusively $$$0$$$, $$$1$$$, and $$$2$$$.
The length of the longest substring from the string representing the data stream containing at most $$$k$$$ instances of the value $$$2$$$, which is an unexpected value for Vitya's program.
16 31201012200120012
13
In the sample, the longest substring from the data flow can be highlighted as $$$12\textbf{0101220012001}2$$$.
On Halloween night, you find yourself in a spooky hallway lined with lanterns. Each lantern is either on (represented by '1') or off (represented by '0'). However, to escape the haunted hallway, all the lanterns need to be either on or off. You have a magical ability: you can flip all the lanterns in any one contiguous section of the hallway, turning all the '1's to '0's and all the '0's to '1's.
You want to get out of the hallway as fast as possible, so you want to make all the lanterns either on or off with the fewest number of lantern flips.
The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of lanterns in the hallway.
The second line contains a binary string $$$S$$$ of length $$$n$$$, where each character represents the state of a lantern ('1' for on and '0' for off).
Print the minimum number of lantern flips you need to do to make all the lanterns either on or off.
101001011001
3
It was the night before exams when all along 24th not a student was awake, as they wanted to be well rested. Freddy Krueger, dream visitor and altruist, thought this would be a good time to check in on students in their dreams before their exams. Freddy is playing with numbers in his head and is curious about how many buildings he'd have to visit to bless a given number of students.
There are $$$n$$$ buildings along 24th, with the $$$i$$$th building housing $$$a_i$$$ students. Freddy is curious about the logistics of $$$m$$$ possible quantities for the number of students he would visit, where the $$$j$$$th possible quantity is given by $$$q_j$$$. When meeting students, Freddy must visit the students' buildings in sequential order starting with the first building. For each number $$$q_j$$$ Freddy is curious about, please output the minimum number of buildings Freddy would have to visit to check that many students. If it's not possible to meet the requested number of students, please output -1.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — the number of buildings and number of quantities Freddy is curious about.
The second line contains $$$n$$$ integers $$$a_1, a_2, ... , a_n$$$ ($$$0 \leq a_i \leq 10^5$$$) — the number of students in each building.
The last line contains $$$m$$$ integers $$$q_1, q_2, ... , q_m$$$ ($$$0 \leq q_j \leq 10^9$$$) — where $$$q_i$$$ is the $$$i$$$th quantity Freddy is curious about.
For each quantity, please output the minimum number of buildings Freddy would have to visit to check that many students, or -1 if it is not possible. Output each answer on its own line.
7 510 8 2 4 4 8 910 15 25 41 100
1 2 5 7 -1
It is the day after a very successful Halloween and Charlie managed to receive so much candy that he can't decide when he should eat all of it!
The candy that Charlie has can be divided into $$$n$$$ types numbered $$$1, \dots, n$$$. For some candy type $$$i$$$, let $$$k_i$$$ denote the amount of candy $$$i$$$ that Charlie has, and let $$$c_i$$$ denote the tastiness of each piece of candy of type $$$i$$$. The total tastiness of Charlie's consumptions is given by the sum of the tastiness of each piece of candy that Charlie eats. Charlie would love to eat all of the candy he has, but unfortunately there are the following restrictions:
- All of the candy expires after $$$d$$$ days, meaning that after the $$$d$$$-th day, Charlie cannot eat any more of his candy.
- Charlie's parents won't allow him to eat more than $$$x$$$ pieces of candy in a given day.
- Charlie will not eat two candies of the same type on the same day.
Please help Charlie and determine the maximum total tastiness he can achieve if he eats his candy optimally!
The first line of input will contain $$$n$$$, $$$d$$$, and $$$x$$$ ($$$1 \leq n, d, x \leq 2 \cdot 10^5$$$) — the number of types of candies, the number of days before all candies expire, and the maximum number of candies Charlie can eat a day.
The next line of input consists of $$$n$$$ space-separated integers $$$k_1, k_2, \dots, k_n$$$ ($$$1 \leq k_i \leq 2 \cdot 10^5$$$) — the amount of candy that Charlie has of each type.
The last line consists of $$$n$$$ space-separated integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \leq c_i \leq 2 \cdot 10^5$$$) — the tastiness of a piece of candy of each type.
Output a single integer denoting the maximum total tastiness that Charlie could achieve by eating the candies optimally.
8 3 31 1 2 1 3 2 2 12 7 6 9 4 3 5 8
54
1 200000 200000200000200000
40000000000
Harry was on a school trip and decided to go to a haunted house. However, he is incredibly afraid of ghosts.
Fortunately, Harry knows the layout of the house - it has $$$n$$$ total rooms and $$$m$$$ doors between rooms. Furthermore, there are $$$k$$$ exits - they are in rooms $$$e_1, \dots e_k$$$.
When Harry was in room $$$s$$$, he found out that there were exactly $$$g$$$ ghosts in the house. Specifically, they are in rooms $$$r_1, \dots r_g$$$.
It takes 1 second for both Harry and ghosts to move between rooms.
An exit is considered good if it is guaranteed that Harry can get to the exit without ever being in the same room as a ghost. Please tell Harry how many good exits there are.
The first line contains 5 space-separated integers $$$n$$$, $$$m$$$, $$$s$$$, $$$k$$$, and $$$g$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$, $$$1 \leq s, k, g \leq n$$$) — the number of rooms, number of doors, Harry's starting room, the number of exits, and the number of ghosts, respectively.
The following $$$m$$$ lines each contain two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq n$$$) – denoting a door between rooms $$$a$$$ and $$$b$$$.
The next line contains $$$k$$$ space-separated integers $$$e_1, \dots, e_k$$$ ($$$1 \leq e_i \leq n$$$) – the rooms that have exits.
The next line contains $$$g$$$ space-separated integers $$$r_1, \dots, r_g$$$ ($$$1 \leq r_i \leq n$$$) – the rooms that have ghosts.
It is guaranteed that there is at most one exit in each room, at most one ghost in each room, and at most one door between each pair of rooms.
The output should consist of exactly one number - denoting the number of good exits.
5 4 5 1 21 22 32 41 513 4
1
5 5 5 1 21 22 32 41 51 413 4
0
In test case 1, Harry can go to room 1 on second 1. Then he can safely exit.
In test case 2, the ghost in room 4 can go to room 1 on second 1, thus blocking the only exit.
Sam is navigating a giant maze of pumpkins, and they need your help to find the exit before it is too late!
The maze can be represented as an $$$n \times m$$$ grid, each cell consisting of one of the following objects:
- A ".", denoting an empty space.
- A "P", denoting an impassable pumpkin.
- A "C", denoting a candy corn, which Sam may collect by passing through.
- A "J", denoting a jack-o'-lantern, which Sam may only pass through by spending a candy corn (if they currently have no candy corns, it acts as an impassable space).
- An "S", denoting Sam's starting space.
- An "E", denoting the exit to the pumpkin patch.
Additionally, Sam can only move in four directions: up, down, left, and right; each taking one unit of time. Given the description of the maze Sam finds themselves in, output the shortest amount it would take for Sam to reach the exit space, our output "SPOOKED!" if it is impossible for Sam to escape.
The input will begin with a single line containing two space-separated integers, $$$n$$$ and $$$m\ (1 \leq n, m \leq 100)$$$. The next $$$n$$$ lines will each contain exactly $$$m$$$ characters, describing the maze. The $$$j^{\text{th}}$$$ character on the $$$i^{\text{th}}$$$ line, denoted as $$$c_{i,j}$$$, satisfies the following requirements:
- $$$c_{i,j} \in \{$$$"."$$$, $$$"P"$$$, $$$"C"$$$, $$$"J"$$$, $$$"S"$$$, $$$"E"$$$\}$$$.
- There exists exactly one $$$(i, j) \in \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$$$ such that $$$c_{i,j} = $$$ "S" and exactly one such that $$$c_{i,j} =$$$ "E".
Finally, let $$$d$$$ denote the number of candy corns in the maze, that is, the number of values $$$(i, j)$$$ such that $$$c_{i,j} = C$$$. It is guaranteed that $$$0 \leq d \leq 8$$$.
The output should consist of exactly one line containing either the phrase "SPOOKED!" if it is impossible for Sam to escape, or the minimum amount of time it would take Sam to reach the exit space.
5 5S..PC.PPP..P....P..J...JE
16
1 10SCCCCJJJJE
9
3 3EJJJSJJJJ
SPOOKED!
There are $$$n$$$ students standing on Speedway, each at some position between $$$1$$$ to $$$n-1$$$. Each student randomly faces either left (towards position $$$0$$$) or right (towards position $$$n$$$) with equal probability independent of any other students. At time $$$t=0$$$, each student begins to move one position per second in the direction they are facing.
If two students collide, they switch directions without stopping. Two students may start at the same location; if they move in the same direction they never collide.
Given $$$q$$$ queries $$$t$$$, each asking for the probability that no students have exited Speedway (i.e., reached position $$$0$$$ or $$$n$$$) after $$$t$$$ seconds, determine the result for each query. It can be shown the probability that no students have exited Speedway is either 0 or of the form $$$2^{-m}$$$ for some integer $$$m$$$. You should output $$$m$$$ for each query. If the probability is $$$0$$$, output $$$-1$$$ instead.
The first line contains two integers $$$n$$$ and $$$q\ (2 \leq n \leq 10^5, 1 \leq q \leq 10^5)$$$, the length of Speedway and the number of queries.
The second line contains $$$n$$$ integers $$$a_1, a_2,...,a_n\ (1\leq a_i\leq n-1)$$$ representing the initial positions of the students, not necessarily sorted.
The next q lines each contain an integer $$$t\ (1 \leq t \leq 10^8)$$$ representing a query, where $$$t$$$ is the time (in seconds) after which you need to determine the probability that no students have evacuated Speedway.
It can be shown the probability that no students have exited Speedway is either 0 or of the form $$$2^{-m}$$$. You should output $$$m$$$ for each query, one on each line. If the probability is $$$0$$$, output $$$-1$$$ instead.
7 26 6 2 2 2 3 31100
2 -1
After $$$1$$$ second, no students have exited Speedway as long as the two students at location $$$6$$$ are both facing left, which has probability $$$\frac{1}{4} = 2^{-2}$$$. After $$$100$$$ seconds, it would be impossible for no students to have exited.