• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

electron++

[Duvida]Inputs ranhosos...

13 mensagens neste tópico

Oi!

Eu estou no treino das ONI e deparei-em com situações de input que nunca tem tinham acontecido...

Existem dois problemas.

Num deles http://www.dcc.fc.up.pt/oni/problemas/2007/qualificacao/probA.html

temos que receber um quantidade de nomes so numa linha de input.

Nesta situação duvido que seja para fazer uma string gigante e depois analisa-la, até porque isso iria demorar muito e consumir tempo precioso de execução, suponho que deve haver uma função que faz isso por nós.  :hmm:

Noutro http://www.dcc.fc.up.pt/oni/problemas/2006/qualificacao/probC.html

a quantidade de linhas que vão ser inseridas não são especificadas, neste estou sem ideias....

Alguém sabe tratar destes inputs??

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

No segundo lês até ao EOF (End of File).

No primeiro tens uma opção muito simples. Como podes ter até 100000 nomes, o melhor é leres caracter a caracter.

Cada caractér não terminal (a, b, X, Z), é concatenado numa string. Quando encontrares caracter espaço, começas a registar outro nome.

Há outras formas, mas não é com o tempo de processar o nome que tens de te preocupar. Esse problema do pim pam pum é bastante simples, se tiveres noções de aneis.

Cumprimentos

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

EOF??

os dados são introduzidos "á mão" não é por nenhum ficheiro...

Noção de aneis...

Sinceramente desconheço, não tens ai nenhum link sobre o tema???

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Desculpa mas estás errado. Os inputs são inseridos "automaticamente".

Na consola se fizeres: "programa < input.txt", em que input.txt é um ficheiro de texto qualquer, ele vai reconhecer isso com o input (stdin). Procura melhor sobre esse tema.

Sobre anéis não tenho assim nada a jeito, mas tenho um exemplo simples:

Anel 7.

- 5 vale 5

- 7 vale 0 ( 7 % 7 = 0 )

- 8 vale 1 ( 8 % 7 = 1 )

- 16 vale 2 ( 16 % 7 = 2 )

Anéis basicamente são a base para muitos algoritmos de criptação, que operam sobre anéis primos enormes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

No primeiro tens uma opção muito simples. Como podes ter até 100000 nomes, o melhor é leres caracter a caracter.

Não. As operações de input/output são "pesadas". Neste caso, o melhor é ler a linha com os nomes todos para um array grande e depois retirar os nomes do array.

Há outras formas, mas não é com o tempo de processar o nome que tens de te preocupar. Esse problema do pim pam pum é bastante simples, se tiveres noções de aneis.

Se bastasse isto não existia apenas um concorrente com 100 pontos (exercício totalmente certo). Não basta porque temos imensos concorrentes (100000).

Eu acho que deve existir alguma forma de calcular o resultado com N pessoas baseado em rodas com N-1 pessoas e assim sucessivamente, mas não achei muito interessante o exercício.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu acho que deve existir alguma forma de calcular o resultado com N pessoas baseado em rodas com N-1 pessoas e assim sucessivamente, mas não achei muito interessante o exercício.

Baseia-se no resto da divisão.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Baseia-se no resto da divisão.

Sim..isso é óbvio... a parte de ignorar as pessoas que foram eliminadas é que é mais complicada de fazer em tempo constante, senão a solução excede o tempo limite.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. As operações de input/output são "pesadas". Neste caso, o melhor é ler a linha com os nomes todos para um array grande e depois retirar os nomes do array.

Com 10000 nomes como adivinhas o tamanho da linha?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Era dito no enunciado que os nomes e palavras não excediam 10 letras logo tinhamos no máximo 100.000 nomes * (10 caracteres + 1 espaço) podiamos ler uma linha de 1.200.000  caracteres por exemplo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Era dito no enunciado que os nomes e palavras não excediam 10 letras logo tinhamos no máximo 100.000 nomes * (10 caracteres + 1 espaço) podiamos ler uma linha de 1.200.000  caracteres por exemplo.

Isso são 1,144MB. Qual é o limite de memória do problema?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora