Maratona de Programa¸˜o da SBC 2007 ca
Sub-Regional Brasil do ACM ICPC
22 de Setembro de 2007

(Este caderno cont´m 10 problemas; as p´ginas est˜o numeradas de 1 a 19, e a a n˜o contando esta p´gina de rosto) a a

Sedes Regionais
Regi˜o Centro-Oeste a • Universidade de Bras´ ılia, Bras´ ılia, DF • Universidade Cat´lica Dom Bosco, Campo Grande, MS o • Universidade Estadual do Mato Grosso do Sul, Dourados, MS Regi˜o Nordeste a • Faculdades Guararapes, Jaboat˜o dos Guararapes, PE a • CEFET-PB, Jo˜o Pessoa, PB a • CEFET-RN, Natal, RN • Centro Universit´rio FIB, Salvador, BA a • Universidade Federal do Maranh˜o, S˜o Lu´ MA a a ıs, • Universidade Federal do Cear´, Sobral, CE a Regi˜o Sul a • Unioeste, Cascavel, PR • FTECBrasil, Caxias do …exibir mais conteúdo…

Lados consecutivos da quadra s˜o sempre a perpendiculares, e o pol´ ıgono descrito na entrada ´ sempre um pol´ e ıgono simples. O final da entrada ´ indicado por N = 0. e A entrada deve ser lida da entrada padr˜o. a

Sa´ ıda
Para cada caso de teste da entrada seu programa deve produzir uma unica linha na sa´ ´ ıda, contendo um n´mero inteiro, indicando o menor n´mero de ju´ de linha necess´rios. u u ızes a A sa´da deve ser escrita na sa´da padr˜o. ı ı a Exemplo de entrada 4 0 0 9 0 9 18 0 18 8 0 0 0 1 1 1 1 -1 -2 -1 -2 1 -1 1 -1 0 12 1 0 2 0 2 1 3 1 3 2 2 2 2 3 1 3 1 2 0 2 0 1 1 1 0 Sa´ para o exemplo de entrada ıda 4 7 6

Maratona de Programa¸˜o da SBC – ACM ICPC – 2007 ca

3

Problema B
Rouba-Monte
Nome do arquivo fonte: rouba.c, rouba.cpp, rouba.java ou rouba.pas Um dos jogos de cartas mais divertidos para crian¸as pequenas, pela simplicidade, ´ Roubac e Monte. O jogo utiliza um ou mais baralhos normais e tem regras muito simples. Cartas s˜o disting¨idas apenas pelo valor (´s, dois, trˆs, . . .), ou seja, os naipes das cartas n˜o s˜o a u a e a a considerados (por exemplo, ´s de paus e ´s de ouro tˆm o mesmo valor). a a e Inicialmente as cartas s˜o embaralhadas e colocadas em uma pilha na mesa de jogo, chamada a de pilha de compra, com face voltada para baixo. Durante o jogo, cada jogador