Comentário por Rogério Júnior
Para ver o caderno de tarefas da primeira fase da Programação Nível 1 da OBI 2017, clique aqui.
Teleférico
Conhecimento prévio necessário:
Este problema tem um enunciado bem simples. A entrada nos dá a capacidade C da cabine e a quantidade A de alunos que precisam ser transportados, e nos pergunta quantas viagens são necessárias. Primeiramente, como o monitor sempre vai, vamos trabalhar com a capacidade de C-1, pois já contaremos sua vaga. Para saber o número de viagens em que a cabine vai cheia, basta calcularmos o valor de (C-1)/A. Em C++, essa operação retorna um inteiro, ou seja, o piso da divisão. Deste modo, precisamos checar se essa divisão dá um valor exato (sem resto) ou se sobram ainda alguns alunos. Assim, se V for o total de viagens, seu valor inicial deve ser (C-1)/A, e se houver algum resto na divisão (if((C-1)%A!=0)), então devemos adicionar uma unidade a V. Por fim, basta imprimirmos o total de viagens. Segue o código para melhor entendimento:
https://gist.github.com/rogerioagjr/18bfe8829a57ab8719b7a3146b271f00
Segredo do Cofre
Conhecimento prévio necessário:
- Entrada e saída (Aula 1)
- Estruturas condicionais (Aula 2)
- Vetores (Aula 3)
- Funções (Aula 4) – não são estritamente necessárias para a solucionar o problema, mas serão utilizadas nessa solução para facilitar o entendimento.
Podemos adaptar o enunciado do problema para uma tarefa um pouco mais formal que facilitará nosso entendimento do código. Cada operação de deslizar o controle do cofre de uma posição para outra pode ser entendida como uma operação realizada num intervalo (L,R) de adicionar um determinado valor D à frequência de cada elemento neste intervalo. Deste modo, devemos implementar uma função upd(L,R,D) que realize esta operação. Assim, em cada operação, devemos saber a posição last em que o controle estava e, ao lermos a posição next para a qual ele deve ir, a mais à esquerda será L e a mais à direita será R. Como queremos adicionar uma unidade a cada elemento no intervalo, chamaremos upd(L,R,1). Depois disso, como não deveríamos contar last novamente, pois ela já foi considerada na operação anterior, devemos tirar uma unidade da frequência da posição last, o que fazemos chamando upd(L,R,-1). Note que last deve começar com o valor 1 e que, como não devemos desconsiderá-lo na primeira operação de upd (pois não houve operação anterior que contasse o last), devemos adicionar uma unidade à frequência da posição 1 antes de processarmos as operações. Fazemos isso, chamando upd(1,1,1).
Por fim, bastaria que percorrêssemos o vetor de frequências que criamos. Em cada posição i, adicionaríamos o valor guardado na frequência desta posição à quantidade de aparições do dígito que está na posição i da barra descrita na entrada. Após isso, só precisaríamos imprimir a frequência total de cada dígito, como e pedido.
O problema, agora, resume-se a implementar a função upd. Não podemos fazer de uma maneira ingênua que percorra todas as casas de L a R, adicionando uma unidade em cada uma, pois isso seria muito lento, visto que a complexidade ficaria O(N) para cada chamada da função e a complexidade final do problema seria O(N*M), o que é muito grande pois ambos N e M podem ir até 105. Sabendo disso, implementaremos a função upd em complexidade constante usando somas parciais. Nós não criaremos um vetor que representa a frequência de cada posição, mas um em que a soma parcial de todo o prefixo até determinada posição representa a sua frequência. Ou seja, se queremos o vetor 0 0 1 1 0, precisamos do vetor 0 0 1 0 -1, pois o primeiro representa a soma parcial de cada um dos prefixos do segundo. Faremos isso pela eficiência porque, agora, para alterarmos todo um intervalo, basto realizarmos duas operações. Se adicionarmos D à posição L de nosso vetor e -D à posição R, note que o valor de D será adicionado a todos os prefixos compreendidos entre L e R, inclusive. Assim, basta que upd realize essas duas operações e, após processada toda a entrada, transformemos o vetor em que upd estava trabalhando no seu vetor de somas parciais, fazendo com que cada posição $$a_i$$ receba o valor de $$\sum_{j=1}^i a_j$$, ou seja, que seja somado ao seu valor a soma de todas as posições anteriores a ela, o que podemos fazer com um único for.
Por fim, basta contarmos as aparições de cada dígito, como explicado anteriormente, e imprimirmos. Não podemos esquecer que um dígito pode estar em até $$10^5$$ posições e ser contado em cada uma das $$10^5$$ operações, aparecendo $$10^10$$ vezes, logo, a frequência de cada dígito deve estar guardada em um long long. Segue o código para melhor entendimento:
https://gist.github.com/rogerioagjr/71e77e3ff30b4be5c05756c09b3d95aa