April Fools Contest 2021 Archive (ZS)
A. Pacman and Power Pellet
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing Pacman and you want to eat the power pellet to defeat the pesky ghosts.

Pacman moves one cell to the left, right, top or bottom every second. What is the minimum time needed for him to eat the power pellet?

Input

The first line of input contains two integers, $$$n, m$$$ ($$$1 \le n,m \le 100$$$, $$$nm \ge 2$$$). The next $$$n$$$ lines of input contains $$$m$$$ characters. Each character is one of the following: #, ., P or O. P denotes Pacman, O denotes the power pellet, . denotes an empty cell and # denotes a blocked cell.

Output

Output the minimum number of seconds required for Pacman to eat the power pellet. If the task is impossible, output $$$-1$$$.

Scoring

You get $$$100$$$ points if and only if you passed all testcases.

Examples
Input
1 2
OP
Output
1
Input
3 5
#####
#O..P
###..
Output
3
Input
3 5
#.#.#
O#.P#
.##.#
Output
-1

B. As Easy As ABC
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Input

The input consists of a string $$$s$$$ ($$$1 \le |s| \le 10$$$), where all characters are the same and can either be A, B or C.

Scoring

There are $$$25$$$ possible tests excluding samples. Getting a test correct will give you $$$4$$$ points (for a total of $$$100$$$ points).

Examples
Input
AAAA
Output
273/275
Input
B
Output
272/300
Input
CCCCCCCCC
Output
36/149
Input
AAA
Output
221/225
Input
A
Output
317/323

C. Two Hashes
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have learned about polynomial hashing recently. Firstly, you choose a prime $$$MOD$$$ and a large enough integer $$$C$$$. Then, for every string $$$s = s_{n-1}s_{n-2}\cdots s_{1}s_{0}$$$ of lowercase English letters, you hash it to the value $$$\displaystyle\sum_{i=0}^{n-1}val(s_{i}) \cdot C^{i} \pmod{MOD}$$$, where val(a) = 1, val(b) = 2, ..., val(z) = 26.

You tested this algorithm by hashing $$$10000$$$ random strings of length $$$50$$$. You choose $$$MOD = 10^{9}+9$$$ because that's your favourite prime. However, you realized halfway that you are not using the same value of $$$C$$$ to hash every string! More precisely, for every string, you chose either $$$C = 115381398$$$ or $$$C = 276147934$$$ uniformly randomly and hash the string using this value of $$$C$$$.

You wonder if there is a way to tell which value of $$$C$$$ you used to hash each string. Can you solve this task?

Sample implementation of the hash function in C++: https://ideone.com/xYGvdD

Input

The first line of input contains a single integer, $$$t$$$ ($$$t = 10000$$$).

Each of the next $$$t$$$ lines contain a single integer, $$$x_i$$$ ($$$0 \le x_i \lt 10^{9}+9$$$), denoting the hash value of the $$$i$$$-th string.

There are more lines in the input but they are meant to be used for the checker only and it is guaranteed that you do not need to use them to get full score.

Output

Output $$$t$$$ lines, each containing a single integer. If you think $$$x_i$$$ is generated by $$$C = 115381398$$$, output $$$1$$$ on the $$$i$$$-th line. Otherwise, output $$$0$$$ on the $$$i$$$-th line.

Scoring

You get more points if you get more testcases correct. You will get positive score if and only if you get at least half the testcases correct.

Example
Input
2
923051192
596459381
Output
1
0
Note

Note that the sample shown is not a valid input based on the constraints, because $$$t \neq 10000$$$.

D. Math Homework
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

zscoder needs to complete his math homework, but he is out of time. Can you help him?

Note: Apparently his homework problems are written in a different language. I hope this won't stop you from solving the problems.

Input

The samples cover all possible types of inputs. Please check them out.

Output

Output a single real number, the answer to the homework problem. Your answer will be accepted if it is close enough to the actual answer (i.e. $$$10^{-4}$$$ relative or absolute error).

It is guaranteed that the answer fits in a C++ long double type in all the hidden testcases.

Scoring

There are $$$13$$$ hidden tests, $$$11$$$ of which are worth $$$6$$$ points each and $$$2$$$ of which are worth $$$17$$$ points (for a total of $$$100$$$ points).

Examples
Input
fallocest(1.2345)*fallocest(1.2345)+sploop(1.2345)*sploop(1.2345)
Output
1.000000000000000
Input
strustate(12)
Output
39916800.000000000000000
Input
fabrate(tudefy(10000000000000000))
Output
4.000000000000000
Input
tudefy(fabrate(10000000000000000))
Output
8.000000000000000
Input
chaness(fallocest(4.1))*strustate(0.5)
Output
1.018848917625599
Input
ensalex(fabrate(3)-sploop(1.23))
Output
0.668343826109546
Input
holofy(1)+quendle(1)
Output
3.560982621408760
Input
ensalex(holofy(1))+fallocest(strustate(1))
Output
1.758585210885417
Input
chaness(-10)/holofy(quendle(0.2))
Output
8.003528474734495
Input
strustate(sploop(0.5))
Output
1.847498857994100
Input
strustate(ensalex(0.49))
Output
1.943784695029594
Input
fabrate(2)+ensalex(2)+fallocest(2)+sploop(2)+strustate(2)+holofy(2)+quendle(2)+tudefy(2)+chaness(2)
Output
14.699921230059308

E. Simple Exercise
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem was created a long time ago. However, since I don't think it was seriously attempted, here it is again.

duckmoon is solving trivial problems on new online judges again. duckmoon99 is browsing the source codes that were submitted by duckmoon. One of the codes caught his attention. Here's the problem statement :

  • Given n positive integers a1, a2, ..., an, find the value of modulo 109 + 7.

    There are t testcases in each input file.

    The first line of input contains the integer t.

    Each testcase consists of two lines. The first line contains the integer n. The second line contains n integers, denoting a1, a2, ..., an.

    Output the correct answer for each testcase on a new line.

Here's his submission to the problem : https://ideone.com/uRM2Po

duckmoon99 immediately contacted duckmoon and told him that his code is wrong. duckmoon said : "But the constraints for n is small enough for the O(tn2) solution to pass. How else could my code possibly be wrong?"

duckmoon99 shakes his head and constructed some testcases for which duckmoon's code will get the wrong answer. Can you find such testcases?

Input

The first line of input contains three integers T, N, MAX (T = 2000, N = 100, MAX = 1000).

This means that in your testcase 1 ≤ t ≤ T, 2 ≤ n ≤ N, 1 ≤ ai ≤ MAX for all 1 ≤ i ≤ n. If any of your testcases are invalid, you get 0 points.

Additionally, all the t testcases must be distinct. Two testcases are distinct if either their values of n are distinct, or there exist an integer that has a different number of occurences in the two sequences of n integers. For example, (2, 3, 2) and (3, 2, 2) are not distinct but (2, 3, 2) and (3, 3, 2) are distinct. If not all t testcases are distinct, you get 0 points.

Output

The first line of output should contain a single integer t (1 ≤ t ≤ T), denoting the number of testcases.

Each testcase consists of two lines. The first line contains the integer n (1 ≤ n ≤ N). The second line contains n space-separated integers, denoting a1, a2, ..., an (1 ≤ ai ≤ MAX).

All t testcases must make duckmoon's code produce a wrong output.

Here's an example of an output if T = 2, N = 1500, MAX = 1000 (that will not be accepted because the code prints the correct answer)


2
5
2 4 1 1000 3
4
5 3 81 191

Note that the output of the program is 


10035
17662

which is correct.

Scoring

If any of the t testcases make duckmoon's code produce a correct output, you get 0 points.

Assume that the total score is 100 points.

Let N0 be the minimum positive integer such that there exist a testcase that fails duckmoon's solution with n = N0.

There are two modes of scoring depending on your testcases :

Mode 1 : When all t testcases satisfy n = N0.

Then, your score for this problem is .

Mode 2 : Not all t testcases satisfy n = N0.

Suppose X of the t testcases satisfy n ≤ 50. Your score for this problem is min(30, 10 + X).

F. Mystery
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem requires interaction with a custom Discord bot.

There are $$$5$$$ mysterious subproblems in this problem. A mysterious bot has already solved this problem, and now it's your turn!

You may provide test inputs to the bot, and it will automatically tell you the correct result! If only you can just let it solve the problem for you......

Anyway, you can find the bot in this Discord server: https://discord.gg/JJxwuSbyuE

Use the command m!help to access the help menu for the bot. Use m!ask <problem number> <input> to learn the output for your given input.

Technical Note: Strings starting with an integer such as 1aa is judged as an integer in the bot but will never appear in the test data, so don't worry about it.

Input

The first line of input contains two integers, $$$t$$$ and $$$k$$$ ($$$1 \le t \le 50000$$$, $$$1 \le k \le 5$$$). $$$t$$$ denotes the number of testcases, whereas $$$k$$$ denotes the problem number.

Then, $$$t$$$ lines follow, where each line contains a valid input to problem $$$k$$$.

Output

Output $$$t$$$ lines, where the $$$i$$$-th line contains the correct output for the $$$i$$$-th input.

Scoring

Each test passed will contribute to your points.

Problem $$$1$$$ is worth $$$3$$$ points overall.

Problem $$$2$$$ is worth $$$16$$$ points overall.

Problem $$$3$$$ is worth $$$30$$$ points overall.

Problem $$$4$$$ is worth $$$25$$$ points overall.

Problem $$$5$$$ is worth $$$26$$$ points overall.

Maximum score for this problem is thus $$$100$$$ points.

Example
Input
5 4
5
8
9
50
100
Output
r
n
n
r
a

G. Can you do the Hololive?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Unlike other problems, this problem is worth 200 points.

This problem requires interaction with a custom Discord bot.

This problem is comprised of $$$10$$$ mini subtasks, each of which is worth $$$20$$$ points and corresponds to a Hololive character. The list of tasks are (in no particular order):

  1. Watame Janken
  2. Friend Fubuki
  3. Mio Yacht
  4. Yandere Rushia
  5. Apex Aqua
  6. Suisei Tetris
  7. All-Rejecting Okayu
  8. Gambling Pekora
  9. Korone Game
  10. Untitled Subaru Game

You should play around with the bot and submit your score using the token generated by h!claim. Please do not share the token with anyone. If your score in the bot is higher than your score here, then your points might be nullified.

You do not need to hack or exploit the bot in any way for this problem (so please don't do it).

You can use h!help to find the list of commands of the bot. You can find the bot in the Discord server: https://discord.gg/JJxwuSbyuE

Details on the tasks and how to use the bot can be found here: https://docs.google.com/document/d/1EOfsjlG_8WlFAhsO98eGDiHmJc6W0lXLero6QLsAzvw/edit?usp=sharing

Input

There is no input.

Output

Output a token that certifies your score. See Scoring.

Scoring

Use h!claim to generate a token which will allow you to claim your current score from the bot. Submit the token (or more precisely, a code that outputs that token) to get the points.