Prova - Olimpíada Brasileira de Informática

OBI2008
Caderno de Tarefas
Modalidade Iniciação • Nı́vel 1, Fase 1
12 de abril de 2008
A PROVA TEM DURAÇÃO DE DUAS HORAS
LEIA ATENTAMENTE AS INSTRUÇÕES ABAIXO ANTES DE INICIAR A PROVA
• A prova deve ser feita individualmente.
• A duração da prova é de duas horas.
• É proibido consultar livros, anotações ou qualquer outro material durante a prova.
• Todas as questões têm o mesmo valor na correção.
• Este caderno de tarefas é composto de 5 páginas (não contando esta folha de rosto), numeradas de 1 a 5.
Verifique se o caderno está completo.
• Seu professor lhe entregará uma Folha de Respostas que deve ser preenchida e devolvida ao final da prova
para correção.
• Se você tiver dificuldades no preenchimento da Folha da Respostas, peça ajuda ao seu professor, que
poderá ajudá-lo(a) no preenchimento.
Sociedade Brasileira de Computação
www.sbc.org.br
Fundação Carlos Chagas
www.fcc.org.br
Olimpı́ada Brasileira de Informática – OBI2008 – Modalidade Iniciação Nı́vel 1 – Fase 1
1
Colorindo o Mapa
Um mapa de um paı́s mostrando seus estados R, S, W, Questão 3. Qual dos seguintes pares de estado podem
X, Y e Z precisa ser colorido. Estados adjacentes não ter a mesma cor?
podem ter a mesma cor. Os únicos estados adjacentes
(A) R e S
entre si são os seguintes:
(B) S e W
(C) W e X
(D) W e Y
• R, S, X e Y são adjacentes a W.
(E) X e Y
• X é adjacente a Y.
Questão 4. Qual dos seguintes estados pode ter a
• R e S são adjacentes a Z.
mesma cor que W?
Questão 1. Qual dos seguintes pares de estados devem ter cores diferentes um do outro?
(A)
(B)
(C)
(D)
(E)
ReX
SeX
SeZ
XeZ
YeZ
(A)
(B)
(C)
(D)
(E)
R
S
X
Y
Z
Questão 5. Se o menor número possı́vel de cores é
usado e um dos estados é o único que possui uma deQuestão 2. Se X tem a mesma cor de Z, então é ver- terminada cor, qual é esse estado?
dade que
(A) Somente W
(B) Somente Z
(A) R tem a mesma cor que Y.
(C) Somente R, ou somente S
(B) S tem a mesma cor que X.
(D) Somente W, ou somente X, ou somente Y
(C) X tem a mesma cor que Y.
(E) Somente W, ou somente Y, ou somente Z
(D) S tem uma cor
diferente de qualquer outro estado.
(E) W tem uma cor
diferente de qualquer outro estado.
Olimpı́ada Brasileira de Informática – OBI2008 – Modalidade Iniciação Nı́vel 1 – Fase 1
2
A Quitanda
Cinco irmãos, José, Karina, Laura, Maria e Nilo, Questão 8. Se Karina está trabalhando exatamente
revezam-se para cuidar da quitanda da famı́lia de quatro dias da semana então qual dos pares abaixo
segunda-feira a sexta-feira. A quitanda deve ter exa- pode ser os que estão trabalhando na quarta-feira?
tamente dois irmãos trabalhando em cada dia, respei(A) José e Laura
tando as seguintes condições:
(B) José e Maria
(C) Karina e Laura
• cada irmão deve trabalhar pelo menos um dia;
(D) Karina e Nilo
(E) Maria e Nilo
• nenhum irmão pode trabalhar três dias consecutivos;
• Karina deve trabalhar na segunda-feira;
• Maria deve trabalhar na quinta-feira e na sextafeira;
• José não pode trabalhar nos mesmos dias que Karina trabalhar.
Questão 9. Se José está trabalhando exclusivamente
nos mesmos dias que Maria está trabalhando, então
qual das opções pode ser verdadeira?
(A)
(B)
(C)
(D)
(E)
José está trabalhando na segunda-feira.
José está trabalhando na quarta-feira.
Karina está trabalhando na sexta-feira.
Laura está trabalhando na sexta-feira.
Nilo está trabalhando na terça-feira.
Questão 6. Qualquer um dos irmãos pode estar traQuestão 10. Se Karina está trabalhando somente um
balhando na quarta-feira, exceto:
dia e Laura está trabalhando exatamente quatro dias,
(A) José
então qual par de irmãos abaixo está trabalhando na
(B) Karina
quarta-feira?
(C) Laura
(A) José e Laura
(D) Maria
(B) José e Nilo
(E) Nilo
(C) Karina e Laura
Questão 7. Se José está trabalhando exatamente três
(D) Laura e Maria
dias da semana, então dois desses dias devem ser:
(E) Laura e Nilo
(A)
(B)
(C)
(D)
(E)
segunda-feira e quarta-feira
terça-feira e quarta-feira
terça-feira e sexta-feira
quarta-feira e sexta-feira
quinta-feira e sexta-feira
Olimpı́ada Brasileira de Informática – OBI2008 – Modalidade Iniciação Nı́vel 1 – Fase 1
3
Rede de Computadores
Numa rede de computadores existem quatro máquinas, Questão 13. Qual das seqüências de cabos abaixo reW, X, Y e Z. Os computadores são conectados entre presenta um caminho que uma mensagem tem de persi por cabos direcionados. Por um cabo ligando, por correr para, saindo de X, retornar a X?
exemplo, o computador W ao computador X passam
(A) de X para W, de W para X.
mensagens apenas do computador W para o compu(B) de X para Y, de Y para
tador X (e não do computador X para o computador
W, de W para Z, de Z para X.
W). Os cabos existentes na rede são os seguintes:
(C) de X para Y, de Y para
Z, de Z para W, W para X.
• de W para X.
(D) de X para Z, de Z para
W, de W para Y, de Y para X.
• de W para Y.
(E) de X para Z, de Z para
• de W para Z e de Z para W.
Y, de Y para W, de W para X.
Questão 14. Se todos os cabos na rede demoram o
mesmo tempo para serem percorridos por uma men• de X para Z.
sagem e se todas as mensagens sempre viajam pelo
caminho mais rápido possı́vel, então o caminho mais
• de Z para Y.
demorado que uma mensagem pode percorrer na rede
Uma mensagem pode ir de um computador para oué o caminho de
tro utilizando apenas um cabo, ou uma seqüência de
(A) X para W.
cabos. Por exemplo, na rede descrita, uma mensagem
(B) Y para W.
pode ir de W para X utilizando por um único cabo; e
(C) Y para Z.
uma mensagem pode ir de X para W utilizando dois
(D) Z para W.
cabos (passando pelo computador Z).
(E) Z para X.
Questão 11. Se uma mensagem deve ir de Y para X
usando o menor número de cabos possı́veis, ela deve Questão 15. Mensagens restritas são mensagens que
devem percorrer um único cabo. Qual cabo deve ser
seguir:
adicionado à rede de forma que cada máquina possa en(A) diretamente de Y para X.
viar mensagens restritas para pelo menos outras duas
(B) passando apenas por W.
máquinas e possa receber mensagens restritas de pelo
(C) passando apenas por Z.
menos outras duas máquinas?
(D) passando por W e depois por Z.
(E) passando por Z e depois por W.
(A) de X a W.
Questão 12. Qual das opções abaixo é uma lista com(B) de Y a W.
pleta e correta de máquinas para as quais uma mensa(C) de Y para Z.
gem pode ir, partindo de Z, utizando um único cabo?
(D) de Z para W.
(E) de Z para X.
(A) W
• de X para Y e de Y para X.
(B)
(C)
(D)
(E)
Y
W, Y
X, Y
W, X, Y
Olimpı́ada Brasileira de Informática – OBI2008 – Modalidade Iniciação Nı́vel 1 – Fase 1
4
Um Dia de Trabalho
Um funcionário de uma empresa tem seis tarefas para Questão 18. Qual é o número total de possı́veis tarerealizar hoje. Essas tarefas são identificadas por R, fas que podem ser realizadas em primeiro lugar?
B, G, S, W e T. As tarefas não podem ser realizadas
(A) 1
ao mesmo tempo e devem ser feitas numa ordem que
(B) 2
obedeça as restrições baixo.
(C) 3
(D) 4
• W é realizada em algum momento após G e al(E) 5
gum momento após T.
Questão 19. Se R é a quinta tarefa a ser realizada
• S é realizada em algum momento após W.
então qual das opções é verdadeira?
• R é realizada em algum momento antes de S.
Questão 16. Qual das opções abaixo é uma lista completa e correta da ordem de realização das tarefas, da
primeira à última?
(A)
(B)
(C)
(D)
(E)
G, R, T, S, W, B
G, T, W, S, R, B
B, G, T, R, W, S
G, B, W, R, T, S
T, W, R, G, S, B
Questão 17. Qual das seguintes opções é sempre verdadeira?
(A)
(B)
(C)
(D)
(E)
S é realizada por último.
G é realizada primeiro.
S é realizada após B.
S é realizada após G.
W é realizada após R.
(A)
(B)
(C)
(D)
(E)
W é a quarta tarefa a ser realizada.
S é a sexta tarefa a ser realizada.
B é a segunda tarefa a ser realizada.
T é a terceira tarefa a ser realizada.
G é a primeira tarefa a ser realizada.
Questão 20. Qual das opções abaixo é a posição mais
tardia em que a tarefa T pode ser realizada?
(A)
(B)
(C)
(D)
(E)
Segundo lugar
Terceiro lugar
Quarto lugar
Quinto lugar
Sexto lugar
Olimpı́ada Brasileira de Informática – OBI2008 – Modalidade Iniciação Nı́vel 1 – Fase 1
5
Instruções para preenchimento da Folha de Respostas
P
r
o
e
e
n
d
n
c
e
h
a
a
o
p
r
s
o
v
c
a
a
m
e
p
s
t
á
o
s
s
e
c
n
o
d
m
s
o
r
e
e
u
a
n
l
i
z
o
a
m
d
e
e
o
n
o
m
e
d
a
e
s
c
o
l
a
a
O
l
i
m
p
í
a
d
a
B
r
a
s
i
l
e
i
r
a
d
e
I
n
f
o
r
m
á
t
i
c
a
O
–
B
I
2
0
0
7
–
M
o
d
a
l
i
d
a
d
e
I
n
i
c
i
a
ç
ã
o
E
s
d
F
N
o
m
e
N
o
m
e
d
o
(
a
)
A
l
u
n
o
(
a
o
l
h
a
d
e
R
e
s
p
o
s
t
a
c
r
e
i
e
v
n
a
s
o
c
r
i
s
ç
ã
e
u
n
ú
m
e
r
o
s
)
M
N
ú
m
e
r
o
d
e
i
n
s
c
r
i
ç
ã
o
d
o
a
l
u
n
o
(
a
a
r
q
u
r
e
s
e
o
s
d
í
e
n
g
t
i
d
e
t
o
s
)
João da Silva
M
a
r
q
u
e
o
n
í
a
l
v
e
l
(
1
o
d
a
E
s
c
o
l
a
S
e
d
0
e
u
E. M. E. F. Vila Lobos
V
2
)
d
a
m
o
d
i
d
a
d
e
q
u
i
s
t
o
d
o
(
a
)
D
e
l
e
g
a
d
o
(
a
)
d
a
O
B
1
1
7
2
c
o
r
s
e
u
o
c
ê
e
s
t
á
p
a
r
t
i
c
i
p
a
n
o
n
d
e
s
a
o
H
0
0
0
0
0
A
1
1
1
1
1
B
2
2
2
2
2
3
3
3
3
3
D
4
4
4
4
4
E
5
5
5
5
5
F
6
6
6
6
6
7
7
7
7
7
H
8
8
8
8
8
I
9
9
9
9
9
J
n
ú
m
e
r
o
I
e
i
v
p
d
n
s
c
r
i
ç
ã
o
C
o
M
I
o
n
d
s
a
1
.
F
.
M
3
.
N
4
.
M
i
d
a
d
e
n
i
c
i
a
ç
ã
o
N
í
v
e
l
1
I
n
i
c
i
a
ç
ã
o
N
í
v
e
l
2
t
2
l
I
r
u
a
ç
ç
s
m
r
q
r
q
o
a
e
a
a
ã
õ
a
u
r
e
d
e
u
G
c
a
i
x
e
a
s
s
e
a
p
r
c
o
e
s
n
e
n
h
e
n
a
s
n
p
f
o
o
s
u
r
t
m
a
m
u
e
s
o
c
a
q
m
a
r
o
m
o
m
u
e
e
s
l
s
p
t
d
á
e
p
ã
o
i
o
s
s
t
a
l
s
o
:
p
e
m
p
o
r
e
t
r
r
o
e
e
s
q
d
p
u
e
o
s
e
s
t
p
t
ã
o
a
i
s
c
u
b
r
d
e
a
c
o
m
c
a
n
e
t
a
e
s
f
e
r
o
g
u
l
r
á
f
i
c
a
d
e
p
o
t
i
n
t
a
.
a
p
r
e
t
a
o
u
a
z
u
l
.
.
o
.
M
a
i
s
u
m
a
m
a
r
c
a
ç
ã
o
a
n
a
a
r
e
s
s
t
M
p
A
0
1
0
2
0
3
0
4
C
B
A
B
A
B
A
B
D
C
C
E
D
E
D
E
D
E
1
1
1
2
1
3
1
4
A
B
A
B
A
B
A
B
A
B
C
C
C
D
E
D
E
D
E
D
E
D
E
a
a
N
A
0
C
C
B
D
E
5
1
C
C
6
0
7
0
8
0
9
1
N
Ã
O
G
R
A
M
P
E
I
E
,
A
B
A
B
A
B
A
B
A
B
C
C
C
C
C
D
E
D
E
D
E
D
E
D
E
0
N
1
6
1
7
1
8
1
9
2
Ã
O
A
M
A
S
S
E
,
N
Ã
O
D
O
B
R
E
,
N
ã
q
u
a
e
c
o
u
a
d
m
d
e
i
a
a
x
q
e
r
u
n
e
s
e
e
s
n
p
t
h
o
ã
s
t
a
o
u
m
a
5
q
0
r
r
A
B
A
B
A
B
A
B
A
B
C
C
C
C
C
D
E
D
E
D
E
D
E
D
E
0
Ã
O
R
A
S
U
R
E
E
N
Ã
O
S
U
J
E
E
S
T
A
F
O
L
H
A
u
e
s
t
ã
o
s
e
m
r
e
s
p
o
s
t
a
o