Trick E. Dingo is trying, as usual, to catch his nemesis the Street Sprinter. His past attempts using magnets, traps and explosives have failed miserably, so he’s catching his breath to gather observational data and learn more about how fast Street Sprinter is.
Trick E. Dingo and Street Sprinter both inhabit a single straight west-east road with a particularly famous rock on it known affectionately as The Origin. Positions on this straight road are measured numerically according to the distance from The Origin, and using negative numbers for positions west of The Origin and positive numbers for positions east of The Origin.
The observations by Trick E. Dingo each contain two numbers: a time, and the value of Street Sprinter’s position on the road at that time. Given this information, what speed must Street Sprinter must be capable of?
The first line contains a number \(2\le N \le 100\ 000\), the number of observations that follow. The next \(N\) lines each contain an integer \(0 \le T \le 1\ 000\ 000\ 000\) indicating the time, in seconds, of when a measurement was made, and an integer \(-1\ 000\ 000\ 000 \le X \le 1\ 000\ 000\ 000\) indicating the position, in metres, of the Street Sprinter at that time. No two lines will have the same value of \(T\).
For 7 of the 15 available marks, \(N \le 1000\).
Output a single number \(X\), such that we can conclude that Street Sprinter’s speed was at least \(X\) metres/second at some point in time, and such that \(X\) is as large as possible. If the correct answer is \(C\), the grader will view \(X\) as correct if \(|X-C|/C < 10^{-5}\).
3
0 100
20 50
10 1207.0
Since the Street Sprinter ran from position 100 to position 120 between time 0 and time 10, we know its speed must have been at least \(2\) at some point in time: if it was always less than \(2\), then the distance of 20 could not be covered in 10 seconds. Likewise, the speed must have been at least 7 in order to travel between position 120 and 50 in 10 seconds.
5
20 -5
0 -17
10 31
5 -3
30 116.8
You have to determine if it is possible to escape from a room. The room is an \(M\)-by-\(N\) grid with each position (cell) containing a positive integer. The rows are numbered \(1,2,\ldots,M\) and the columns are numbered \(1,2,\ldots,N\). We use \((r,c)\) to refer to the cell in row \(r\) and column \(c\).
You start in the top-left corner at \((1,1)\) and exit from the bottom-right corner at \((M,N)\). If you are in a cell containing the value \(x\), then you can jump to any cell \((a,b)\) satisfying \(a \times b = x\). For example, if you are in a cell containing a \(6\), you can jump to cell \((2,3)\).
Note that from a cell containing a \(6\), there are up to four cells you can jump to: \((2,3)\), \((3,2)\), \((1,6)\), or \((6,1)\). If the room is a \(5\)-by-\(6\) grid, there isn’t a row \(6\) so only the first three jumps would be possible.
The first line of the input will be an integer \(M\) \((1 \leq M \leq 1000)\). The second line of the input will be an integer \(N\) \((1 \leq N \leq 1000)\). The remaining input gives the positive integers in the cells of the room with \(M\) rows and \(N\) columns. It consists of \(M\) lines where each line contains \(N\) positive integers, each less than or equal to \(1\,000\,000\), separated by single spaces.
For 1 of the 15 available marks, \(M=2\) and \(N=2\).
For an additional 2 of the 15 available marks, \(M=1\).
For an additional 4 of the 15 available marks, all of the integers in the cells will be unique.
For an additional 4 of the 15 available marks, \(M\leq 200\) and \(N\leq 200\).
Output yes if it is possible to escape from
the room. Otherwise, output no.
3
4
3 10 8 14
1 11 12 12
6 2 3 9yes
Starting in the cell at \((1,1)\) which contains a \(3\), one possibility is to jump to the cell at \((1,3)\). This cell contains an \(8\) so from it, you could jump to the cell at \((2,4)\). This brings you to a cell containing \(12\) from which you can jump to the exit at \((3,4)\). Note that another way to escape is to jump from the starting cell to the cell at \((3,1)\) to the cell at \((2,3)\) to the exit.
The online grader begins by testing submissions using the sample input. All other tests are skipped if the sample test is not passed. If you are only attempting the first three subtasks (the first 7 marks), then you might want to handle the specific values of the sample input as a special case.
For the final subtask (worth 2 marks), if you are using Java, then Scanner will probably take too long to read in the large amount of data. A much faster alternative is BufferedReader.
You’re given a string \(N\), called the needle, and a string \(H\), called the haystack, both of which contain only lowercase letters “a"..“z".
Write a program to count the number of distinct permutations of \(N\) which appear as a substring of \(H\) at least once. Note that \(N\) can have anywhere between 1 and \(|N|!\) distinct permutations in total – for example, the string “aab" has 3 distinct permutations (“aab", “aba", and “baa").
The first line contains \(N\) \((1 \le |N| \le 200\ 000)\), the needle string.
The second line contains \(H\) \((1 \le |H| \le 200\ 000)\), the haystack string.
For 3 of the 15 available marks, \(|N| \le 8\) and \(|H| \le 200\).
For an additional 2 of the 15 available marks, \(|N| \le 200\) and \(|H| \le 200\).
For an additional 2 of the 15 available marks, \(|N| \le 2000\) and \(|H| \le 2000\).
Output consists of one integer, the number of distinct permutations of \(N\) which appear as a substring of \(H\).
aab
abacabaa2
The permutations “aba" and “baa" each appear as substrings of \(H\) (the former appears twice), while the permutation “aab" does not appear.
There are \(N\) people sitting at a
circular table for a long session of negotiations. Each person belongs
to one of the three groups: A,
B, or C. A group is
happy if all of its members are sitting contiguously in a block
of consecutive seats. You would like to make all groups happy by some
sequence of swap operations. In each swap operation, two people
exchange seats with each other. What is the minimum number of swaps
required to make all groups happy?
The input consists of a single line containing \(N\) \((1\le N\le
1\:000\:000)\) characters, where each character is
A, B, or
C. The \(i\)-th character denotes the group of the
person initially sitting at the \(i\)-th seat at the table, where seats are
numbered in clockwise order.
For 4 of the 15 available marks, the input has no
C characters and \(N\le 5\:000\).
For an additional 4 of the 15 available marks, the input has no
C characters.
For an additional 4 of the 15 available marks, \(N\le 5\:000\).
Output a single integer, the minimum possible number of swaps.
BABCBCACCA
2
In one possible sequence, the first swap results in the seating layout
AABCBCBCCA. After the second swap, the layout
is AABBBCCCCA.
On their way to the contest grounds, Josh, his coach, and his \(N-2\) teammates decide to stop at a burger joint that offers \(M\) distinct burger menu items. After ordering their favourite burgers, the team members line up, with the coach in the first position and Josh last, to pick up their burgers. Unfortunately, the coach forgot what he ordered. He picks a burger at random and walks away. The other team members, in sequence, pick up their favourite burger if available, or a random remaining burger if there are no more of their favourite burger. What is the probability that Josh, being last in line, will get to eat his favourite burger?
The first line contains the number \(N\) \((3\leq N\leq 1~000~000)\), the total number of people and burgers. The next line contains \(N\) numbers, the \(i\)-th being \(b_i\) \((1\leq b_i\leq M\leq 500~000)\), denoting the item number of the \(i\)-th person’s favourite burger. The first person in line is the coach, and the \(N\)-th person is Josh.
For 4 of the 15 available marks, \(N\leq 100~000\) and \(M\leq 1000\).
For an additional 5 of the 15 available marks, \(M\leq 5000\).
Output a single number \(P\), the probability that Josh will get to eat his favourite burger, \(b_N\). If the correct answer is \(C\), the grader will view \(P\) correct if \(|P-C|<10^{-6}\).
3
1 2 30.5
The coach randomly chooses between the three burgers. With probability \(1/3\), he chooses his favourite burger (burger 1), and Josh gets to eat his favourite burger (burger 3). With probability \(1/3\), he chooses Josh’s favourite burger, and Josh fails to eat his favourite burger. With probability \(1/3\), he chooses the second person’s burger, there is a \(1/2\) chance that the second person chooses Josh’s burger, denying Josh the pleasure of eating his favourite burger.
7
1 2 3 1 1 2 30.57142857