Check out Python input/output or C++ input/output or Java input/output for reading in the input numbers.
A good contest must have a good contest name. Busy Beaver has many ideas for how to name his next great programming contest; can you tell him which ones are the best?
A word is a string (of length at least one) containing only uppercase letters. A good contest name is a word that can be written in the form $$$ABB$$$ where $$$A$$$ and $$$B$$$ are words.
You're given $$$Q$$$ strings of uppercase letters. For $$$i=1 \ldots Q$$$, output "YES" if the $$$i^\text{th}$$$ string is a good contest name, and "NO" otherwise.
The first line contains $$$Q$$$ ($$$1 \le Q \le 100$$$).
The next $$$Q$$$ lines contain one string each. Each string consists of between $$$3$$$ and $$$5000$$$ uppercase letters.
It is guaranteed that the sum of lengths of all strings is at most $$$5000$$$.
Output $$$Q$$$ lines, the answer for each string. The output is case insensitive, so "YES", "yes", and "Yes", for example, will be treated identically.
5MITITMITIITAAAKLDSJLAJJLAJJABCABC
YES NO YES YES NO
Explanation:
MITIT can be written as [M][IT][IT].
MITIIT cannot be written as $$$ABB$$$ for any words $$$A$$$ and $$$B$$$.
AAA can be written as [A][A][A].
KLDSJLAJJLAJJ can be written as [KLDSJ][LAJJ][LAJJ] or [KLDSJLAJJLA][J][J].
ABCABC cannot be written as $$$ABB$$$ for any words $$$A$$$ and $$$B$$$ ([][ABC][ABC] doesn't count because the first word cannot be empty).
Busy Beaver is taking his first exam at the Maximally Intensive Testing Institute of Technology (MITIT). The exam is long and time is limited, so he needs to plan a strategy.
The exam is $$$M$$$ minutes long, with $$$N$$$ problems. The $$$i^\text{th}$$$ problem has a positive integer difficulty value, $$$d_i$$$. A problem with difficulty $$$d$$$ takes $$$d$$$ minutes to do, and is worth $$$d+1$$$ points. There is no partial credit for completing part of a problem.
Also, if Busy Beaver turns in the exam $$$X$$$ minutes before time is up ($$$0 \le X \le M$$$), he will receive $$$X$$$ bonus points added to his score.
What is the maximum possible score Busy Beaver could get?
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$N$$$, $$$M$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le M \le 10^9$$$).
The second line of each test case contains $$$N$$$ space-separated integers $$$d_1, \dots, d_N$$$ ($$$1 \le d_i \le 10^9$$$).
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, output a single integer: the maximum possible score.
- ($$$15$$$ points) There is sufficient time to finish all of the problems.
- ($$$15$$$ points) All the problems have the same difficulty.
- ($$$70$$$ points) No additional constraints.
44 71 2 3 44 4515 10 5 105 1020 30 40 50 605 108 4 13 5 7
10 49 10 12
In the first test case, Busy Beaver can do the problems with difficulties $$$1$$$, $$$2$$$, and $$$4$$$, in $$$7$$$ minutes. Busy Beaver will get $$$2 + 3 + 5 = 10$$$ points this way (no bonus points, because there is no extra time remaining).
In the second test case, Busy Beaver can do all four problems with 5 minutes to spare, and get a total of $$$49$$$ points: $$$16 + 11 + 6 + 11 = 44$$$ points from the problems, plus $$$5$$$ bonus points.
In the third test case, Busy Beaver cannot do any one of the problems within the given time! So the best thing to do is to submit a blank exam right after the timer starts, which gives $$$10$$$ bonus points.
In the fourth test case, Busy Beaver can do the two problems with difficulties $$$4$$$ and $$$5$$$, in $$$9$$$ minutes; Busy Beaver will receive $$$1$$$ bonus point since there is $$$1$$$ minute remaining, and get $$$5 + 6 + 1 = 12$$$ points in total.
Busy Beaver really likes composite numbers. One day he saw a number on a blackboard and wanted to make it composite without changing it too much.
You are given a positive integer $$$N$$$, whose digits are all $$$1$$$'s and $$$2$$$'s.
Delete at most one digit from $$$N$$$, possibly leaving $$$\boldsymbol{N}$$$ the same as before, so that $$$N$$$ becomes composite. You cannot reorder digits you do not delete. To prove that your new number is composite, you also need to output a nontrivial factor.
A positive integer $$$d$$$ is a nontrivial factor of a positive integer $$$n$$$ if $$$n$$$ is a multiple of $$$d$$$, $$$d \neq 1$$$, and $$$d \neq n$$$.
The first line contains a positive integer $$$T$$$ ($$$1 \le T \le 200$$$), the number of test cases.
Each test case contains one line: a positive integer $$$N$$$ ($$$10^3 \lt N \lt 10^{200}$$$) consisting of only the digits $$$1$$$ and $$$2$$$.
For each test case, output a line with two numbers separated by a space.
First output a positive integer $$$M$$$, such that either $$$M = N$$$ or $$$M$$$ is missing one of the digits of $$$N$$$. Then output a positive integer $$$K$$$ such that $$$M$$$ is a multiple of $$$K$$$ and $$$1 \lt K \lt M$$$.
It can be shown that a solution always exists under the problem's constraints. If there are multiple possible values for $$$M$$$ and/or $$$K$$$, any valid combination will be accepted.
- ($$$10$$$ points) $$$N$$$'s digits are all $$$2$$$'s.
- ($$$10$$$ points) $$$N$$$'s digits are all $$$1$$$'s.
- ($$$10$$$ points) $$$N \lt 10^4$$$.
- ($$$20$$$ points) $$$N \lt 10^8$$$.
- ($$$50$$$ points) No other constraints.
4 121212 11121 12211 212221112112211
121212 10101 1121 59 2211 67 21221112112211 4933994911
In the first sample test case, $$$121212$$$ is already composite, so we don't have to delete any digit, and we can output one of its nontrivial factors. $$$10101$$$ is one possibility, since $$$121212 = 12 \cdot 10101$$$.
In the second sample, we can delete the first $$$1$$$ to turn the number into $$$1121$$$, which is composite since $$$1121 = 19 \cdot 59$$$, and outputting either $$$19$$$ or $$$59$$$ would work. We could also have left $$$11121$$$ as it is; if we do that, some of the possible answers are 11121 33 and 11121 337.
In the third sample, $$$12211$$$ is prime, so we must delete some digit. Some other possible solutions are 1211 7 and 1221 37.
Busy Beaver is exploring the underground MIT campus. There are $$$N$$$ buildings labelled $$$1,\dots,N$$$ and $$$M$$$ tunnels labelled $$$1,\dots,M$$$ connecting certain pairs of buildings. The $$$i^\text{th}$$$ tunnel connects building $$$a_i$$$ and $$$b_i$$$. In order to enter it, you must first pay $$$c_i$$$ coins. However, after walking through the tunnel and appreciating its art, you are rewarded with $$$r_i$$$ coins.
Busy Beaver lives in building $$$1$$$ and will attend his lecture in building $$$N$$$. What's the minimum number of coins he needs to bring with him to be able to reach building $$$N$$$?
Keep in mind the following:
- Tunnels can be traversed in any direction, any number of times. Each time you go through, the fee is incurred and the reward is collected.
- Busy Beaver can use the coins he is rewarded with to pay future entrance fees.
- There may be more than one tunnel connecting two buildings.
- You can never have a negative number of coins.
The first line contains two space separated integers, $$$N$$$ and $$$M$$$ ($$$2\le N \le 10^5$$$, $$$1\le M \le 2\cdot 10^5$$$).
The next $$$M$$$ lines describe the tunnels. The $$$i^\text{th}$$$ of them consists of four space separated integers, $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$r_i$$$ ($$$1 \le a_i,b_i \le N$$$, $$$a_i \ne b_i$$$, $$$0 \le c_i,r_i \le 10^9$$$).
It is guaranteed that building $$$N$$$ is reachable from building $$$1$$$ starting with a finite number of coins.
Output one line with the answer.
- ($$$20$$$ points) There are $$$N-1$$$ tunnels: one tunnel connecting building $$$i$$$ to building $$$i+1$$$ for all $$$1 \le i \lt N$$$.
- ($$$20$$$ points) $$$r_i = 0$$$ for all $$$1 \le i \le M$$$.
- ($$$20$$$ points) $$$c_i = r_i$$$ for all $$$1 \le i \le M$$$.
- ($$$20$$$ points) $$$c_i \ge r_i$$$ for all $$$1 \le i \le M$$$.
- ($$$20$$$ points) No additional constraints.
3 31 2 2 12 3 3 01 3 5 0
4
4 31 2 3 12 3 1 23 4 2 4
3
3 41 2 4 31 2 4 62 1 5 42 3 10 9
4
Sample Explanation 1
If Busy Beaver starts with $$$4$$$ coins, he can first go through the tunnel from building $$$1$$$ to building $$$2$$$, paying $$$2$$$ coins and getting $$$1$$$ coin in return (so he has $$$4-2+1=3$$$ coins when he arrives at building $$$2$$$), then go through the tunnel from building $$$2$$$ to building $$$3$$$ using his $$$3$$$ coins.
Sample Explanation 2
If Busy Beaver starts with $$$3$$$ coins, he can first go through the tunnel from building $$$1$$$ to building $$$2$$$, with $$$1$$$ coin when he arrives. Then he can go to building $$$3$$$, after which he has $$$2$$$ coins. Finally, he can reach building $$$4$$$ by paying $$$2$$$ coins and getting $$$4$$$ coins when he arrives.
Sample Explanation 3
Busy Beaver can start in building $$$1$$$ with $$$4$$$ coins, traverse through tunnel $$$2$$$ $$$3$$$ times, enter tunnel $$$4$$$ with $$$10$$$ coins, and arrive at building $$$3$$$ with $$$9$$$ coins. It can be shown that Busy Beaver cannot reach building $$$3$$$ starting with fewer than $$$4$$$ coins.
It's the finals week of Busy Beaver's senior year, and he just remembered about the list of must-do activities to complete before graduating he received during freshman orientation.
You are given an array of $$$N$$$ numbers $$$a_1, \ldots, a_N$$$, where $$$a_i$$$ represents the joy of completing the $$$i^\text{th}$$$ activity.
Due to his limited time at MIT, he has decided to only complete a contiguous subsegment of these activities. Additionally, to make the most out of it, the subsegment must contain at least two activities.
While procrastinating when preparing for his finals, he came up with a sophisticated way of scoring a subsegment. The score of the subsegment from index $$$l$$$ to $$$r$$$ is the minimum XOR of two distinct activities. Formally, the subsegment from index $$$l$$$ to $$$r$$$ has a score of $$$\min\limits_{l \leq i \lt j \leq r} a_i \oplus a_j$$$.
Busy Beaver's favorite number is $$$K$$$, so he would like to calculate the number of subsegments with score $$$K$$$. Can you help him?
The first line contains two integers $$$N$$$, $$$K$$$ ($$$2 \le N \le 10^5$$$, $$$0 \le K \lt 2^{30}$$$).
The second line contains $$$N$$$ space-separated integers $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \lt 2^{30}$$$).
Output a single integer: the number of contiguous subsegments of size at least two with score $$$K$$$.
- ($$$15$$$ points) $$$N \leq 5000$$$.
- ($$$10$$$ points) $$$K = 0$$$.
- ($$$25$$$ points) Array $$$a$$$ is sorted in non-decreasing order ($$$a_{1} \leq \ldots \leq a_{N}$$$).
- ($$$50$$$ points) No additional constraints.
5 21 3 1 4 5
3
There are three subsegments that should be counted:
- $$$l = 1, r = 2$$$.
- $$$l = 2, r = 3$$$.
- $$$l = 2, r = 4$$$.
In programming contests, beavers solve problems in order, from first to last. Revaebs, on the other hand, are a special type of rodent that solve problems in reverse order, from last to first.
$$$N$$$ beavers and $$$N$$$ revaebs will compete against each other in the upcoming programming contest! The contest consists of $$$N$$$ problems, the $$$k^{\text{th}}$$$ problem having an integer point value $$$p_k$$$ between $$$l_k$$$ and $$$r_k$$$, inclusive. A contestant's score is the sum of the point values of the problems they solve.
On contest day, it is known that the $$$i^{\text{th}}$$$ beaver solved the first $$$i$$$ problems, and the $$$j^{\text{th}}$$$ revaeb solved the last $$$j$$$ problems. Additionally, the only pair of contestants with the same score are the two that solved all problems, the $$$N^{\text{th}}$$$ beaver and the $$$N^{\text{th}}$$$ revaeb. Given this information, count the number of possible assignments of points values to the problems in the contest. Since this number might be large, output its remainder when divided by $$$10^9 + 7$$$.
The first line contains $$$N$$$ ($$$1 \leq N \leq 50$$$), the number of problems in the contest.
$$$N$$$ lines follow. The $$$k^{\text{th}}$$$ of these lines contains two space-separated integers, $$$l_k$$$ and $$$r_k$$$ ($$$1 \le l_k \le r_k \le 2000$$$).
Output one line containing the answer: the number of sequences of point values modulo $$$10^9+7$$$.
- ($$$10$$$ points) $$$N \leq 8$$$ and $$$r_k \leq 8$$$ for all $$$k$$$.
- ($$$30$$$ points) $$$l_k = 1$$$ for all $$$k$$$ and there exists a fixed $$$R$$$ such that $$$r_k = R$$$ for all $$$k$$$.
- ($$$30$$$ points) $$$r_k \leq 100$$$ for all $$$k$$$.
- ($$$30$$$ points) No additional constraints.
41 12 23 310 10
1
11 2000
2000
41 21 21 21 2
2
51 32 41 41 23 3
18
61 51 51 51 51 51 5
5120
Sample Explanation 1
The point values of the problems can only be $$$1, 2, 3, 10$$$. Using these point values, the scores of the beavers are $$$1, 3, 6, 16$$$ respectively and the scores of the revaebs are $$$10, 13, 15, 16$$$ respectively. All of these are different other than the score of $$$16$$$ attained by the $$$4^{\text{th}}$$$ beaver and revaeb, so this one sequence is valid, making the answer $$$1$$$.
Sample Explanation 2
This sample satisfies the constraints for the second subtask.
Sample Explanation 3
This sample satisfies the constraints for the second subtask.
The only valid sequences of point values are $$$1, 2, 2, 2$$$ and $$$2, 2, 2, 1$$$, making the answer $$$2$$$.
Sample Explanation 5
This sample satisfies the constraints for the second subtask.