354 lines
9.6 KiB
TeX
354 lines
9.6 KiB
TeX
\documentclass[12pt,a4paper]{article}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{amsmath, amssymb}
|
|
\usepackage{geometry}
|
|
\usepackage{fancyhdr}
|
|
\usepackage{listings}
|
|
\usepackage{xcolor}
|
|
\usepackage{enumitem}
|
|
\usepackage{comment}
|
|
% Page layout
|
|
\geometry{margin=1in}
|
|
\pagestyle{fancy}
|
|
\fancyhf{}
|
|
\fancyhead[L]{Programming Competition Test}
|
|
\fancyhead[R]{\today}
|
|
\fancyfoot[C]{\thepage}
|
|
|
|
% Listings style for code
|
|
\lstset{
|
|
language=Java,
|
|
basicstyle=\ttfamily\small,
|
|
keywordstyle=\color{blue},
|
|
commentstyle=\color{green!60!black},
|
|
stringstyle=\color{red},
|
|
numbers=left,
|
|
numberstyle=\tiny,
|
|
stepnumber=1,
|
|
numbersep=5pt,
|
|
showstringspaces=false,
|
|
breaklines=true,
|
|
frame=single,
|
|
rulecolor=\color{black!30},
|
|
backgroundcolor=\color{black!2}
|
|
}
|
|
|
|
% Custom commands
|
|
\newcommand{\problem}[1]{\section*{#1}}
|
|
\newcommand{\inputformat}{\textbf{Input format:}}
|
|
\newcommand{\outputformat}{\textbf{Output format:}}
|
|
\newcommand{\examples}{\textbf{Example(s):}}
|
|
|
|
\begin{document}
|
|
|
|
\begin{center}
|
|
{\LARGE \textbf{Programming Competition Test}}\\[2mm]
|
|
{\large Duration: 2 hours \quad Total Marks: 100}
|
|
\end{center}
|
|
|
|
\section*{Instructions}
|
|
\begin{enumerate}[label=\arabic*.]
|
|
\item Use Java. IntelliJ and other common IDEs are available on the provided systems.
|
|
\item Write the most efficient solution you can. Solutions have been profiled for optimal performance, and suboptimal solutions risk being timed out.
|
|
\item Open and log ito $\text{PC}^2$ early.
|
|
\item Use fast IO, testcases can be up to 1 GB in size.
|
|
\end{enumerate}
|
|
|
|
\begin{comment}
|
|
% ========================= Problem 1 =========================
|
|
\problem{Problem 1: Two Sum}
|
|
\textit{Difficulty: Easy}
|
|
|
|
Given an array of integers \texttt{nums} and an integer \texttt{target}, return indices of the two numbers such that they add up to \texttt{target}. Assume exactly one solution exists.
|
|
|
|
\inputformat
|
|
\begin{itemize}
|
|
\item First line contains an integer $n$ ($2 \leq n \leq 10^5$), the size of the array.
|
|
\item Second line contains $n$ integers, the elements of the array.
|
|
\item Third line contains the integer \texttt{target}.
|
|
\end{itemize}
|
|
|
|
\outputformat
|
|
\begin{itemize}
|
|
\item Print two integers, the indices of the elements adding up to \texttt{target}.
|
|
\end{itemize}
|
|
|
|
\examples
|
|
\begin{verbatim}
|
|
Input:
|
|
4
|
|
2 7 11 15
|
|
9
|
|
|
|
Output:
|
|
0 1
|
|
\end{verbatim}
|
|
|
|
% ========================= Problem 2 =========================
|
|
\problem{Problem 2: Longest Substring Without Repeating Characters}
|
|
\textit{Difficulty: Medium}
|
|
|
|
Given a string \texttt{s}, find the length of the longest substring without repeating characters.
|
|
|
|
\inputformat
|
|
\begin{itemize}
|
|
\item A single line containing the string \texttt{s} ($1 \leq |s| \leq 10^5$).
|
|
\end{itemize}
|
|
|
|
\outputformat
|
|
\begin{itemize}
|
|
\item A single integer, the length of the longest substring without repeated characters.
|
|
\end{itemize}
|
|
|
|
\examples
|
|
\begin{verbatim}
|
|
Input:
|
|
abcabcbb
|
|
|
|
Output:
|
|
3
|
|
\end{verbatim}
|
|
|
|
% ========================= Problem 3 =========================
|
|
\problem{Problem 3: Merge Intervals}
|
|
\textit{Difficulty: Hard}
|
|
|
|
Given a collection of intervals, merge all overlapping intervals.
|
|
|
|
\inputformat
|
|
\begin{itemize}
|
|
\item First line contains an integer $n$ ($1 \leq n \leq 10^4$), the number of intervals.
|
|
\item Next $n$ lines contain two integers each, representing the start and end of each interval.
|
|
\end{itemize}
|
|
|
|
\outputformat
|
|
\begin{itemize}
|
|
\item Print the merged intervals in ascending order of start times.
|
|
\end{itemize}
|
|
|
|
\examples
|
|
\begin{verbatim}
|
|
Input:
|
|
4
|
|
1 3
|
|
2 6
|
|
8 10
|
|
15 18
|
|
|
|
Output:
|
|
1 6
|
|
8 10
|
|
15 18
|
|
\end{verbatim}
|
|
\end{comment}
|
|
\newpage
|
|
% ========================= Problem 6 =========================
|
|
\problem{Problem 6(.7): Sequencing}
|
|
\textit{Difficulty: Easy}
|
|
|
|
You are given a string S composed of only the characters 6, 7, A, B, and \# (without the quotation marks). This string is processed from left to right, and you must maintain a sequence of chracters that changes according to these rules:
|
|
\begin{itemize}
|
|
\item 6 - add a 6 to the end of the sequence
|
|
\item 7 - if the sequence's last chracter is 6, remove that last 6, otherwise, add 7 to the end of the sequence
|
|
\item A - reverse the sequence
|
|
\item B - add a duplicate of the current sequence to the end of it
|
|
\item \# - clear the sequence
|
|
\end{itemize}
|
|
|
|
\inputformat
|
|
\begin{itemize}
|
|
\item The first line consists of the string $S$ ($1 \leq |S| \leq 10^5$). The string consists only of the characters 6, 7, A, B, and \#.
|
|
\end{itemize}
|
|
|
|
\outputformat
|
|
\begin{itemize}
|
|
\item Output a single line containig the final form of the sequence. If the sequence is empty at the end, output “EMPTY” (without the quotations).
|
|
\end{itemize}
|
|
|
|
\examples
|
|
\begin{verbatim}
|
|
Input 1:
|
|
67A6
|
|
|
|
Output 1:
|
|
6
|
|
|
|
Input 2:
|
|
66B7
|
|
|
|
Output 2:
|
|
666
|
|
|
|
Input 3:
|
|
7A7#
|
|
|
|
Output 3:
|
|
EMPTY
|
|
\end{verbatim}
|
|
|
|
% ========================= Problem 7 =========================
|
|
\newpage
|
|
\problem{Problem 7: Limited Jumps}
|
|
\textit{Difficulty: Medium}
|
|
|
|
You are given a grid of size N x M, where each cell contains either 6 or 7. You start at the top-left corner (1,1) and want to reach the bottom-right corner (N,M). You can move right, down, or jump diagonally (right+down). The maze has these rules:
|
|
\begin{itemize}
|
|
\item You can step on a 6 any number of times
|
|
\item You can step on a 7 at most once in your path
|
|
\item You can make at most one diagonal move in your path
|
|
\end{itemize}
|
|
|
|
Your task is to determine if there exists any valid path from (1,1) to (N,M) obeying the rules.
|
|
|
|
\inputformat
|
|
\begin{itemize}
|
|
\item The first line consists 2 integers $N$ and $M$ ($1 \leq N, M \leq 10^9$), the number of rows and columns, respectively
|
|
\item The next N lines will consist of strings of length M, containing 6 or 7
|
|
\end{itemize}
|
|
|
|
\outputformat
|
|
\begin{itemize}
|
|
\item Output a single line. If there exists a valid path, print ``Sixxx sevennn" (without the quotations). If there does not exist a valid path, print ``Six was afraid of seven after all" (without the quotations).
|
|
\end{itemize}
|
|
|
|
\examples
|
|
\begin{verbatim}
|
|
Input 1:
|
|
2 2
|
|
66
|
|
67
|
|
|
|
Output 1:
|
|
Sixxx sevennn
|
|
|
|
Input 2:
|
|
2 2
|
|
77
|
|
77
|
|
|
|
Output 2:
|
|
Six was afraid of seven after all
|
|
|
|
Input 3:
|
|
3 3
|
|
666
|
|
676
|
|
666
|
|
|
|
Output 3:
|
|
Sixxx sevennn
|
|
\end{verbatim}
|
|
|
|
% ========================= Problem 8 =========================
|
|
\newpage
|
|
\problem{Problem 8: Staircase}
|
|
\textit{Difficulty: Medium}
|
|
|
|
There is a staircase with N steps. Each step is labelled with a 6 or a 7. Simon starts at step 1 and wishes to reach the top step (Step N). If a step is labelled with a 6, Simon may go up 1 or 2 steps. If a step is labelled with a 7, Simon can move up exactly 1 step. Your job is to find the total number of distinct ways Simon can reach the top step N from , given these rules.
|
|
|
|
\inputformat
|
|
\begin{itemize}
|
|
\item The first line consists an integer $N$ ($1 \leq N \leq 10^5$), the number of steps
|
|
\item The second line will consist of N integers, the label of each step (either 6 or 7)
|
|
\end{itemize}
|
|
|
|
\outputformat
|
|
\begin{itemize}
|
|
\item Output the number of distinct ways Simon can reach the top step N.
|
|
\end{itemize}
|
|
|
|
\examples
|
|
\begin{verbatim}
|
|
Input 1:
|
|
5
|
|
66766
|
|
|
|
Output 1:
|
|
3
|
|
|
|
Explanation 1:
|
|
Case 1: Step 1->2->3->4->5
|
|
Case 2: Step 1->2->4->5
|
|
Case 3: Step 1->3->4->5
|
|
|
|
Input 2:
|
|
3
|
|
677
|
|
|
|
Output 2:
|
|
2
|
|
|
|
Explanation 2:
|
|
Case 1: 1->2->3
|
|
Case 2: 1->3
|
|
|
|
Input 3:
|
|
1
|
|
6
|
|
|
|
Output 3:
|
|
1
|
|
|
|
Explanation 3:
|
|
There is only one way to get to the top (which Simon is already at).
|
|
\end{verbatim}
|
|
|
|
% ========================= Problem 9 =========================
|
|
\newpage
|
|
\problem{Problem 9: Showering}
|
|
\textit{Difficulty: Medium}
|
|
|
|
We all know that CS students don't shower often. In fact, Simon showers about 6 to 7 times every year, a practice of discipline and optimization. To motivate himself to shower, Simon invented a mini-game involving a sequence made only of 6s and 7s.
|
|
Before every shower, Simon stares at the sequence and simulates a “cleaning process.” He believes that every time he cleans up the sequence, he cleans up his soul enough to deserve a shower.
|
|
The sequence S of length N consisting only of 6 and 7.\newline\newline
|
|
Simon scans the string left to right. Whenever he encounters the pattern “67”, he considers that a sign of impurity since the 6 is “dirtier” than the 7, so they must be flipped to “76” on the spot. This change happens immediately because Simon believes cleanliness must spread instantly. After reaching the end, Simon restarts the sweep from the beginning, repeating passes until there are no more “67” pairs, meaning the sequence has reached maximum spiritual hygiene. Your task is to determine the number of flips Simon must do to achiece spiritual hygiene.
|
|
|
|
\inputformat
|
|
\begin{itemize}
|
|
\item The first line consists an integer $N$ ($1 \leq N \leq 10^9$), the length of the sequence
|
|
\item The second line will consist of a string S, with length N
|
|
\end{itemize}
|
|
|
|
\outputformat
|
|
\begin{itemize}
|
|
\item Output the number of steps required to achieve spiritual cleanliness
|
|
\end{itemize}
|
|
|
|
\examples
|
|
\begin{verbatim}
|
|
Input 1:
|
|
4
|
|
6677
|
|
|
|
Output 1:
|
|
4
|
|
|
|
Explanation 1:
|
|
First Swap: 6677 -> 6767
|
|
Second Swap: 6767 -> 6776
|
|
Third Swap (returns to beginning): 6776 -> 7676
|
|
Fourth Swap: 7676 -> 7766
|
|
|
|
Input 2:
|
|
5
|
|
77766
|
|
|
|
Output 2:
|
|
0
|
|
|
|
Explanation 2:
|
|
The sequence is already spiritually clean
|
|
|
|
Input 3:
|
|
5
|
|
67676
|
|
|
|
Output 3:
|
|
3
|
|
|
|
Explanation 3:
|
|
First Swap: 67676 -> 76676
|
|
Second Swap: 76676 -> 76766
|
|
Third Swap (return to beginning): 76766 -> 77666
|
|
\end{verbatim}
|
|
\end{document} |