Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Rui_Santos

Programação C# e Pascal

Mensagens Recomendadas

Rui_Santos

Boas, não consigo resolver uns problemas entre eles A B e C..

Podem me ajudar ?

Problema A

Problema A - Frota Imperial

maníaco Palpatine é o Imperador e supremo líder do Império Galáctico. Para que o seu regime possa manter o controlo sobre todas as galáxias, Palpatine necessita de uma enorme frota imperial constituída por milhões de diferentes naves espaciais. Para facilitar a tarefa logística de coordenar toda esta frota, o Imperador decidiu numerar todas as naves com números inteiros consecutivos, começando no número 1. Sempre que uma nova nave sai de um estaleiro espacial recebe o primeiro número livre que nunca tenha sido antes atribuído.

Recentemente, Palpatine requisitou uma escolta para poder visitar Naboo, o planeta onde nasceu. O esquadrão escolhido corresponde a um conjunto de naves numeradas consecutivamente, tal como em todas as suas outras viagens anteriores. Em particular, eram as naves 88, 89 e 90. Palpatine reparou com agrado que o dígito (ou algarismo) 8, o seu favorito, era o mais frequente nos números destas naves, pois aparecia três vezes (o dígito 9 aparece duas vezes e o dígito 0 uma vez). Como a sua ânsia por poder era infinita (∞), nada como ter um dígito (8) que lhe fazia lembrar precisamente isso!

Palpatine pôs-se a pensar e reparou que numa viagem anterior tal não tinha acontecido e o dígito mais frequente era outro. Isto desagradou-lhe e decidiu que a partir de agora tal nunca mais iria acontecer. O problema é que os esquadrões são em tão quantidade que se torna complicado contar os dígitos manualmente. Como Grande Almirante do Império Galáctico, tens de ajudar o Imperador. Sabendo que os esquadrões a considerar estão sempre numerados consecutivamente, qual é o dígito que aparece mais vezes? E quantas vezes aparece?

O Problema

Dada um conjunto de N intervalos de números, a tua tarefa é descobrir, para cada intervalo, qual o(s) dígito(s) que aparece mais vezes, bem como quantas vezes ele aparece.

Input

Na primeira linha vem um único número inteiro N, indicando a quantidade de intervalos a considerar.

Nas N linhas seguintes vem um par de números Ai Bi (separados por um espaço), indicando que i-ésimo intervalo de números a considerar é [A,B] (ou seja, os números de A a B, inclusive).

Output

O output deve ser constituído por N linhas, uma para cada um dos intervalos do input. Cada uma destas linhas deve começar por ter um número inteiro indicando quantas vezes aparece o dígito mais frequente, seguida de uma lista (por ordem crescente) dos dígitos que aparecem com essa frequência máxima. Todos os números de uma mesma linha devem ser separados por um único espaço.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa: 1 ≤ N ≤ 1 000 Número de intervalos a considerar 1 ≤ A ≤ B ≤ 1 000 000 000 Limites de cada intervalo

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 30% dos pontos, acontece sempre que A ≤ B ≤ 1 000.

Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que A ≤ B ≤ 1 000 000

Exemplo de Input

4

88 90

99 100

1 9

1 10

Exemplo de Output

3 8

2 0 9

1 1 2 3 4 5 6 7 8 9

2 1

Explicação do Input/Output

A primeira linha do output, 3 8, indica que para o primeiro intervalo (que era [88,90] o dígito que aparece mais vezes é o 8, e que aparece três vezes. A segunda linha, 2 0 9 diz respeito ao segundo caso ([99,100]) e diz que os dígitos que aparecem mais vezes são o 0 e 9, sendo que aparecem duas vezes cada um. A terceira linha diz respeito a [1,9] e diz que os dígitos 1, 2, 3, 4, 5, 6, 7, 8 e 9 são os que aparecem mais vezes (uma vez, neste caso). Finalmente, a quarta linha diz que no intervalo [1,10] o dígito mais frequente é o 1, que aparece duas vezes.

Problema B

Problema B - Viagem Alternativa

o Darth Vader tem a sua nave privada a arranjar, tem de recorrer aos serviços de transportes públicos. Na sua galáxia existe um serviço chamdo TIE Bus, uma nave semelhante um TIE Fighter, mas mais comprida e com vários lugares. Um TIE Bus tem N lugares que são dispostos numa linha. Todos os lugares têm um número de 1 a N, referente à sua ordem na linha.

O Darth Vader observou que durante uma viagem iam entrando pessoas e saindo uma a uma, sem nenhuma ordem fixa. Cada pessoa entra inicialmente para um lugar fixo L que é indicado no bilhete que têm de ter para viajar no TIE Bus. Porém, ninguém gosta do lugar que lhes calha, ou porque é perto de uma janela, ou porque não é perto de uma janela, ou simplesmente porque conhecem alguém num lugar distante daquele e querem conversar. Por isso, cada pessoa escolhe um número P e procuram o P-ésimo lugar desocupado, ou seja, um lugar que tem P lugares desocupados entre ele e L. O P-ésimo lugar pode ser tanto antes como depois de L (ou o próprio L), depende da preferência do passageiro. Caso não existam P lugares desocupados (na direção preferida), o passageiro em questão amua e decide sair à procura de um novo TIE Bus. Notem que o próprio lugar L pode estar ocupado, pois alguém pode ter escolhido esse lugar anteriormente e que podem haver vários passageiros com o mesmo lugar L no bilhete independentemente de quando entram (a empresa é um bocadinho desorganizada).

Um possível exemplo deste comportamento é o seguinte:

  • O Darth Vader entra num TIE Bus de 5 lugares (nota que ele, como governador da galáxia, tem um lugar especial e não ocupa nenhum dos 5 lugares que estamos a estudar).
  • Entra um passageiro para o lugar 3 e decide procurar o 1º lugar desocupado depois do seu, que é o seu próprio lugar (aqui a definição de depois inclui o seu próprio lugar) e por isso fica no lugar 3.
  • Entra um passageiro para o lugar 1 e decide procurar o 3º lugar desocupado depois do seu, que é o lugar 4 (visto que o 3 está ocupado) e por isso fica no lugar 4.
  • O passageiro do lugar 3 chega ao seu destino e sai.
  • Entra um passageiro para o lugar 5 e decide procurar o 2º lugar desocupado antes do seu, que é o lugar 3 (visto que o 4 está ocupado) e por isso fica no lugar 3.

O Problema

Dado o tamanho N do TIE Bus e um número de mudanças de passageiros Q, a tua tarefa é descobrir onde fica cada um dos passageiros que entra. Uma mudança é uma entrada de um passageiro para um lugar L, um número escolhido P e um sentido de procura s (o sentido procura representa o sentido para onde esse passageiro se desloca, para depois ou antes deL) ou uma saída do passageiro de um lugar L.

Input

Na primeira linha vêm dois números inteiros separados por um espaço: N, o número de lugares e Q, o número de mudanças.

Seguem-se Q linhas indicando as mudanças. Cada uma delas começa por ter um caracter indicando o tipo de mundaça. Se o caracter for um 'E', significa que entrou um passageiro e por isso segue-se um inteiro L, o seu lugar, um inteiro P, o número de lugares desocupados que o passageiro se desloca, e um segundo caracter que representa o sentido de procura (o sentido de procura pode ser 'D', que significa que procura um lugar depois do seu, ou 'A', que significa que procura um lugar antes do seu). Se o caracter for um 'S', significa que saiu um passageiro e por isso segue-se um inteiro L que representa o lugar de onde ele sai.

É garantido que todas as saídas e entradas de passageiros são válidas.

Output

Para cada mudança em que entre um passageiro, uma linha com um inteiro representando o lugar onde esse passageiro ficou ou, caso não encontre lugar, a palavra "Saiu" (sem as aspas).

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa: 1 ≤ N ≤ 500 000 Número de Lugares 1 ≤ Q ≤ 500 000 Número de Mudanças 1 ≤ L, P ≤ N Lugar de entrada ou de saída e número de lugares que cada passageiro se desloca

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, o valor de N será menor ou igual a 1 000 e Q e será menor que 100.

Para um conjunto de casos de teste valendo 60% dos pontos, o valor de Q será menor ou igual a 10 000.

Exemplo de Input 1

5 4

E 3 1 D

E 1 3 D

S 3

E 5 2 A

Exemplo de Output 1

3

4

3

Explicação de Input/Output 1

Este caso refere-se ao exemplo dado no enuncidado

Exemplo de Input 2

6 7

E 1 1 D

E 6 1 A

E 1 1 D

E 6 1 A

E 4 2 D

S 6

E 1 3 D

Exemplo de Output 2

1

6

2

5

Saiu

6

Problema C

Problema C - Contrabando de Mel

Darth Vader, como indivíduo extremamente culto, tem uma grande estima pela IOI (International Olympiad in Informatics) e por isso não podia deixar de estar presente na 25ª edição da competição, na Austrália. Antes de apanhar uma nave de transporte intraterráqueo, ficou alojado uma noite num hotel. No dia de partida, não pôde deixar de comer um bom pequeno-almoço. Foi aí que visionou uma pequena maravilha da natureza: um mini-pote de mel.

Sem ninguém notar, o Darth Vader colocou um largo conjunto de mini-potes de mel de baixo da capa e foi para o espaçoporto. Infelizmente aí deparou-se com um problema: como passar os mini-potes de mel pela segurança?

O Darth Vader tem à sua disposição N malas de viagem seguidas, numa linha (a ordem é mantida sempre). Cada mala pode levar no máximo um único mini-pote de mel. No entanto, se existirem mini-potes mel muito próximos uns dos outros a segurança pode desconfiar que o Darth Vader está a fazer contrabando e prendê-lo. Cada mala tem um alcance pré-determinado Ai. O alcance de cada mala representa a distância mínima a que tem de estar a próxima mala (à frente ou atrás) com um mini-pote de mel (a distância mede-se em número de malas no intervalo).

Como exemplo, imagina que o Darth Vader tem um conjunto de malas com os seguintes alcances:

3 3 2 1 3 2

Se pusermos um mini-pote na terceira mala (que tem alcance 2) só podemos pôr mini-potes na primeira mala e a partir da quinta mala (de alcance 3).

Com estas condicionantes, qual o número máximo de potes de mel que é possível colocar?

O Problema

Dado um conjunto de N malas e os respetivos alcances Ai, a tua tarefa é determinar o número máximo de mini-potes de mel que o Darth Vader consegue levar para a Austrália sem ser preso por contrabando. Podes assumir que o número de mini-potes de mel disponíveis era suficiente para encher todas as malas, se tal fosse possível.

Input

Na primeira linha vem um único número inteiro N, indicando o número de malas.

Segue-se uma linha com N números inteiros (separados por um único espaço) onde o i-ésimo número representa o alcance Ai da i-ésima mala.

Output

Uma linha contendo um único inteiro que representa o maior número de mini-potes de mel que o Darth Vader pode levar.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa: 1 ≤ N ≤ 10 000 Número de malas 1 ≤ Ai ≤ N Alcance da i-ésima mala

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 30% dos pontos, o valor de N será menor ou igual a 20.

Para um conjunto de casos de teste valendo 60% dos pontos, o valor de N será menor ou igual a 100.

Exemplo de Input 1

5

1 2 3 2 1

Exemplo de Output 1

2

Clarificação de Output 1

A resposta corresponde à seguinte situação (existem várias possíveis):

X - - - X

Onde o 'X' representa uma mala escolhida e '-' uma não escolhida.

Exemplo de Input 2

7

1 7 2 7 2 3 1

Exemplo de Output 2

4

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
nunopicado

Mais concretamente, quais são as tuas dúvidas?

Descarregar os problemas aqui sem indicares as dúvidas não ajuda a esclarece-las. ;)


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
nunopicado

Ajudar, terás quem te ajude...

Mas se não puseres duvidas concretas, significa que queres que te façam o trabalho.

E isso duvido que alguém faça.

Começas um programa de cada vez, tenta fazer, e quando esbarrares em alguma duvida concreta, coloca aqui.

  • Voto 1

"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Estes problemas são da qualificação das Olimpiadas Nacionais de Informática. O autor do tópico está a violar as regras da competição.

Por favor não lhe respondam até às 18h de hoje, data do fim da qualificação.

  • Voto 1

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
nunopicado

Proponho ao autor, caso não considere a afirmação anterior como verdadeira, que o indique aqui.

Caso contrário, e assim for, gostava que me tirasse uma curiosidade.

Quebrar as regras logo na qualificação não iria ser apenas adiar o problema? "OK, estou qualificado, e agora? Como continuar as olimpíadas?"


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
thoga31

Tópico encerrado por violação das Regras do Fórum, ponto 2.3 (citado no final), com a agravante da quebra das regras da competição de onde os problemas aqui colocados tiveram origem.

2. Tópicos e mensagens:

3. Não é permitida a criação de tópicos ou colocação de mensagens a pedir que se façam trabalhos. Pedir ajuda é diferente de pedir trabalhos feitos. Em caso de incumprimento o staff pode bloquear, ou mesmo apagar, o tópico/mensagem.


Knowledge is free! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Convidado
Este tópico está fechado a novas respostas.

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.