Consider a string containing lowercase letters only. We call the string odd if every letter in the string appears an odd number of times. Similarly, we call the string even if every letter in the string appears an even number of times.
Given a string, determine if it is odd or even.
There is only one input line; it contains a string of lowercase letters only. The string will contain $$$1$$$ to $$$60$$$ letters (inclusive).
Print $$$0$$$ (zero) if the string is even, $$$1$$$ (one) if the string is odd, and $$$0/1$$$ (zero and one with a slash in between) if it is neither.
geekkeeg
0
funnyn
1
zztop
0/1
The Fibonacci sequence is defined as follows:
$$$F_0 = 0$$$
$$$F_1 = 1$$$
$$$F_n = F_{n-1} + F_{n-2}$$$ for $$$n \ge 2$$$
The numbers in this sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... The Fibonacci sequence has many applications including Mathematics, Computer Science, Nature, Economics, Art, and Music.
The Fiborooji sequence is a simplified version of the Fibonacci sequence. The Fiborooji sequence starts with two single-digit, non-negative numbers (at least one of the two numbers being non-zero). Each subsequent number is the sum of its preceding two numbers (like the Fibonacci sequence) but the numbers always stay single digit. This is done by keeping only the rightmost digit if the sum of the preceding two numbers end up having two digits. For example, if we have 8 and 7, the sum will be 15 but the next number will be 5 and not 15. As another example, if we have 4 and 6, the sum will be 10 but the next number will be 0 and not 10. Here is the Fiborooji sequence if we start with 2 and 1: 2, 1, 3, 4, 7, 1, 8, 9, 7, 6, ...
Applications of the Fiborooji sequence are being studied. One observation (discovery!) is that, regardless of the first two numbers (single digit) you start with, these two numbers will be repeated after a while which means the sequence will loop through the same numbers.
Given the first two single-digit numbers, find the length of the sequence when the starting two numbers repeat (i.e., reappear consecutively).
There is only one input line; it contains two single-digit, non-negative numbers, at least one of the two numbers being non-zero.
Print the length of the sequence when the starting two numbers repeat.
3 4
14
0 6
22
1 0
62
5 5
5
Explanation of the first Sample Input/Output:
The sequence will be 3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2, 1, 3, 4, which has a length of 14. Note that we started with "3 4" and, when "3 4" is repeated (reappear consecutively), the sequence has 14 elements.
In soccer, a win is worth 3 points, draw (tie) is worth 1 point, and loss is worth zero points. Soccer standing tables show the following info for each team: number of matches played (MP), number of wins (W), number of draws (D), number of losses (L), and total number of points (Pts). For example, the entry:
| USA | 11 | 5 | 4 | 2 | 19 |
Indicates USA has played 11 matches, won 5 of them, drew 4 matches and lost 2, for a total number of points of 19 (5*3 + 4*1).
Even though the info is complete and helpful, some publications/websites list the numbers in different orders, e.g., the number of losses may be listed before the number of draws. And, if the columns are not labeled as to what they represent, that causes confusion.
Given five integers representing the entry for a soccer team, print these numbers in the order of MP-W-D-L-Pts.
There is only one input line: it contains five integers, each between $$$0$$$ and $$$300$$$, inclusive. Assume that the input represents a valid entry, e.g., MP = W + D + L. Also assume that the input will not be all zeros, i.e., some games have been played.
Print the numbers in the order of MP-W-D-L-Pts. Assume that there will be exactly one valid answer.
19 11 2 4 5
11 5 4 2 19
2 2 6 20 10
10 6 2 2 20
0 0 1 1 0
1 0 0 1 0
Consider a city where each building is a rectangle with its base on the positive x-axis, its two walls parallel to the positive y-axis, and its roof parallel to x-axis. The walls of two buildings can touch each other, i.e., the buildings can be right next to each other. The buildings do not, however, have any area in common, i.e., no two buildings intersect/overlap.
Lulu (our beloved caterpillar) lives at coordinates $$$(0,0)$$$ and works at coordinates $$$(100,0)$$$. Every morning, Lulu crawls from home to office. Without any buildings, this is a distance of 100 but, unfortunately, the buildings force Lulu to crawl up and down of the building walls and they add to the distance Lulu has to travel. Note that Lulu starts at home, ends at the office, and is always crawling on $$$x$$$-axis, side of a wall going up (parallel to $$$y$$$-axis), top of a building (parallel to $$$x$$$-axis), or side of a wall coming down (parallel to $$$y$$$-axis).
Given the description of all the buildings, compute the total distance travelled by Lulu.
The first input line contains an integer, $$$n$$$ $$$(1 ≤ n ≤ 50)$$$, indicating the number of buildings. Each of the next $$$n$$$ input lines describes a building. A building is described by three integers: $$$s$$$ $$$(1 ≤ s ≤ 98)$$$, indicating the lower-left corner of the building, $$$w$$$ $$$(1 ≤ w ≤ 98)$$$, indicating the width of the building, and $$$h$$$ $$$(1 ≤ h ≤ 100)$$$, indicating the height of the building. Assume $$$s + w ≤ 99$$$, i.e., no building will end beyond $$$(99,0)$$$.
Print the total distance travelled by Lulu.
2 40 3 7 60 10 12
138
2 43 10 12 40 3 7
124
3 40 3 7 43 10 12 53 20 8
124
3 70 20 8 40 3 7 43 10 12
140
4 12 2 10 14 4 20 18 6 15 24 8 25
160
UCF has some very large classes such as COT 3100 (Introduction to Discrete Mathematics). Unfortunately, some students don't learn well in this environment. Luckily, UCF has so many knowledgeable students (referred to as TAs for the rest of this problem) that classes can be split up into smaller "tutorial" groups led by TAs, where students are more likely to achieve their potential.
In order for a tutorial group to be successful, the knowledge level of students within that group has to be relatively close to one another. More specifically, the difference between the minimum and maximum knowledge levels of students in a tutorial group can't exceed a given value k. In addition, for a tutorial group to be successful, it cannot have more than s students, for a given value s. (Of course, each group must have at least one student!) Finally, it must be possible to order the tutorial groups as $$$T_1, T_2, ..., T_m$$$, such that for any integer $$$i$$$, $$$1 ≤ i \lt m$$$, the maximum knowledge level of a student in tutorial $$$T_i$$$ is strictly lower than the minimum knowledge level of a student in tutorial $$$T_{i+1}$$$. Since TAs are so plentiful and knowledgeable, as many tutorial groups as desired can be formed.
As an example, consider a class where the students have knowledge levels 10, 6, 5, 9 and 12, such that the difference between the minimum and maximum levels of students in a tutorial can't be greater than 5 and there can be no more than 3 students in a group. For this example, we can split the class into tutorial groups in the following 13 ways:
Given all of these restrictions, your COT 3100 instructor (Dr. Travis Meade) would like to know how many ways the tutorials can be formed.
Given the knowledge level of each student in a class, the maximum difference between knowledge levels allowed in a tutorial group and the maximum number of students in a tutorial group, calculate the number of different ways to form tutorial groups. Since this number could be quite large, report it modulo $$$10^9 + 7$$$.
The first input line contains three space separated integers: $$$n$$$ $$$(1 ≤ n ≤ 10,000)$$$, indicating the number of students in the class, $$$k$$$ $$$(1 ≤ k ≤ 10^9)$$$, indicating the maximum difference between the minimum and maximum knowledge levels of students in a single tutorial, and $$$s$$$ $$$(1 ≤ s ≤ 100)$$$, indicating the maximum number of students allowed in a tutorial.
The following input line contains $$$n$$$ space separated integers. The $$$i^{th}$$$ of these integers is $$$a_i$$$ $$$(1 ≤ a_i ≤ 10^9)$$$, indicating the knowledge level of the $$$i^{th}$$$ student. Assume that all the knowledge levels are distinct, i.e., no duplicates.
Print the number of different ways to form tutorial groups, modulo $$$10^9 + 7$$$. Note that two ways of forming tutorial groups are different if there is a set (tutorial group) in one but not in the other.
6 2 5 3 6 7 12 15 16
4
7 10 7 2 3 4 6 7 8 9
64
5 5 3 10 6 5 9 12
13
Your friend, Mikey, has had issues recently; every week he gets food poisoning. Mikey is pretty sure that the food poisoning is from exactly one restaurant; he doesn't know which one though. Mikey wants to devise a strategy to find out. He wants to find out as quickly as possible (least number of weeks).
Mikey is willing to eat at a subset of his usual restaurants each week to find the bad restaurant (the subset can be as small or as large as needed). However, Mikey doesn't want to get food poisoning too many times, so he wants to find the bad restaurant while getting poisoned at most p times.
Note that if Mikey eats at a subset of restaurants in a given week and gets food poisoning, then the bad restaurant is in that subset; if he doesn't get food poisoning, then the bad restaurant is not in that subset. Note also that the subset of restaurants for different weeks do not have to be the same size.
Given the number of restaurants and the maximum allowable number of times to get food poisoning, determine (in the worst case) the least number of weeks needed to find out which restaurant is giving Mikey food poisoning.
There is only one input line; it contains two integers: $$$n$$$ $$$(1 ≤ n ≤ 100,000)$$$, indicating the number of restaurants, and $$$p$$$ $$$(1 ≤ p ≤ 10,000)$$$, indicating the maximum number of times Mikey is willing to get food poisoning.
Print the least number of weeks Mikey will need to eat before definitively determining which restaurant is giving him food poisoning, given an optimum strategy, but worst luck. Note that there will always be an answer.
8 1
7
7 2
3
Explanation of the First Sample Input/Output:
Mikey can eat in one restaurant each week; that will tell him if that restaurant is causing the food poisoning. After at most 7 weeks, he will know the bad restaurant since there are only 8 restaurants.
You are riding a toboggan on the straight line which can be modeled by the positive $$$x$$$-axis. You start at $$$x = 0$$$ and must get a boost to get started. Since there is friction, after that initial boost, eventually you would slow to a stop. Luckily, there are several positions along the positive $$$x$$$-axis where you will receive another boost! As long as you can make it to the next boosting position, you'll be able to finish the ride.
Of course, not only do you want to finish the ride, you also want to finish it within some time limit. Luckily, you are allowed to manipulate the boosts you receive. Unfortunately, you must set all boosts to the exact same value. Specifically, you must pick some constant, $$$c$$$, and then $$$c$$$ meters/second will be added to your velocity instantaneously, as soon as you arrive at each boost point.
If you start at a position with an initial velocity of $$$v$$$ meters/second, without any more boosts, you will travel for $$$v$$$ seconds exactly, losing a velocity of $$$1$$$ meter/second every second. At the end of the $$$v$$$ seconds, you will be stationary and will have traveled a distance of $$$\frac{v^2}{2}$$$ meters.
If you start at a position with an initial velocity of $$$v$$$ and travel for $$$t$$$ seconds, where $$$t \lt v$$$, then you will travel a distance of $$$t(v - \frac{t}{2})$$$ meters.
Here is an example of a possible toboggan ride:
Boost value $$$= 10$$$ m/s
Boost locations: $$$x = 0, 32, 110$$$
End of Ride Location: $$$x = 238$$$
Starting at $$$x = 0$$$ and traveling for $$$4$$$ seconds, we go a distance of $$$4(10 - 4/2) = 32$$$ m, arriving at the second boost point with a velocity of $$$6$$$ m/s (since we lose $$$1$$$ m of velocity each second). The boost at $$$x = 32$$$ m changes our velocity from $$$6$$$ m/s to $$$16$$$ m/s.
Next, we travel for $$$6$$$ seconds and go a distance of $$$6(16 - 6/2) = 78$$$ m, arriving at $$$x = 32$$$ m $$$+ 78$$$ m $$$= 110$$$ m, where we get our final boost. At this point in time, our velocity is $$$16$$$ m/s - $$$6$$$ m/s = 10 m/s.
We receive the final boost at $$$x = 110$$$ m, which changes our velocity from $$$10$$$ m/s to $$$20$$$ m/s. We travel another $$$8$$$ seconds and go a distance of $$$8(20 - 8/2) = 128$$$ to finish the ride at $$$x = 238$$$ m. Thus, in order to finish the ride in $$$4 + 6 + 8 = 18$$$ seconds, we must set our boost to at least $$$10$$$ m/s.
Given the length of the toboggan ride (in meters), the locations where a boost will be provided, and an amount of time to finish the ride (in seconds), determine the least amount of boost in meters/second necessary to finish the ride by the desired goal time.
The first input line contains three space separated integers: $$$L$$$ $$$(1 ≤ L ≤ 10^9)$$$, indicating the length of the toboggan ride in meters, $$$n$$$ $$$(1 ≤ n ≤ 100)$$$, indicating the number of boosts, and $$$t$$$ $$$(1 ≤ t ≤ 10^9)$$$, indicating the amount of time in seconds to complete the ride.
The second input line contains $$$n$$$ space separated distinct integers $$$b_1, b_2, b_3, ..., b_n$$$ $$$(0 = b_1 \lt b_2 \lt b_3 \lt ... \lt b_n \lt L)$$$, representing the locations where the $$$n$$$ boosts occur. Note that the first value in this list is zero ($$$0$$$).
Print a single floating-point number representing the minimum boost necessary to finish the ride in the desired amount of time. Any answer with an absolute or relative error of $$$10^{-4}$$$ will be accepted.
238 3 18 0 32 110
10.0
1000 5 20 0 200 315 816 900
27.829407683424986
You are working on several discord bots in one larger server. Each bot has a channel that it "listens" to (in non-technical terms, a bot is in a channel and receives all the messages sent to that channel). When the channel the bot listens to gets a message, the bot will send the same message to a number of other channels (dependent on the bot), causing bots in those channels to receive the message and send the same message to other channels.
Note that all the bots in a channel receive a message sent to the channel and all the bots in the channel will forward the message to their receiving channels.
You have the list of bots, and now you're curious if there is a channel such that if you post a message inside of it, all the other channels will have at least one copy of the message. For example, in the configuration illustrated in the picture, if we post a message inside the channel containing bot $$$b_1$$$, all the other channels will have (receive) at least one copy of the message.
Since there may be several such channels, you wonder how many are there?
Given the description of the server (number of channels and bot descriptions), determine the number of channels that can allow for a message to be sent to all the other channels.
The first input line contains two integers: $$$c$$$ $$$(1 ≤ c ≤ 100,000)$$$, indicating the number of channels in the server, and $$$b$$$ $$$(1 ≤ b ≤ 100,000)$$$, indicating the number of bots in the server.
Each of the next b input lines starts with an integer, $$$l_i$$$ $$$(1 ≤ l_i ≤ c)$$$, indicating the channel the $$$i^{th}$$$ bot is listening to (i.e., the channel the bot is in), and $$$m_i$$$ $$$(1 ≤ m_i ≤ c)$$$ indicating the number of channels the ith bot will send the message to. The line will contain $$$m_i$$$ more integers, $$$a_1, a_2, ... a_{l_i}$$$ $$$(1 ≤ a_j ≤ c)$$$, indicating the channels to which the $$$i^{th}$$$ bot will forward its messages to.
It is guaranteed that the total number of receiving channels in the input will not exceed $$$200,000$$$.
Print the number of channels that can be used to send a message to all the other channels.
4 4 1 1 2 2 2 3 4 3 2 3 4 2 1 2
1
5 4 1 5 1 2 3 4 5 2 4 3 1 4 2 3 3 1 2 3 4 2 1 2
4
Explanation of the First Sample Input/Output:
This data set corresponds to the configuration illustrated in the above picture.
There are 4 channels and 4 bots.
Bot 1 is in Channel 1 and forwards messages to Channel 2.
Bot 2 is in Channel 2 and forwards messages to Channels 3 and 4.
Bot 3 is in Channel 3 and forwards messages to Channels 3 and 4.
Bot 4 is in Channel 2 and forwards messages to Channel 2.
Messages posted in Channel 1 will get to all the other channels. This is the only such channel.
A subsequence of a given sequence of integers is a subset of the values in the sequence in the same order. A $$$k$$$-gap subsequence of a sequence of integers is a subsequence such that consecutive elements in the subsequence differ by at least $$$k$$$. For example, the sequence
3, 12, 8, 4, 2, 5, 1, 9, 8, 6, 5, 1, 7
has a $$$4$$$-gap subsequence of $$$3, 12, 8, 4, 9, 5, 1$$$ and $$$7$$$ (highlighted in bold above) since
$$$|3 - 12|$$$, $$$|12 - 8|$$$, $$$|8 - 4|$$$, $$$|4 - 9|$$$, $$$|9 - 5|$$$, $$$|5 - 1|$$$ and $$$|1 - 7|$$$ are all $$$4$$$ or greater.
Given a sequence and a value of $$$k$$$, determine the length of the longest $$$k$$$-gap subsequence.
The first input line contains two space separated integers: $$$n$$$ $$$(1 ≤ n ≤ 300,000)$$$, indicating the length of the sequence, and $$$k$$$ $$$(1 ≤ k ≤ 10^9)$$$, indicating the value of $$$k$$$ for the input case. The following input line contains n space separated integers. The $$$i^{th}$$$ of these integers is $$$a_i$$$ $$$(1 ≤ a_i ≤ 10^9)$$$, the $$$i^{th}$$$ value of the input sequence.
Print the length of the longest $$$k$$$-gap subsequence of the input sequence.
10 2 1 2 3 2 1 3 1 3 5 6
7
5 12 3 7 14 20 32
3
13 4 3 12 8 4 2 5 1 9 8 6 5 1 7
8
UCF has been continuously placing high in various university rankings and, as such, more students would like to attend UCF. To provide the best education environment, new buildings are added to the campus master plan and, as such, we see construction at various sites.
For the purposes of this problem, treat UCF's campus as a grid with Cartesian Coordinates. Each location is a lattice point and one can travel one unit north, south, east, or west from a lattice point to the adjacent lattice points. There is construction at some lattice points and these can't be crossed when traveling between locations.
The Manhattan distance between any two locations $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$. When traveling between two locations, you only allow yourself to travel the Manhattan distance between the two locations; this implies that each step should get you closer to the destination. For example, if the destination is to the northwest of the starting location (i.e., you are traveling in the northwest direction), the only steps you allow yourself to take are moving one unit north or one unit west (the only exception is when the constructions force you to "go around").
You'd like to know the number of different ways you can make several journeys, assuming that you're only willing to travel the Manhattan distance between the locations and are avoiding all intersections that are under construction. Since this number could be quite large, calculate it modulo $$$10^9 + 7$$$.
Given a list of locations that are under construction, as well as several trips denoted by pairs of ordered pairs of locations, determine the number of ways to make each of those trips, avoiding any construction intersections while traveling the Manhattan distance between the locations.
The first input line contains an integer, $$$n$$$ $$$(0 ≤ n ≤ 10)$$$, representing the number of locations under construction. Each of the next n input lines contains a pair of space separated integers, $$$x$$$ $$$(0 ≤ x ≤ 500,000)$$$ and $$$y$$$ $$$(0 ≤ y ≤ 500,000)$$$, indicating that the location (x, y) is under construction. Assume that all construction locations are distinct, i.e., no duplicates.
The next input line contains an integer, $$$t$$$ $$$(1 ≤ t ≤ 10000)$$$, representing the number of trips you plan on taking on campus. Each of the following t input lines contains four space separated integers: $$$x_1, y_1, x_2, y_2$$$ $$$(0 ≤ x_1, y_1, x_2, y_2 ≤ 500,000)$$$, representing a trip to evaluate from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$. It is guaranteed that neither the starting nor ending point of the trip will be one of the construction locations, and the starting and ending locations will be distinct as well. Assume that all the trips will have a Manhattan distance greater than $$$0$$$.
For each trip to evaluate, print a single line with the number of ways the trip can be made while avoiding construction locations and traveling only the Manhattan distance between the two locations, modulo $$$10^9 + 7$$$. Two paths for making a trip are different if they differ in a particular step, e.g., NN, NW, WW, WN are all different.
3 2 4 4 2 5 1 2 0 0 4 4 3 2 3 100
40 1
2 1 1 2 2 2 0 0 3 3 3 7 7 5
4 15
Ali is playing a board game by himself. The board's track consists of $$$N$$$ locations (cells, spots) laid out in a circle, i.e., the board cell $$$N$$$ is followed by the board cell $$$1$$$. At every step in the game, Ali rolls a die with k sides and moves his piece forward (clockwise) as many cells (spots) as it is indicated by the die. The die's sides have the value $$$1, 2, 3, ..., k$$$ (each occurring exactly once), and each side is equally likely to come up.
Ali starts his piece at location $$$1$$$, and when Ali moves his piece past location $$$N$$$, Ali's piece continues its movement to locations $$$1, 2,$$$ etc. (again, the board is circular).
There are several spots on the board that are instant win cells, and there are several spots on the board that are instant loss cells. Reaching either one of these spots ends the game immediately. Any spot that is not an instant win or an instant loss allows the game to continue.
Ali wants to know the probability that he will end up winning. Since Ali is very precise, Ali wants to know the fraction of winning as $$$\frac{p}{q}$$$. Since p and q can be quite large, compute the answer as $$$p(q^{-1})$$$ mod $$$10007$$$ instead, where $$$q^{-1}$$$ denotes the multiplicative inverse of $$$q$$$ modulo $$$10,007$$$.
Given the layout of the board and the die used, determine the probability of winning.
The first input line contains four integers: $$$n$$$ $$$(1 ≤ n ≤ 50)$$$, indicating the number of spots on the board, $$$d$$$ $$$(1 ≤ d ≤ 120)$$$, indicating the number of sides on the die, $$$w$$$ $$$(0 ≤ w \lt n)$$$, indicating the number of winning spots on the board, and $$$l$$$ $$$(0 ≤ l \lt n-w)$$$, indicating the number of losing spots on the board.
Each of the next $$$w$$$ input lines contains an integer (between $$$2$$$ and $$$n$$$, inclusive) indicating a winning location. Each of the next $$$l$$$ input lines contains an integer (between $$$2$$$ and $$$n$$$, inclusive) indicating a losing location.
Assume that all the winning locations are distinct, all the losing locations are distinct, no location will be both a winning and losing spot, and location $$$1$$$ will not be winning or losing.
Print the integral probability of winning $$$\frac{p}{q}$$$ as $$$p(q^{-1})$$$ mod $$$10007$$$, where $$$q^{-1}$$$ denotes the multiplicative inverse of $$$q$$$ modulo $$$10,007$$$.
4 6 1 1 2 4
8578
5 2 1 0 2
1
The answer to the first case is $$$\frac{4}{7}$$$.
Math Refresher (Definition of Multiplicative Inverse):
Another name for Reciprocal.
What you multiply by a number to get $$$1$$$.
Example: $$$8 × (\frac{1}{8}) = 1$$$
In other words: when we multiply a number by its "Multiplicative Inverse", we get $$$1$$$.
But not when the number is $$$0$$$ because $$$\frac{1}{0}$$$ is undefined!