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.
Alice is going trick-or-treating! Her goal is to visit every house in her neighborhood before they turn off their lights. Alice's neighborhood is represented by an one-dimensional array, with the i-th element representing the amount of minutes before the i-th house turns off its lights. Every minute, Alice can go one house to the left, or one house to the right. If Alice arrives at the moment a house turns its lights off, they will not give her candy. Alice needs you to help her find out if she can visit every house before they turn their lights off. If she can, find the minimum amount of time it would take her. Else, output -1.
The first line of each test cases contains integer $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2000, 1 \leq k \leq n$$$), the size of the array and Alice's position in the array (1-indexed).
The second line contains $$$n$$$ integers $$$a_1, a_2,...,a_n\ (1 \leq a_i \leq 10^6)$$$, the elements of the array.
For each test case, output the minimum time it would take Alice to visit every house and still collect candy from them. If this is not possible, output -1.
5 25 1 2 9 8
7
5 3100 3 1 5 6
8
5 22 1 4 5 5
-1
It can be shown that Alice cannot visit all of the houses in time in third test case.
Alex loves poker! Unfortunately, today all the players in his home game have transformed into ghosts and ghouls. Also, instead of a standard 52-deck, there are $$$n$$$ cards in a row, each with one of the thirteen ranks. For simplicity, all the ranks are integers from $$$1$$$ to $$$13$$$.
Alex soon discovers that the spirits really love "phantom" combinations, which are defined to be combinations of cards whose product of denominations is $$$5 \bmod 13$$$. For example, a $$$2$$$, $$$5$$$, and $$$7$$$ is a "phantom" combination since $$$2 \cdot 5 \cdot 7 = 70$$$, which is $$$5 \bmod 13$$$.
As Alex gets up to leave, he is met with $$$q$$$ different challenges! On each challenge, the ghoul asks two types of queries:
- 1 i x ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 13$$$) — Set the rank of the $$$i$$$th card to $$$x$$$.
- 2 l r ($$$1 \leq l \leq r \leq n$$$) — Find the number of phantom combinations of cards using only the cards from indices $$$l$$$ to $$$r$$$, inclusive.
Alex is stunned; how is he going to leave now? Can you help him process each of the queries? The answers for query 2 may be large, so output the answer $$$\bmod 10^9 + 7$$$.
The first line contains two space separated integers, $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^4$$$) — the number of total cards and the number of queries that need to be processed.
The second line contains $$$n$$$ space-separated integers $$$d_1, d_2, \dots, d_n$$$ ($$$1 \leq d_i \leq 13$$$) — the initial ranks of each cards.
The next $$$q$$$ lines contain a query, one per each line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.
For each query of the second type print the answer for it – the number of possible phantom combinations of cards using only cards within the specified range.
4 31 2 5 92 1 41 2 32 1 3
4 2