Fact or Fiction, some people consider 7 to be a lucky digit/number.
Given a number, determine how lucky the number is by printing one of four values:
- Print 0 if the number does not contain 7 and is not divisible by 7.
- Print 1 if the number does not contain 7 but is divisible by 7.
- Print 2 if the number does contain 7 but is not divisible by 7.
- Print 3 if the number does contain 7 and is divisible by 7.
There is only one input line; it contains an integer between $$$1$$$ and $$$10^9$$$, inclusive.
Print one of the four messages as described above.
25
0
42
1
170
2
777
3
1
0
70
3
The United Credit Finance (UCF) is running a simple scenario to see how many customers are happy with the company. UCF has one person (teller) serving the customers. Customers are numbered $$$1$$$ to $$$n$$$, and they arrive for service in sequential order, i.e., Customer 1 arrives first, then Customer 2, then Customer 3, etc. Also, no two customers arrive at the same time, i.e., Customer 2 will arrive later than Customer 1, Customer 3 will arrive later than Customer 2, etc. Customers are also processed in the order of arrival (i.e., not out of order).
As you might have noticed while waiting in a line, some customers get impatient and leave. Given the information about the UCF customers, you are to determine which customers are happy, i.e., they don't leave before being processed.
The first input line contains an integer, $$$n$$$ $$$(1 \le n \le 10^3)$$$, indicating how many different customers are arriving. Each of the next $$$n$$$ input lines contains the information about a customer as follows:
- customer number ($$$1, 2, 3,$$$ etc., in sequential order),
- arrival time (an integer between $$$1$$$ and $$$10^4$$$, inclusive),
- service time (an integer between $$$1$$$ and $$$10^4$$$, inclusive) indicating how long it will take the teller to process this customer (once the customer is at the teller),
- patience time (an integer between $$$1$$$ and $$$10^4$$$, inclusive) indicating how long the customer will wait in line before giving up and leaving, i.e., if the customer is not at the teller, the customer will leave. Note that if a customer leaves, the teller will not process them, i.e., the customer will not take the teller's time.
Print the happy customer numbers in sequential order (happy means they were processed, i.e., did not leave).
7 1 50 10 5 2 52 5 4 3 58 20 5 4 85 7 10 5 86 10 1 6 88 20 3 7 89 30 3
1 3 4 7
Explanation of Sample Input/Output:
- The teller is done with Customer 1 at time 60 (50 + 10). This means the teller can process the next customer at time 60.
- Customer 2 arrives at time 52. The patience time for this customer is 4 so, since they arrive at time 52, if processing them does not start by time 56 (52 + 4), they leave. The teller is done with Customer 1 at time 60 so Customer 2 leaves. Note that if a customer leaves, they will not take the teller's time.
- Since Customer 2 leaves, the teller can start Customer 3 at time 60 (this customer was willing to wait until time 63 to start being processed). The teller is done with Customer 3 at time 80 (60 + 20).
- The teller is done with Customer 4 at time 92 (85 + 7). Note that the teller doesn't have customers from time 80 (when the teller is done with Customer 3) to time 85 (when Customer 4 arrives).
- Customer 5 arrives at time 86 and expects to be processed starting at time 87, so they leave (the teller is done with Customer 4 at time 92).
- Customer 6 arrives at time 88 and expects to be processed starting at time 91, so they leave (the teller is done with Customer 4 at time 92).
- Customer 7 arrives at time 89 and expects to be processed starting at time 92. The teller is available at that time (teller is done with Customer 4 at time 92) so this customer is processed.
Snails have many enemies including snakes, turtles, and birds. So, snails need to communicate their travel paths using cryptography to avoid their routes being detected.
The encryption technique: The message will contain only letters. Let's assume the message length is L. We use the smallest odd integer $$$N$$$ such that $$$N \times N \ge L$$$. Then, an $$$N \times N$$$ table is used to encrypt the message as follows: Put the first letter of the message in the cell at the center of the table and then put the remaining letters in the table by moving in a circular way (snail like) around the center cell. For example, the table to the right shows the order for placing the letters from the message in a $$$7 \times 7$$$ table. So, from the center cell, we move up, then move right, then move down, then move left, then move up, etc.
Below are some sample encryptions. To help with the illustrations, when encrypting the message, if there are more cells in the table than there are letters in the message, we put the character '#' in the extra cells.
Given the size of the two-dimensional table to use and the original message, you are to encrypt the message (to help snails live longer lives).
The first input line contains an odd integer, $$$n$$$ $$$(1 \le n \le 19)$$$, indicating the table size to use. The second input line will provide the message to encrypt, a string of $$$1$$$ to $$$361$$$ ($$$19 \times 19$$$) letters (lowercase and uppercase). Assume that the message will fit in the table.
Print the encrypted message on one output line using the row-major order, i.e., print Row 1 followed by Row 2, followed by Row 3, etc. Remember to print a newline character after printing the last row. The output should not include '#' characters.
3 ABCDEFGH
BCHADGFE
5 ABCDEFGHIJKLMNOPQRSTUVW
JKLMIBCNWHADOVGFEPUTSRQ
The 2023 FIFA Women's World Cup was held during the summer. Several games ended in ties and penalty kicks had to be taken to determine the winner.
The professional soccer goal size (length) is 7.32m. The success rate of penalty kicks at the professional level is above $$$80\%$$$. If the goal length was much longer, can this success rate reach $$$100\%$$$?
To simplify the problem, we will assume that there is no concept of time or ball speed, so if the goalie's reach intersects the ball's travel path, the goalie will block the ball.
As illustrated in the picture below, we'll assume the goalie is at $$$(0,0)$$$ and the penalty taker (kicker) is at $$$(0,y)$$$; $$$y$$$ will be a positive integer.
The kicker will kick the ball towards the goal line (to the left or right of the goalie). We'll assume the ball will intersect the goal line at $$$(x,0)$$$; $$$x$$$ will be a non-zero integer.
The goalie will dive to the left or right (based on the direction of the ball). The goalie has a limited reach $$$r$$$; $$$r$$$ will be a positive integer.
The goalie will save the penalty if the point representing the ball (while travelling) is on the line representing the goalie's reach. The goalie can save the penalty (i.e., block the ball) on the $$$x$$$-axis as well.
The primary objective for the goalie is to save the penalty and the secondary objective is to dive as close to the $$$x$$$-axis as possible, i.e., the angle between the goalie's reach and the $$$x$$$-axis is as small as possible.
Given the kicker's position ($$$y$$$), intersection point of the ball with the goal line ($$$x$$$) and the goalie's reach ($$$r$$$), determine whether the goalie will save (block) the penalty kick.
There is only one input line; it provides three integers $$$y$$$, $$$x$$$ and $$$r$$$, as described above. Assume $$$1 \le y \le 10^3$$$, $$$-10^3 \le x \le 10^3$$$ (excluding zero), and $$$1 \le r \le 10^3$$$.
Print -1 if the goalie cannot save the penalty; otherwise print the minimum angle that the goalie needs to dive to block the ball. Answers within an absolute or relative error of $$$10^{-6}$$$ will be accepted.
10 100 2
-1
10 3 3
0
3 10 6
11.9151974458468181694570375839
20 -200 5
-1
20 -5 5
0
5 -20 8
23.2890180235694685961789218709
Some UCF students know that Arup loves collecting Pez dispensers. Pez dispensers dispense 12 candies in a fixed sequence. Arup is so discerning, that he can actually tell the difference between the taste of different Pez candies and values them differently.
Imagine a situation where he wants to eat exactly 7 Pez candies and his four dispensers have candies with the following values, each listed from top to bottom of the respective dispenser:
In this situation, if he wanted to maximize the total value of the 7 candies he eats, he should take 6 candies from the second Pez dispenser and 1 candy from the third dispenser, for a total value of 83. He is required to eat the candies in a specific order from each dispenser (from the top). In this particular situation, it's worth it to eat all of the candies with value 1 in the second stack in order to get to the candy worth 70. From there, the maximum remaining candy at the top of any of the dispensers makes the most sense to add.
Given the values of each of the candies in Arup's Pez dispensers as well as the number of candies he wants to eat, determine the maximum total value he will be able to obtain if he chooses his candies optimally.
The first input line contains two integers: $$$n$$$ $$$(1 \le n \le 1000)$$$, indicating the number of Pez dispensers Arup has, and $$$k$$$ $$$(1 \le k \le 12n)$$$, representing the number of candies Arup is willing to eat.
Each of the next $$$n$$$ input lines contains 12 integers (each integer between $$$1$$$ and $$$300$$$, inclusive), indicating the value of the candies in one of Arup's Pez dispensers. These values are listed from top to bottom of each Pez dispenser.
Print the maximum total value of the candies Arup could choose, if he chooses optimally.
4 7 3 6 8 2 2 5 6 1 2 3 1 4 4 1 1 1 1 70 4 1 5 3 2 3 5 3 2 6 6 2 3 1 6 2 3 2 1 4 3 8 4 9 2 1 6 5 4 1
83
1 6 20 30 40 15 1 14 2 2 2 2 2 2
120
Uncle Trapezoid has a piece of land in the shape of a trapezoid that he would like to split into four pieces to bequeath to his four nieces. He is fairly lazy, so all he will do is pick a particular point inside of the trapezoid, and then the four pieces will be the four triangles formed by this point and each of the four sides of the trapezoid as illustrated below:
Naturally, Uncle Trapezoid wants to be as fair as possible and minimize the difference in area between the smallest triangle and the largest triangle.
Given the length of both bases and the height of a trapezoid, determine the smallest possible difference in area between the smallest and largest triangles formed by choosing any point inside of the trapezoid to form the four triangles (one with each side of the trapezoid).
Note: The bases must be parallel with a distance equal to the height between the two lines the bases define. However, where the bases are located relative to each other does not affect the answer to this problem.
There is only one input line; it contains three integers: $$$b_1$$$ $$$(1 \le b_1 \le 10^4)$$$, $$$b_2$$$ $$$(1 \le b_2 \lt b_1)$$$, and $$$h$$$ $$$(1 \le h \le 10^4)$$$, representing the lengths of the long base, short base and height of the trapezoid, respectively.
Print the smallest possible difference in area between the smallest and largest triangles that the trapezoid could be partitioned into. Any answer within an absolute or relative tolerance of $$$10^{-6}$$$ will be accepted.
20 12 16
8.0
20 18 10
0.2631578947368496
Orlando is quickly growing and new houses have to be built. However, people don't like being too close to each other these days. Universal Condos Forever (UCF) is building some housing units. The land they have is parceled out in grid squares as shown below:
In the example above, there are 5 rows and 4 columns. The owners of the condos, denoted by triangles, do NOT want other condos in ANY of the potentially 8 adjacent (up, down, left, right, diagonal) grid squares. For example, the above layout is a valid arrangement of five condos.
Given the number of rows and columns in the lot that UCF is building condo units, determine the number of different sets of placements of condos they could choose. Two sets are different if in one set a condo is built on a specific square but in the other set no condo is on that same exact square, or vice versa. Since the number of different arrangements could be very large, find the value modulo $$$10^9 + 7$$$.
Note: trivially, building no condos is always a valid arrangement.
There is only one input line; it contains two integers: $$$r$$$ $$$(1 \le r \le 10)$$$ and $$$c$$$ $$$(1 \le c \le 10^3)$$$, representing the number of rows and columns (respectively) for UCF's lot.
Print the number of valid arrangements of condos, modulo $$$10^9 + 7$$$.
2 3
11
5 4
1213
Explanation of the first Sample Input/Output:
There is $$$1$$$ way of placing zero condos.
There are $$$6$$$ ways of placing one condo.
There are $$$4$$$ ways of placing two condos.
We cannot place three or more condos.
So, the total number of valid arrangements is $$$1 + 6 + 4 = 11$$$.
In the wild west, they take their Computer Science very seriously. Smokin' Joe is widely known for his skills, and outlaws come from across the land to challenge him in a good ol' fashioned sortin' duel. The way that outlaws duel in the wild west, of course, is trying to be the one who makes the last move to sort an array of integers.
One fateful day, Smokin' Joe's nemesis, an infamous character known as The Outlaw, came to town and challenged Joe to a duel. The rules of the duel are as follows: the outlaw will spin the chambers, and a random permutation of length n will fall out (a permutation of length $$$n$$$ is an array of the integers from $$$1$$$ to $$$n$$$ in any order). Smokin' Joe and The Outlaw will take turns swapping two elements in this permutation, until the permutation is sorted in increasing order. The winner is the player who makes the last swap. Once an element is in its final position (i.e., value $$$k$$$ is at position $$$k$$$), that element cannot be moved for the rest of the game; otherwise, there are no restrictions on which two elements can be swapped.
Both Smokin' Joe and The Outlaw will always play perfectly, i.e., they play to win and not necessarily to sort the list as quickly as possible. Can you predict who will win?
Given a permutation, predict the winner of the game, where players take turns swapping elements, and an element cannot move once it's in its final sorted position. The winner is the person who makes the final move to sort the array. Note that Smokin' Joe goes first, i.e., makes the first move.
The input will consist of two lines. The first input line contains an integer, $$$n$$$ $$$(1 \le n \le 10^6)$$$, the length of the permutation. The second input line contains $$$n$$$ distinct integers, the permutation. It is guaranteed that it will be a permutation of the integers from $$$1$$$ to $$$n$$$, and the permutation is not already sorted.
If Smokin' Joe wins, print "Smokin Joe!" (note that the apostrophe of Smokin' is omitted in the output since apostrophe may come out as different ASCII characters on different machines and may cause "format errors" in the output). If The Outlaw wins, print "Oh No!".
3 1 3 2
Smokin Joe!
4 4 3 2 1
Oh No!
A greedy drake in a long-forgotten castle stores their treasures. The drake is obsessed with certain types of treasures. It has been rumored that although the types are few, the volume is plenty. You know that the treasures would be worth a lot in the black market, which is why you waited with your carrying pack for the time when the drake leaves to pillage a nearby town.
When you enter the drake's abode, you notice near countless treasures and you are afraid that your pack may not be big enough. You are not planning on a return trip so your goal will be to get the most value out of this one and only opportunity.
Given the number of treasure types (each with some multiplicity, worth, and volume), and some maximum volume that can be carried, determine the most worth you can carry within the given volume limit.
The first input line contains two integers: $$$n$$$ $$$(1 \le n \le 20)$$$, indicating the number of treasure types and $$$V$$$ $$$(1 \le V \le 10^{15})$$$, indicating the maximum volume you can carry. Each of the next $$$n$$$ input lines contains three integers: $$$m$$$ $$$(1 \le m \le 10^{15})$$$, indicating the multiplicity of the item, $$$w$$$ $$$(1 \le w \le 10^3)$$$, indicating the worth of each of this item, and $$$v$$$ $$$(1 \le v \le 10^3)$$$, representing the volume of each of this item.
Print the maximum worth you can carry.
3 100 20 1 1 12 5 4 10 11 10
117
1 1000000000000 1000000000000 1000 1
1000000000000000
The UCF Programming Team Coaches, besides being the most experienced coaching group in the world, are also conscious of the forests in our planet disappearing. The coaches have taken the initiative of developing a 1-D forest. They have planted a tree seed at each integer location in the range of $$$1$$$ and $$$10^5$$$. These $$$10^5$$$ trees are currently of height $$$0$$$ (zero) but the coaches have recruited three forest rangers (Alice, Bob, and Cutz) to maintain this 1-D forest. The forest rangers are really like fairies once you see their power!
Alice loves to watch the trees grow. She was gifted a magical watering pot that can make a tree grow K units, where $$$K$$$ is the amount of water she pours on the tree. Additionally, each tree that is $$$D$$$ $$$(D \lt K)$$$ distance away from the spot will grow $$$K-D$$$ units.
Bob loves to climb the trees in the forest. Bob has a special tape that can measure the height of any tree.
Cutz likes to cut all the trees in the forest to a specific height, i.e., taller trees are cut to all have a specific height (note that shorter trees are not affected/cut). More specifically, Cutz decides on a threshold (maximum height) and then all the trees taller than this threshold will be cut to have this new height. Cutz likes decreasing sequences (!) so they always cut at a height lower than the previous one they used (with the only exception being the first cut).
For a given list of commands that Alice, Bob, and Cutz performed, determine the height Bob measured in each of his commands. Remember that all the trees start at height $$$0$$$.
Input will begin with a single integer, $$$t$$$ $$$(1 \le t \le 2 \times 10^5)$$$, representing the number of transactions.
Each of the following $$$t$$$ input lines will represent a single transaction in one of the following three forms:
- $$$A$$$ $$$L$$$ $$$K$$$
- $$$B$$$ $$$L$$$
- $$$C$$$ $$$H$$$
For the transaction beginning with $$$A$$$, Alice will water the tree at position $$$L$$$ $$$(1 \le L \le 10^5)$$$ with $$$K$$$ $$$(1 \le K \le 10^6)$$$ units of water, i.e., certain trees grow in height as described above.
For the transaction beginning with $$$B$$$, Bob will measure the tree at position $$$L$$$ $$$(1 \le L \le 10^5)$$$.
For the transaction beginning with $$$C$$$, Cutz will cut all the trees in the forest to height $$$H$$$ $$$(1 \le H \le 10^8)$$$.
There is no output required for transactions beginning with $$$A$$$ or $$$C$$$. For each transaction beginning with $$$B$$$, print the height of the tree that Bob measured.
6 A 7 5 B 6 C 4 A 5 4 B 6 B 7
4 7 6
7 A 10 8 B 10 C 6 A 10 8 C 4 B 3 B 5
8 2 4
In an unenchanted forest there is a mundane rabbit that steals from your garden and you end up chasing after it. The rabbit constantly moves its burrow, so knowing your options for catching the bugger is not easy. The forest is a collection of clearings joined by trails, each trail connecting exactly two clearings. You know, when you chase the rabbit, where it starts and ends its journey. You are solely interested in knowing clearing(s) you can set up a snare to ensure that you trap the rabbit. Note that setting up a snare in rabbit's starting or ending clearings will definitely catch the rabbit. (We trust that you don't plan on injuring the rabbit, only taking back your vegetables.)
It will always be the case that the rabbit can reach any clearing from any other clearing, i.e., the rabbit can travel from any clearing to any other clearing.
Given the description of the forest, determine the number of possible clearings where you are guaranteed to be able to trap the rabbit.
The first input line contains two integers: $$$C$$$ $$$(1 \le C \le 10^5)$$$, representing the number of clearings, and $$$T$$$ $$$(C-1 \le T \le 2 \times 10^5)$$$, representing the number of trails.
Each of the following $$$T$$$ input lines contains two integers $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le C; a \ne b)$$$, representing that clearings $$$a$$$ and $$$b$$$ are connected by a trail. No pair of clearings are connected directly by more than one trail.
After the initial information for all the clearings, the input will have a set of transactions (operations) to be processed. This section of the input starts with an integer, $$$t$$$ $$$(1 \le t \le 10^5)$$$, indicating the number of transactions. Each of the next t input lines contains a transaction to be processed with the following format:
- Trap Transaction: This input line provides two valid clearings $$$s$$$ and $$$d$$$. The bunny is moving from $$$s$$$ to $$$d$$$ and you need to determine the number of clearings a trap could be placed such that the bunny can be caught. Note that only a single trap must be placed in a single clearing to catch the rabbit, and we are interested in knowing how many such clearings exist. Note also that $$$s$$$ and $$$d$$$ are two of the answers, i.e., the result will be at least $$$2$$$.
For each Trap transaction, print the number of locations that you can place a trap to guarantee the bunny will be caught as it travels from its starting clearing to the ending clearing.
9 10 1 2 1 3 2 4 3 4 3 5 3 6 5 6 4 7 7 8 7 9 10 1 2 8 6 1 9 9 8 4 2 6 4 1 6 9 7 4 5 3 4
2 5 4 3 2 3 3 2 3 2
4 4 1 2 2 3 3 4 4 2 3 1 2 1 4 2 3
2 3 2
Jesse Mary just purchased an exquisite framed painting of her favorite creatures: Cows! She wants to hang this painting, but she's misplaced her hammer. She does, however, have a wall full of pins, and an extremely excessive amount of rope (string). Being a pragmatic topologist, she wants to save herself some work in the future. She would like to tie the painting to the wall such that the painting hangs, but she only has to remove one pin for the painting to fall. Furthermore, she would like this to be true of any pin.
The above arrangement (the path created by the rope, starting with the picture, going around the pins and ending at the picture) is such that the painting will hang. But, if either pin is removed, the painting will fall on the ground, i.e., if we remove either pin, the rope won't be around the other pin and the picture will fall on the ground.
Formally, if we model her wall as a 2-D plane, she would like to find a cyclic (the start and end are the same point) path which is not homotopic to a point, but upon removal of any one of the pins, becomes so. "Homotopic" means topologically equivalent under deformation. In the above image, the path from the painting, along the black rope (string), and back to the painting (the painting closes the loop) is such a path: The path is non-homotopic to a point, meaning the painting hangs. However, if you remove either pin, the path becomes homotopic to a point, which means the painting will fall!
Given a set of points on the 2-D plane, output a cyclic path which is not homotopic to a point, but when any one of the points is removed, becomes homotopic to a point. You can ignore all self- interactions the rope has (i.e., there will be no knots).
The first input line contains an integer, $$$n$$$ $$$(2 ≤ n ≤ 100)$$$, indicating the number of pins. Each of the next $$$n$$$ input lines contains two integers $$$x_i$$$, $$$y_i$$$ $$$(1 \le x_i, y_i \le 10^4)$$$, the coordinates of the pins. To make it easier to construct a path without hitting pins, no two pins will have the same $$$x$$$- or $$$y$$$-coordinate.
The first line of your output should contain a single integer, $$$p$$$ $$$(3 \le p \le 32,000)$$$, the number of points in your path. Then, $$$p$$$ lines should follow, the $$$i^{th}$$$ of which should have two integers $$$x_i$$$, $$$y_i$$$ $$$(0 \le x_i, y_i \le 10^5)$$$, the $$$x$$$- and $$$y$$$-coordinates of the points on your path. The first and last point of your path should be the same, and your path must not contain any of the pins. If there are multiple correct answers, you may print any one of them.
2 3 3 10 10
10 1 1 5 13 13 11 5 3 0 5 3 1 11 10 5 15 4 1 1 1