%&&'    

 !"#!#$

Maratona de Programa c ao da SBC 2008

Caderno de Problemas (Este caderno cont em 10 problemas; as p aginas est ao numeradas de 1 a 17, n ao contando esta p agina de rosto)

Promo c ao:

Patroc nio:

v5.0

Maratona de Programa c ao da SBC ACM ICPC 2008

Problema A
Apagando e Ganhando
Nome do arquivo fonte: apagando.c, apagando.cpp ou apagando.java Juliano e f a do programa de audit orio Apagando e Ganhando, um programa no qual os participantes s ao selecionados atr aves de um sorteio e recebem pr emios em dinheiro por participarem. No programa, o apresentador escreve um n umero de N d gitos em uma lousa. O participante ent ao deve apagar exatamente D d gitos do n umero que est a na lousa; o n umero formado pelos d gitos que restaram e ent ao o pr emio do participante. Juliano nalmente foi selecionado para participar do programa, e pediu que voc e escrevesse um programa que, dados o n umero que o apresentador escreveu na lousa, e quantos d gitos Juliano tem que apagar, determina o valor do maior pr emio que Juliano pode ganhar.

Entrada
A entrada cont em v arios casos de teste. A primeira linha de cada caso de teste cont em dois 5 inteiros N e D (1 D < N 10 ), indicando a quantidade de d gitos do n umero que o apresentador escreveu na lousa e quantos d gitos devem ser apagados. A linha seguinte cont em o n umero escrito pelo apresentador, que n ao cont em zeros ` a esquerda. O nal da entrada e indicado por uma linha que cont em apenas dois zeros, separados por um espa co em branco. Os dados devem ser lidos da entrada padr ao.

Sa da
Para cada caso de teste da entrada seu programa deve imprimir uma u nica linha na sa da, contendo o maior pr emio que Juliano pode ganhar. O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 4 2 3759 6 3 123123 7 4 1000000 0 0 Exemplo de sa da 79 323 100

Maratona de Programa c ao da SBC ACM ICPC 2008

Problema B
Babel
Nome do arquivo fonte: babel.c, babel.cpp ou babel.java Jo aozinho e Mariazinha s ao dois irm aos que est ao muito empolgados com suas aulas de idiomas, cada um est a fazendo v arios diferentes cursinhos. Ao chegar em casa comentam sobre gram atica, vocabul ario, cultura dos pa ses etc. Numa dessas conversas perceberam que algumas palavras s ao comuns a mais de um idioma, mesmo que n ao necessariamente tenham o mesmo signicado. Por exemplo, amigo existe em portugu es e espanhol e tem o mesmo signicado, enquanto que date e uma palavra comum entre franc es e ingl es mas que pode ter signicados diferentes, uma vez que date tamb em se refere a um encontro em ingl es, al em de data de calend ario. J a red em espanhol se refere a uma rede, enquanto que em ingl es se refere ` a cor vermelha. Outro exemplo seria actual que, em ingl es signica algo real e, em espanhol, tem o signicado de presente, atual (como em portugu es). Empolgados com essas descobertas, resolveram escrever num caderno todas as palavras em comum que conseguiram pensar, associando cada uma a um par de idiomas. Observador como e, Jo aozinho prop os um desao a Mariazinha: dados um idioma de origem e um de destino, escrever uma s erie de palavras sendo que a primeira necessariamente deveria pertencer ao idioma de origem e a u ltima ao de destino. Duas palavras adjacentes nessa seq u encia deveriam necessariamente pertencer a um mesmo idioma. Por exemplo, se o idioma de origem fosse portugu es e o de destino franc es, Mariazinha poderia escrever a seq u encia amigo actual date (portugu es/espanhol, espanhol/ingl es, ingl es/franc es). Para a surpresa de Jo aozinho, Mariazinha conseguiu resolver o problema com muita facilidade. Irritado com o sucesso de sua irm a, ele resolveu complicar ainda mais o problema com duas restri co es: Mariazinha deve encontrar a solu c ao que tenha o menor comprimento da seq u encia total n ao contando os espa cos entre as palavras e duas palavras consecutivas n ao podem ter a mesma letra inicial. Sendo assim, a solu ca o anterior passa a ser inv alida, pois amigo e actual t em a mesma poss letra inicial. E vel, por em, encontrar outra solu ca o, que no caso seria amigo red date, cujo comprimento total e 12. Jo aozinho fez uma extensa pesquisa na internet e compilou uma enorme lista de palavras e desaou Mariazinha a resolver o problema. Como e poss vel que haja mais de uma solu ca o, ele pediu para que ela apenas respondesse o comprimento da seq u encia encontrada dadas as restri c oes ou se n ao h a solu c ao poss vel. Voc e seria capaz de ajudar Mariazinha?

Entrada
A entrada cont em v arios casos de teste. A primeira linha de um caso de teste cont em um inteiro M (1 M 2000), representando o total de palavras compiladas por Jo aozinho. A segunda linha cont em duas cadeias de caracteres distintas O e D, separadas por um espa co em branco, indicando os idiomas de origem e destino respectivamente. Cada uma das M linhas seguintes cont em tr es cadeias de caracteres I1 , I2 e P , separadas por um espa co em branco, representando dois idiomas e uma palavra comum entre ambos (I1 e I2 s ao sempre diferentes). Todas as cadeias de caracteres ter ao tamanho m nimo 1 e m aximo 50 e conter ao apenas letras min usculas. Um mesmo par de idiomas pode ter v arias palavras diferentes associadas a ele, por em uma mesma palavra P nunca ser a repetida. O nal da entrada e indicado por uma linha que cont em apenas um zero.

Maratona de Programa c ao da SBC ACM ICPC 2008

Os dados devem ser lidos da entrada padr ao.

Sa da
Para cada caso de teste da entrada seu programa deve imprimir um u nico inteiro, o comprimento da menor seq u encia que satisfa ca as restri co es de Jo aozinho, ou impossivel (em min usculas, sem acento) caso n ao seja poss vel. O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 4 portugues frances ingles espanhol red espanhol portugues amigo frances ingles date espanhol ingles actual 4 portugues alemao ingles espanhol red espanhol portugues amigo frances ingles date espanhol ingles actual 6 portugues frances ingles espanhol red espanhol portugues amigo frances ingles date frances espanhol la portugues ingles a espanhol ingles actual 0 Exemplo de sa da 12 impossivel 5

Maratona de Programa c ao da SBC ACM ICPC 2008

Problema C
O Sal ao do Clube
Nome do arquivo fonte: clube.c, clube.cpp ou clube.java O Clube Recreativo de Tingu a est a construindo a sua nova sede social. Os s ocios desejam que o piso do sal ao da sede seja de t abuas de madeira, pois consideram que este e o melhor tipo de piso para os famosos bailes do clube. Uma madeireira da regi ao doou uma grande quantidade de t abuas de boa qualidade, para serem utilizadas no piso. As t abuas doadas t em todas a mesma largura, mas t em comprimentos distintos. O piso do sal ao da sede social e retangular. As t abuas devem ser colocadas justapostas, sem que qualquer parte de uma t abua seja sobreposta a outra t abua, e devem cobrir todo o piso do sal ao. Elas devem ser dispostas alinhadas, no sentido longitudinal, e todas devem estar no mesmo sentido (ou seja, todas as t abuas devem estar paralelas, no sentido longitudinal). Al em disso, os s ocios n ao querem muitas emendas no piso, e portanto se uma t abua n ao e longa o bastante para cobrir a dist ancia entre um lado e outro do sal ao, ela pode ser emendada a no m aximo uma outra t abua para completar a dist ancia. H a por em uma complica ca o adicional. O carpinteiro-chefe tem um grande respeito por todas as madeiras e prefere n ao serrar qualquer t abua. Assim, ele deseja saber se e poss vel forrar todo o piso com as t abuas doadas, obedecendo ` as restri co es especicadas; caso seja poss vel, o carpinteiro-chefe deseja ainda saber o menor n umero de t abuas que ser a necess ario utilizar. A gura abaixo ilustra duas poss veis maneiras de forrar o piso de um sal ao com dimens oes 4 5 metros para um conjunto de dez t abuas doadas, com 100 cm de largura, e comprimentos 1, 2, 2, 2, 2, 3, 3, 4, 4 e 5 metros.

5m

4m

5m

4m

Entrada
A entrada cont em v arios casos de teste. A primeira linha de um caso de teste cont em dois inteiros M e N indicando as dimens oes, em metros, do sal ao (1 M, N 104 ). A segunda linha cont em um inteiro L, representando a largura das t abuas, em cent metros (1 L 100). A terceira linha cont em um inteiro, K , indicando o n umero de t abuas doadas (1 K 105 ). A quarta linha cont em K inteiros Xi , separados por um espa co, cada um representando o 4 comprimento, em metros, de uma t abua (1 Xi 10 para 1 i K ). O nal da entrada e indicado por uma linha que cont em apenas dois zeros, separados por um espa co em branco. Os dados devem ser lidos da entrada padr ao.

Maratona de Programa c ao da SBC ACM ICPC 2008

Sa da
Para cada um dos casos de teste da entrada seu programa deve imprimir uma u nica linha, contendo o menor n umero de t abuas necess ario para cobrir todo o piso do sal ao, obedecendo ` as restri c oes estabelecidas. Caso n ao seja poss vel cobrir todo o piso do sal ao obedecendo ` as restri c oes estabelecidas, imprima uma linha com a palavra impossivel (letras min usculas, sem acento). O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 4 5 100 10 1 2 5 4 100 7 4 5 4 5 99 4 4 4 3 2 100 7 2 4 0 0 Exemplo de sa da 7 5 impossivel impossivel

2 2 2 3 3 4 4 5

4 4 4 4 3

4 4

1 4 2 4 4

Maratona de Programa c ao da SBC ACM ICPC 2008

Problema D
Dama
Nome do arquivo fonte: dama.c, dama.cpp ou dama.java O jogo de xadrez possui v arias pe cas com movimentos curiosos: uma delas e a dama, que pode se mover qualquer quantidade de casas na mesma linha, na mesma coluna, ou em uma das duas diagonais, conforme exemplica a gura abaixo:

O grande mestre de xadrez Kary Gasparov inventou um novo tipo de problema de xadrez: dada a posi c ao de uma dama em um tabuleiro de xadrez vazio (ou seja, um tabuleiro 8 8, com 64 casas), de quantos movimentos, no m nimo, ela precisa para chegar em outra casa do tabuleiro? Kary achou a solu c ao para alguns desses problemas, mas teve diculdade com outros, e por isso pediu que voc e escrevesse um programa que resolve esse tipo de problema.

Entrada
A entrada cont em v arios casos de teste. A primeira e u nica linha de cada caso de teste cont em quatro inteiros X1 , Y1 , X2 e Y2 (1 X1 , Y1 , X2 , Y2 8). A dama come ca na casa de coordenadas (X1 , Y1 ), e a casa de destino e a casa de coordenadas (X2 , Y2 ). No tabuleiro, as colunas s ao numeradas da esquerda para a direita de 1 a 8 e as linhas de cima para baixo tamb em de 1 a 8. As coordenadas de uma casa na linha X e coluna Y s ao (X, Y ). O nal da entrada e indicado por uma linha contendo quatro zeros. Os dados devem ser lidos da entrada padr ao.

Sa da
Para cada caso de teste da entrada seu programa deve imprimir uma u nica linha na sa da, contendo um n umero inteiro, indicando o menor n umero de movimentos necess arios para a dama chegar em sua casa de destino. O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 4 3 5 0 4 5 5 0 6 3 4 0 2 5 3 0 Exemplo de sa da 1 0 2

Maratona de Programa c ao da SBC ACM ICPC 2008

Problema E
Bolhas e Baldes
Nome do arquivo fonte: bolhas.c, bolhas.cpp ou bolhas.java Andrea, Carlos e Marcelo s ao muito amigos e passam todos os nais de semana ` a beira da piscina. Enquanto Andrea se bronzeia ao sol, os dois cam jogando Bolhas. Andrea, uma cientista da computa ca o muito esperta, j a disse a eles que n ao entende por que passam tanto tempo jogando um jogo t ao prim ario. Usando o computador port atil dela, os dois geram um inteiro aleat orio N e uma seq u encia de inteiros, tamb em aleat oria, que e uma permuta ca o de 1, 2, . . . , N . O jogo ent ao come ca, cada jogador faz um movimento, e a jogada passa para o outro jogador. Marcelo e sempre o primeiro a come car a jogar. Um movimento de um jogador consiste na escolha de um par de elementos consecutivos da seq u encia que estejam fora de ordem e em inverter a ordem dos dois elementos. Por exemplo, dada a seq u encia 1, 5, 3, 4, 2, o jogador pode inverter as posi c oes de 5 e 3 ou de 4 e 2, mas n ao pode inverter as posi co es de 3 e 4, nem de 5 e 2. Continuando com o exemplo, se o jogador decide inverter as posi c oes de 5 e 3 ent ao a nova seq u encia ser a 1, 3, 5, 4, 2. Mais cedo ou mais tarde, a seq u encia car a ordenada. Perde o jogador impossibilitado de fazer um movimento. Andrea, com algum desd em, sempre diz que seria mais simples jogar cara ou coroa, com o mesmo efeito. Sua miss ao, caso decida aceit a-la, e determinar quem ganha o jogo, dada a seq u encia inicial.

Entrada
A entrada cont em v arios casos de teste. Os dados de cada caso de teste est ao numa u nica linha, e s ao inteiros separados por um espa co em branco. Cada linha cont em um inteiro N , 5 2 N 10 , seguido da seq u encia inicial P = (X1 , X2 , . . . , XN ) de N inteiros distintos dois a dois, onde 1 Xi N para 1 i N . O nal da entrada e indicado por uma linha que cont em apenas o n umero zero. Os dados devem ser lidos da entrada padr ao.

Sa da
Para cada caso de teste da entrada seu programa deve imprimir uma u nica linha, com o nome do vencedor, igual a Carlos ou a Marcelo, sem espa cos em branco. O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 5 5 5 6 5 6 0 1 5 1 3 5 6 5 1 2 5 4 5 3 3 3 2 3 4 4 4 4 1 2 3 2 2 5 4 6 1 2 1 Exemplo de sa da Marcelo Carlos Carlos Carlos Carlos Marcelo

Maratona de Programa c ao da SBC ACM ICPC 2008

Problema F
Loop Musical
Nome do arquivo fonte: loop.c, loop.cpp ou loop.java Um loop musical e um trecho de m usica que foi composto para repetir continuamente (ou seja, o trecho inicia novamente toda vez que chega ao nal), sem que se note descontinuidade. Loops s ao muito usados na sonoriza ca o de jogos, especialmente jogos casuais pela internet. Loops podem ser digitalizados por exemplo utilizando PCM. PCM, do ingl es Pulse Code Modulation, e uma t ecnica para representa c ao de sinais anal ogicos, muito utilizada em audio digital. Nessa t ecnica, a magnitude do sinal e amostrada a intervalos regulares de tempo, e os valores amostrados s ao armazenados em sequ encia. Para reproduzir a forma de onda amostrada, o processo e invertido (demodula c ao). Fernandinha trabalha para uma empresa que desenvolve jogos e comp os um bonito loop musical, codicando-o em PCM. Analisando a forma de onda do seu loop em um software de edi c ao de audio, Fernandinha cou curiosa ao notar a quantidade de picos existentes. Um pico em uma forma de onda e um valor de uma amostra que representa um m aximo ou m nimo local, ou seja, um ponto de inex ao da forma de onda. A gura abaixo ilustra (a) um exemplo de forma de onda e (b) o loop formado com essa forma de onda, contendo 48 picos.

(a) Uma forma de onda

(b) Mesma forma de onda em loop

Fernandinha e uma amiga muito querida e pediu sua ajuda para determinar quantos picos existem no seu loop musical.

Entrada
A entrada cont em v arios casos de teste. A primeira linha de um caso de teste cont em um inteiro N , representando o n umero de amostras no loop musical de Fernandinha (2 N 104 ). A segunda linha cont em N inteiros Hi , separados por espa cos, representando a sequ encia de magnitudes das amostras (104 Hi 104 para 1 i N , H1 = HN e Hi = Hi+1 para 1 i < N ). Note que H1 segue HN quando o loop e reproduzido. O nal da entrada e indicado por uma linha que cont em apenas o n umero zero. Os dados devem ser lidos da entrada padr ao.

Maratona de Programa c ao da SBC ACM ICPC 2008

Sa da
Para cada caso de teste da entrada seu programa deve imprimir uma u nica linha, contendo apenas um inteiro, o n umero de picos existentes no loop musical de Fernandinha. O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 2 1 -3 6 40 0 -41 0 41 42 4 300 450 449 450 0 Exemplo de sa da 2 2 4

Maratona de Programa c ao da SBC ACM ICPC 2008

10

Problema G
Set
Nome do arquivo fonte: set.c, set.cpp ou set.java Set e um jogo jogado com um baralho no qual cada carta pode ter uma, duas ou tr es guras. Todas as guras em uma carta s ao iguais, e podem ser c rculos, quadrados ou tri angulos. Um set e um conjunto de tr es cartas em que, para cada caracter stica (n umero e gura), ou as tr es cartas s ao iguais, ou as tr es cartas s ao diferentes. Por exemplo, na gura abaixo, (a) e um set v alido, j a que todas as cartas t em o mesmo tipo de gura e todas elas t em n umeros diferentes de guras. Em (b), tanto as guras quanto os n umeros s ao diferentes para cada carta. Por outro lado, (c) n ao e um set, j a que as duas u ltimas cartas t em a mesma gura, mas esta e diferente da gura da primeira carta.

(a)

(b)

(c)

O objetivo do jogo e formar o maior n umero de sets com as cartas que est ao na mesa; cada vez que um set e formado, as tr es cartas correspondentes s ao removidas de jogo. Quando h a poucas cartas na mesa, e f acil determinar o maior n umero de sets que podem ser formados; no entanto, quando h a muitas cartas h a muitas combina c oes poss veis. Seu colega quer treinar para o campeonato mundial de Set, e por isso pediu que voc e zesse um programa que calcula o maior n umero de sets que podem ser formados com um determinado conjunto de cartas.

Entrada
A entrada cont em v arios casos de teste. A primeira linha de cada caso de teste cont em um 4 inteiro N (3 N 3 10 ), indicando o n umero de cartas na mesa; cada uma das N linhas seguintes cont em a descri ca o de uma carta. A descri c ao de uma carta e dada por duas palavras separadas por um espa co; a primeira, um, dois ou tres, indica quantas guras aquela carta possui. A segunda, circulo (ou circulos), quadrado (ou quadrados) ou triangulo (ou triangulos) indica qual tipo de gura est a naquela carta. O nal da entrada e indicado por uma linha contendo um zero. Os dados devem ser lidos da entrada padr ao.

Sa da
Para cada caso de teste da entrada seu programa deve imprimir uma u nica linha na sa da, contendo um n umero inteiro, indicando o maior n umero de sets que podem ser formados com as cartas dadas.

Maratona de Programa c ao da SBC ACM ICPC 2008

11

O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 3 um circulo dois circulos tres circulos 3 um triangulo tres quadrados dois circulos 6 dois quadrados dois quadrados dois quadrados dois quadrados dois quadrados dois quadrados 4 um quadrado tres triangulos um quadrado dois triangulos 0 Exemplo de sa da 1 1 2 0

Maratona de Programa c ao da SBC ACM ICPC 2008

12

Problema H
Divis ao da Nlog onia
Nome do arquivo fonte: nlog.c, nlog.cpp ou nlog.java Depois de s eculos de escaramu cas entre os quatro povos habitantes da Nlog onia, e de dezenas de anos de negocia c oes envolvendo diplomatas, pol ticos e as for cas armadas de todas as partes interessadas, com a intermedia c ao da ONU, OTAN, G7 e SBC, foi nalmente decidida e aceita por todos a maneira de dividir o pa s em quatro territ orios independentes. Ficou decidido que um ponto, denominado ponto divisor, cujas coordenadas foram estabelecidas nas negocia co es, deniria a divis ao do pa s, da seguinte maneira. Duas linhas, ambas contendo o ponto divisor, uma na dire ca o norte-sul e uma na dire ca o leste-oeste, seriam tra cadas no mapa, dividindo o pa s em quatro novos pa ses. Iniciando no quadrante mais ao norte e mais ao oeste, em sentido hor ario, os novos pa ses seriam chamados de Nlog onia do Noroeste, Nlog onia do Nordeste, Nlog onia do Sudeste e Nlog onia do Sudoeste.
N

 
O

 
L

 
S

 

 !" #$%$& '

A ONU determinou que fosse disponibilizada uma p agina na Internet para que os habitantes pudessem consultar em qual dos novos pa ses suas resid encias est ao, e voc e foi contratado para ajudar a implementar o sistema.

Entrada
A entrada cont em v arios casos de teste. A primeira linha de um caso de teste cont em um 3 inteiro K indicando o n umero de consultas que ser ao realizadas (0 < K 10 ). A segunda linha de um caso de teste cont em dois n umeros inteiros N e M representando as coordenadas do ponto divisor (104 < N, M < 104 ). Cada uma das K linhas seguintes cont em dois inteiros X e Y representando as coordenadas de uma resid encia (104 X, Y 104 ). Em todas as coordenadas dadas, o primeiro valor corresponde ` a dire ca o leste-oeste, e o segundo valor corresponde ` a dire ca o norte-sul. O nal da entrada e indicado por uma linha que cont em apenas o n umero zero. Os dados devem ser lidos da entrada padr ao.

Maratona de Programa c ao da SBC ACM ICPC 2008

13

Sa da
Para cada caso de teste da entrada seu programa deve imprimir uma linha contendo: a palavra divisa se a resid encia encontra-se em cima de uma das linhas divis orias (nortesul ou leste-oeste); NO se a resid encia encontra-se na Nlog onia do Noroeste; NE se a resid encia encontra-se na Nlog onia do Nordeste; SE se a resid encia encontra-se na Nlog onia do Sudeste; SO se a resid encia encontra-se na Nlog onia do Sudoeste. O resultado de seu programa deve ser escrito na sa da padr ao. Exemplo de entrada 3 2 1 10 10 -10 1 0 33 4 -1000 -1000 -1000 -1000 0 0 -2000 -10000 -999 -1001 0 Exemplo de sa da NE divisa NO divisa NE SO SE

Maratona de Programa c ao da SBC ACM ICPC 2008

14

Problema I
Maior Subseq u encia Crescente
Nome do arquivo fonte: seq.c, seq.cpp ou seq.java Determinar a subseq u encia (cont gua) crescente de maior comprimento em uma lista de n umeros e um problema j a cl assico em competi co es de programa c ao. Este e o problema que voc e deve resolver aqui, mas para n ao deixar voc e bocejando de t edio enquanto o soluciona, introduzimos uma pequena modica ca o: a lista de n umeros e dada na forma de uma matriz bidimensional e a seq u encia de comprimento m aximo est a embutida em uma submatriz da matriz original. Vamos denir mais precisamente o problema. A lineariza ca o de uma matriz bidimensional e a justaposi c ao de suas linhas, da primeira ` au ltima. Uma submatriz e uma regi ao retangular (de lados paralelos aos da matriz) de uma matriz. O tamanho de uma submatriz e seu n umero de elementos. Voc e deve escrever um programa que, dada uma matriz de n umeros inteiros, determine a maior submatriz que, quando linearizada, resulta em uma seq u encia crescente. A gura abaixo mostra alguns exemplos de submatrizes de tamanho m aximo que cont em subseq u encias crescentes. Note que mais de uma submatriz que cont em uma subseq u encia de comprimento m aximo pode estar presente em uma mesma matriz. Note ainda que numa seq u encia crescente n ao pode haver elementos repetidos: 22, 31, 33 e uma seq u encia crescente, ao passo que 22, 31, 31, 33 n ao e.
                     

Entrada
A entrada cont em v arios casos de teste. A primeira linha de um caso de teste cont em dois inteiros N e M indicando as dimens oes da matriz (1 N, M 600). Cada uma das N linhas seguintes cont em M inteiros, separados por um espa co, descrevendo os elementos da matriz. O elemento Xi,j da matriz e o j - esimo inteiro da i- esima linha da entrada (106 Xi,j 106 ). O nal da entrada e indicado por uma linha que cont em apenas dois zeros, separados por um espa co em branco. Os dados devem ser lidos da entrada padr ao.

Sa da
Para cada um dos casos de teste da entrada seu programa deve imprimir uma u nica linha, contendo o n umero de elementos da maior submatriz que, quando linearizada, resulta em uma seq u encia crescente. O resultado de seu programa deve ser escrito na sa da padr ao.

Maratona de Programa c ao da SBC ACM ICPC 2008

15

Exemplo de entrada 3 3 1 2 5 4 6 7 10 8 3 3 4 1 2 1 2 9 6 7 3 8 7 2 8 4 2 -23 -12 0 2 16 15 57 33 4 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0

Exemplo de sa da 4 3 4 1

Maratona de Programa c ao da SBC ACM ICPC 2008

16

Problema J
Vampiros
Nome do arquivo fonte: vampiros.c, vampiros.cpp ou vampiros.java Felipinho est a empolgado com seu novo jogo de RPG sobre guerras entre cl as de vampiros. Nesse jogo ele representa um personagem de um vampiro e constantemente entra em conito contra vampiros de outros cl as. Tais batalhas s ao realizadas com base nas caracter sticas de cada personagem envolvido e com a ajuda de um dado comum de seis faces. Por simplicidade, vamos considerar apenas as lutas entre dois vampiros, vampiro 1 e vampiro 2. Cada um possui uma energia vital (chamaremos de EV1 e EV2 respectivamente) e, al em disso, s ao determinadas uma for ca de ataque AT e uma capacidade de dano D. O combate e realizado em turnos da maneira descrita a seguir. A cada turno um dado e rolado, se o valor obtido for menor do que ou igual a AT , o vampiro 1 venceu o turno, caso contr ario o vampiro 2 e quem venceu. O vencedor suga energia vital do advers ario igual ao valor D, ou seja, D pontos de EV s ao diminu dos do perdedor e acrescentados ao vencedor. O combate segue at e que um dos vampiros que com EV igual a ou menor do que zero. Por exemplo, suponhamos que EV1 = 7, EV2 = 5, AT = 2, D = 4. Rola-se o dado e o valor obtido foi 3. Nesse caso, o vampiro 2 venceu o turno e, portanto, 4 pontos de EV s ao diminu dos do vampiro 1 e acrescentados ao vampiro 2. Sendo assim, os novos valores seriam EV1 = 3 e EV2 = 9. Observe que se no pr oximo turno o vampiro 2 ganhar novamente, o combate ir a terminar. Os valores de AT e D s ao constantes durante todo o combate, apenas EV1 e EV2 variam. Apesar de gostar muito do jogo, Felipinho acha que os combates est ao muito demorados e e gostaria de conhecer de antem ao a probabilidade de vencer, para saber se vale a pena lutar. Assim, ele pediu que voc e escrevesse um programa que, dados os valores iniciais de EV1 , EV2 , al em de AT e D, calculasse a probabilidade de o vampiro 1 vencer o combate.

Entrada
A entrada cont em v arios casos de teste. Cada caso de teste ocupa uma u nica linha, com os quatro inteiros EV1 , EV2 , AT e D separados por um espa co em branco (1 EV1 , EV2 10, 1 AT 5 e 1 D 10). O nal da entrada e indicado por uma linha contendo quatro zeros. Os dados devem ser lidos da entrada padr ao.

Sa da
Para cada caso de teste da entrada seu programa deve imprimir uma u nica linha. A linha deve conter apenas um n umero real, escrito com precis ao de uma casa decimal, representando, em termos de percentagem, a probabilidade de o vampiro 1 vencer o combate. O resultado de seu programa deve ser escrito na sa da padr ao.

Maratona de Programa c ao da SBC ACM ICPC 2008

17

Exemplo de entrada 1 1 8 7 0 1 2 5 5 0 3 1 3 2 0 1 1 1 4 0

Exemplo de sa da 50.0 3.2 61.5 20.0