Welcome to UTPC! We are excited for a great semester of contests ahead and hope that you enjoy today's contest. To start with (and as a way to test and get used to the Codeforces submission system), just read the input in and output it unchanged.
The input will contain a single string $$$s$$$ of length $$$n$$$ where $$$1 \leq n \leq 100$$$.
Output the same string as the input.
Welcome to UTPC!
Welcome to UTPC!
Abhilash got a cat, but he hasn't decided what to name it yet. He's been deciding between various names, and is struggling to pick one that would be perfect for his pet. As such, he decides to come up with a scoring system.
Every letter in the name is given a value, with "a" having a value of 1, "b" having a value of 2, and so on and so forth, until finally we have "z" having a value of 26. Abhilash has decided that he will take the name with the largest product of the values of its letters, mod $$$10^9 + 7$$$, which is a very large prime. Taking something mod $$$10^9 + 7$$$ means that you need to only output the remainder when dividing by $$$10^9 + 7$$$. However, as he is very poor at math, he wants you to help him write a program to determine the scores of names!
The input will be one line of lower case characters with no spaces of length $$$n (1 \le n \le 10^3)$$$.
A single integer, the score of the given name.
catluri
2449440
For the sample input, we have "c" as the 3rd letter of the alphabet, "a" as the 1st, and so on and so forth. Multiplying these all together, we get $$$3 \cdot 1 \cdot 20 \cdot 12 \cdot 21 \cdot 18 \cdot 9 \pmod{10^9 + 7} = 2449440$$$.
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.#.#.
.#....#..