UTPC April Fools Contest 2024
A. Are you a Robot?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

B. Working Out
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Where does a competitive programmer go to work out?

C. Passcode
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
If at first you don't succeed, try, try again.
— Someone, probably...

Alice accidentally locked this problem behind a five digit passcode, but she forgot what it was. Apparently, if you get accepted, it means you've guessed the passcode correctly...

Help her figure out the passcode before it's too late!

Output

Please output Alice's passcode. It is guaranteed that:

  • The correct passcode will receive an "accepted" verdict.
  • A passcode which is incorrect but has at most five digits and is comprised of only digits will receive a "wrong answer" verdict.
  • A passcode which is malformed (too long or contains invalid characters) will receive a "wrong error" verdict on test case 1.

D. Prestige Hunter
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Our friend Sweat is constantly sweating about the prestige of the companies he is applying to. His friend, Perspirate, offered him a CSV table, which she claims is a comprehensive list of the most prestigious companies, alongside their ranking by prestige.

To help Sweat and Perspirate cope with their stress, you are tasked with building an application that, for each of $$$T$$$ inquiries, given a company name, check if it is on the list of prestigious companies - and if so, how highly it places on the prestige list.

The list of companies may be accessed at: https://pastebin.com/f3099efT

Input

First, one line, representing $$$T$$$.

Then, for each of the $$$T$$$ following lines, one string representing the company name - please disregard case.

You may assume $$$T\leq 1000$$$, and no line's input will be longer than 1000 characters in length.

Output

For each of the $$$T$$$ lines, if the company is in the list of prestigious companies, print the prestige ranking of the company (starting with 1), else print -1.

Example
Input
5
meta
Capital One
nETflIx
goOgLe
asdfrteghafdbdhsarwgdraet wegnfr
Output
117
40
126
87
-1

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

Dylan Smith noticed something fishy with the blog post. In order to confirm his suspicions, he wants you to compute the fishy frequency constant, which corresponds to the floor of the hypotenuse $$$h$$$ of the right triangle with leg lengths:

$$$a = \lim_{k \rightarrow \infty} (\frac{\int_{0}^{\infty}2-\frac{2x^2}{1+x^2} dx}{1 - \frac{1}{k! + 1}})^{k!} \cdot e^{-k! \ln (\frac{1}{4}\int_{0}^{2\pi} \sqrt{2 + \cos x + \sqrt{5 + 4\cos x}} dx)}$$$
$$$b = \sum_{k=0}^{\infty} ( \frac{1}{(\sum_{j=0}^{\infty} \frac{16(-1)^j(2j)!}{(j!)^2(4j+1)4^{100j}})^k} (\frac{8k+7}{32k^2 + 20k + 2} - \frac{1 + \int_{0}^{\infty} \frac{\cos x - e^{-x}}{x} dx}{8k+5} - \frac{4 \cdot \sum_{n=0}^{\infty} \frac{(-1)^n}{2n+1}}{(8k+6) \cdot \int_{0}^{\infty} \frac{dx}{\sqrt{x} (x+1)}}))$$$
$$$h = \lfloor \sqrt{a^2 + b^2} \rfloor$$$
Output

Print one integer, the fishy frequency constant.

F. Those Who Know
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fortune favors the bold (?)

Input

Output a single string $$$s$$$ without whitespace, where $$$1 \leq |s| \leq 10^5$$$.

Example
Input
i know!
Output
i-don't-:(

G. :wink:
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Examples
Input
April
Output
Fools'
Input
was
Output
to
Input
this
Output
year,
Input
affair.
Output
And

H. Find the Bug Week 15
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Being such a good student, I was working ahead on the Find the Bug homeworks for CS104c, and I stumbled upon this secret Week 15 FTB! However, this one's got me stumped. Can you help me come up with a test case that the code fails on?

import java.io.*;
import java.util.*;

/**
 * 
 * Problem statement:
 * Given an array of 1<=n<=51 integers between -1e9 and 1e9,
 * count the number of longest (strictly) increasing subsequences.
 * Output this number modulo 1e9+7.
 * 
 * Sample Input:
 * 5
 * 1 3 2 2 5
 * Answer:
 * 3
 * Explanation:
 * The 3 longest increasing subsequences are [1 3 5], [1 2 5], and [1 2 5].
 *
 *
 * This problem should be a pretty straightforward dp, but I'm not sure where my bug is.
 * Maybe an off-by-one error somewhere...?
 * Help me find a test case that I fail on!
 * 
 */
public class FindTheBug15 {
	
	static final long MOD = 100000007;
	
	public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
        	nums[i] = in.nextInt();
        }
        
        //dp[i] = number of maximum length increasing subsequences ending at nums[i]
        long[] dp = new long[n];
        
        //len[i] = maximum length of increasing subsequence ending at nums[i]
        int[] len = new int[n];
        
        //longest increasing subsequence we've seen
        int mxLen = 0;
        for(int i = 0; i < n; i++) {
            len[i] = 1;
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    //longer increasing subsequence(s) found
                    if(len[j]+1 > len[i]) {
                        len[i] = len[j]+1;
                        dp[i] = dp[j];
                    }
                    //same length increasing subsequence(s) found
                    else if(len[j]+1 == len[i]) {
                        dp[i] += dp[j];
                        dp[i] %= MOD;
                    }
                }
            }
            mxLen = Math.max(mxLen, len[i]);
        }
        long ans = 0;
        for(int i = 0; i < n; i++) {
            if(len[i] == mxLen) {
                ans += dp[i];
                ans %= MOD;
            }
        }

        System.out.println(ans);
    }
}
Output

On the first line, output a single integer $$$n\ (1\leq n \leq 51)$$$. On the next line, output $$$n$$$ space separated integers $$$a_1\dots a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$.

When run on your output, the code given above should produce the wrong answer.

Example
Input
Help me find a test case that the above code fails on!
Output
[Output your test case here]

I. Oh It's XOR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a graph with $$$n$$$ vertices and $$$m$$$ undirected, unweighted edges. ($$$2 \leq n \leq 10$$$^$$$3$$$, $$$1 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$)

Vertices are numbered from $$$1$$$ to $$$n$$$, and vertex $$$i$$$ has value $$$v_i$$$. ($$$0 \leq v_i \lt 2$$$^$$$30$$$)

Output the maximum value of $$$v_{p_1}$$$ ^ $$$v_{p_2}$$$ ^ ... ^ $$$v_{p_k}$$$ where $$$p$$$ is a an array with distinct values ($$$1 \leq p_i \leq n$$$, $$$1 \leq k \leq n$$$), such that there is an edge between $$$p_i$$$ and $$$p_{i+1}$$$ for $$$1 \leq i \lt k$$$, and ^ denotes the bitwise XOR operator.

Input

The first line of input will consist of two integers $$$n$$$ and $$$m$$$. ($$$2 \leq n \leq 10$$$^$$$3$$$, $$$1 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$)

The next line will contain $$$v_1 ... v_n$$$. ($$$0 \leq v_i \lt 2$$$^$$$30$$$)

The $$$i$$$th of the next $$$m$$$ lines will contain $$$a_i$$$ and $$$b_i$$$, denoting an edge between vertex $$$a_i$$$ and vertex $$$b_i$$$. ($$$1 \leq a_i, b_i, \leq n$$$, $$$a_i \neq b_i$$$, each edge is unique)

Output

Output the answer.

Example
Input
5 5
1 4 3 2 5
1 2
2 3
3 4
4 5
3 5
Output
7

J. Gacha Rolling
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're playing your favorite (and the best) mobile rhythm gacha game, D4DJ Groovy Mix.

Recently, they collaborated with one of your favorite anime series, Monogatari, and you want to pull for the best girl from that series, Hitagi Senjougahara.
Fortunately, you have plenty of money from your coding job, and have enough diamonds to pull as many times as you want. Keep pulling until you pull Hitagi.

Rates:

3% for 4* card

70% for a 4* card to be a collaboration member.

25% for a collaboration member to be Hitagi Senjougahara (the other collab members are Nadeko, Mayoi, and Suruga)

Output

Output any 32-bit signed integer (which is used to seed the RNG) on the first line in order to do 10 pulls on the banner.

Example
Input
Draw 10 for 3000 diamonds
Output
12

K. Vote Here!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thanks for sticking around! Now that you've had some time to try out the problems, we want to know—which one was your favorite?

Example
Input
Cast your vote here!
Output
Your favorite problem