Universidade Federal do Espírito Santo
Departamento de Informática
Programa de EducaçãoTutorial – PET EngComp
E-mail: [email protected]
Home-Page: www.inf.ufes.br/~pet
Tel. (27) 3335-2161
Realização:
Apoio:
4º Torneio de Programação – TOPCOM 4
PET – Engenharia de Computação - UFES
PROBLEMA A
Números Feios
“Números feios” são números cujos únicos fatores primos são 2, 3 ou 5. A seqüência
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
mostra os primeiros 11 números feios. Por convenção, 1 é incluído.
Escreva um programa que imprima o 1500º número feio.
A ENTRADA E A SAÍDA
Não existe entrada para este programa. A saída deve ser uma linha simples como mostrado
abaixo com <numero> substituído pelo número calculado.
EXEMPLO DE SAÍDA
O numero feio de ordem 1500 eh <numero>.
4º Torneio de Programação – TOPCOM 4
PET – Engenharia de Computação - UFES
PROBLEMA B
Desafio de Palavras-Cruzadas
Quase todo mundo está familiarizado com o desafio de palavras-cruzada. Nesse problema,
você terá que lidar com um tipo de palavras-cruzada que é adequado para ser resolvido por
um computador automático. Uma descrição do desafio é uma lista das palavras possíveis
(o dicionário) são dadas, e o objetivo é encontrar o número de possíveis soluções, caso
exista alguma, usando o dado dicionário.
O desafio é representado como uma matriz bidimensional de espaços brancos e pretos. A
solução é um subconjunto de palavras do dicionário que preenchem toda a seqüência de
espaços em branco de uma forma tal que todas as palavras, tanto na horizontal quanto na
vertical, são palavras válidas no dicionário. Uma “palavra” de uma letra somente não
necessita estar no dicionário.
Segue um exemplo de palavras-cruzada no qual espaços em branco e preto são
respectivamente representados por caracteres de ‘.’ e ‘#’, de dicionário, e a solução para
esse desafio:
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
#
#
.
#
#
#
.
.
.
.
#
.
#
.
.
.
.
.
.
#
.
.
.
.
.
.
.
#
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
#
#
.
#
.
.
#
.
.
#
.
.
#
.
.
.
.
.
.
.
.
.
#
.
.
.
.
aa ac al alao ali ap
atencao atlanta camilo
doar dr duo eam eis el
epoca et icar ileso is
la loto mal men
merito mi no
oaristo oo os pios
resto roa roca rt
sa senil si tule
variedades verdadeiro
v
e
r
d
a
d
e
i
r
o
a
p
#
o
a
r
i
s
t
o
r
o
c
a
#
#
s
#
#
#
i
c
a
r
#
r
#
m
a
l
e
a
m
#
m
e
r
i
t
o
d
#
i
l
e
s
o
#
e
t
a
t
l
a
n
t
a
#
n
o
d
u
o
#
#
o
#
a
c
#
e
l
#
s
a
#
a
l
a
o
s
e
n
i
l
#
p
i
o
s
Seu objetivo é desenvolver um programa para resolver o desafio de palavras-cruzadas
passado.
A ENTRADA
A entrada começa com um único inteiro positivo sozinho numa linha indicando o número
de casos que se seguirão, cada um deles descritos abaixo. Essa linha é seguida por uma
linha em branco, e também haverá uma linha em branco entre as entradas de dois casos
consecutivos.
A entrada consiste em uma configuração de um tabuleiro de palavras-cruzada de tamanho
10X10 e um dicionário de palavras. Para o tabuleiro, cada linha de entrada é uma
seqüência de caracteres '.' e '#'. Você deve assumir que a configuração dada é sempre
correta.
O dicionário de palavras começa imediatamente depois da última linha do tabuleiro. Cada
4º Torneio de Programação – TOPCOM 4
PET – Engenharia de Computação - UFES
palavra é uma seqüência caracteres minúsculas e sem acentos e elas são separadas por
espaços. O dicionário termina quando se chega ao final do arquivo de entrada.
A SAÍDA
Para cada caso de teste, a saída deve seguir a descrição abaixo. As saídas de dois casos
consecutivos serão separadas por uma linha em branco.
O programa deve ter como saída o número de soluções que uma dada palavra-cruzada
aceita.
EXEMPLO DE ENTRADA
1
..........
.....#....
.#......#.
....#..#..
..##...#..
..#.....##
...#...#..
..#..##...
..#.......
..#....#..
aa ac al alao
ali ap atencao
atlanta camilo
doar dr duo eam
eis el epoca et
icar ileso is
la loto mal men
merito mi no
oaristo oo os pios
resto roa roca rt
sa senil si tule
variedades verdadeiro
EXEMPLO DE SAÍDA
1
4º Torneio de Programação – TOPCOM 4
PET – Engenharia de Computação - UFES
PROBLEMA C
Números na base 7K
Consideremos números na base K, contendo exatamente N dígitos. Nós definimos que um
número é válido se sua notação na base K não contenha 2 zeros sucessivos.
Exemplo:
1010230 é um número válido de 7 dígitos
1000198 não é um número válido
0001235 não é um número de 7 dígitos, é um de 4 dígitos
Dados N e K, você deverá calcular a quantidade de números na base K válidos.
Você pode assumir que 2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.
A ENTRADA
Dois números decimais N e K.
A SAÍDA
O resultado em notação decimal.
EXEMPLO DE ENTRADA
2
10
EXEMPLO DE SAÍDA
90
4º Torneio de Programação – TOPCOM 4
PET – Engenharia de Computação - UFES
PROBLEMA D
Problema A+B
Calcular A + B
A ENTRADA
AeB
A SAÍDA
A+B
EXEMPLO DE ENTRADA
1 5
EXEMPLO DE SAÍDA
6