83 lines
4.2 KiB
TeX
83 lines
4.2 KiB
TeX
\documentclass{maratona}
|
|
|
|
\begin{document}
|
|
\begin{ProblemaAutor}{}{Pique Pega}{1}{256}{Arthur Andrade D'Olival}
|
|
|
|
No grande Arraiá de São João, o aguardado Casamento Caipira virou uma tremenda confusão!
|
|
O \textbf{Noivo} entrou em pânico na hora do "sim" e fugiu correndo.
|
|
Imediatamente, o \textbf{Delegado} da festa foi acionado pelo pai da noiva para capturar o fujão e arrastá-lo direto para a barraca da Cadeia.
|
|
|
|
O local da festa possui uma organização bem tradicional: o arraiá é composto por $n$ barracas numeradas de $1$ a $n$, que são conectadas por exatamente $n-1$ corredores de terra batida decorados com bandeirinhas coloridas.
|
|
A organização foi feita de tal forma que existe sempre um único caminho simples caminhando pelos corredores entre quaisquer duas barracas.
|
|
|
|
A perseguição começa com o Delegado na barraca $a$, e o Noivo escondido na barraca $b$. Eles correm em turnos alternados, e o \textbf{Delegado dá o primeiro pique de corrida}.
|
|
|
|
\begin{itemize}
|
|
\item No seu turno, o \textbf{Delegado} pode correr por até $d_a$ corredores de bandeirinhas para tentar encurralar o fujão.
|
|
\item Na sua vez, o \textbf{Noivo} pode disparar por até $d_b$ corredores para tentar se afastar da autoridade.
|
|
\end{itemize}
|
|
|
|
A distância entre duas barracas é o número de corredores no único caminho entre elas.
|
|
No desespero (ou para comer uma paçoca), ambos podem optar por não correr e permanecer na mesma barraca durante o seu turno.
|
|
O movimento é focado apenas no destino: eles cruzam os corredores sem parar nas barracas intermediárias.
|
|
|
|
O Delegado vence se, em até $10^{100}$ turnos, conseguir chegar na \textbf{mesma barraca} que o Noivo, efetuando a prisão.
|
|
Caso contrário, se o Noivo conseguir sambar pelo arraiá e despistar o Delegado a noite inteira, o Noivo vence, e continua solteiro.
|
|
|
|
Sua tarefa é determinar quem sairá vencedor dessa confusão junina, assumindo que tanto o Delegado quanto o Noivo corram e se escondam de maneira absolutamente ótima.
|
|
|
|
|
|
Para cada caso de teste, imprima uma única linha contendo o vencedor dessa perseguição caipira: \texttt{Delegado} ou \texttt{Noivo}.
|
|
|
|
\Entrada
|
|
|
|
A primeira linha da entrada contém um inteiro $t$ ($1 \le t \le 10^4$), indicando o número de casos de teste.
|
|
|
|
A primeira linha de cada caso de teste contém cinco inteiros: $n, a, b, d_a, d_b$ ($2 \le n \le 10^5$, $1 \le a, b \le n$, $a \neq b$, $1 \le d_a, d_b \le n-1$), representando o número de barracas no arraiá, a barraca inicial do Delegado, a barraca inicial do Noivo, o fôlego máximo de corrida do Delegado e o fôlego máximo de fuga do Noivo, respectivamente.
|
|
|
|
As próximas $n-1$ linhas descrevem os corredores do arraiá.
|
|
Cada linha contém dois inteiros $u$ e $v$ ($1 \le u, v \le n, u \neq v$), indicando um corredor direto de bandeirinhas ligando as barracas $u$ e $v$.
|
|
|
|
É garantido que a soma de $n$ em todos os casos de teste não excede $10^5$.
|
|
|
|
\Saida
|
|
|
|
Para cada caso de teste, imprima uma única linha contendo o vencedor dessa perseguição caipira: \texttt{Delegado} ou \texttt{Noivo}.
|
|
|
|
\ExemploEntrada
|
|
\begin{Exemplo}
|
|
\texttt{1} & \texttt{Delegado}\\
|
|
\texttt{4~3~2~1~2} & \\
|
|
\texttt{1~2} & \\
|
|
\texttt{1~3} & \\
|
|
\texttt{1~4} & \\
|
|
\rowcolor{gray!20}\texttt{1} & \texttt{Noivo}\\
|
|
\rowcolor{gray!20}\texttt{6~6~1~2~5} & \\
|
|
\rowcolor{gray!20}\texttt{1~2} & \\
|
|
\rowcolor{gray!20}\texttt{2~3} & \\
|
|
\rowcolor{gray!20}\texttt{3~4} & \\
|
|
\rowcolor{gray!20}\texttt{4~5} & \\
|
|
\rowcolor{gray!20}\texttt{5~6} & \\
|
|
\end{Exemplo}
|
|
|
|
|
|
|
|
\Notas
|
|
|
|
No primeiro caso de teste, o Delegado pode vencer se movendo para a barraca 1. Então, para onde quer que o Noivo se mova em seguida, o Delegado poderá se mover para a mesma barraca no turno seguinte.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\includegraphics[width=0.25\textwidth]{image1.png}
|
|
\end{figure}
|
|
|
|
No segundo caso de teste, o Noivo tem a seguinte estratégia para vencer. Para onde quer que o Delegado se mova, o Noivo sempre se moverá para aquela entre as barracas 1 ou 6 que estiver mais distante do Delegado.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\includegraphics[width=0.5\textwidth]{image2.png}
|
|
\end{figure}
|
|
|
|
Problema adaptado de \href{https://codeforces.com/contest/1405/problem/D}{Codeforces Round 668 (Div. 2, Problem D)}.\end{ProblemaAutor}
|
|
\end{document}
|