Maratona dos Bixes 2023 - UNICAMP
A. Distribuindo doces
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

É Halloween e você tem K doces e quer distribuir todos eles para N crianças. Você sabe que uma criança ficará triste se receber estritamente menos que L doces. Além disso, você se preocupa pela saúde delas e não quer dar mais de R doces para nenhuma criança, pois se sentiria triste e culpado. Existe alguma maneira de distribuir todos os seus K doces sem deixar ninguém triste, nem você nem uma criança?

Input

A entrada é uma única linha com 4 inteiros N, K, L, R. É garantido que 1 ≤ N ≤ 103, 1 ≤ K ≤ 106 e 0 ≤ L ≤ R ≤ 105. Adicionalmente, N·R ≤ 108.

Output

Imprima, em uma única linha, o caracter 'S' se for possível distribuir todos os doces dadas as restrições e 'N' do contrário. Não imprima 'N' e 'S' com as aspas.

Examples
Input
1 2 2 4
Output
S
Input
2 1 6 10
Output
N
Input
3 9 3 3
Output
S
Input
3 10 3 3
Output
N

B. Triplas pitagóricas
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Marcinho estava estudando seu livro de geometria quando encontrou esse fato interessante: "Dizemos que uma tripla de inteiros (a, b, c) é pitagórica se a2 + b2 = c2". Incrivelmente, todas as triplas podem ser achadas com a fórmula abaixo, substituindo m, n por inteiros, com m > n:

a = m2 - n2,  b = 2mn,  c = m2 + n2.

Marcinho ficou muito curioso e quis testar essa fórmula. Dados m e n, retorne a tripla (a, b, c) na ordem indicada no livro.

Input

A entrada consiste de uma linha com dois inteiros m, n nessa ordem. É garantido que 1 ≤ n < m ≤ 104.

Output

Uma única linha com os inteiros a, b e c separados por espaço.

Examples
Input
2 1
Output
3 4 5
Input
3 2
Output
5 12 13
Note

4 3 5 não é uma resposta aceitável para o exemplo. Imprima a, b, c na ordem descrita pela fórmula de Marcinho.

C. Martelo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eren Yeager está na origem da reta real. Ele quer atingir seu objetivo de chegar na coordenada X.

Há uma muralha na coordenada Y, que Eren não consegue passar a princípio.

Felizmente, depois de pegar um martelo na coordenada Z, ele consegue destruir a muralha e passar por ela.

Determine se Eren consegue atingir seu objetivo. Se ele conseguir, ache a menor distância que ele precisa viajar para fazer isso.

Input

A entrada é dada por uma linha com 3 inteiros X, Y, Z, satisfazendo:

  •  - 1000 ≤ X, Y, Z ≤ 1000,

  • X, Y e Z são distintos e nenhum deles é 0.
Output

Se Eren conseguir atingir seu objetivo, imprima a menor distância que ele precisa percorrer. Caso contrário, imprima  - 1.

Examples
Input
10 -10 1
Output
10
Input
20 10 -10
Output
40
Input
100 1 1000
Output
-1
Input
-678 -666 -518
Output
678
Input
-22 55 -163
Output
22

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

Na disciplina de Desafios de Programação, foi aplicada uma prova com 3 problemas: o primeiro valendo 1 ponto, o segundo valendo 2 pontos e o terceiro valendo 4 pontos.

Lucca, Yvens e Passinho fizeram essa prova. Lucca obteve L pontos e Yvens obteve Y pontos.

Passinho sentou-se entre Lucca e Yvens e, coincidentemente, resolveu todos problemas que foram resolvidos por pelo menos um dos dois, mas não resolveu nenhum problema que nenhum dos dois resolveu.

Encontre a pontuação de Passinho.

Pode ser provado que a pontuação de Passinho é unicamente determinada sob as restrições deste problema.

Input

A entrada consiste de uma única linha contendo dois inteiros L e Y separados por um espaço. É garantido que 0 ≤ L, Y ≤ 7.

Output

Imprima uma linha com um único inteiro, a pontuação de Passinho.

Examples
Input
0 0
Output
0
Input
1 2
Output
3
Input
5 3
Output
7
Input
2 5
Output
7
Input
2 6
Output
6

E. Copos
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Anissa adora copos de água nos mais diversos formatos. Hoje ela decidiu criar um copo que suporta exatamente V ml de água. Ela quer que seu copo seja um paralelepípedo com cada um dos lados tendo um tamanho inteiro de centímetros. Lembre-se que 1 ml = 1 cm3.

Mas como ela se preocupa no tempo gasto para lavar o copo após o uso, ela quer o copo com a menor área de superfície.

Lembre-se que para um paralelepípedo de lados (a, b, c), a área da supérficie é dada por:

S = 2(ab + ac + bc).
Input

Um único inteiro 1 ≤ V ≤ 106.

Output

Imprima em uma linha um único inteiro S: a menor área da superfície dentre as de todos os paralelepípedos de lados com tamanho inteiro e volume V.

Examples
Input
1
Output
6
Input
6
Output
22
Input
240
Output
236
Input
1000000
Output
60000

F. Pegadinha
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

No prédio da Nlogônia, moram N pessoas. De noite, todas decidiram fazer uma pegadinha e apertar o interruptor das lâmpadas dos vizinhos. A primeira pessoa vem e aperta os interruptores dos andares 1, 2, 3, ..., N, a segunda dos andares 2, 4, 6, ..., a terceira dos andares 3, 6, 9, ... e assim por diante.

Inicialmente todas as lâmpadas estavam desligadas. Agora você está encarregado de desligar todas as lâmpadas acesas por essa traquinagem.

Observação: O valor da entrada é grande. Caso esteja recebendo Time Limit Exceeded é possível que você tenha que repensar se não há como ter uma ideia mais otimizada.

Input

A entrada consiste em uma unica linha com um inteiro N. É garantido que 1 ≤ N ≤ 108.

Output

Imprima todos os andares que voce deve desligar, um por linha e em ordem crescente.

Examples
Input
3
Output
1
Input
6
Output
1
4
Input
1
Output
1
Note

Por exemplo, para N = 6 temos o seguinte padrão, em que 0 representa luz desligada naquela posição e 1 ligada:

Início: 000000

(1) 111111 (todas as lâmpadas foram ligadas)

(2) 101010 (lâmpadas 2,4,6 foram desligadas)

(3) 100011 (lâmpada 3 desligada, lâmpada 6 ligada)

(4) 100111 (lâmpada 4 ligada)

(5) 100101 (lâmpada 5 desligada)

(6) 100100 (lâmpada 6 desligada)

No final apenas as lâmpadas nas posições 1 e 4 estão ligadas.

G. Presentes de Páscoa
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fred, que mora em Natal-RN, esqueceu novamente os presentes de Páscoa. Seus priminhos estão esperando e ele precisa correr.

Fred entrou em uma loja onde existem exatamente N ovos de chocolate. O valor do i-ésimo ovo é Pi centavos. Ele não lembra quantos primos tem então quer comprar o máximo de presentes que seu dinheiro permitir. Fred olha para o seu bolso e vê que tem exatamente C centavos. Ajude ele a comprar o máximo possível de presentes e salvar a páscoa!

Input

A primeira linha da entrada contém um inteiro 1 ≤ N ≤ 105. A segunda linha contém um inteiro 1 ≤ C ≤ 108 e a terceira e última linha contém N inteiros 1 ≤ Pi ≤ 105.

Output

Imprima um único inteiro na saída: o número máximo de ovos que Fred pode comprar.

Examples
Input
4
15
1 2 3 5
Output
4
Input
5
10
1 9 4 6 3
Output
3

H. Shrek II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Shrek e o Burro decidiram jogar um jogo que o próprio Shrek inventou para passar o tempo.

Inicialmente, Shrek coloca uma quantidade de moedas em uma pilha e depois em outra, de modo que a primeira pilha tenha A moedas e a segunda B moedas. A partir daí eles jogam alternados, com o Burro começando.

Em um turno o jogador deve tirar exatamente 1 moeda de uma das pilhas ou das duas pilhas. Note que ele não pode pular a vez. Quem tirar a última moeda ganha, sem importar quem tirou mais moedas.

Por exemplo, se A = 2 e B = 1, um possível jogo seria:

  1. O Burro tira uma moeda de A e outra de B. Agora, A = 1 e B = 0.

  2. Shrek tira uma moeda de A. Agora, A = 0 e B = 0. Logo, Shrek ganhou.

Após um tempo jogando eles percebem que existe uma estratégia ótima, que pode garantir a vitória independente das jogadas do adversário. Seu objetivo é, dado A e B, dizer se há como garantir a vitória e, se for o caso, qual deve ser sua primeira jogada para garanti-la.

Por exemplo, se A = 2 e B = 2, é possível mostrar que Shrek sempre ganha caso os dois joguem com uma estratégia ótima. Já para A = 1 e B = 1, o Burro sempre ganha (pois pode tirar ambas as moedas na primeira jogada).

Input

A entrada contém dois inteiros separados por espaço A e B, 0 ≤ A, B ≤ 109.

Output

Você joga como se fosse o Burro. Se for impossível garantir a vitória, imprima simplesmente 'N'. Se for possível, imprima um 'S' e na linha seguinte indique de quais pilhas deve retirar as moedas na primeira jogada: imprima A se só da primeira, B se só da segunda ou A B se de ambas. (Não imprima 'N' e 'S' com as aspas)

Examples
Input
1 0
Output
S
A
Input
1 1
Output
S
A B
Input
2 1
Output
S
B
Input
2 2
Output
N
Input
2 0
Output
N

I. Fila da cantina
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Assim que o alarme do recreio tocou, a diretora da escola de Nlogônia observou seus alunos formarem uma fila na cantina. Ela viu que algumas crianças demoram muito para escolher seu pedido se estão no início da fila assim que o recreio começa, enquanto outras já vem com o pedido pronto na cabeça. Após análise cuidadosa, ela encontra a posição ideal para cada criança pi.

Assim que o recreio começa, ela observa as crianças novamente. Para ela, seria perfeito se a criança na 1ª posição fosse aquela com pi = 1, na segunda com pi = 2 etc. Mas esse não é o caso.

Para ajudar a tornar a fila ordenada, a diretora pode pedir a duas crianças, em quaisquer posições da fila, para que troquem de lugar. Assim que elas tiverem trocado, ela pode fazer o mesmo para outro par de crianças, até que a fila esteja ordenada. Qual o menor número de operações de troca para que isso aconteça?

Input

Na 1ª linha, leia um único inteiro N, o número de crianças. Segue uma linha com 1 ≤ N ≤ 103 inteiros pi indicando que a criança na i-ésima posição da fila deve ficar na posição pi após a ordenação.

Output

Imprima um único inteiro: a quantidade mínima de trocas para reordenar as crianças.

Examples
Input
4
2 1 4 3
Output
2
Input
4
1 2 3 4
Output
0
Input
3
2 3 1
Output
2
Input
3
3 2 1
Output
1
Note

Por exemplo, se p = {2, 1, 4, 3}, podemos primeiro trocar as crianças nas posições 1 e 2. Agora p = {1, 2, 4, 3} e as 2 primeiras crianças da fila já estão nas suas posições desejadas. Após trocar as crianças nas posições 3 e 4, temos que p = {1, 2, 3, 4} e a ordenação foi atingida.

J. Butão
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Naim gosta muito de jogos e sempre que vê seu amigo Morato propõe algum tipo de desafio. Dessa vez Morato foi desafiado a resolver o seguinte problema.

Naim o entregou um dispositivo que possui uma tela e um butão. A tela sempre mostra apenas um número: 0, 1 ou 2, e começa mostrando o número 0. Quando a tela está mostrando o número k e o butão é apertado, a tela passa a mostrar o número ak. Ajude Morato a responder as duas seguintes perguntas:

  • Quantas vezes é preciso apertar o butão para que algum número apareça pela segunda vez?
  • Qual número vai estar na tela após Morato apertar o butão N vezes?
Input

A primeira linha contém um inteiro N, 1 ≤ N ≤ 109, o número de vezes que Morato vai apertar o butão. A segunda linha contém 3 inteiros a0, a1, a2, 0 ≤ a0, a1, a2 ≤ 2, a lista de inteiros descrita no enunciado.

Output

Imprima duas linhas. A primeira representa a resposta para a primeira pergunta e a segunda representa a resposta para a segunda pergunta.

Examples
Input
2
1 2 0
Output
3
2
Input
1439287
1 0 1
Output
2
1
Input
1000000000
1 2 0
Output
3
1
Input
3
1 2 1
Output
3
1
Input
1000
1 2 2
Output
3
2
Note

Por exemplo, se a = {1, 2, 0}. Temos o seguinte fluxo:

Inicialmente o número é 0. Após apertar 1 vez o número passa as ser a0 = 1.

Após a 2 vez passa a ser a1 = 2. Após 3 vezes a2 = 0 e assim por diante.

K. Picolés e triângulos
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magali adora picolés. Quando ela termina de comer, ela dá o palito para Cebolinha, que tenta montar um triângulo com os palitos que já lhe foram dados. Assim que ele consegue montar, cebolinha sai satisfeito.

Você deve dizer quantos palitos Cebolinha tinha no momento em que ele concluiu seu triângulo ou dizer se isso nunca acontecer.

Input

A primeira linha contém um inteiro N, 1 ≤ N ≤ 5·107, o número de palitos comidos por Magali. Seguem N linhas, a i-ésima com um inteiro pi, 1 ≤ pi ≤ 1018, o tamanho dos palitos, em cm, na ordem que Magali os come (e dá para Cebolinha).

Note que alguns palitos podem ser MUITO grandes. Se estiver usando C/C++/Java use inteiros de 64-bits (long long para C++). Para Python não tem problema.

Output

Um inteiro K que diz quantos palitos o Cebolinha tinha quando ele finalmente montou seu triângulo ou -1 caso ele nunca consiga.

Examples
Input
6
1
1
2
3
1
2
Output
5
Input
3
1
2
3
Output
-1
Input
2
5
5
Output
-1
Input
3
100000000000000000
100000000000000000
100000000000000001
Output
3
Note

Por exemplo, se Magali comeu, nessa ordem, palitos de tamanho 1,1,2,3,1,1. Apenas após o 5º palito ele consegue formar um triângulo, usando os palitos {1,1,1}. Note que com os palitos de tamanho {1,1,2} é possível formar um "triângulo degenerado" (uma reta), mas isso não conta!