Entendendo a entrada e saída dos problemas de online judges

Publicado por Delacyr Categoria: Geral|SPOJ

29 Mar 2010

Notei que algumas pessoas enfrentam problemas ao entender a forma de como será dada a entrada/saída dos problemas. Aqui vai um exemplo de como se deve interpretar a entrada e saída de um problema do Spoj:

Problema: 811. Quermesse

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém um número inteiro positivo N que indica o número de participantes da festa. A linha seguinte contém a sequência, em ordem de entrada, dos N ingressos das pessoas que participaram da festa. O final da entrada é indicado quando N = 0. Para cada conjunto de teste da entrada haverá um único ganhador.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas. A primeira linha identifica o conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A segunda linha deve conter o número do ingresso do ganhador, conforme determinado pelo seu programa. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de entrada

4
4 5 3 1
10
9 8 7 6 1 4 3 2 12 10
0

Exemplo de saída

Teste 1
3

Teste 2
10

Restrições

0 <= N <= 10000 (N = 0 apenas para indicar o fim da entrada)

Quando um problema diz que a entrada é composta de vários conjuntos de teste, então quer dizer que haverá um novo caso de teste enquanto a condição de parada seja satisfeita. No problema acima, cada caso de teste é composto por um inteiro N e em seguida por N inteiros. Nota-se que nos problemas de online judges nunca será necessário alocação dinâmica, percebemos nesse caso que haverá um vetor de inteiros onde o seu tamanho máximo será definido pela variável N. Observando as restrições impostas pelo problema acima, basta declarar um vetor com 10001 posições (a posição 0 conta).

int i,n,teste,ganhador,v[10001];
teste=1;
while (scanf("%d",&n) && n){ //Enquanto eu ler a variável N e essa variável for diferente de 0
       for (i=0;i<n;++i) //Armazena os N inteiros em um vetor
               scanf("%d",&v[i]);

       //Aqui vai o processamento desse vetor

       printf("Teste %d\n",teste++); //Primeira linha Teste x
       printf("%d\n\n",ganhador); //Segunda linha o ganhador seguido por duas quebras de linhas, pois no enunciado, está claro que a terceira linha da saída deve ser em branco.
}

Espero que tenha esclarecido um pouco a forma como se deve ler e imprimir em um problema de online judge. Aconselho a dar uma lida no site criado pelo Vinicius Fortuna com intuito de auxiliar os iniciantes em maratonas e afins.

Ainda tem dúvidas? Entre em contato ou deixe um comentário.

Resolução F91 por Phyllipe César

Publicado por Phyllipe Categoria: Seletivas|SPOJ

24 Feb 2010
Resumo}
Dado um inteiro N, retorne $f(N)$ seguindo as seguintes restrições:
\begin{enumerate}
\item $ N \geq 101 $
\begin{itemize}
\item $f(N) = N-10$
\end{itemize}
\item $ N \leq 100 $
\begin{itemize}
\item $f(N) = f ( f (N + 11) )$
\end{itemize}
\end{enumerate}
\section{Análise}
Temos dois casos básicos para o problema:
\begin{enumerate}
\item $ N \geq 101 $
\item $ N \leq 100 $
\end{enumerate}
\newline
Para o primeiro caso executaremos a propria definição do algoritmo:
\begin{equation}
f(N) = N - 10
\end{equation}
\newline
O segundo caso é mais "complicado", segue a definição:
\begin{equation}
f(N) = f( f(N + 11) )
\end{equation}
\newline
Note que, se temos um inteiro $x$, sendo $90 \leq x \leq 100$, $f(x+11)$ retornará $x+1$.
\newline
Como dada na definição, o retorno de $f(x)$ será $f( f (x + 11) ) = f(x+1) $
\newline
Considerando $ x = 90 $, notamos que
\begin{equation}
f(90) = f(91) = f(92) = f(93)  = ... = f (101)
\end{equation}
Pela equação de número $2.1$ temos:
\begin{equation}
f(101) = 91
\end{equation}
Logo, $f(90) = f(91) = ... f(100) = f(101) = 91$
\newline
Se temos agora um inteiro $k$, $79 \leq k \leq 89$, temos que $f(k) = f (f (k+11))$ Note que $k+11$ está nos limites de $90 \leq k+11 \leq 100$, logo $f(k+11) = 91$, e temos que $f(k) = f(91) $, que como provado anteriormente, retornará $91$.
\newline
O mesmo façamos para uma variavél, $68 \leq v \leq 78$, $f(v)$ claramente retornará $91$.
\newline
Ou seja, o algoritmo baseia-se em:
\begin{enumerate}
\item $N \geq 101$
\begin{itemize}
\item $return$  $N-10$
\end{itemize}
\item $N \leq 100$
\begin{itemize}
\item $return$ $ 91$
\end{itemize}
  1. \end{enumerate}

Resumo

Dado um inteiro N, retorne f(N) seguindo as seguintes restrições:

  1. N \geq 101
  2. N \leq 100

Link: http://br.spoj.pl/problems/F91/

Análise

Temos dois casos básicos para o problema:

  1. N \geq 101
  2. N \leq 100

Para o primeiro caso executaremos a propria definição do algoritmo:

f(N) = N - 10

O segundo caso é mais "complicado", segue a definição:

f(N) = f( f(N + 11) )

Note que, se temos um inteiro x, sendo 90 \leq x \leq 100, f(x+11)retornará x+1.

Como dada na definição, o retorno de f(x) será f( f (x + 11) ) = f(x+1)

Considerando x = 90 , notamos que

f(90) = f(91) = f(92) = f(9u) = f(100) = f (101)

Pelas equações anteriores temos:

f(101) = 91

Logo, f(90) = f(91) = f(9u) = f(100) = f(101) = 91

Se temos agora um inteiro k, 79 \leq k \leq 89, temos que f(k) = f (f (k+11)) Note que k+11 está nos limites de 90 \leq k+11 \leq 100, logo f(k+11) = 91, e temos que f(k) = f(91) , que como provado anteriormente, retornará 91.

O mesmo façamos para uma variavél, 68 \leq v \leq 78, f(v) claramente retornará 91.

Ou seja, o algoritmo baseia-se em:

  1. N \geq 101
  • return N-10
  1. N \leq 100
  • return 91

[]'s Phyllipe César

Testando o LaTeX

Publicado por Delacyr Categoria: Geral

24 Feb 2010

Testando  o latex no wordpress:

e^{\i \pi} + 1 = 0

Quadrados - OBI

Publicado por Delacyr Categoria: OBI|SPOJ

13 Jul 2009

Tarefa:

Dado um inteiro N, determine quanto vale N2.

Entrada:

A entrada é composta por um único caso de teste, composto por uma única linha que contém o inteiro N.

Como resolver:

Fácil como o problema Soma também da OBI, basta ler um inteiro N, e imprimir uma multiplicação do inteiro com ele mesmo. Assim:


printf("%d\n",n*n);

Problema: 3829. Quadrados

Ainda tem dúvidas? Entre em contato ou deixe um comentário.

Soma - OBI

Publicado por Delacyr Categoria: OBI|SPOJ

13 Jul 2009

Tarefa:

Dada uma lista de N inteiros, encontre a soma de todos eles.

Entrada:

A entrada é composta de um único caso de teste. A primeira linha contém um inteiro positivo N. As N linhas seguintes contêm cada uma um inteiro X, representando os N números a serem somados.

Saída:

Seu programa deve produzir uma única linha na saída, contendo a soma de todos os N inteiros.

Como resolver:

Através de um laço de 1 até N, bastará ler um número a cada iteração, acumulá-lo (somar) em uma variavel denominada soma, e quando sair do laço fazer a impressão dessa variável. Simples.

Problema: 3830. Soma

Ainda tem dúvidas? Entre em contato ou deixe um comentário.

Par ou ímpar - OBI

Publicado por Delacyr Categoria: OBI|SPOJ

7 Jun 2009

Tarefa

Dada uma seqüência de informações sobre partidas de Par ou Ímpar (nomes dos jogadores e números que os jogadores escolheram), você deve escrever um programa para indicar o vencedor de cada uma das partidas.

Como resolver:

Uma das formas de se resolver esse problema (não quer dizer que é a mais fácil) é após ler um inteiro N e os os nomes de cada um dos jogadores (jogador 1 sempre é par, jogador 2 sempre é impar), utilizar um vetor de strings para guardar o nome do vencedor a cada jogada.

struct reg{
char nome[11];
}vetor[1000];

Dentro do laço de N iterações, você lerá os dois valores A e B, após lê-los, basta fazer uma verificação da soma dos valores. Se a soma for par, só copiar o nome do jogador para o vetor de strings na posição i (onde i corresponde a i-ésima iteração). Como copiar strings? Utilizando a função strcpy da string.h.


strcpy(string_destino,string_origem);

Ao final, basta imprimir o vetor de strings seguindo a formatação recomendada pelo problema.

Problema: 1363. Par ou ímpar

Ainda tem dúvidas? Entre em contato ou deixe um comentário.

Crescimento das populações de bacilos - Seletivas

Publicado por Delacyr Categoria: Seletivas|SPOJ

6 Jun 2009

Tarefa

Sua tarefa é, dado um inteiro K (1 <= K <= 10^1000000 ou seja, K pode ter 1000000 de dígitos), determinar os três últimos dígitos do número de bacilos após K instantes de tempo, partindo de uma população inicial com um indivíduo.

Como resolver:

Diante de uma rápida análise do problema KOCH, podemos perceber que se trata de manipulação de big numbers, quem nunca trabalhou com big numbers, aconselho baixar o The Art of Programming Contest (está ali na barra lateral), - um e-book com instruções, códigos genéricos e problemas de maratonas de programação em geral-, pois iremos precisar dele.

Para quem ainda não sacou a idéia, os números de bacilos após K instantes de tempo é simplesmente a sequência de fibonacci. Mas como conseguir o instante K da sequência de fibonacci, quando K pode ter 1000000 de dígitos? Precisaremos manipular big numbers. Para nos poupar tempo, já existe um algoritmo pronto para calcular qualquer instante da sequência de fibonacci, onde esse instante pode ser um número muito grande. (Ver página 219 - The Art of Programming Contest).

Com o código em mãos, nos resta pouco para resolver esse problema. Pesquisando no fórum do SPOJ, descobrimos que existe um padrão da resposta a cada 1500 instantes, então nos bastará apenas utilizar o resto da divisão de K por 1500, mas como fazer divisão de big numbers? Você descobrirá na página 215 no The Art of Programming Contest).

Agora que você já sabe como calcular qualquer big number instante da sequência de fibonacci e também sabe que o resto da divisão de K por 1500 é o número de bacilos, como iremos imprimir apenas os 3 últimos dígitos desse resto? Basta que você você divida novamente o resto por 1000. Independente do valor dessa divisão, para imprimir sempre 3 dígitos, mesmo que o valor dê menos que 3 dígitos, a formatação se dará dessa forma:


printf("%03ld",variavel); //03, quer dizer 3x o número zero

Veja no site do Vinícius Fortuna, os vários formatos de entrada e saída para competições em geral.

Problema: 3090. Crescimento das populações de bacilos

Dúvidas? Entre em contato ou deixe um comentário.

Cofrinhos da Vó Vitória - OBI

Publicado por Delacyr Categoria: OBI|SPOJ

6 Jun 2009

Tarefa

Vó Vitória está ?cando velha e tem medo que deslizes de memória a façam cometer injustiças com os netos, deixando de compensar as diferenças entre os cofrinhos. Sua tarefa é ajudar Vó Vitória, escrevendo um programa de computador que indique as diferenças entre os depósitos, de forma que ela não tenha que preocupar-se em memorizá-las.

Como resolver:

Inicialmente, para armazenar - e depois imprimir - as diferenças de depósitos de Joãozinho e Zezinho, você necessitará utilizar um vetor zerado. Uma dica é utilizar a função memset da bibiliteca string.h. Após feito isso, inicia-se o processo de guardar a diferença entre o depósito do Zezinho e Joãozinho. Dentro de um laço de N iterações, você lerá o valor do depósito de cada um deles. Após a leitura dos depósitos, agora é o momento de guardar a diferença dos depósitos no vetor, lembrando que você deve tratar juntamente com a diferença do depósito anterior. Ficando dessa forma:

diferenca[i]=(diferenca[i-1]+deposito_joaozinho)-deposito_zezinho;

Assim você trata de incluir a diferença do depósito feito anteriormente no cáculo da nova diferença de depósitos entre os netos da Vó Vitória.

Problema: 840. Cofrinhos da Vó Vitória

Dúvidas? Entre em contato ou deixe um comentário.

Meteoros - OBI

Publicado por Delacyr Categoria: OBI|SPOJ

6 Jun 2009

Tarefa

São dados:

  • uma lista de pontos no plano cartesiano, onde cada ponto corresponde à posição onde caiu um meteorito;
  • as coordenadas de um retângulo que delimita uma fazenda.

As linhas que delimitam a fazenda são paralelas aos eixos cartesianos. Sua tarefa é escrever um programa que determine quantos meteoritos caíram dentro da fazenda (incluindo meteoritos que caíram exatamente sobre as linhas que delimitam a fazenda).

Como resolver:

Esse problema é de simples solução, o objetivo do METEORO é descobrir quantos meteoritos caíram dentro da fazenda. Depois que você ler os as coordenadas de um retângulo (X1, Y1, X2, Y2),  dentro de um laço com N iterações, ler os pontos (X,Y) e após cada leitura, já comparar com as coordenadas do retângulo para descobrir se o meteorito caiu dentro da fazendo ou não. Para tal, basta verificar se X está entre X1 e X2 e Y entre Y1 e Y2, caso essa verificação seja verdadeira, some 1 meteorito a mais que caiu dentro da fazenda, depois basta imprimir tal variável.

Problema: 1330. Meteoros

Dúvidas? Entre em contato ou deixe um comentário.

Bits Trocados - OBI

Publicado por Delacyr Categoria: OBI|SPOJ

5 Jun 2009

História

As Ilhas Weblands formam um reino independente nos mares do Pacífico. Como é um reino recente, a sociedade é muito influenciada pela informática. A moeda oficial é o Bit; existem notas de B$ 50,00, B$10,00, B$5,00 e B$1,00. Você foi contratado(a) para ajudar na programação dos caixas automáticos de um grande banco das Ilhas Weblands.

Tarefa

Sua tarefa é escrever um programa que, dado o valor de Bits desejado pelo cliente, determine o número de cada uma das notas necessário para totalizar esse valor, de modo a minimizar a quantidade de cédulas entregues. Por exemplo, se o cliente deseja retirar B$50,00, basta entregar uma única nota de cinquenta Bits. Se o cliente deseja retirar B$72,00, é necessário entregar uma nota de B$50,00, duas de B$10,00 e duas de B$1,00.

Como resolver:

Para esse problema, basta que você tenha conhecimento dos operadores de divisão e resto, que são "/" e "%", respectivamente. O que você vai fazer é simplesmente manipular o valor de Bits que o cliente informou. Para saber o número mínimo de notas a ser entregue, basta que você guarde em cada variável declarada para cada tipo de nota (50,10,5 e 1), o resultado da divisão do Bit informado pelo cliente por 50, 10, 5, 1, mas claro, antes de passar para a próxima divisão, atualize o valor que restou de Bits, fazendo com que esse valor (bits informado pelo cliente) receba o resto da divisão do valor de bits pelo valor da nota em questão. Ex: (Bit = Bit % 50). Ao final, basta imprimir as variáveis de cada nota.

Problema: 812. Bits Trocados

Dúvidas? Entre em contato ou deixe um comentário.

Sobre este blog

Criado com objetivo de compartilhar informações sobre tudo que diz respeito a algoritmos, estruturas de dados e problemas de online judges.

Dúvidas ou sugestões? Entre em contato.

Categorias

Links

E-Books

  • emily: alguem pode me ajudar a responder essa questao? ler tres valores(A,B,C) e apresentá-los em ordem [...]
  • alles loane bastos da silva: estou com duvidas em um exercicios referente ao da Leticia de elaborar um conversor que suporte tres [...]
  • leticia: olá pessoal estou aprendendo uma materia nova esse ano, e eu nao estou conseguindo realizar esse pr [...]
  • Débora: ALGUÉM PODE ME AJUDAR A RESOLER ESSE ALGORITMO. Escreva um programa que leia 5 notas entre 0 e 1 [...]
  • MARCOS: ALGUEM PODE ME AJUDAR FAZENDO FAVOR? faça um algoritmo que leia 200 idades, entre 1 e 15 anos (val [...]

Copyright © 2009 - Algoritmos - is proudly powered by WordPress | Log in

Compositio Theme is created by: Design Disease brought to you by PremiumThemes.com