Comentário NOIC OBI 2017 - Fase 1 - Programação Nível 1

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:

Entrada e saída (Aula 1)
Estruturas condicionais (Aula 2)

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:

	// Teleférico - F1P1 - OBI 2017
	// Rogério Júnior
	// Complexidade: O(1)

	#include <cstdio> // scanf e printf

	int main(){

	// declaro e leio os valores de C e A
	int c, a;
	scanf("%d %d", &c, &a);

	// o número de viagens começa com a quantidade de viagens
	// em que o bonde vai totalmente lotado
	int v=(c-1)/a;

	// se ainda sobrarem alunos, adiciono mais uma viagem
	if((c-1)%a!=0) v++;

	// por fim, imprimo o número final de viagens
	printf("%d\n", v);

	return 0;
	}

view raw

teleferico.cpp

hosted with ❤ by GitHub

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é 10⁵. 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:

	// Segredo do Cofre - F1P1 - OBI 2017
	// Rogério Júnior
	// O(N+M)

	#include <cstdio> // scanf e printf
	#include <algorithm> // min e max

	using namespace std;

	#define MAXN 100100 // defino o valor de MAXN

	// declaro, respectivamente, N, M, e vetor que representa a barra
	// e o vetor de frequência das posições
	int n, m, v[MAXN], f[MAXN];

	// declaro o vaetor que guardará a frequência final de cada dígito
	long long dig[10];

	// função upd
	void upd(int l, int r, int d){

	f[l]+=d;
	f[r+1]-=d;
	}

	int main(){

	//leio os valores de N e M
	scanf("%d %d", &n, &m);

	// leio os valores em cada posição da barra
	for(int i=1;i<=n;i++) scanf("%d", &v[i]);

	// declaro last, que começa com valor 1
	int last=1;

	// adiciono 1 à frequência da primeira posição
	upd(1,1,1);

	// em cada operação
	for(int i=1;i<=m;i++){

	// leio a posição para onde o controle deve ir
	int next;
	scanf("%d", &next);

	// defino os valores de L e R
	int l=min(last,next), r=max(last,next);

	// uso upd para adicionar 1 à frequência de todas as posições entre L e R
	upd(l,r,1);

	// e depois retiro uma unidade da frequência da posição last
	upd(last,last,-1);

	// atualizo o novo valor de last para a próxima operação
	last=next;
	}

	// para cada posição da barra
	for(int i=1;i<=n;i++){

	// descubro sua frequência adicionando a ela a soma
	// das frequêncas de todas as casas anteriores
	// ela ordem das operações, f[i-1] já guarda essa soma,
	// logo basta adicionar seu valor a f[i], que agora
	// também guardará toda a soma do prefixo que acaba nele
	// e será usada para definir essa soma para i+1
	f[i]+=f[i-1];

	// e adiciono a frequência da posição no dígito que ela guarda
	dig[v[i]]+=f[i];
	}

	// por fim, basta imprimir a frequência de cada dígito
	for(int i=0;i<10;i++) printf("%d ", dig[i]);

	printf("\n");

	return 0;
	}

view raw

cofre.cpp

hosted with ❤ by GitHub