Abhilash's dog Brian woke up late today, and there's only $$$m$$$ minutes left until his first class at Doge University starts! He needs to do many tasks before the first class starts. Sadly, Brian will probably not be able to finish all of his tasks. Brian is very efficient however, and can start the next task immediately after the previous, and can join class on Zoom at any point. This means that if Brian can finish a task just as class is about to start at time $$$m$$$, that task can be done. Given that he must do $$$n$$$ tasks in order, where each task $$$i$$$ takes $$$t_i$$$ minutes to complete, determine exactly how many tasks Brian can finish before his first class starts!
The first line of the input contains $$$m (0 \le m \le 10^8)$$$, the number of minutes left until Brian's first class.
The next line of the input will contain $$$n (1 \le n \le 10^3)$$$, the number of tasks Brian needs to do.
The next $$$n$$$ lines of the input will each contain an integer $$$t_i (1 \le t_i \le 10^5)$$$, the amount of time it takes Brian to complete the $$$i^{th}$$$ task.
A single integer, the number of tasks Brian can fully complete before his first class starts. If Brian can only partially finish a task, that does not count.
5 4 1 2 3 4
2
0 4 1 2 3 4
0
10 4 1 2 3 4
4
The City of Austin is building a new dogpark and would like to know your thoughts on its design. Knowing the local geography, you hope that you and your doggo can see over all the surrounding hills. Thus, you want to help the City build the tallest possible dogpark.
The City has set aside a $$$L$$$ length plot of land for the dogpark. Each of the $$$L$$$ locations in the dogpark will have some integer height $$$h_i$$$. To allow for easy entry, the park must begin and end with height $$$0$$$. To allow for optimal play, the heights of adjacent portions of the dogpark cannot differ by more than $$$1$$$.
Given the length $$$L$$$ of the dogpark, please provide the maximum possible height of the new dogpark.
A single integer $$$1 \leq L \leq 10^5$$$, specifying the length of the dogpark.
A single integer indicating the height of the tallest possible location within the dogpark.
4
1
5
2
For $$$L = 4$$$, we could have a dogpark of heights $$$0, 0, 1, 0$$$, so maximum height $$$= 1$$$.
For $$$L = 5$$$, we could have a dogpark of heights $$$0, 1, 2, 1, 0$$$, so maximum height $$$= 2$$$.
George is building a massive pet store, so he can share his love of various animals with the rest of the world. However, he knows that certain pets are quite territorial and won't behave well if they don't have enough personal space.
Each pet will requires its own rectangular area of personal space. However, George isn't too skilled at building out rectangular pens, so he's instead decided to construct a circular pen for each pet that is guaranteed to fully contain the pet's required rectangular area. Note that it isn't sufficient to build a circular pen that has a greater area than the rectangle because the circular pen must contain the entire rectangle itself. Ideally, to cut down on costs, George wants to minimize the total area of circular pens built for each pet.
Given the $$$n$$$ pets at George's pet store and the rectangular areas that each pet requires, figure out the minimum total area required to build out the circular pens for each pet. Your answer will be judged correct if it is within $$$10^{-4}$$$ of the true solution.
The first line will consist of a single integer $$$n (1 \leq n \leq 10^5)$$$. The next $$$n$$$ lines will consist of two numbers $$$h_i$$$ and $$$w_i$$$ ($$$1 \leq h_i, w_i \leq 10^5$$$), which indicates that the $$$i$$$th pet requires a rectangular area of height $$$h_i$$$ and width $$$w_i$$$.
Output a single real number giving the total minimal area of the circular pens that will fully contain each pet's required rectangular area.
1 1 1
1.5707963267948968
2 2 4 4 2
31.415926535897935
For the first sample, George will construct a singular circular pen with radius $$$\frac{1}{\sqrt{2}}$$$, which gives the corresponding area.
Michaela and Mat are arguing about what kind of pet is cutest. Mat says that you can tell what pet is cutest simply by looking at how many people own a pet, so if more people own a type of pet, then more people will think that type of pet is cute. Michaela vehemently disagrees and wants to find an example that disproves Mat's claim
Given a list of how many people own a type of pet and how many people think a pet is cute, determine whether or not Michaela can find an example that proves Mat wrong, i.e. where less people own a pet but more people think it's cute.
For example, if 30 people own cats and 40 think cats are cute while 20 people own dogs but 50 think dogs are cute, it would be an example that disproves Mat's claim.
The first line is $$$1 \leq n \leq 10^5$$$, the number of lines representing types of pets that follow.
The next $$$n$$$ lines contain two integers, $$$a_i$$$ and $$$b_i$$$, $$$0 \leq a_i, b_i \leq 10^9$$$, where $$$a_i$$$ represents the number of people that own this type of pet and $$$b_i$$$ represents the number of people who think it is cute.
One line with "yes" if Michaela can prove Mat wrong, "no" if she cannot. (case insensitive)
3 1 2 2 3 3 1
yes
3 1 5 1 7 1 1
no
Betty owns a dog daycare service. Part of her advertised duties involves taking the dogs out on a walk. However, she only has $$$3$$$ leashes for her $$$5$$$ dogs. She knows from experience that if she takes out $$$2$$$ dogs who are friendly with each other and $$$1$$$ who neither of the other two like, then the dogs will be sad after the walk. The only way for the dogs to be happy is if all $$$3$$$ of the dogs like each other or if none of the dogs like each other (in that case, one dog won't feel left out). As Betty was thinking about how to make such a group, a friend of hers noted that with $$$6$$$ dogs, it is always possible to find a group of $$$3$$$ dogs who all like each other or all dislike each other. Given a list of $$$n$$$ pairs of dog friendships, see if it is possible for Betty to form a group of $$$3$$$ who will all be happy at the end of the walk.
Note: When it says all $$$3$$$ dogs like each other, it must mean that there is a dog friendship between each pair of dogs in the group of $$$3$$$ (i.e. if the group was A, B, C then there must be friendship between A and B, A and C, and B and C). Similar property must hold except there shouldn't be any pair-wise friendships in the group for all $$$3$$$ to dislike each other. Assume that if a friendship is not listed between two dogs, it means that the two dogs don't like each other.
The first line contains a single integer $$$n$$$ which is the number of dog friendships among the $$$5$$$ dogs ($$$1 \leq n \leq 10$$$).
The following $$$n$$$ lines will each contain two space-separated integers $$$a_{i}$$$ and $$$b_{i}$$$ which are two dogs that are friends (each dog is represented by a unique number between $$$1$$$ and $$$5$$$). You are guaranteed that $$$a_{i} \neq b_{i}$$$ and $$$1 \leq a_{i}, b_{i} \leq 5$$$. Also, a friendship between dog A and B is symmetrical (B is also friends with A) so you will never have a repeat/symmetrical friendship listed.
Print Happy Doggos! if such a group of $$$3$$$ exists or Sad Doggos... if no such group exists.
4 1 3 2 3 1 4 5 3
Happy Doggos!
5 1 2 2 3 3 4 4 5 5 1
Sad Doggos...
George is building a massive pet store, so he can share his love of various animals with the rest of the world. However, he knows that certain pets are quite territorial and won't behave well if they don't have enough personal space.
Each pet will requires its own rectangular area of personal space. To deal with this, George has enlisted a contractor to build out a large $$$\textbf{square}$$$ pen that contains a subdivided rectangular pen for each pet. Each pet's subdivided pen must touch the southern border of the overall square pen, so that George has easy access to each pet. Each pet's rectangular enclosure can be rotated to fit within the square as long as one edge of the rectangle manages to touch the southern border.
Ideally, to cut down on costs, George wants to minimize the total side length of the entire square pen, but still build the square pen large enough that each pet has enough personal space disjoint from any other pet's personal space.
Given the $$$n$$$ pets at George's pet store and the rectangular areas that each pet requires, figure out the minimum total side length required to build out the total square pen for each pet.
The first line will consist of a single integer $$$n (1 \leq n \leq 10^5)$$$. The next $$$n$$$ lines will consist of two numbers $$$h_i$$$ and $$$w_i$$$ ($$$1 \leq h_i, w_i \leq 10^9$$$), which indicates that the $$$i$$$th pet requires a rectangular area of height $$$h_i$$$ and width $$$w_i$$$.
Output a single integer giving the minimal side length of the overall square pen that will fully contain each pet's required rectangular area.
1 1 1
1
3 2 4 4 3 3 1
6
In the first sample, the first pet only needs a single square of personal space, so a 1x1 square will suffice.
In the second sample, by placing the edge with length 2 of the first pet's space, the edge with length 3 of the second pet's space, and the edge of length 1 of the third pet's space along the southern border, we can fit all pets within a 6x6 square. No smaller square will fit these three pets.
Two dog walkers, Aarvind and Bailey, are planning a Saturday afternoon walk at the local dog park! The dogs they are walking love specific areas in the park (i.e. places with special sticks or other dogs), and Aarvind and Bailey have taken the time to mark these spots on a map of the dog park. Specifically, Aarvind's dogs like the two spots marked with a, and Bailey's dogs like the two spots marked with b.
Aarvind and Bailey want to plot out paths for their respective walks, traveling from one of their dogs' favorite spots to the other before ending the walk. However, they don't want to do too much walking. They would also like to meet up somewhere in the middle of their walks to let all of the dogs play together! Given a map of the park, help Aarvind and Bailey plot two paths of minimum combined length that intersect in at least one spot in the park.
The first line of input contains two integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 500$$$), which give the number of rows and columns in the dog park map respectively.
$$$N$$$ lines follow, each containing $$$M$$$ characters denoting grid cells on the park map. A # character denotes a tree in the park that cannot be walked through. A . denotes a patch of grass that can readily be traversed. Then an a denotes a start or end location for Aarvind, and a b character denotes a start or end location for Bailey.
Note that at each step of their walks, Aarvind and Bailey can only move into an adjacent cell, where an adjacent cell is defined to be one either above, below, to the left, or to the right of the current cell on the map. Additionally, Aarvind and Bailey can always walk through map cells marked with a or b.
Following the $$$N$$$ lines containing the park map are four lines of input. The first two of these lines each contain two integers $$$a_r$$$ and $$$a_c$$$, giving the row and column location of an a character marked on the map. Likewise, the next two lines each contain $$$b_r$$$ and $$$b_c$$$ with the location a b character.
Print the minimum possible sum of the lengths of two paths—one for Aarvind connecting the a cells and another for Bailey connecting the b cells—such that the two paths intersect at at least one location in the park. If no such paths are possible, simply print the string IMPOSSIBLE.
12 9 ...#...#. #.####.## #b..####. ..###.... .....#..# ..#...### .....#.## .......a. ......#.# .#b.#.... ##.a.#.#. .#....#.. 7 7 10 3 2 1 9 2
17
6 8 .a.....# ....#.## .....#.b ..###... a..#b... ..#..### 0 1 4 0 2 7 4 4
IMPOSSIBLE
For the first sample case, the following paths result in the minimal sum of 17, where cells that are a part of the solution paths are marked with * and the intersection cell is marked with X:
...#...#.
#.####.##
#b..####.
.*###....
.*...#..#
.*#...###
.**..#.##
..X****a.
..**..#.#
.#b*#....
##.a.#.#.
.#....#..
Edison is a smart pupper but he's very particular about the amount of food he eats. He insists that the number of kibbles in his bowl must be an integer with exactly $$$n$$$ non-zero digits. However, Edison has even more rules for his food.
Edison has two favorite digits $$$x$$$ and $$$y$$$. He considers a number to be 'excellent' if its decimal representation consists of only $$$x$$$ and $$$y$$$ and the sum of all of its digits also only consists of $$$x$$$ and $$$y$$$ in its decimal representation. For example, if Edison's favorite digits are $$$1$$$ and $$$3$$$ then $$$111$$$ and $$$11333$$$ are excellent but $$$13$$$ and $$$31$$$ aren't.
Given Edison's favorite two digits $$$x$$$ and $$$y$$$ as well as his requirement for the number to be an excellent number with $$$n$$$ non-zero digits, tell Edison how many numbers satisfy his constraints. Note, this answer may be quite large so he will be happy if you give the answer modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.
The first and only line of input contains three space-separated integers, $$$x$$$, $$$y$$$, and $$$n$$$ where $$$x$$$ and $$$y$$$ are Edison's favorite two digits (it could be that $$$x = y$$$) and then $$$n$$$ is the length of the intended amount of food. It is true that $$$1 \leq x, y \leq 9$$$ and $$$1 \leq n \leq 10^{6}$$$.
A single integer representing the number of excellent numbers with exactly $$$n$$$ non-zero digits modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.
1 3 3
1
2 3 10
165
Katya loves rats, and she has many such pets that she takes care of. Rats are very social and intelligent creatures—not to mention they have beady eyes and stringy tails and the cutest little paws...
Katya has recently been training her rats to follow different scents and use scent trails to solve mazes. To train a rat, Katya will design a maze layout and then build it in her room using cardboard boxes for the barriers. Then she will mark a path from a start location to an exit location in the maze with a scent trail, using the specific scent that the rat was trained to recognize.
Now that Katya's rats have gotten pretty good at this task, she wants to run several of her rats through a maze at the same time, to see how their speeds compare and whether they will be distracted by the presence of other rats. However, she wants it to be easy enough for a particular rat to recognize its custom scent trail, so she will avoid marking any one section of the maze with more than one scent.
Help Katya mark paths for her rats in a maze that she designed! Given a grid map of the maze with # denoting a barrier, . denoting an open cell that can be traversed, and S and E denoting the starting and ending cells respectively, output the maximum number of paths from S to E which never overlap.
The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 500$$$), denoting the number of rows and columns in the grid to follow. The next $$$N$$$ lines each contain $$$M$$$ characters, representing cells in the rat maze.
Then the next line contains two integers $$$S_r$$$ and $$$S_c$$$, denoting the zero-indexed row and column indices respectively where the start cell is located, and likewise, the following line contains $$$E_r$$$ and $$$E_c$$$ with the location of the end cell.
Output the maximum number of paths from the start cell to the end cell that can be marked simultaneously in the maze as scent trails.
Note that for a rat be able to follow a scent from one cell to another, the two cells must be adjacent in that one is immediately above, below, to the left, or to the right of the other cell.
15 9 .#....... ......... ..E...#.. .#..#.... #..#..... ##.#..### ......... .#.#...#. ..#...... ......... ...#..... S..#...#. ....#.#.. #........ .....##.# 11 0 2 2
2
7 14 .............. #...#.....#.#. ..#...#....... ........#..... .#..S.......E. ...#.....#...# ......#.##.#.. 4 4 4 12
3
The doggos of UTPC (Ubiquitous Toy Poodle Committee) are preparing for a war with TAMU (Terrier Alliance of Mischievous Upstarts). Every war has rules, and both sides have agreed to settle individual battles by sending $$$K$$$ canine warriors, armed to the teeth with squeaky toys, to duke it out in the dog park. Squeaky toys can be categorized into one of $$$10^9$$$ types, labeled by integers from $$$1$$$ to $$$10^9$$$ (inclusive), and two squeaky toys of the same type are indistinguishable. Furthermore, every member of UTPC and TAMU owns exactly one squeaky toy weapon.
You are an analyst for UTPC, and have been tasked with considering all possibilities for assembling an army of $$$K$$$ soldiers with their respective squeaky toys. Upper-management believes that every one of the $$$N$$$ members of the organization is effective with their own squeaky toy, and that the difference in armies solely depends on the number of users of each squeaky toy used within it. For example, with $$$K=3$$$, army $$$A = (1, 1, 2)$$$, an army with two users of squeaky toy type $$$1$$$ and one user of squeaky toy type $$$2$$$, would be considered to be the same as army $$$B = (1, 2, 1)$$$. However, armies $$$C = (1, 2, 2)$$$ and $$$D = (1, 2, 3)$$$ would be different from both $$$A$$$ and $$$B$$$.
You quickly realize that the count of possible armies would exceed any canine computational power that you could ever muster, and dogmatically insist that the best estimate for this calculation is finding the number modulo $$$31051$$$. The Council of Poodles accepts your argument, but the task ahead is still not easy!
The first line of input contains two space-separated integers $$$N$$$ ($$$1 \leq N \leq 100000$$$) and $$$K$$$ ($$$1 \leq K \leq N$$$). The second line of input contains $$$N$$$ space-separated positive integers denoting the type of the $$$i$$$-th squeaky toy owned by a member of UTPC. Each of these positive integers is at most $$$10^9$$$ in value.
Output a single integer representing the number of possible distinct armies modulo $$$31051$$$ that the UTPC can field in battle.
4 2 1 2 4 4
4
4 1 2 3 5 7
4
The prime $$$31051$$$ was chosen because $$$WOOF$$$, when written as a sequence of numbers based on $$$1$$$-indexed positions in the alphabet, becomes $$$23-15-15-6$$$, and $$$23*15*15*6+1 = 31051$$$. :)