A group of men are traveling with supplies to Fort McGurry in the higher area of the Yukon Territory. After setting up camp for the night, they realize that they are surrounded by wolves. The travelers have a large number of tamed dogs, and they want to be alerted by any attempt by the wolf pack to attack.
The camp can be modeled as a rectangle consisting of $$$R \times C$$$ cells. Each cell is either empty, contains a person, a wolf, or a dog. People and dogs always stay in place, but wolves can roam freely around the camp, by repeatedly moving to the left, right, up or down to a neighboring cell. When a wolf enters a cell with a person, it attacks it. However, no wolf can enter a cell with a dog. Can you coordinate a placement of dogs in the camp in such a way that no wolf can reach any traveler? Note that a dog cannot be placed in a cell that a wolf starts in, and the number of dogs available can be assumed to be at least $$$R \times C$$$. No wolf can move outside the designated rectangle of cells.
The first line of input contains two integers, $$$R$$$ and $$$C$$$ ($$$1 \leq R, C \leq 50$$$), denoting the number of rows and the numbers of columns respectively.
Each of the following $$$R$$$ lines is a string consisting of exactly $$$C$$$ characters, representing one row of the camp. In this context, 'P' means a person, 'W' a wolf and '.' an empty cell.
Output a single line with the word "No" if a wolf can reach a person without traversing a cell with a dog in it for any setup, and "Yes" otherwise.
6 6 ..P... ..P.W. .P.... ..W... ...W.. ......
Yes
1 2 PW
No
Isaiah and Mina are camping and after a long foraging trip, they collected $$$n$$$ total pieces of firewood. However, they are each in a different camp-site and so they decide to place their stash in a central location. Additionally, Isaiah and Mina each have their own warming constants, denoted by $$$a$$$ and $$$b$$$ respectively. The warming constant is a fixed number such that the amount of firewood the person needs is equal to the greatest common divisor of the number of pieces of firewood left in the central stash and the person's warming constant.
Every night, Mina takes the amount of firewood she needs first and then Isaiah takes the quantity that he needs. Given this scenario, figure out the person who first does not have enough firewood to take from the stash (the number of pieces of firewood is strictly less than the amount that the person needs to take, note that for this problem we define $$$\gcd(0,x) = \gcd(x, 0) = x$$$).
The first and only line of input will contain three space-separated integers $$$n$$$, $$$a$$$, and $$$b$$$ such that $$$1 \leq n, a, b \leq 10^{4}$$$ where $$$n$$$ is the number of pieces of firewood in the stash at the start, $$$a$$$ is the warming constant for Isaiah, and $$$b$$$ is the warming constant for Mina.
If Isaiah will be the first one to not have enough firewood, output 0, otherwise output 1.
9 5 3
0
12 4 2
1
In the first sample, Mina will start and take $$$\gcd(9,3) = 3$$$ pieces, leaving $$$6$$$ in the stash. Then Isaiah will take $$$\gcd(6,5) = 1$$$ piece, leaving $$$5$$$ in the stash. Mina will then take $$$\gcd(5, 3) = 1$$$ piece, leaving $$$4$$$ in the stash. Isaiah will take $$$\gcd(4,5) = 1$$$ piece, leaving $$$3$$$ in the stash. Mina will take $$$\gcd(3,3) = 3$$$ pieces, leaving $$$0$$$ in the stash. Now, when Isaiah goes to take $$$\gcd(0, 5) = 5$$$ pieces, there will not be enough for him so you output 0.
After a local forest tour gone wrong, you and $$$n$$$ other survivors have been stranded in the wilderness. Due to your incredible leadership skills, you have taken command of the rest of the survivors and need to organize them in order to get the necessary supplies to survive.
There are $$$n$$$ different types of food that each of the $$$n$$$ survivors can collect. Each survivor can collect any of the types of food, but they each have different skill levels at collecting each type of food, which represent the amount of that food that they can collect.
You must assign each survivor to a single food type and ensure that your camp has a survivor assigned to each food type to maximize the value of the food you get. In this case, you and the survivors all pool together the collected food, so the value of the assignment is the sum of all the food collected by each survivor. How do you maximize this assignment of survivors?
The first line will consist of a single integer $$$n$$$ ($$$2 \leq n \leq 10$$$) giving the number of survivors. The next $$$n$$$ lines will each consist of $$$n$$$ integers where the $$$j$$$th integer on the $$$i$$$th line, $$$s_{ij}$$$ ($$$0 \leq s_{ij} \leq 10^5$$$), gives the skill point value for survivor $$$i$$$ when it is assigned food type $$$j$$$.
Output a single integer giving the total value of the optimal assignment of survivors to tasks.
2 3 4 0 2
5
For the sample, it is optimal to make the first survivor do the first task and the second survivor do the second task, which leads to a total value of $$$3 + 2 = 5$$$.
Justin the frog is hopping between lily pads. He starts at lily pad $$$0$$$, and there are $$$L + 1$$$ total lily pads. He can do one of two things:
- Jump forward $$$N$$$ lily pads
- Jump backward $$$M$$$ lily pads
Justin must land on a lily pad after every jump, or he will fall into the water. Today, Justin is hungry and he notices that there are $$$F$$$ flies on some lily pads. If Justin can make it to those lily pads somehow, he will be able to eat the flies. However, due to his restrictive movement, he may not be able to reach all lily pads. Help Justin determine how many flies he can reach!
The first line of the input will contain $$$N (1 \le N \le 100), M (1 \le M \le 100)$$$, and $$$L (1 \le L \le 10^4)$$$, which detail the number of pads $$$N$$$ that Justin can move forward in a jump, the number of pads $$$M$$$ that Justin can move backward in a jump, and the number of the very last lily pad.
The next line of the input will have a single integer $$$F$$$ $$$(1 \le F \le 100)$$$, the number of flies.
The next $$$F$$$ lines will each contain a single integer $$$f_i$$$ where $$$0 \le f_i \le L$$$, the location of the $$$i^{th}$$$ fly.
A single integer $$$f$$$, the number of flies that Justin can snack on. Note that this is the number of flies that Justin can reach, not the number of flies Justin can snack on in one trip.
4 2 100 4 1 2 3 4
2
Shannon and $$$6$$$ of her friends are planning an *extended* camping trip. They plan on packing rations in order to last them for the entirety of their trip. However, they don't know exactly how long they plan to remain camping so Shannon decides to concatenate a lot of randomly generated digits to make the number $$$s$$$ and pack $$$s$$$ rations.
However, she quickly realizes that $$$s$$$ isn't divisible evenly by $$$7$$$. Her friend group is highly competitive for food and refuse to split rations or allow one person to get more rations than another person. Thus, Shannon needs to pack a number that is perfectly divisible by $$$7$$$ and decides to simply rearrange the digits of $$$s$$$. Luckily, she finds that $$$s$$$ at least one of each of the following digits: 1, 6, 8, and 9. Help Shannon permute the digits of her number $$$s$$$ to figure out the number of rations to pack for the group's trip!
The first and only line will contain the positive number $$$s$$$ which does not have any leading zeros and contains at least one of each of the following digits: 1, 6, 8, and 9. It is also guaranteed that $$$1689 \leq s \leq 10^{10^6}$$$ ($$$s$$$ will have at least $$$4$$$ digits and at most $$$10^{6}$$$ digits).
Output the result of the permutation aka the number of rations that Shannon should bring so that it will be divisible by $$$7$$$. The number should not contain any leading zeros but it should still use the same number of each digit as $$$s$$$.
If it is not possible to permute the digits to create a number divisible by $$$7$$$, output $$$-1$$$.
1689
1869
8589157262
2255781689
This was supposed to be a fun, wilderness adventure. With an area map and the legendary Bear Grylls as your guide, even a trip deep into the jungle was set to be a casual test of your survival skills and nothing more. That was, until you woke up on the second night with Bear Grylls nowhere to be found.
You frantically remember what Bear told you about the importance of finding potable water and how long you can survive without it. With a conveniently packed TI-84 calculator, you scramble to write a program that can calculate your optimal surviving escape route, else you may fall victim to the ruthlessness of the jungle...
The first line of input contains two integers $$$K$$$ and $$$S$$$, where $$$1 \leq K \leq 10^3$$$ and the ratio $$$S/K \leq 100$$$. The value $$$K$$$ is the number of hours required to travel between two adjacent regions of the jungle, and adjacency is defined to be those regions immediately above/below or to the left/right of another map region. $$$S$$$ is the number of hours that you are able to survive after replenishing your supply of drinking water.
The next line of input contains another two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 500$$$) which denote the number of rows and columns respectively in the jungle grid map. $$$N$$$ lines follow, each containing $$$M$$$ characters that represent regions of space in the jungle. A # character represents an untraversable region, packed with thick brush and trees. A . character represents a traversable region, clear enough to be crossed. A $ character represents a traversable region that also contains drinking water to fully replenish your supply. Lastly, an @ represents your single starting location on the map, and an E character represents the single helicopter pick-up zone which is your exit point from the jungle.
Note, you are guaranteed that there will be fewer than $$$10^3$$$ regions containing drinking water (denoted $).
Print out the minimum number of hours required for you to successfully reach the helicopter pick-up zone and escape! If it is not possible for you to escape the jungle from your start location, output IMPOSSIBLE.
5 21 6 20 #$###.$.###...$.#### #.@..$...##.#.#..### #.#.####....$.##$### #.#.#....$#.##....E# #$..$...###.##.##### #####..$###.$..##...
150
1 5 5 15 ##$....##...#.# #..#.#.$.##.#.# #.##$.##...$... @...##...$#.##E ###...$####.###
IMPOSSIBLE
After a local forest tour gone wrong, you and $$$n$$$ other survivors have been stranded in the wilderness. Due to your incredible leadership skills, you have taken command of the rest of the survivors and need to organize them in order to get the necessary supplies to survive.
There are $$$n$$$ different types of food that each of the $$$n$$$ survivors can collect. Each survivor can collect any of the types of food, but they each have different skill levels at collecting each type of food, which represent the amount of that food that they can collect.
You must assign each survivor to a single food type and ensure that your camp has a survivor assigned to each food type to maximize the value of the food you get. In this case, the survivors take the food they collected for themselves but refuse to take any food above the minimum food collected by any other survivor to prevent jealousy from tearing apart the group, so the value of the assignment is the min of all the food collected by each survivor. How do you maximize this assignment of survivors?
The first line will consist of a single integer $$$n$$$ ($$$2 \leq n \leq 500$$$) giving the number of survivors. The next $$$n$$$ lines will each consist of $$$n$$$ integers where the $$$j$$$th integer on the $$$i$$$th line, $$$s_{ij}$$$ ($$$0 \leq s_{ij} \leq 10^5$$$), gives the skill point value for survivor $$$i$$$ when it is assigned food type $$$j$$$.
Output a single integer giving the total value of the optimal assignment of survivors to tasks.
3 3 2 3 2 1 1 1 2 3
2
One optimal assignment is to assign the first survivor to the second food type, the second survivor to the first food type, and the third survivor to the third food type, which gives a value of $$$2$$$.
Akhil and his students are going camping! While his students are all merrily preparing for the outing, Akhil is more focused on the safety of the students. As such, he wants to bring a few more adults along with him on the trip to make sure that the students will not be put in danger.
At the campsite, all suitable camping sites are at lattice points on the 2D coordinate grid. This is to ensure that the tents will be easy to identify, and it ensures that the distance between tents will not to be little. However, there are some lattice points on the grid that instead of a camping set, where a watchtower has been put in place. These watchtowers are particularly advanced. If two watchtowers are occupied by teachers, then they will both be alerted if a student crosses the line segment with the two watchtowers as endpoints. However, if there exists a watchtower between two watchtowers such that all 3 towers are perfectly colinear, then a teacher is needed at all 3 if the desire is to watch the entire segment.
Once night comes, Akhil wants to make sure that no student can wander off from their tent into the wilderness without any adult being alerted via a watchtower. Such locations are deemed "safe" if there is some way of occupying 3 or more watchtowers such that a student at that spot cannot wander off infinitely in some direction without alerting a watchtower. Given the locations of the watchtowers, Akhil wants to determine the maximum number of students that can go on this camping trip. A student can go if there is an available "safe" camping spot (that is not occupied by a watchtower). Help Akhil find the maximum number of students that can safely go on the camping trip and the minimum number of adults required to ensure that all "safe" spots are indeed guarded.
The first line will contain $$$n (1 \le n \le 10^5)$$$, the number of watchtowers. Note that every lattice point that is not a watchtower is a viable camping spot.
The next $$$n$$$ lines will each contain a pair of integers $$$x_i, y_i (0 \le x_i, y_i \le 10^9)$$$, denoting the location of the $$$i^{th}$$$ watchtower.
Output two lines of output, with the first being the maximum number of "safe" students, and the second being the minimum number of adults needed to accommodate this maximum amount of students.
7 0 3 2 2 2 6 4 0 5 4 6 7 8 3
29 5
8 0 0 0 1 0 2 2 2 2 1 2 0 1 0 1 2
1 8
Buck has settled into life as a pack wolf after answering the call of the wild. However, he is often required to defend his title as leader of the pack due to his domesticated past. All pack wolves are masters of mathematics, so it is only natural that they spar by asking for solutions to computational problems. The challenger asks Buck to count the number of whole numbers at most $$$N$$$ that contain $$$2^x$$$ as a substring. Even with the vast knowledge of combinatorial techniques, the sheer size of $$$N$$$ makes it difficult for our favorite St. Bernard–Scotch Collie mix to calculate the answer mentally. Can you help Buck live up to his reputation as "Ghost Dog" of the Northland by finding this result?
The input consists of one line of two space separated integers, $$$N$$$ ($$$0 \leq N \leq 9 \cdot 10^{18}$$$) and $$$x$$$ ($$$0 \leq x \leq 62$$$), which are described above.
A single integer representing the number of distinct whole numbers at most $$$N$$$ whose decimal form contains the digits of $$$2^x$$$ as a substring.
1000000 1
468559
1000000 5
49401