XIV Maratona de Programação da SBC - Problema D

Continuando a postagem das soluções da maratona de programação de 2009. Vamos ao Problema D - Subprime, outro problema de contas bem simples, mas com um enunciado um pouco mais complexo. No problema anterior (o B, do alarme, escolhido como primeiro), tínhamos apenas 4 valores para manipular e a lógica era um pouco chata. Neste problema, a lógica é menos chata (já chegamos nela), mas a quantidade de valores é maior e não são diretamente os valores que nos interessam. Isso pode assustar os mais desavisados, ou os pressionados pelo tempo na competição.

No universo do problema proposto, um sistema financeiro saudável é aquele que se resolve por si só. Isto é, se para cada um dos bancos a soma das suas reservas e os seus créditos forem maiores ou iguais às suas dívidas, não será necessária uma intervenção. Neste caso, imprimimos S na saída. Caso contrário, se para ao menos um dos bancos a dívida for maior que a soma das reservas e dos créditos, será necessária a intervenção do governo e devemos imprimir N.

Uma característica que confunde o competidor neste problema é como os dados são apresentados e como eles devem ser analisados. A pergunta que devemos responder é:

reservas+créditos >= dívidas

Porém, o problema não dá isso para cada banco, à exceção das reservas. Sabemos que os bancos tem créditos e que eles tem dívidas, mas as informações tem que ser extraídas das debêntures do sistema financeiro da nLogônia. Esse é o ponto principal do problema, passada essa etapa, o resto é ladeira. Assim, precisamos armazenar três valores para cada banco, reservas, creditos e dividas. Como são até 20 bancos no sistema financeiro, podemos usar vetores alocados estaticamente, em que posições de mesmo índice representam uma informação de um banco específico. Não são vetores que podem estourar a pilha se declarados localmente, mas por costume declarei os vetores como globais.

Para resolver o problema, usamos duas variáveis, nbancos e ndeben, que indicam o número de bancos (o número de posições usadas do vetor) e quantas debêntures devemos ler. Primeiramente, lemos no vetor reservas o quanto cada banco tem no caixa. Isso é simples e direto. Em seguida, devemos determinar indiretamente as o conteúdo dos vetores creditos e dividas. Em geral, aqui eu vejo o maior problema de interpretação para os novatos na competição, porque o próximo dado da entrada são as debêntures emitidas. O que devemos fazer aqui é o seguinte, a cada debênture lida, associamos o valor da debênture ao crédito do banco credor e o mesmo valor à dívida do banco devedor. Tal processo é feito cumulativamente, a cada debênture encontrada, somamos o valor dela ao crédito de um banco e à dívida de outro.

Assim, zeramos todas as posições dos vetores creditos e dividas usando memset (se você programa C e não sabe como isso é feito, tome vergonha e volte pra faculdade). A cada debênture lida, guardamos o montante na variável valor, o banco que cedeu o dinheiro em credor (um número inteiro de 1 a nbancos) e o banco que emprestou em deve (também um valor de 1 a nbancos). Agora, adicionamos valor à posição credor-1 do vetor creditos e à posição deve-1 do vetor dividas. Como os vetores em C começam em 0 e os bancos em 1, devemos subtrair um de credor e de deve para manter o acesso coerente aos vetores. Pergunta inocente do leitor incauto: perdemos os debêntures originais, oh céus, o que fazer? Não precisa, os debêntures não precisam ser guardados em memória ou analisados mais tarde. Precisamos deles apenas para extrair os créditos e dívidas. Feito isto, os debêntures em si são irrelevantes ao problema.

A etapa final faz o seguinte, para cada banco i, de 0 a i<nbancos, testamos se isso é verade:

reservas[i]+créditos[i] >= dívidas[i]

Se para ao menos um dos bancos isso for falso, o sistema bancário é inviável. Se para todos os bancos isso for verdade, o sistema é viável. O problema é que o computador não tem comando mágico para comparar simultaneamente conjuntos condições de tamanho variável. Assim, devemos testar, individualmente, cada um dos nbancos para dizer isso. Para isso, usamos uma variável booleana pode, que diz isso pra gente. Lembre-se: em C, 0 (zero) é falso, qualquer valor diferente de 0 (zero) é verdade. Inicialmente partimos do pressuposto de que o sistema é viável e associamos -1 ao valor de pode (por que -1? Converta pra binário e descubra, oras!). em seguida, para cada banco testamos se ele é inviável:

reservas[i]+créditos[i] < dividas[i]

Caso um dos bancos for inviável, associamos 0 à variável pode e encerramos a repetição. Se todos os bancos forem viáveis, a variável pode continua com -1. Ao encerrar a repetição (normalmente ou pelo break), testamos o valor de pode. Se for verdade, imprimimos S. Caso contrário, imprimimos N.

O programa C que faz o proposto e atende aos requisitos de tempo da maratona de programação está disponível aqui.