Estiagem

Revista Brasileira de Computação Aplicada (ISSN 2176-6649), Passo Fundo, v. 5, n. 2, p. xx-xx, out. 2013 1

Estiagem

Gilberto Gampert1

Resumo: Este artigo descreve a solução para o problema denominado Estiagem apresentado na

XIII Maratona de Programação IME-USP de 2009. O contexto do problema é calcular o consumo

médio de determinadas regiões para avaliar o comportamento da população em época de

racionamento. Serão informados dados de consumo de algumas cidades (por amostragem) e o

algoritmo deverá apresentar o consumo por pessoa e o consumo médio da cidade por habitante.

Como há um limitador de tempo, o resultado deverá ser apresentado em menos de 2 segundos.

Palavras-chave: URI Online Judge. Otimização de algoritmo. Problema da estiagem.

Abstract: This article describes the solution to the problem named Drought presented in the XIII

Programming Marathon IME-USP, 2009. The context of the problem is calculate the average

consumption of certain regions to assess the behavior of the population in times of rationing.

Consumption data from some cities will be informed (by sampling) and the algorithm should

present per capita consumption and the average consumption of the city. As there is a limit of

time, the result should be displayed in less than 2 seconds.

Keywords: URI Online Judge. Algorithm optimization. Problem of drought.

1 O problema da estiagem

O presente artigo, para a disciplina de Algoritmos e Estruturas de dados, visa apresentar a solução para o

problema da Estiagem, que foi apresentado na XIII Maratona de Programação IME-USP de 2009, que foi obtido

no site URI Online Judge.

Segundo o autor do problema [1], o governo federal criou um órgão para avaliação do consumo em

regiões onde ocorre estiagem. O objetivo é avaliar o comportamento da população em época de racionamento.

Este órgão vai avaliar algumas cidades (por amostragem) e calcular o consumo por pessoa e o consumo médio

da cidade habitante.

1.1 Entrada

Serão fornecidos diversos casos de teste. Para cada caso deve-se informar um número inteiro N (1 ≤ N ≤ 1*106) que indica a quantidade de imóveis. Para cada imóvel deve-se ler um par de valores inteiros, sendo o

primeiro X (1 ≤ X ≤ 10) indicando a quantidade de moradores e o segundo Y (1 ≤ Y ≤ 200) indicando o

consumo total do imóvel. Nenhum imóvel consome mais do que 200 m3 por mês. Deve-se indicar o final da

entrada de dados informando o número 0 (zero) na quantidade de imóveis.

1.2 Saída

Para cada conjunto de informações, deve-se exibir a mensagem “Cidade# n:”, sendo n o número da

cidade. A seguir deve-se listar, em ordem crescente de consumo, a quantidade de pessoas, um hífen e o consumo

destas pessoas (arredondado para baixo). Na próxima linha, deve-se exibir o consumo médio por pessoa da

cidade, com 2 casas decimais e sem arredondamento. Imprimir uma linha em branco entre dois casos de testes.

1 Programa de Pós-Graduação em Computação Aplicada. Instituto de Ciências Exatas e Geociências, UPF, Campus 1 - BR

285 - Passo Fundo (RS) - Brasil {[email protected]}


No final da saída não deve haver uma linha em branco. A Tab. 1 exemplifica um conjunto de entrada e as saídas

esperadas.

Tabela 1: Exemplo de entradas e saídas

Entradas Saídas

3

3 22

2 11

3 39

5

1 25

2 20

3 31

2 40

6 70

0

Cidade# 1:

2-5 3-7 3-13

Consumo medio: 9.00 m3.

Cidade# 2:

5-10 6-11 2-20 1-25

Consumo medio: 13.28 m3.

2 Solução

Após o estudo do problema, identificou-se que existem 2 desafios principais na resolução do problema:

Primeiro: acumular e exibir em ordem crescente de consumo;

Segundo: o limite de tempo de 2 segundos.

Percebeu-se que a melhor forma de acumular o consumo é utilizar um vetor.

Antes de chegar na solução que proposta neste trabalho, testou-se a possibilidade de trabalhar com

alocação dinâmica para o vetor e a utilização de um método de ordenação. Descreve-se a seguir as duas técnicas

utilizadas e a conclusão de qual foi mais eficiente.

2.1 Alocação dinâmica e ordenação

Na primeira alternativa de solução, após ler os dados de uma cidade, calculou-se o consumo por pessoa

para cada imóvel e verificou-se se o consumo já estava presente no vetor. Em caso positivo, somou-se o número

de pessoas naquela posição do vetor. Caso contrário, uma nova posição foi alocada dinamicamente e inicializada

com o número de pessoas. Após ler e processar todos os valores da cidade, procedeu-se com a ordenação do

vetor, utilizando o algoritmo quicksort [2]. O pseudocódigo abaixo demonstra o núcleo da ideia:

1. ler num;

2. para i de 0 até num { 3. ler pessoas, consumo; 4. cons_med = arred_abaixo((inteiro) consumo / pessoas); 5. se cons_acum[cons_med] 6. cons_acum[cons_med] += pessoas; 7. senão {

8. aloca(cons_acum[cons_med]); 9. cons_acum[cons_med] = pessoas; 10. }

11. }

12. ordenar(cons_acum);

Ao término da execução do algoritmo desta técnica, utilizando como entrada o primeiro caso do exemplo

da Tab. 1, o vetor apresentou-se como mostrado na Figura 1. Esta técnica falha em atender aos requisitos do

problema, pois a mesma estourou o tempo limite de 2 segundos.


Figura 1: Vetor após a execução da primeira técnica

2.2 Acumular ordenado

Na segunda alternativa, utilizou-se um vetor com alocação prévia de 200 posições, pois o problema deixa

claro que o consumo não poderá ser maior do que este valor, estabele-se assim um limitador. Então, utilizamos a

fórmula descrita em (1) para determinar o índice do vetor. O valor obtido, é um dos possíveis consumos, no

intervalo fechado de 1 até 200.

indice = arred_abaixo((inteiro) consumo / pessoas);

(1)

Basta acumular o número de pessoas que apresentam este consumo no índice do vetor obtido no cálculo e

o vetor estará organizado automaticamente. O pseudocódigo a seguir ilustra a técnica:

1. declara e inicializa cons_acum[200];

2. ler num;

3. para i de 0 até num { 4. ler pessoas, consumo; 5. indice = arred_abaixo((inteiro) consumo / pessoas); 6. cons_acum[indice] += pessoas; 7. }

Ao término da execução do algoritmo desta técnica, utilizando como entrada o primeiro caso do exemplo

da Tab. 1, o vetor apresentou-se como mostrado na Figura 2.

Figura 2: Vetor após a execução da segunda técnica


Esta nova abordagem tem a vantagem de acumular a quantidade de pessoas na posição que o índice do

vetor que corresponde ao consumo aponta e desta forma, automaticamente, ordena em ordem crescente de

consumo. Como não há necessidade de alocar dinamicamente cada posição do vetor e nem ordenar para exibir

em ordem crescente, o tempo limite de 2 segundos foi respeitado.

3 Considerações finais

Observou-se que a primeira técnica foi mais eficiente na utilização da memória. Ela somente aloca uma

nova posição no vetor quando detecta uma nova média de consumo. Porém, apesar de mais econômica, a técnica

estourou o tempo limite pelo problema, sendo assim descartada.

A segunda técnica não apresentou tanta eficiência na utilização de memória, pois iniciava o algoritmo

com o vetor de 200 posições pré-alocado. Mas, foi muito mais eficiente na execução para o pior caso, 1*106

casos, sendo que apresentou tempo inferior ao limite proposto pelo problema.

Referências

[1] TONIN, Neilor. Estiagem. Uri Online Judge (Online), 2009. Disponível em:

http://www.urionlinejudge.com.br/judge/pt/problems/view/1023. 1023. Acesso em: 25 mai. 2014.

[2] FARIAS, Fábio Henrique de; SILVA, Fabiano Barbosa Mendes da. Quicksort e Quicksort Aleatorizado: Um

estudo comparativo. Congresso de Matemática Aplicada e Computacional CMAC Nordeste. Anual, 2012.

http://www.urionlinejudge.com.br/judge/pt/problems/view/1023.%201023

Software

Estiagem