UNICAMP Selection Contest 2024
Statement is not available in English language
A. Cubo mágico da Showpee
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lucas decidiu aproveitar uma promoção e comprou dois Cubos mágicos pela Showpee, porém, para sua surpresa ele recebeu dois objetos nem um pouco mágicos! Eram objetos de duas dimensões, portanto vamos apelidá-los de "quadrados mágicos".

Lucas tem a sua frente dois quadrados mágicos que podem ser representados por duas matrizes n por m. Em cada quadradinho (i, j) da matriz k tem um número vki, j, porque a Showpee achou mais barato escrever números do que gastar com tinta. O quadrado mágico lhe permite fazer trocas entre os quadradinhos, porém apenas se eles compartilham um lado horizontalmente ou verticalmente.

Agora Lucas se indaga, será que é possível deixar o primeiro quadrado mágico exatamente igual ao segundo apenas fazendo essas operações de troca entre quadradinhos adjacentes? Como Lucas está deprimido com sua compra furada, ele pediu sua ajuda. Por favor, não o deixe na mão!

Input

A primeira linha da entrada contém um inteiro 1 ≤ t ≤ 105, representando a quantidade de casos de teste.

Para cada um dos casos de teste, leia primeiro dois inteiros n e m, 1 ≤ n, m ≤ 105 e nm ≤ 105. Também é garantido que a soma de nm em todos os casos de teste é no máximo 105. Seguem n linhas com m inteiros v1i, j representando que o número que está escrito na linha i e coluna j do primeiro quadrado mágico. Seguem mais n linhas com m inteiros v2i, j representando o segundo quadrado mágico.

É garantido que 1 ≤ vki, j ≤ 109, para 1 ≤ k ≤ 2, 1 ≤ i ≤ n e 1 ≤ j ≤ m.

Output

Para cada caso de teste, imprima YES se é possível deixar os dois quadrados mágicos iguais e NO caso contrário.

Example
Input
4
1 1
1
2
2 2
1 2
3 4
4 3
2 1
1 2
10 20
30 10
2 1
10
20
20
10
Output
NO
YES
NO
YES
Note

Lucas pode apenas fazer a operação de troca entre quadradinhos adjacentes. Ele não pode arrancar peças, rescrever, ou rotacionar o quadrado.

Note que você só precisa dizer se é possível ou não fazer a transformação! Você não precisa dizer como.

Statement is not available in English language
B. Quadrados consecutivos
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Música.

Como toda fã de matemática, Anya adora observar o padrão em números. Hoje ela acaba de descobrir um padrão para a diferença entre quadrados consecutivos. Formalmente, dado um número n, ela está interessada na diferença (n + 1)2 - n2.

Orgulhosa com sua descoberta ela te desafia a escrever um programa que consegue achar essa diferença mesmo para números astronomicamente grandes!

Input

A primeira linha da entrada contém um único inteiro m representando a quantidade de dígitos do número n. É garantido que 1 ≤ m ≤ 106.

Segue uma linha com um inteiro positivo n de m dígitos. É garantido que o primeiro dígito de n é diferente de 0.

Output

Imprima uma única linha com o inteiro (n + 1)2 - n2, com o primeiro dígito diferente de zero.

Examples
Input
1
1
Output
3
Input
1
2
Output
5
Input
3
999
Output
1999
Input
18
123456789987654321
Output
246913579975308643
Note

Se você estiver usando Python, note que a função padrão int: str -  > int do python é quadrática, então mesmo a leitura do input da seguinte forma irá resultar em TLE:

m = int(input())
n = int(input())

Statement is not available in English language
C. Algoritmo de Euclides
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Música - Arriety's Song

Reza a lenda que Euclides inventou seu famoso algoritmo eficiente para computar o máximo divisor comum (mdc) ao ver um aluno tentando computá-lo com o seguinte algoritmo:

// Algoritmo para computar o mdc(a,b)
long long mdc(long long a, long long b){
     long long loops = 0; // contador para fins da questão apenas
     while( a != b ){
         loops++;
         if( a > b ){ 
             a-= b;
         } else{
             b-=a;
         }
     }
     return a;
}

Seu aluno estava muito feliz ao ver que esse algoritmo funcionava para números pequenos com grande eficiência. Já seu mestre não estava muito impressionado e perguntou quão eficiente seria o algoritmo se a = 1 e b = 1018. Seu aluno responde que este é apenas um caso particular, e que obviamente o máximo divisor comum é 1, logo ninguém sequer usaria um algoritmo para computar isso.

Não satisfeito, Euclides pergunta, "e se a = 6 e b = 123450, quantas operações serão feitas?".

Com desdém, o aluno responde: "Não sei, me diz você".

A lenda segue dizendo que neste momento Euclides voltou para sua casa furioso e decidiu computar quantas operações são feitas no algoritmo do seu aluno, para que ele entenda o quão ineficiente o algoritmo é. A lenda também diz que nessa jornada Euclides acabou encontrando um algoritmo muito eficiente, que faz apenas O(log(max(a, b)) operações.

Será que você também consegue computar quantas operações o algoritmo apresentado iria realizar para cada par a e b? Por operações entenda o valor de loops exposto no código acima.

Input

A primeira linha contém um inteiro t ≤ 500, a quantidade de pares que estamos interessados.

Seguem t linhas, cada uma com um par de inteiros positivos a e b, 1 ≤ a, b ≤ 1018.

Output

Imprima t linhas, cada uma representando a quantidade de laços no algoritmo do aluno para cada par a e b.

Example
Input
4
1 1
15 10
1 1000000000000000
1234500 54321001234500
Output
0
2
999999999999999
44002456
Note

Por operações entenda como o valor de loops no código de C++ exposto. long long é um tipo de dados de 64-bits in C++.

Vale notar que o algoritmo acima só funciona para números inteiros positivos, o que é o caso dessa questão.

Statement is not available in English language
D. Manipulando dados
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Fonte - climate.gov

Infelizmente, é comum a alteração de dados em experimentos na Academia como forma de obter um resultado mais expressivo. Você está interessado em saber o quão expressiva essa técnica realmente pode ser.

Para isso, você selecionou uma lista de valores Xi, representando a variação da temperatura média da cidade Melão-com-presunto ao longo de um período de n dias. Você está interessado em como uma empresa poderia manipular os dados para mostrar que a variação é praticamente constante, levando assim a conclusão de que o Aquecimento global não existe.

Para isso, você acha que um cientista poderia escolher analisar apenas k dias consecutivos para tirar as conclusões que mais lhe apeteçam. Em particular, ele irá selecionar o intervalo de k dias consecutivos com menor valor do desvio padrão.

Lembre que o desvio padrão de um conjunto Xl, Xl + 1, ..., Xr, com r - l + 1 = k, é dado por:

Em que M é a média aritmética:

Será que você consegue achar qual seria esse intervalo de dias usado por um cientista malicioso? Qual seria o desvio padrão para tal intervalo?

Input

A primeira linha da entrada tem dois inteiros n e k, representando a quantidade total de dias e o tamanho do intervalo que estamos interessados. É garantido que k ≤ n ≤ 200000.

Seguem n inteiros  - 104 ≤ Xi ≤ 104, representando a variação da temperatura do dia i em relação ao anterior em micro-celsius.

Output

Na primeira linha da saída imprima dois inteiros l e r representando que o intervalo analisado foi de Xl até Xr. Se existem muitos intervalos com o mesmo desvio padrão mínimo, imprima o intervalo com menor l.

Na segunda linha imprima um número real σ representando o desvio padrão do intervalo. Sua resposta será considerada correta se o erro relativo ou absoluto for menor ou igual a 10 - 6.

Examples
Input
7 3
1 4 2 4 7 8 9
Output
5 7
0.8164965809
Input
5 3
0 0 1 0 0
Output
1 3
0.4714045208
Input
8 2
0 10 -1 1 -1 1 -2 4
Output
3 4
1.0000000000
Note

Cuidado com erro de precisão no seu cálculo! É uma boa prática para programação competitiva, e recomendado nesse problema, fazer o máximo de contas usando apenas inteiros. Erros de precisão estão associados ao fato de que o computador precisa "truncar" os números para guardá-los na memória. É possível que um programa funcione bem para entradas pequenas, mas tenha erro de precisão para grandes entradas.

Os dados da questão são hipotéticos!

Para alguns navegadores as fórmulas não carregam, por isso elas seguem como imagem:

Fórmula do Desvio padrão
Fórmula da Média aritmética

Statement is not available in English language
E. Equação do Show Perfeito
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Musica - Backslide

A banda **Twenty Two Pilots** está planejando um show épico, e cada música que eles tocam tem um impacto específico no público, medido por um coeficiente de intensidade. O objetivo do show é alcançar exatamente um nível de intensidade total k.

Você foi escolhido para ajudar a banda a encontrar uma combinação de músicas que atenda a essa exigência. Para isso, você precisa encontrar uma solução inteira para a seguinte equação:

onde:

  • ai são os coeficientes de intensidade de cada música, fornecidos pela banda. Todos os coeficientes são inteiros positivos.
  • xi são os números inteiros que representam quantas vezes cada música será tocada no show. Esse número pode ser zero ou até negativo, pois, como sabemos, tocar uma música ao contrário ainda é uma música mas com a intensidade oposta.
  • k é a intensidade total desejada do show, dada pela banda. É garantido que k > 0 e que k é um inteiro.
Input

A primeira linha possui um número t, 1 ≤ t ≤ 103, representando a quantidade de casos de teste.

Para cada caso de teste, leia na primeira linha os inteiros n e k. É garantido que 1 ≤ n ≤ 100 e 1 ≤ k ≤ 109. Na segunda linha do caso de teste, leia n inteiros ai separados por espaço. É garantido que 1 ≤ ai ≤ 109.

Output

Para cada caso de teste imprima primeiro YES se existe solução inteira para a equação do show perfeito ou NO caso contrário. No caso da solução existir, imprima em uma segunda linha n valores inteiros separados por espaço, SEM ESPAÇO NO FINAL DA LINHA. Por razões técnicas, outputs fora do padrão receberão resposta errada!

Example
Input
4
2 5
10 15
3 1
6 10 15
3 1
2 4 2
5 5
15 6 21 27 33
Output
YES
-1 1
YES
1 1 -1
NO
NO
Note

Por favor fique atento ao formato do output para não imprimir espaços extras!

Alguns navegadores não carregaram a fórmula, então ela segue também como imagem:

Statement is not available in English language
F. Sol
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Música - Sol de ninguém

Representação do primeiro caso de teste. O ponto F representa o foco da elipse onde está a estrela em questão. Os pontos A - E são as respostas dos 5 testes na ordem em que aparecem.

Zezé adora astronomia. Hoje aprendeu na escola que a órbita dos planetas segue uma trajetória elíptica. Ele achou curioso especialmente a segunda lei de Kepler que diz que para um tempo constante a área varrida pela órbita de um planeta também é constante, independente da posição inicial do planeta.

Ele quer comprovar experimentalmente essa lei, e para isso lhe pediu que diga exatamente em qual posição um planeta estará ao ter coberto exatamente p% da área disponível. Você sabe que o planeta começa no eixo x, com x > 0, que a estrela que o planeta orbita está no eixo x, do lado oposto, x < 0, e que o planeta rotaciona no sentido anti-horário. Zezé também vai lhe dar o valor dos eixos da elipse b e c. Veja as imagens para esclarecimento, que representam os pontos da primeira entrada do exemplo.

Representação da área varrida pela órbita do planeta do início até o momento em que ele chega no ponto C. É possível mostrar que a área em amarelo representa 20% da área total da elipse.

Para lhe ajudar, ele decidiu te dar também a fórmula da elipse. Seja a2 = b2 + c2, temos que a elipse é descrita por:

Com essas informações você consegue ajudar Zezé a localizar o planeta?

Input

Na primeira linha leia um inteiro t ≤ 500, a quantidade de casos de testes.

Para cada um dos t casos de teste leia duas linhas. A primeira linha contém 2 inteiros b c, representando os parâmetros da elipse, e a segunda linha contem um inteiro p, a porcentagem de área da elipse que deve ser coberta. É garantido que 1 ≤ b, c ≤ 106 e que 0 ≤ p ≤ 100.

Output

Para cada caso de teste imprima 2 números reais x e y, representando as coordenadas do planeta. A sua resposta será aceita se o erro absoluto ou relativo for menor ou igual a 10 - 6.

Example
Input
5
1 1
0
1 1
10
1 1
20
1 1
50
1 1
100
Output
1.4142135624 0.0000000000
1.3177013994 0.3630860931
1.0189297472 0.6934631102
-1.4142135624 0.0000000000
1.4142135624 -0.0000000000
Note

Alguns navegadores não carregaram a fórmula, então ela segue também como imagem:

Equação da elipse

Statement is not available in English language
G. Pulos perdidos
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Música - Navigating

Tyler tem um sapo muito curioso. Ele gosta de superar seu recorde de tamanho de pulos, e por isso, todo dia começa a manhã com um pulo de distância 1nm, depois de 2nm até pulos muito grandes da ordem de 250nm (sim, ele consegue pular praticamente um ano luz!). Ou seja, o tamanho do pulo dobra a cada pulo, começando de 1 nanômetro.

Tyler também é muito curioso e um dia decidiu anotar todos os pulos do sapo, do primeiro ao último. Para isso, você pode considerar que o sapo faz pulos em uma reta, e sempre está em coordenadas inteiras, as quais são anotadas por Tyler.

Feliz ele resolveu levar as anotações para sua escola. Para sua surpresa, no dia seguinte, seu irmão mais novo Josh, que não sabia o que eram os números, cortou o papel em pedaços cada um com uma das anotações, e comeu alguns dos pedaços de papel.

Agora tudo que Tyler tem são algumas das anotações, em uma ordem arbitrária. Quando reclamou ao seu irmão, este lhe disse que não comeu nem o primeiro nem o último número. Será que você consegue ajudar Tyler a encontrar uma sequência válida de posições condizentes com os pulos do sapo?

Input

A entrada consiste de vários casos de teste. Na primeira linha leia um inteiro t ≤ 50 representando a quantidade de casos de teste.

Após, para cada caso de teste leia um inteiro 1 ≤ n ≤ 51, a quantidade de anotações que restaram. Seguem n inteiros p1, p2, ..., pn representando as posições anotadas em nanômetros. É garantido que  - 1018 ≤ pi ≤ 1018.

Output

Para cada caso de teste imprima primeiro a quantidade total de anotações 1 ≤ n ≤ q ≤ 51 e na linha seguinte q inteiros a1, a2, ...aq representando as posições do sapo. Você deve garantir que o primeiro e o último número estão entre as anotações de Tyler. Além disso, deve garantir que  - 2·1018 ≤ ai ≤ 2·1018. Devido ao validador especial, por favor não imprima espaços ou linhas extras!.

É garantido que uma resposta sempre existe para os casos gerados. É garantido que os pulos tem tamanho no máximo 250.

Examples
Input
2
3
15 16 22
1
-1000000000000000000
Output
4
15 16 18 22
1
-1000000000000000000
Input
3
3
1 0 7
3
-1 0 -5
3
0 -5 -1
Output
4
0 1 3 7
4
0 1 -1 -5
4
0 1 -1 -5
Note

Créditos da imagem

Note que é possível que n = 1. Neste caso o sapo foi muito preguiçoso e não fez nenhum pulo :(

Note também que Josh pode ter na verdade comido 0 pedaços de papel, e estava apenas pregando uma peça em Tyler.

Statement is not available in English language
H. Árvore de Strings
time limit per test
1.2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Música - Reason

Gon está prestes a subir a Árvore do Mundo, uma árvore com mais de 1700m de altura. Como Gon adora árvores e vai passar bastante tempo escalando, ele decidiu resolver a seguinte questão sobre uma outra árvore mágica:

Considere uma árvore enraizada no vértice 1 com uma letra escrita em cada aresta. Considere agora para todo par de vértices u e v em que u é ancestral direto ou indireto de v. O caminho de u para v pode ser representado por uma série de k arestas e1, e2, ..., ek. Seja cei o caractere escrito na aresta ei. Definimos s(u, v) como a string formada pelas arestas ei na ordem que aparecem: s(u, v) = ce1 + ce2 + ... + cek, em que  +  representa a concatenação dos caracteres.

Para cada nó u imprima o tamanho da maior string lexicograficamente que começa em u. Ou seja, entre todos os v tal que u é ancestral de v, seja s(u, v * ) a maior string lexicograficamente. Imprima |s(u, v * )|.

Também imprima na linha seguinte a maior string lexicograficamente entre todas as possíveis. Ou seja, maxu ancestral de v(s(u, v)).

Input

A primeira linha contém um inteiro t ≤ 2·105, representando a quantidade de casos de teste. Cada caso de teste segue no seguinte formato:

Na primeira linha leia o tamanho da árvore n, 1 ≤ n ≤ 2·105. Por fim, seguem n - 1 linhas com um inteiro pi e um caracter ci, representando uma aresta direcionada de pi para i + 1, com 1 ≤ i < n. É garantido que para todo i, pi < i + 1 e que ci é uma letra latina minúscula (de "a" até "z").

Também é garantido que a soma de n nos casos de teste é no máximo 2·105.

Output

Para cada um dos casos de teste imprima primeiro uma linha com n caracteres, representando o tamanho da maior string que começa no nó i, para 1 ≤ i ≤ n, nessa ordem. Na linha seguinte imprima a maior string lexicograficamente que pode ser obtida, entre todos os pares de vértices u e v, em que u é ancestral de v.

Examples
Input
2
5
1 b
1 a
3 b
4 a
5
1 a
2 b
3 a
3 a
Output
1 0 2 1 0
ba
3 2 1 0 0
ba
Input
3
5
1 a
1 d
2 a
4 b
5
1 c
2 d
1 c
3 c
5
1 c
1 d
3 a
4 b
Output
1 2 0 1 0
d
3 2 1 0 0
dc
3 0 2 1 0
dab

Statement is not available in English language
I. Desafio para o ChatGPT
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Música - Midwest Indigo

Na faculdade aprendemos um conceito chamado "Árvore Geradora Mínima". Ela consiste em achar um subconjunto de arestas de um grafo de modo que as arestas formem uma árvore (grafo conexo, que conecta todos os vértices, e acíclico), e com menor soma total dos pesos.

Fábio quer passar essa questão para seus alunos, mas como hoje me dia o ChatGPT consegue resolver a questão ele resolveu deixar um pouco mais complicado. A questão é a seguinte:

É dada uma árvore T de n vértices com peso nas arestas e nos vértices. Os pesos nos vértices são dados por uma sequência pi, para 1 ≤ i ≤ n.

Defina um novo grafo G completo, em que existe uma aresta de u para v com peso w(u, v) = p(u) + d(u, v) + p(v), sendo d(u, v) a distância de u e v em T. Ou seja, d(u, v) é a soma dos pesos das arestas no menor caminho de u até v na árvore T, enquanto w(u, v) é d(u, v) somado aos pesos dos vértices u e v.

Você deve encontrar o custo da árvore geradora mínima de G.

Será que você consegue se provar mais inteligente que o Chat-GPT e resolver essa questão?

Input

A primeira linha do input contém um inteiro n, 1 ≤ n ≤ 3·105, representando o número de vértices em T.

Seguem n inteiros pi, 1 ≤ pi ≤ 109.

Por fim, seguem n - 1 linhas ui vi wi representando uma aresta de T de ui para vi com peso wi. É garantido que T é uma árvore e que 1 ≤ wi ≤ 109.

Output

Imprima um único inteiro representando o custo da árvore geradora mínima de G.

Examples
Input
4
1000 1 10 100
1 2 1
1 3 2
1 4 3
Output
1121
Input
4
1 2 3 4
1 2 1
2 3 100
3 4 1
Output
117