XXVI Olimpíada Brasileira de Informática

Corrida Robótica

Uma nova modalidade de corrida de carros foi inaugurada, chamada de Fórmula R, para carros autônomos (carros sem motorista, dirigidos por robótica). Na primeira corrida participaram cinco carros, identificados por números, que iniciaram a corrida na seguinte ordem: 22 (primeiro colocado nos treinos), 16, 27, 31 e 13 (último colocado nos treinos). Uma ultrapassagem ocorre quando um carro passa na frente de um outro carro.

Questão 1. A seguinte ordem de ultrapassagens ocorreu durante a primeira corrida: o carro 27 ultrapassou o carro 16; o carro 13 ultrapassou o carro 31; o carro 16 ultrapassou o carro 27; o carro 16 ultrapassou o carro 22; o carro 27 ultrapassou o carro 22, e então a corrida terminou. Apenas essas ultrapassagens aconteceram. Qual a ordem de chegada dos carros, do primeiro ao último colocado?
27, 16, 22, 13, 31
22, 27, 16, 31, 13
22, 16, 27, 31, 13
16, 22, 27, 13, 31
16, 27, 22, 13, 31

Questão 2. Na segunda corrida, os carros iniciaram na mesma ordem da primeira corrida (ou seja, 22, 16, 27, 31 e 13). Qual o menor número possível de ultrapassagens durante a segunda corrida, sabendo que os carros terminaram na ordem 13 (vencedor), 22, 16, 31 e 27 (último colocado)?
5
6
7
8
9

Tarefas Iniciação Nível 1
Promoção:
sbc
Patrocínio
 
Apoio
 
Coordenação