53 Problemas de Programacao
53 Problemas de Programacao
53 Problemas de Programacao
Problemas de Programação
Edição 2009
(Versão Preliminar – 20091209)
Sumário
Nível iniciante......................................................................................................................................1
1 Problema da soma.........................................................................................................................2
2 Problema da média........................................................................................................................3
3 Problema do número espelho........................................................................................................4
4 Problema da sequência de Fibonacci............................................................................................5
5 Problema da conjectura de Goldbach...........................................................................................6
6 Problema do quadrado gêmeo das partes......................................................................................7
7 Problema da soma reservada.........................................................................................................9
8 Problema dos casais....................................................................................................................10
9 Problema dos sucessores.............................................................................................................11
10 Problema do quadrado perfeito.................................................................................................12
11 Problema da competição alien..................................................................................................13
Nível intermediário.............................................................................................................................14
1 Problema das sequências alternadas...........................................................................................15
2 Problema da letra mais frequente................................................................................................17
3 Problema do giro da palavra.......................................................................................................19
4 Problema da palavra mágica.......................................................................................................21
5 Problema do conjunto e seus elementos únicos..........................................................................23
6 Problema da moda......................................................................................................................25
7 Problema da simplificação das frações.......................................................................................27
8 Problema do colecionador de moedas........................................................................................28
9 Problema da transmissão de rádio..............................................................................................29
10 Problema da idade em dias.......................................................................................................30
11 Problema da separação das sílabas (versão light).....................................................................32
12 Problema da codificação da string............................................................................................34
13 Problema do professor de matemática caxias...........................................................................36
14 Problema da competição de ciclismo........................................................................................39
15 Problema do baile de casais......................................................................................................41
16 Problema do TMA....................................................................................................................43
17 Problema do tesouro real..........................................................................................................44
18 Problema da escrita no celular..................................................................................................46
19 Problema do checksum.............................................................................................................48
20 Problema das operações com conjuntos...................................................................................49
21 Problema do decifrador de senhas............................................................................................51
22 Problema da operação entre números binários.........................................................................53
23 Problema da sopa de letras na formação de palavras................................................................54
24 Problema do número binariamente contido..............................................................................56
25 Problema das placas com anagrama perfeito............................................................................57
Nível avançado...................................................................................................................................58
1 Problema da sequência de algarismos agrupados com ordenação..............................................59
2 Problema do professor de terceiro ano.......................................................................................60
3 Problema da prefeitura em crise.................................................................................................62
4 Problema da separação das sílabas.............................................................................................65
5 Problema da sexta-feira treze......................................................................................................69
6 Problema do arranjo dos caracteres............................................................................................70
7 Problema da cifra no DNA.........................................................................................................72
8 Problema do grafo conexo..........................................................................................................74
9 Problema do dicionário de sinônimos.........................................................................................75
10 Problema da matriz do Paint.....................................................................................................79
11 Problema da memória transacional...........................................................................................81
12 Problema do palíndromo...........................................................................................................82
13 Problema dos fazendeiros trabalhadores...................................................................................84
14 Problema do teste oftálmico para programadores.....................................................................85
15 Problema da grade de programação..........................................................................................88
16 Problema da permutação...........................................................................................................90
17 Problema da caminhada perfeita...............................................................................................91
Prefácio
A ideia inicial deste material foi construída quando eu tive o prazer de lecionar a disciplina
Laboratório de Programação II para os alunos do curso de Ciências da Computação da
Universidade Federal da Bahia. O desafio naquele momento era trabalhar problemas de
programação típicos de competição.
Os frutos do trabalho me fizeram perceber que o modelo adotado poderia ser utilizado em
outros cursos que objetivassem desenvolver a lógica ou aproximar o estudante de uma
linguagem de programação. Percebi que os alunos gostavam da proposta e se sentiam
desafiados e motivados.
A compilação apresentada aqui é um pouco daquilo que consegui construir na docência
de dois semestres em cursos de programação e linguagem. Tenho em muito a agradecer
aos alunos que participaram de todo o processo, elogiando, criticando, reportando
problemas e sugerindo esclarecimentos.
Organizei os problemas em nível de dificuldade conforme a minha avaliação e julgamento.
A sugestão é que o leitor leia primeiro o problema por inteiro e depois decida se está
pronto ou não para desenvolver uma solução.
Salvador, 09 de novembro de 2009.
53 Problemas de Programação – Prof. Adonai Medrado 1
Nível iniciante
53 Problemas de Programação – Prof. Adonai Medrado 2
1 Problema da soma
Faça um programa capaz de solicitar um número N (1<N<1000) do usuário e ler N
números inteiros. Após a leitura do último número deve-se informar:
• Na primeira linha a soma dos N números em decimal.
• Na segunda linha a soma em hexadecimal dos números pares informados.
• Na terceira linha a soma em octal dos números impares informados.
Assuma que todos os números fornecidos pelo usuário serão inteiros válidos e que as
somas nunca serão superiores a um número inteiro de 32 bits.
Exemplo 1
Entrada
3
1
2
3
Saída
6
2
4
Exemplo 2
Entrada
10
1
2
3
4
5
6
7
8
9
0
Saída
45
14
31
53 Problemas de Programação – Prof. Adonai Medrado 3
2 Problema da média
Faça um programa capaz de solicitar um número inteiro N (1<N<1000) do usuário e ler N
números inteiros. Ao final da leitura do último número, o programa deverá informar, com
uma casa decimal, a média aritmética entre os N números que estejam contidos no
intervalo fechado entre -1000 e 1000.
Assuma que todos os números fornecidos pelo usuário serão inteiros válidos e que a
soma de todos os N nunca será superior a um número inteiro de 32 bits.
Exemplo 1
Entrada
2
3
4
Saída
3.5
Exemplo 2
Entrada
3
3
1001
4
Saída
3.5
Exemplo 3
Entrada
3
3
-1999
3
Saída
3.0
53 Problemas de Programação – Prof. Adonai Medrado 4
Exemplo 1
Entrada
1E1B9
Saída
S
Exemplo 2
Entrada
1E240
Saída
N
53 Problemas de Programação – Prof. Adonai Medrado 5
Exemplo 1
Entrada
20
Saída
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
Exemplo 2
Entrada
1
Saída
0
53 Problemas de Programação – Prof. Adonai Medrado 6
Exemplo 1
Entrada
720
Saída
11
709
Exemplo 2
Entrada
666
Saída
5
661
53 Problemas de Programação – Prof. Adonai Medrado 7
Os números que têm esta propriedade são conhecidos como número de Kaprekar.
Cada um dos números apresentados tiveram seus algarismos decompostos de tal forma
que a soma das partes elevado ao quadrado era igual ao número original.
Faça um programa capaz de ler e identificar se um determinado número N
(1<=N<=100.000.000) possui ou não esta propriedade. Caso positivo, o programa deverá
retornar uma única linha com o valor 1, caso contrário deve-se retornar uma linha com
valor 0.
Exemplo 1
Entrada
60481729
Saída
1
Exemplo 2
Entrada
60481728
Saída
0
53 Problemas de Programação – Prof. Adonai Medrado 8
Exemplo 3
Entrada
300814336
Saída
1
Exemplo 4
Entrada
88200
Saída
0
53 Problemas de Programação – Prof. Adonai Medrado 9
Exemplo 1
Entrada
1000
1200
Saída
22
Exemplo 2
Entrada
5
130000
Saída
63
Exemplo 3
Entrada
5
130000
Saída
63
Exemplo 1
Entrada
6
1 2 3 4 5 6
Saída
S
Exemplo 2
Entrada
8
1 3 5 7 9 11 13 15
Saída
N
Exemplo 3
Entrada
4
1 2 3 4
Saída
S
Exemplo 4
Entrada
6
1 2 3 4 8 7
Saída
S
53 Problemas de Programação – Prof. Adonai Medrado 11
Exemplo
Entrada
1
2
3
4
5
6
7
8
9
10
0
Saída
2
3
4
5
6
7
8
9
10
11
53 Problemas de Programação – Prof. Adonai Medrado 12
Exemplo 1
Entrada
2
3
4
5
6
7
8
9
0
Saída
2
Exemplo 2
Entrada
4
9
16
144
0
Saída
4
53 Problemas de Programação – Prof. Adonai Medrado 13
Exemplo 1
Entrada
3
sss.aasd.sss...
Saída
2
Exemplo 2
Entrada
2
123123kj244141hm22242420+-
xx....sadf...dfadfa..sd.
Saída
4
Exemplo 3
Entrada
5
asdfg..lk..ujjmjh...lkium
Saída
2
53 Problemas de Programação – Prof. Adonai Medrado 14
Nível intermediário
53 Problemas de Programação – Prof. Adonai Medrado 15
Exemplo
Entrada
4
87
55
34
0
53
21
8
61
82
9
80
78
1
10
99
4
78
43
71
23
Saída
0 34 53 55 87
82 61 21 9 8
1 10 78 80 99
78 71 43 23 4
Variação 1
Resolva o mesmo problema só que assuma que o número de elementos em cada
seqüência pode variar.
• Antes de cada sequência o usuário informá qual o número de elementos da
sequência.
Variação 2
Resolva o mesmo problema só que desta vez imprima na saída a sequência:
• Em ordem crescente, quando nenhum elemento da sequência for primo.
53 Problemas de Programação – Prof. Adonai Medrado 16
Variação 3
Resolva o mesmo problema alternando a ordem crescente e decrescente, só que faça a
ordenação de acordo com o peso P definido abaixo.
• O peso P de cada elemento será a quantidade de divisores inteiros positivos que
ele possui.
53 Problemas de Programação – Prof. Adonai Medrado 17
A entrada será uma cadeia de caracteres sem espaços de no máximo 1000 caracteres. A
saída deverá ser a(s) letra(s) mais frequente(s) seguida por sua porcentagem com duas
casas decimais.
Deve-se desconsiderar diferenças de maiúsculas e minúsculas.
Qualquer outro caractere que não seja uma letra de A a Z deverá ser desconsiderado no
cálculo da porcentagem e na contagem. A saída deve ser dada em letras minúsculas.
Exemplo 1
Entrada
aabc
Saída
a 50.00%
Exemplo 2
Entrada
aabcc
Saída
a 40.00%
c 40.00%
Exemplo 3
Entrada
aabcc
Saída
a 40.00%
c 40.00%
Exemplo 4
Entrada
asl;dzc]ewa;d]sd.vcxhkjasdfa]]bkjolnn
opuibuiopjl;
Saída
a 9.76%
d 9.76%
53 Problemas de Programação – Prof. Adonai Medrado 19
Exemplo 1
Entrada
programacao
programacao
Saída
1
Exemplo 2
Entrada
programacao
rogramacaop
Saída
1
O mesmo resultado é esperado para: ogramacaopr, gramacaopro, ramacaoprog,
amacaoprogr, macaoprogra, acaoprogram, caoprograma, aoprogramac, oprogramaca e
macaoprogra.
Exemplo 3
Entrada
papagaio
opapagai
53 Problemas de Programação – Prof. Adonai Medrado 20
Saída
1
O mesmo resultado é esperado para: apagaiop, pagaiopa, agaiopap, gaiopapa, aiopapag,
iopapaga e papagaio.
Exemplo 4
Entrada
papagaio
opapagia
Saída
0
53 Problemas de Programação – Prof. Adonai Medrado 21
Exemplo 1
Entrada
popo
Saída
N
Exemplo 2
Entrada
gugu
Saída
S
Exemplo 3
Entrada
tutu
53 Problemas de Programação – Prof. Adonai Medrado 22
Saída
S
Exemplo 4
Entrada
aaaaa
Saída
N
Exemplo 5
Entrada
tatatt
Saída
S
Exemplo 6
Entrada
gramados
Saída
N
53 Problemas de Programação – Prof. Adonai Medrado 23
Exemplo 1
Entrada
10
10
10
9
9
8
8
7
7
6
6
Saída
6
7
8
9
10
Exemplo 2
Entrada
5
-1
-1
-1
-1
-1
Saída
-1
Exemplo 3
Entrada
5
-123
123
999
1000
53 Problemas de Programação – Prof. Adonai Medrado 24
-1000
Saída
-1000
-123
123
999
1000
53 Problemas de Programação – Prof. Adonai Medrado 25
6 Problema da moda
A moda é o conjunto formado pelos elementos com a maior frequência em uma amostra.
Por exemplo, na amostra (1,2,3,3,3,4,4,4,4,5) a moda é {4}, na amostra
(1,1,1,2,2,2,3,4,5,5,6) a moda é {1,2}.
Faça um programa capaz de calcular a moda de uma amostra de dados K.
A entrada será um número indefinido de elementos de K um por linha.
A saída deverá ser os elementos K pertencentes à moda em ordem crescente um em
cada linha.
K terá como elementos números inteiros positivos entre 0 e 256, sendo que o número
zero identifica o fim da entrada de dados.
Exemplo
Entrada
256
1
5
91
83
256
4
5
60
7
8
29
42
8
42
24
5
42
256
0
Saída
5
42
256
Variação 1
Considere que K terá como elementos números inteiros entre -2147483648 e
2147483647, sendo que o número zero identifica o fim da entrada de dados.
Exemplo
Entrada
1
5
53 Problemas de Programação – Prof. Adonai Medrado 26
91
83
2
467
4
467
5
60
7
8
467
29
42
8
42
24
5
42
0
Saída
5
42
467
Variação 2
K terá como elementos cadeias de caracteres sem espaço com no máximo 50 caracteres,
sendo que a cadeia "0" (sem as aspas) identifica o fim da entrada de dados.
53 Problemas de Programação – Prof. Adonai Medrado 27
Exemplo
Entrada
0 1
1 1
2 2
2 4
9 3
25 625
0 0
Saída
0 1
1 1
1 1
1 2
3 1
1 25
53 Problemas de Programação – Prof. Adonai Medrado 28
Exemplo
Entrada
5
9
4
7
8
17
2
4
0
Neste exemplo:
• Nv=5.
• Nc=2.
• Conforme o vetor V, o valor da moeda "0" é $9, da moeda "1" é $4, da moeda "2" é
$7, da moeda "3" é $8, da moeda "4" é $17.
• Conforme o vetor C, o colecionador possui a moeda "0" e "4", que custam
respectivamente $9 e $17 conforme consta no vetor V.
Saída
3
Exemplo 1
Entrada
90c87esd67uj,./';*&^120lin87uj101gu87km102a77jh150gem..&
Saída
linguagem
Exemplo 2
Entrada
*(12*23qualquer130i120n87j102t87ejh104er*&^_)(105n7k122e33kw140t**
Saída
internet
53 Problemas de Programação – Prof. Adonai Medrado 30
Exemplo 1
Entrada
21
9
1981
Saída
10006
(Considerando dia 12/02/2009)
Exemplo 2
Entrada
31
7
1981
Saída
10058
(Considerando dia 12/02/2009)
53 Problemas de Programação – Prof. Adonai Medrado 31
Exemplo 3
Entrada
1
3
2004
Saída
1809
(Considerando dia 12/02/2009)
Outros exemplos
Você pode gerar mais casos de teste para a data atual em:
http://www.peterrussell.com/age.php
53 Problemas de Programação – Prof. Adonai Medrado 32
Exemplo 1
Entrada
p2r4o5g2r4a5ma7ção
Saída
programa-ção
pro-gramação
progra-mação
Exemplo 2
Entrada
pro7gra9ma7ção
Saída
progra-mação
pro-gramação
programa-ção
53 Problemas de Programação – Prof. Adonai Medrado 33
Exemplo 3
Entrada
i2n3c4o8n2s7t6i9t8u7c2i4o5n6a4l
Saída
inconsti-tucional
incons-titucional
inconstitu-cional
inconstitucio-nal
in-constitucional
53 Problemas de Programação – Prof. Adonai Medrado 34
Formato de entrada
• Uma linha contendo a letra C ou a letra D. Caso C então a próxima linha
representará uma cadeia a ser codificada, caso D então a próxima linha deverá ser
decodificada.
• Uma linha contendo a cadeia a ser processada.
Formato de saída
• Uma linha contendo o resultado do processamento ou, caso a cadeia de entrada
não for válida, uma linha em branco.
Exemplo 1
Entrada
C
ABC
Saída
ABC
Exemplo 2
Entrada
C
AAAAAAAABC
53 Problemas de Programação – Prof. Adonai Medrado 35
Saída
8ABC
Exemplo 3
Entrada
C
ABCZ
Saída
ABC2Z
Exemplo 4
Entrada
C
ABCZ9Z
Saída
ABC3ZJ2Z
Exemplo 5
Entrada
D
2Z
Saída
Z
Exemplo 6
Entrada
C
1234567890
Saída
ZBZCZDZEZFZGZHZIZJZA
Exemplo 7
Entrada
D
Z
Saída
Exemplo 1
Entrada
(1+2)+(3+4)
[(1+2)+(3+4)]
{[(1+2)+(3+4)]}
{{[(1+2)+(3+4)]}}
0
Saída
1
1
1
1
Exemplo 2
Entrada
()
()()
[()()]
{[()()]}
53 Problemas de Programação – Prof. Adonai Medrado 37
{[()]}
0
Saída
1
1
1
1
1
Exemplo 3
Entrada
((
))()
[()()[
{[()))]}
{[()]{
{]()))]}
}[()]{
0
Saída
0
0
0
0
0
0
0
Exemplo 4
Entrada
(1+2)(
)1+2)+(3+4)
](1+2)+(3+4)[
}[(1+2)+(3+4)]{
0
Saída
0
0
0
0
Exemplo 5
Entrada
{(1+2)+(3+4)}
([3+4])
[3+4]
[({1+2}+{3+4})]
0
53 Problemas de Programação – Prof. Adonai Medrado 38
Saída
0
0
0
0
53 Problemas de Programação – Prof. Adonai Medrado 39
Exemplo
Entrada
5
2011
10
500 450 300 200 150 100 150 160 120 130
53 Problemas de Programação – Prof. Adonai Medrado 40
2121
12
440 400 330 300 250 240 250 150 120 100 120 100
2121
2
1440 900
2000
8
400 420 300 290 200 180 150 160
1800
10
520 400 390 290 220 280 150 160 100 120
Saída
2
32.7
Para clarificação e testes, segue abaixo, em ordem decrescente, os valores de distância e
velocidade média de cada competidor no exemplo acima.
• Competidor 2) 25452 32.7
• Competidor 1) 20110 32.0
• Competidor 5) 18000 24.6
• Competidor 4) 16000 27.4
• Competidor 3) 4242 6.5
53 Problemas de Programação – Prof. Adonai Medrado 41
Exemplo 1
Entrada
2
18 21
Saída
S
Exemplo 2
Entrada
2
21 22
Saída
F
Exemplo 3
Entrada
7
21 22 24 55 23 32 57
Saída
S
Possível solução: (22,23),(24,55),(32,57). O homem com idade de 21 ficará sem par,
porém não há problema nisto.
53 Problemas de Programação – Prof. Adonai Medrado 42
Exemplo 4
Entrada
8
21 31 33 35 37 39 41 43
Saída
S
Explicação: Não há mulheres para ficarem desacompanhadas. Pela regra descrita a festa
seria um sucesso.
Exemplo 5
Entrada
9
21 31 33 35 37 39 41 43 58
Saída
F
Explicação: A única mulher de 58 anos não dançará com nenhum homem da festa já que
todos são mais jovens que ela.
Exemplo 6
Entrada
4
22 32 36 48
Saída
F
53 Problemas de Programação – Prof. Adonai Medrado 43
16 Problema do TMA
O tempo médio de atendimento (TMA) de uma central de teleatendimento é calculado
pela média dos tempos de todos os atendimentos realizados em um período.
O gerente de uma central deseja contratá-lo como analista chefe, porém, para testar suas
habilidades de programador, lhe propôs o desafio de calcular o tempo médio de
atendimento com base em um arquivo texto.
O formato do arquivo é bastante simples. Cada linha do arquivo contém dois valores
inteiros. O primeiro representa o momento de início do atendimento, o segundo o
momento de fim de atendimento.
Cada momento é medido em minutos a partir do início do horário do expediente.
Faça um programa que leia este arquivo (que estará no mesmo diretório do seu programa
com o nome entrada.txt) e exiba na saída padrão o mínimo, o máximo, a moda e a média
com uma casa decimal (um valor em cada linha, nesta ordem) do tempo de atendimento.
Algumas considerações:
• Cada momento está no intervalo fechado entre 0 e 1000.
• O arquivo não está ordenado e terá no mínimo uma linha.
• Se não existir moda ou se existir mais de um tempo de atendimento que seja a
moda, imprima -1.
• O separador dos decimais da moda deve ser de acordo com as configurações
regionais do computador.
Exemplo
Arquivo entrada.txt
5 12
6 20
7 8
6 98
11 14
8 25
98 100
56 79
45 98
12 55
1 3
4 6
7 10
10 13
13 16
Saída
1
92
3
17,9
53 Problemas de Programação – Prof. Adonai Medrado 44
Exemplo 1
Entrada
3
1
10
8
7
56
13
Saída
230
Possível resposta: A={10,1,8}.
Exemplo 2
Entrada
5
12
3
53
8
91
74
2
3
4
64
Saída
1123
Possível resposta: A={3,91,53,12,8}.
Exemplo 3
Entrada
5
1
1
1
6
0
2
7
8
3
1
Saída
18
Possível resposta: A={1,1,0,1,6}.
Exemplo 4
Entrada
9
5
15
100
31
39
0
0
3
26
11
12
13
2
3
4
5
9
1
Saída
528
Possível resposta: A={3,0,0,39,31,26,15,5,100}.
53 Problemas de Programação – Prof. Adonai Medrado 46
Exemplo 1
Entrada
internet
Saída
#4=3
#6=2
#8=1
#3=2
#7=3
#6=2
#3=2
#8=1
Exemplo 2
Entrada
preconceber
Saída
#7=1
#7=3
#3=2
#2=3
53 Problemas de Programação – Prof. Adonai Medrado 47
#6=3
#6=2
#2=3
#3=2
#2=2
#3=2
#7=3
Exemplo 3
Entrada
zunzunzum
Saída
#9=4
#8=2
#6=2
#9=4
#8=2
#6=2
#9=4
#8=2
#6=1
Variação 1
Faça o caminho inverso da dificuldade anterior, ou seja, recebendo a saída anterior como
entrada, dê a entrada.
Você receberá um número N identificando quantas teclas serão informadas.
Repeite o formato apresentado.
Exemplo 1
Entrada
9
#9=4
#8=2
#6=2
#9=4
#8=2
#6=2
#9=4
#8=2
#6=1
Saída
Zunzunzum
53 Problemas de Programação – Prof. Adonai Medrado 48
19 Problema do checksum
Os algoritmos de verificação tipo Checksum trabalham executando operações sobre um
conjunto de dados e são úteis para verificar se este conjunto de dados permanece
íntegro.
Este problema considera o seguinte algoritmo de checksum:
• Para cada byte B na posição P (sendo a primeira posição zero, a segunda 1, etc.):
• Para cada B que estiver em uma posição P impar, deve-se contar a
quantidade de bits 0 em B e acumular esta quantidade em um inteiro W.
• Para cada B que estiver em uma posição P par, deve-se contar a quantidade
de bits 1 em B e acumular esta quantidade em um inteiro W.
O resultado deste algoritmo é W que deverá suportar um valor máximo de 32bits.
Atenção: este algoritmo é apenas um exemplo para fins didáticos e não deve ser
utilizado em aplicações reais.
Faça um programa que receberá na entrada padrão um número indefinido de cadeias de
caracteres (K), cada uma sem espaço e com máximo de 200 caracteres). Cada K
representará o caminho de um arquivo para o qual deve ser calculado o checksum
segundo algoritmo descrito acima. A entrada termina quando for encontrada a cadeia "0"
(sem as aspas).
A saída deverá ser dada na saída padrão e deverá ser o número W descrito no algoritmo
acima.
Exemplo
Entrada
exemplo1.in
exemplo2.in
exemplo3.in
exemplo4.in
exemplo5.in
exemplo6.in
0
Saída
400
402
207
42146
96072
36937
Os arquivos deste exemplo podem ser baixados em:
http://www.adonaimedrado.pro.br/wiki/documentos/professor/problema_checksum_
entradas.zip.
53 Problemas de Programação – Prof. Adonai Medrado 49
Exemplo 1
Entrada
u
4
1
2
4
5
2
3
4
Saída
1 2 3 4 5
Exemplo 2
Entrada
i
4
53 Problemas de Programação – Prof. Adonai Medrado 50
1
2
4
5
2
3
4
Saída
4
Exemplo 3
Entrada
d
4
1
2
4
5
2
3
4
Saída
1 2 5
53 Problemas de Programação – Prof. Adonai Medrado 51
Exemplo 1
Entrada
MNAU
LACN
AKIM
IKJH
ILKC
JKBM
MUDH
ADIK
HUDM
Saída
1
(Senha: AKD)
53 Problemas de Programação – Prof. Adonai Medrado 52
Exemplo 2
Entrada
HJMI
OPJH
AJMO
MIUN
ABCI
IJKB
ONHK
LOUN
UODN
Saída
0
(Senha: JI(O ou N))
53 Problemas de Programação – Prof. Adonai Medrado 53
Exemplo 1
Entrada
+
00000001
00000011
Saída
00000100
Exemplo 2
Entrada
-
00000010
00000001
Saída
00000001
Exemplo 3
Entrada
*
00000001
00000011
Saída
00000011
Exemplo 4
Entrada
%
00010100
00000011
Saída
00000010
53 Problemas de Programação – Prof. Adonai Medrado 54
Exemplo 1
Entrada
sopadeletras
sopas
tras
traz
trazer
talo
proda
adelok
kulad
mea
lopr
Saída
OK
OK
-1
-1
OK
OK
-1
-1
-1
OK
Variação 1
Considere a mesma situação anterior só que assuma que quando um caractere C for
utilizado na formação de um elemento possível de P, C deverá ser descartado.
Entrada
sopadeletrasparaformarpalavras
palavra
palavras
sapo
dele
akmopr
53 Problemas de Programação – Prof. Adonai Medrado 55
rrstafmp
juaarso
orsaaaa
ors
aaarr
Saída
OK
-1
OK
OK
-1
OK
-1
-1
OK
-1
53 Problemas de Programação – Prof. Adonai Medrado 56
Exemplo 1
Entrada
448
3
3
Sendo N=448, M=3, K=3.
Saída
1
Exemplo 2
Entrada
448
5
3
Saída
0
53 Problemas de Programação – Prof. Adonai Medrado 57
Exemplo 1
Entrada
XXYX
Saída
2
O objetivo é conseguir emplacar o veículo com a placa XYXX, para tanto deve-se deixar o
emplacamento para exatos 2 dias depois, assim “pularia-se” a placa XXYY.
Exemplo 2
Entrada
XXXX
Saída
-1
Exemplo 3
Entrada
XXXY
Saída
7
53 Problemas de Programação – Prof. Adonai Medrado 58
Nível avançado
53 Problemas de Programação – Prof. Adonai Medrado 59
Exemplo
Entrada
10
56348631
897434
4321895
98746321
695413245
129078
89078905432
89021
78903278
89278
Saída
1.022333445666788899
2.0034578899
4.34789
5.11223344456899
8.0012223777788999
53 Problemas de Programação – Prof. Adonai Medrado 60
Exemplo 1
Entrada
18
4
aluno1 1
aluno2 2
aluno3 3
aluno4 4
Saída
0 aluno1 aluno4
1 aluno2 aluno3
0.5
Exemplo 2
Entrada
18
3
53 Problemas de Programação – Prof. Adonai Medrado 61
aluno1 0
aluno2 2
aluno4 18
Saída
0 aluno1
2 aluno4
1.0
Exemplo 3
Entrada
33
1
aluno1 32
Saída
1 aluno1
1 aluno1
1.0
53 Problemas de Programação – Prof. Adonai Medrado 62
Entrada
A entrada consistirá de vários casos de teste. Cada caso de teste é constituído por:
1. Uma linha contendo um inteiro K (0<=K<=1000000) e um inteiro J (0<=J<=1000). K
representa a verba disponível para o pagamento da folha. J representa o número
de servidores.
2. As próximas J linhas serão apresentadas no formato:
<nome> <idade> <salario>
O nome terá no máximo 50 caracteres e não conterá espaços. A entrada termina quando
K e J forem informados como zero.
Saída
A saída deverá seguir rigorosamente o exemplo abaixo, indicando para cada K o nome
dos funcionários que receberão salário. Assim, para cada caso de testes deve ser gerada
a seguinte saída:
• A primeira linha deve conter a cadeia "Teste N", onde N é representa o número do
caso de teste começando em 1.
• As linhas seguintes são os nomes dos funcionários em ordem alfabética.
• A última linha deve ser em branco.
Exemplo
Entrada
5 5
Z 29 10
53 Problemas de Programação – Prof. Adonai Medrado 63
D 30 10
A 30 10
E 68 12
C 25 5
15 5
Z 29 10
D 30 10
A 30 10
E 68 12
C 25 5
20 5
Z 29 10
D 30 10
A 30 10
E 68 12
C 25 5
25 5
Z 29 10
D 30 10
A 30 10
E 68 12
C 25 5
35 5
Z 29 10
D 30 10
A 30 10
E 68 12
C 25 5
50 5
Z 29 10
D 30 10
A 30 10
E 68 12
C 25 5
0 0
Saída
Teste 1
C
Teste 2
A
C
Teste 3
A
C
Teste 4
A
C
D
Teste 5
A
C
D
Z
53 Problemas de Programação – Prof. Adonai Medrado 64
Teste 6
A
C
D
E
Z
53 Problemas de Programação – Prof. Adonai Medrado 65
s i l á b i c a s
s2i
l4á
i3l2á
l4á
á1b2
3b2i
i1c4
3c2a
2s.
------------------
s2i3l4á3b2i3c4a2s <--- Resultado
Faça um programa que, recebendo um número N, um conjunto R de N partículas e uma
palavra P, mostre:
1. o resultado do processamento.
2. todas as divisões silábicas possíveis (uma por linha) em ordem de preferência.
3. a separação das sílabas das palavras.
Considere que:
• N será um número inteiro tal que 1<=N<=1000.
• cada partícula do conjunto R tem até 10 caracteres.
• a palavra P tem até 100 caracteres.
Exemplo 1
Entrada
8
s2i
i3l2á
l4á
á1b2
3b2i
i1c4
3c2a
2s.
silábicas
Saída
s2i3l4á3b2i3c4a2s
si-lábicas
silá-bicas
silábi-cas
si-lá-bi-cas
Exemplo 2
Entrada
5
1c2i
ê2n1c2
i1ê
53 Problemas de Programação – Prof. Adonai Medrado 67
i2a
n3c42
ciência
Saída
ci1ê2n3c4i2a
ciên-cia
ci-ência
ci-ên-cia
Variação
Resolva o mesmo problema só que desta vez, ao invés de você receber uma lista de
partículas para cada palavra, você deverá ler uma lista fixa no arquivo
http://www.adonaimedrado.pro.br/wiki/documentos/outros/hyph_pt_BR.dic8.
Nesta dificuldade, o programa só receberá a palavra como entrada e retornará além do
solicitado na dificuldade 1 as partículas de fato utilizadas no processamento da palavra.
Exemplo 1
Entrada
programa
Saída
1g4r2
1m2a
a1m2a
o3g2
o3g2
r2o
r4a
pr2o3g4r4a1m2a
pro-grama
progra-ma
pro-gra-ma
Exemplo 2
Entrada
computador
Saída
1d2o
1p2u
1t2a
2m3p4
4r.
a1d2o
o2m1p2u
o4r.
8 Este arquivo também é do projeto VERO do BrOffice (http://www.broffice.org/verortografico), porém sofreu uma
pequena alteração para este problema (exclusão da primeira linha).
53 Problemas de Programação – Prof. Adonai Medrado 68
u3t2
co2m3p4u3t2a1d2o4r
com-putador
compu-tador
computa-dor
com-pu-ta-dor
Exemplo 3
Entrada
universidade
Saída
1d2a
1d2e
1n2i
1s2i
1v2e
a1d2e
e2r3s4i
i3d2
i3v2
r1s2i
u1n2i
u1n2i3v2e2r3s4i3d2a1d2e
uni-versidade
univer-sidade
universi-dade
u-niversidade
universida-de
u-ni-ver-si-da-de
53 Problemas de Programação – Prof. Adonai Medrado 69
Formato de entrada
Uma linha com o inteiro N.
Exemplo de entrada
20
Formato de saída
Uma linha com sete inteiros separados por espaço. Estes inteiros representam o número
de vezes em que o décimo terceiro dia do mês caiu no sábado, no domingo, na segunda,
na terça, ..., na sexta [atenção à ordem].
Exemplo de saída
36 33 34 33 35 35 34
Exemplo 1
Entrada
4
2
5
Saída
BA
Exemplo 2
Entrada
5
3
10
Saída
ABE
53 Problemas de Programação – Prof. Adonai Medrado 71
Exemplo 3
Entrada
5
6
1000
Saída
ABCEEE
Exemplo 4
Entrada
2
5
20
Saída
BAABB
53 Problemas de Programação – Prof. Adonai Medrado 72
Exemplo 1
Entrada
AAACCAAGTAAA
ATTCACATGACGCACAAAATAAAAAAGAAAATG
AAGATGATAATTCCACATAAAAATATGCAC
AGCAAAATCACAAGTAAA
AAGAAAATCACACATAAA
ACCAAAAAGAAA
ACACAGAAGATGAGTAAA
CCAATCAGACCCACACACCAGAGAAATAAAAATACA
CATACAAAGAGTAAAAATATG
ATCATGCATACAAACATGATGAGG
AACAAACATACACACAGAAAA
ATAACACAGAAA
AAGAAAAATACAAGACACAAA
AAGATGATCCAGATGAGTACA
CGCAAAATCACGAAA
0
Saída
AULA
PROGRAMACAO
COMPUTADOR
JANELA
CANETA
FACA
ESCOLA
UNIVERSIDADE
TECLADO
NOTEBOOK
53 Problemas de Programação – Prof. Adonai Medrado 73
BATERIA
MESA
CADEIRA
CONSOLE
ZANGA
Exemplo 2
Entrada
AAGATGAGACAGAAACGGCAACCAAAAAGTCAACCAACACAC
AGTAAAAACATGCACAAACATATGCACAGAATGCGGAATACACGTATTCACATGACGCACAAAATAAAAAAGAAAATGCTAAGAAGA
CCAATCAGACCCACACACCAGAGAAATAAAAATACACGGACCACAAATACACACAAAAGTCGTAATAAACTAAACAAAACTAGAAAA
0
Saída
COISA QUALQUER
LABORATORIO DE PROGRAMACAO II
UNIVERSIDADE FEDERAL DA BAHIA
53 Problemas de Programação – Prof. Adonai Medrado 74
Exemplo 1
Entrada
6 5
1 2
3 4
2 3
5 6
4 5
Saída
1
Exemplo 2
Entrada
6 4
1 2
3 4
2 3
5 6
Saída
0
53 Problemas de Programação – Prof. Adonai Medrado 75
Exemplo 1
Entrada
2
inocente: ingênuo
ingênuo: simples
inocente: ingênuo
Saída
V
Exemplo 2
Entrada
2
inocente: ingênuo
ingênuo: simples
inocente: simples
Saída
V
53 Problemas de Programação – Prof. Adonai Medrado 76
Exemplo 3
Entrada
2
inocente: ingênuo
ingênuo: simples
simples: inocente
Saída
V
Exemplo 4
Entrada
3
inocente: ingênuo
ingênuo: simples
contagiar: contaminar
simples: contaminar
Saída
F
Exemplo 5
Entrada
2
inocente: ingênuo
ingênuo: simples
simples: puro
Saída
F
Exemplo 6
Entrada
6
a: b
b: c
b: d
b: e
b: f
b: g
a: g
Saída
V
53 Problemas de Programação – Prof. Adonai Medrado 77
Exemplo 7
Entrada
6
a: e
b: c
b: d
b: e
b: f
b: g
a: g
Saída
V
Exemplo 8
Entrada
7
a: e
b: c
b: d
b: e
b: f
b: g
h: d
a: h
Saída
V
Exemplo 9
Entrada
5
a: a
b: b
c: d
d: b
b: a
a: d
Saída
V
Exemplo 10
Entrada
2
a: b
b: a
a: b
53 Problemas de Programação – Prof. Adonai Medrado 78
Saída
V
Exemplo 11
Entrada
2
a: b
b: a
a: a
Saída
V
53 Problemas de Programação – Prof. Adonai Medrado 79
Exemplo 1
Entrada
7
7
1 1 3 0 0 0 1
0 0 1 2 0 1 0
0 0 1 0 1 0 1
9 6 3 1 0 1 0
6 2 4 7 1 0 1
0 0 0 0 0 0 1
0 1 9 6 0 1 0
0
1
2
Saída
1 1 3 0 0 0 1
2 2 1 2 0 1 0
2 2 1 0 1 0 1
9 6 3 1 0 1 0
6 2 4 7 1 0 1
0 0 0 0 0 0 1
0 1 9 6 0 1 0
53 Problemas de Programação – Prof. Adonai Medrado 80
Exemplo 2
Entrada
7
7
1 1 3 0 0 0 1
0 0 1 2 0 1 0
0 0 1 0 1 0 1
9 6 3 1 0 1 0
6 2 4 7 1 0 1
0 0 0 0 0 0 1
0 1 9 6 0 1 0
0
0
2
Saída
2 2 3 0 0 0 2
0 0 2 2 0 2 0
0 0 2 0 2 0 2
9 6 3 2 0 2 0
6 2 4 7 2 0 2
0 0 0 0 0 0 2
0 1 9 6 0 2 0
53 Problemas de Programação – Prof. Adonai Medrado 81
Exemplo 1
Entrada
A=28
Saída
A=28
Exemplo 2
Entrada
B,A=28,B,A=29,C,A=50,R,B=50
Saída
B=50
Exemplo 3
Entrada
B,A=25,B,A=29,R,C,B=50
Saída
A=25
B=50
53 Problemas de Programação – Prof. Adonai Medrado 82
12 Problema do palíndromo10
Números palíndromos são aqueles que são lidos da mesma forma de trás para frente. O
número 12321 é um palíndromo típico.
Dado uma base B (2<=B<=20), imprima todos os inteiros N (1<=N<=300) tais que o
quadrado de N seja um palíndromo quando representado na base B; imprima também
todos os quadrados. Use as letras 'A', 'B'... para representar os dígitos 10, 11...
Lembre-se de imprimir tanto o número quanto seu quadrado na base B.
Formato de entrada
Uma única linha com B, a base.
Exemplo de entrada
10
Formato de saída
Linhas com dois inteiros na base B. O primeiro sendo o número cujo quadrado é um
palíndromo; o segundo o quadrado.
Exemplo de saída
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696
Variação 111
Considere mais de um caso de teste por vez. O final do teste será identificado com B igual
a zero.
Entrada
16
17
0
Saída
1 1
2 4
3 9
11 121
22 484
101 10201
111 12321
121 14641
1 1
2 4
3 9
4 G
6 22
C 88
11 121
1B 2C2
22 484
4G 1771
66 2662
101 10201
53 Problemas de Programação – Prof. Adonai Medrado 84
Seu trabalho é escrever um programa que examine uma lista de tempos iniciais e finais
para N (1<=N<=5000) fazendeiros e compute (em segundos):
• O intervalo de tempo mais longo onde pelo menos uma vaca era ordenhada.
• O intervalo de tempo mais longo (depois do início da primeira ordenha) durante o
qual nenhuma vaca foi ordenhada.
Formato da entrada
• Linha 1: Um único inteiro.
• Linha 2..(N+1): Com dois inteiros não negativos menores que 1000000,
representado o tempo em segundos de início e de fim da ordenha de cada
fazendeiro.
Exemplo de entrada
3
300 1000
700 1200
1500 2100
Formato de saída
Uma única linha com dois inteiros que representam [respectivamente] o maior tempo
contínuo de ordenha e ocioso.
Exemplo de saída
900 300
IF(A
1+2=
(;)=
=B)1
Formato da entrada
• Uma linha contendo um inteiro N representado quantidade de linhas e colunas da
matriz quadrada M.
• N linhas contendo os elementos de cada linha de M.
Formato de saída
Uma única linha contendo a palavra OK, caso os parênteses estejam postos corretamente
ou a palavra ERRO, caso contrário.
Exemplo 1
Entrada
4
IF(A
1+2=
(;)=
=B)1
Saída
OK
Exemplo 2
Entrada
4
IF)A
1+2=
(;(=
=B)1
53 Problemas de Programação – Prof. Adonai Medrado 86
Saída
ERRO
Exemplo 3
Entrada
1
A
Saída
OK
Exemplo 4
Entrada
1
(
Saída
ERRO
Exemplo 5
Entrada
3
)))
ABC
(((
Saída
ERRO
Exemplo 6
Entrada
3
(((
ABC
)))
Saída
OK
Exemplo 7
Entrada
3
(()
ABC
))(
53 Problemas de Programação – Prof. Adonai Medrado 87
Saída
OK
53 Problemas de Programação – Prof. Adonai Medrado 88
Faça um programa que receba a lista de séries com seus horários de início e fim e que
retorne a lista de séries que não chocam com nenhuma outra.
Formato de entrada
• Uma linha com um inteiro N (1<=N<=100).
• N linhas, cada uma com o nome do programa (com até 10 caracteres), o momento
início e o momento fim, ambos intervalos fechados entre 1 e 300.
Formato de saída
• Uma linha contendo a lista dos programas que não se chocam em ordem alfabética
e separados por espaço. Caso não haja programas deve-se retornar uma linha em
branco.
Exemplo 1
Entrada
1
a 1 2
Saída
a
Exemplo 2
Entrada
2
a 1 3
b 2 4
Saída
Exemplo 3
Entrada
3
a 1 3
b 4 5
c 6 10
53 Problemas de Programação – Prof. Adonai Medrado 89
Saída
a b c
Exemplo 4
Entrada
4
a 1 3
b 2 7
c 6 10
d 11 12
Saída
d
Exemplo 5
Exemplo
8
a 1 3
b 2 7
c 6 10
d 11 12
e 1 13
f 14 16
g 12 15
h 17 18
Saída
h
53 Problemas de Programação – Prof. Adonai Medrado 90
16 Problema da permutação
De modo informal e para os objetivos deste problema, podemos dizer que permutação é a
forma de rearranjar as letras de uma palavra.
Faça um problema capaz de receber vários casos de teste. Cada caso de teste contém
uma cadeia M e uma cadeia N ambas sem espaço com até 10 caracteres.
Seu objetivo é identificar para cada caso de teste a ordem em que a cadeia N apareceria
caso ordenássemos todas as permutações de M em ordem alfabética.
A saída deve conter três linhas. A primeira linha é uma cadeia no formato "Teste K", onde
K é o número do caso de testes começando de 1. A segunda linha é um número inteiro
que identifica a posição da permutação N segundo os critérios descritos. A terceira linha
deve ser uma linha em branco.
A entrada termina quando N=M=0.
Algumas considerações:
• A própria string M é considerada uma permutação de si própria.
• Caso N não seja uma permutação de M o valor da ordem deve ser informado como
-1.
Exemplo
Entrada
abc abc
abc acb
abc bac
abc bca
abc cab
abc cba
0 0
Saída
Teste 1
1
Teste 2
2
Teste 3
3
Teste 4
4
Teste 5
5
Teste 6
6
53 Problemas de Programação – Prof. Adonai Medrado 91
Exemplo 1
Entrada
00000000
0C000000
00000000
00T00000
0000Q000
0B000000
000K0000
00000000
Saída
V
O cavalo é capaz de realizar uma caminhada perfeita.
Exemplo 2
Entrada
00000000
0T000000
00000000
00000000
0000Q000
000K0000
00B00000
0C000000
Saída
V
O bispo e a rainha são capaz de realizar uma caminhada perfeita.
53 Problemas de Programação – Prof. Adonai Medrado 92
Exemplo 3
Entrada
00000000
00000000
00000000
00000000
0000T000
000K0000
00C00000
00000000
Saída
F