UTPC April Fools Contest 2026
A. Captcha
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

B. Right or Wrong?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Input

$$$a$$$, $$$b$$$, $$$c$$$ $$$(1\le a\le b\le c\le 10^9)$$$

Examples
Input
3 4 5
Output
YES
Input
3 4 6
Output
NO
Input
7 24 25
Output
YES
Input
6 20 21
Output
NO
Input
10 10 10
Output
NO

C. New Sorting Algorithm
time limit per test
15 seconds
memory limit per test
8 megabytes
input
standard input
output
standard output

Michael is on a crunch so he gives you a permutation of $$$n$$$ numbers to sort.

He wants you to sort it quickly and efficiently, but it seems like none of the current sorting algorithms are working for him. As the master of computational science and analysis, he has enlisted your help.

Help him do this!

Input

The first line contains $$$n$$$ the number of numbers Michael wants you to sort. $$$1 \leq n \leq 5\cdot 10^6$$$.

The second line contains the numbers $$$a_1, a_2, ..., a_n$$$, $$$1 \leq a_i \leq n$$$.

Output

Output $$$n$$$ integers, the numbers sorted.

Note

Credit: DanielQiu

D. Subset Sums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp has an array $$$a$$$ that consists of $$$a_1,a_2,\cdots, a_n$$$. How many unique subsets of $$$a$$$ sum to $$$k$$$? Print your answer in mod $$$10^9+7$$$.

Here, subsets are distinguished by the indices used to create those subsets.

Input

The first line of input contains $$$n$$$ and $$$k$$$ $$$(1\le n\le 5\cdot 10^5, 0\le k\le 10^9)$$$.

The second line of input contains $$$a_1,a_2,\cdots,a_n$$$ $$$(0\le a_i\le 10^9)$$$.

Output

Output the answer in mod $$$10^9+7$$$.

Example
Input
5 3
8 1 3 2 4
Output
2
Note

In this testcase, only the sets $$$\{1,2\}$$$ and $$$\{3\}$$$ work. These sets have a sum of $$$3$$$, as desired. The sets are unique since they are composed of different sets of indices.

$$$$$$\color{white}{y=\frac{1}{\max(b,1+b-a)}x\{0\le y\le 2\}}$$$$$$ $$$$$$\color{white}{y=-\frac{1}{1+b-a}x+\frac{2}{1+b-a}\cdot\frac{\sqrt{2-a}}{\sqrt{2-a}}\{0\le y\le 2\}}$$$$$$ $$$$$$\color{white}{y=-\sqrt{a-1+b}\,x+a-1\{0\le x\le 2\}\{-2\sqrt{b}\le y\le 1\}}$$$$$$ $$$$$$\color{white}{x=-\frac{1}{\min(b+a-1,0.25)}\left(y-2.5+\frac{a}{2}\right)^2-a+3\{0\le x\le 2\}\{1\le y\le 2\}}$$$$$$ $$$$$$\color{white}{b=10^{-6}}$$$$$$

E. Gemini
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Castor is taking a number theory course. Help him answer a question from his class:

Partition the first $$$n$$$ positive integers into $$$k$$$ sets such that numbers in each set are pairwise coprime, and print out your construction. Also, $$$k$$$ must be minimal.

Input

The first line contains $$$n$$$ $$$(4\le n\le 3\cdot 10^5)$$$

Output

Print out $$$k$$$ lines, each containing $$$m_i$$$ followed by $$$m_i$$$ integers $$$a_{i,1},a_{i,2},\cdots,a_{i,m_i}$$$ — representing the $$$i$$$th set of the partition. Do not print out $$$k$$$ itself.

Also, if you print out extra things at the end, the checker will ignore them. :)

Example
Input
10
Output
[sorry, we don't have the answer to the sample]

F. Something's Fishy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thank god I don't live in Asia. Their ICPC Championship seems ridiculously hard.

Let $$$|$$$ be such that $$$69|420 = 69420$$$.

$$$$$$ X = \left\lfloor\varphi^{16}\right\rfloor $$$$$$

$$$$$$ a = \text{The number of official Codeforces April Fools contests so far} $$$$$$

$$$$$$ r = \text{The number of r's in the word "strawberry"} $$$$$$

$$$$$$ c = \text{The most common "random" number from 1 to 100, inclusive, according to Veritasium} $$$$$$

$$$$$$ l = \lim_{x\rightarrow \infty}\left(\ln(x) - \frac{x}{\pi(x)}\right) \quad \text{, where } \pi(x) \text{ is the prime-counting function} $$$$$$

$$$$$$ j = \text{The number of days in July during a leap year} $$$$$$

$$$$$$ h = \operatorname{Median}\bigl(\{d \in \mathbb{Z}_{ \gt 0} : d \text{ is squarefree and } \mathbb{Q}(\sqrt{-d}) \text{ has class number } 1\}\bigr) $$$$$$

$$$$$$ m = \text{3-digit number most closely associated with Matikanefukukitaru} $$$$$$

$$$$$$ Y = (a|r) \cdot (c+10) \cdot (l|j) \cdot (h|m) \mod 10^9+7 $$$$$$

Output

The answer is a word or phrase. Submit in all caps, no spaces.

G. Forgot where I took this pic
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Where did I take this pic????

Reverse image search and Google Maps 3D View may help!

Output

Output two real numbers $$$-90 \le a \le 90$$$ and $$$−180 \le b \le 180$$$, separated by a space.

Example
Input
hello
Output
lat long

H. Fill in the Blanks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp has a very large collection of numbers $$$\{a_1,a_2,a_3,\cdots\}$$$.

You are given $$$a_i$$$. Find $$$a_j$$$.

(He doesn't like $$$a_1$$$, so he will never ask you about it).

Input

The first line of input contains $$$i$$$ and $$$a_i$$$ $$$(2\le i, 1\le a_i\le 10^{18})$$$.

The second line of input contains $$$j$$$ $$$(2\le j\le 10)$$$.

It is guaranteed that only digits or whitespaces appear in the input.

Output

Output $$$a_j$$$.

Examples
Input
8 67
7
Output
106
Input
10 2
2
Output
10
Input
3 100
5
Output
14
Input
9 24
3
Output
211
Input
15 123
10
Output
258

I. Networking Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a professional network modeled as an undirected graph of $$$n$$$ nodes and $$$m$$$ edges, where node $$$1$$$ represents a connected industry professional. Your goal is to establish a direct connection between yourself (node $$$0$$$) and node $$$1$$$ as efficiently as possible.

It is known that node $$$1$$$ spends much time on the 6th floor of GDC.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^9$$$, $$$1 \leq m \leq 10^9$$$) — the number of nodes and edges. The graph is guaranteed to be connected.

Output

Establish a connection between node $$$0$$$ and node $$$1$$$.

Example
Input
6 7
0 2
2 3
3 4
4 5
5 1
2 5
3 1
Output
??

J. Guess the Number!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp loves to read minds! Now, he will challenge you to read his mind.

Magikarp has chosen a number $$$x$$$ $$$(1\le x\le 10^6)$$$. You can ask him questions of the form "Is $$$x$$$ at least $$$k$$$?". He will answer 1 if the answer is "Yes", and 0 if the answer is "No".

Magikarp realizes this is quite easy if you can ask as many questions as you want, so he will try to challenge you! Solve this when the number of questions you can ask is at most $$$4!$$$

Input

This is an interactive problem, so there is no input to read at the start.

Output

To ask a question, print a line of the form ? k where $$$1 \le k \le 10^6$$$.

After printing a question, you must flush the output and then read one integer from the interactor:

  • 1, if $$$x \ge k$$$
  • 0, if $$$x \lt k$$$

When you are ready to give your final answer, print a line of the form ! y where $$$y$$$ is your guess for $$$x$$$.

After printing your final answer, flush the output and terminate immediately.

Interaction

The hidden integer $$$x$$$ is fixed for the entire test.

If your program asks more than the allowed number of queries, prints an invalid query, uses a value of $$$k$$$ outside the allowed range, or does not follow the required format, the verdict may be Wrong Answer.

Remember to flush the output after every query and after the final answer. For example:

  • in C++, use cout « endl; or cout.flush();
  • in Java, use System.out.flush();
  • in Python, use sys.stdout.flush()
Example
Input
5
Output
  







        

        





    
        
K. Guessing Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
This is a history major's nightmare!
  
Hint: $$$\color{white}{\text{The present is built upon the results of the past.}}$$$
Please submit your answer in all caps.
Example
Input
the answer to this puzzle!

Output
[REDACTED]
  







        

        





    
        
L. MST
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given $$$n$$$ nodes and $$$m$$$ edges. You want to select some subset of the edges such that it forms an undirected acyclic graph with the minimum possible sum of edge weights.
Print out the minimum possible sum of edge weights.
Input
The first line of input contains $$$n$$$ and $$$m$$$ $$$(1\le n,m\le 2\cdot 10^5)$$$ — the number of nodes and the number of edges, respectively.
The $$$j$$$th of the next $$$m$$$ lines contains 3 integers $$$u_j$$$, $$$v_j$$$, $$$w_j$$$ $$$(1\le u_j, v_j\le n, 1\le w_j\le 10^9)$$$ — the start node, end node, and weight of the $$$j$$$th undirected edge, respectively.
Output
Output a single integer, the minimum possible sum of edge weights of any valid set of edges.
Note
Sorry, we don't have the budget for samples.
  







        

        





    
        
M. META
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
There are 12 clues for this puzzle. Each problem corresponds to exactly one clue, so solving problem B will give you clue B, and solving problem E will give you clue E. To get clues, submit a clarification with links to your AC submissions, and you will receive clues for those problems. This puzzle might be possible without all the clues, but it will be harder.
Magikarp arrives in a place full of undirected acyclic connected graphs to collect his final prize. "These undirected acyclic connected graphs could really use a trim," Magikarp thinks, as he arrives at a glowing treasure chest. 
When he tries to open it, he discovers a large lock sealing the chest shut.
What should Magikarp do to get his final prize?
1. [5] -> 8
2. [5] -> 3
3. [2,3] -> 16, 15
4. [1] -> 11
5. [1,3] -> 10, 12
6. [2] -> 1
7. [5] -> 2
8. [3,5] -> 7, 6
9. [1] -> 14
10. [5] -> 5
11. [4,5] -> 9, 13
12. [1] -> 4
Output
Your final answer will be 4 words. Submit them all on separate lines, with proper capitalization.
Example
Input
What will the answer be?

Output
What will the answer be?
Note
There is intermediate answer checking for this puzzle, at the cost of a WA submission. To do this, submit a solution that prints out a single string of capitalized letters, so if your answer to a clue is "fish", submit "FISH". If your answer to a clue is "magic carp", submit "MAGICCARP". You will receive a WA verdict for this.
If you want a hint on this problem and this problem only, submit a solution that prints out the following text (don't worry about line breaks, but capitalization and punctuation will matter):
  
where X is the number of this hint (starting from 1). Then, submit a clarification with a link to this submission, along with what you want to ask for the hint.