Assisti "Avatar" de James Cameron

É difícil falar do James Cameron sem vir a mente bons filmes, como Exteminador do Futuro 2 ou True Lies. Mas também é difícil falar de James Cameron sem vir a mente alguns filmes discutíveis, como Titanic ou Piranhas 2 - Assassinas Voadoras. A contraposição é proposital, idem para o exagero embutido. Titanic não é ruim como Piranhas 2, mas certamente o segundo é mais honesto nas suas intenções. Podemos afirmar que James Cameron é um cineasta de grandes bilheterias, mas não justifica a sua auto-idolatração (comprovada pelo "I'm king of the world!" no Oscar), coisa que os estúdios sabem muito bem e seu último trabalho é prova disso.

Falar do Avatar é fácil se o colocarmos em dois planos distintos: o plano técnico e o plano de conteúdo, aquilo que costumamos chamar de roteiro. Tecnicamente, não há nada que chegue perto de Avatar hoje. Provavelmente só teremos coisas parecidas no ano que vem, ou depois ainda. Prova disso é a sessão de trailers no Imax 3D, que inclusive conta com o Alice do Tim burton, também filmado em 3D, mas com uma técnica definitivamente menos apurada. Se Avatar é a ponta do iceberg da tecnologia de filmagem em 3D, James Cameron acertou na mosca. O filme vai se tornar a referência definitiva da virada do cinema tradicional para o cinema 3D, impulsionando o mercado de TVs (a Samsung já começou) e videogames (o PS3 já tem patch de firmware pronto e o Super Stardust HD já roda nele).

O mundo de Pandora é realista, não apenas pelo 3D da imagem, mas pelo fato de que em nenhum momento os efeitos especiais ficam evidentes. Claro, é fisicamente impossível uma montanha voadora, sabemos que isso não existe. Mas a imagem na tela é bastante crível e não deixa pistas da junção das imagens de cachoeiras e montanhas reais para formar a cena de tirar o fôlego. A integração cenário artificial, personagens em motion capture e atores reais é orgânica, forte candidato a Oscar de efeitos visuais e com razão. Sem contar que no futuro a equipe de produção vai ganhar um daqueles Oscar especiais pelas contribuições para a indústria de cinema.

Quando chegamos no plano do roteiro, a coisa fica feia, literalmente. Avatar é um potpourri de diversas tendências, filmes e influências. No campo cinematográfico, a mais marcante é Dança com Lobos, mas não passa longe de um Pocahontas da Disney também. A colcha de retalhos passa pela militância verde utópica (e chata pra caramba), cria estereótipos bidimensionais, faz críticas à colonização do continente americano e descamba diversas vezes para o misticismo puro. Não preciso comentar que o filme é politicamente corretíssimo. Fórmula mais instável do que nitroglicerina, o roteiro é literalmente uma bomba.

Árvore de Mana - Secret of Mana (SNES)

As influências entram no campo dos games também. Foi difícil ver a árvore dos Na'Vi e não lembrar do Secret of Mana, ou então ver o vôo do Toruk Macto sem pensar no Panzer Dragoon, em especial o Orta. Também não dá para pensar na árvore das almas sem lembrar do life stream do Final Fantasy VII. Paro por aqui porque se cavocar, sai mais. Até minha irmã que não é tanto de jogar identificou elementos no meio.

Panzer Dragoon Orta

Talvez o romance entre Jake Sully e Neytiri até seja melhor que o apresentado em Titanic, mas em 2:30 de filme é pouco frente à avalanche de explicações convenientes para justificar ápices do filme, como o trecho do esqueleto do maior predador alado de Pandora e a solução do Jake a certa altura do filme. Também não ajuda nada o Deus ex-machina baseado na teoria de Gaia que resolve o problema relevante de tentar usar um arco-e-flecha contra uma nave blindada e com munição à vontade. Evito discutir a cena final, que é ultrajante em termos de previsível.

Aí vem a pergunta: como é que um filme desses custa 500 milhões de dólares e ninguém vê os defeitos? Simples: esse dinheiro é um troco que os investidores usaram para garantir lucros maiores com a posse (e patente) da tecnologia criada para fazer o Avatar. Se o filme não se pagasse, a Fox não iria dar bola, o lucro viria a longo prazo mesmo. Mas como as expectativas eram grandes, a Fox sabia que não ia levar prejuízo e teria, de graça, tecnologia de ponta. Burros eles seriam se não investissem os 500 milhões no filme.

Enfim, é um filme para ser visto em 3D, porque ele é uma demonstração do que será visto no cinema nos próximos anos. É um evento cinematográfico que só pode ser comparado ao advento da cor em E o Vento Levou ..., o que não é pouca coisa para um fã de cinema ficar de fora. Só não seja mão de vaca para esperar sair em DVD ou para assistir em cinema tradicional: Avatar não tem graça nenhuma sem a profundidade e exuberância do 3D. Em casa, só com TV e BluRay 3D, coisa que vai levar um tempinho para ser realidade de mercado. Só que até lá, vai ter coisa bem melhor pra assistir numa TV dessas. Ainda bem.

Então Você Quer Fazer Jogos?

Se tem uma coisa que é bastante comum, é o sujeito fazer um vestibular e descobrir que o curso era algo completamente diferente do que ele esperava. Uma tirinha do Nerdson, que menciona especificamente "aprender a fazer jogos" e "fazer um curso de computação", exemplifica claramente o caso com grandes chances de acabar em frustração.

A maioria das pessoas que querem fazer um jogo são, na maioria esmagadora, jogadores que se encantam com as imagens na tela. Nada de anormal, a pessoa que vira pintor também se apaixona pela arte vendo trabalhos de terceiros. Só que ao contrário do pintor, que trabalha sozinho e tem uma técnica comum a maioria de seus trabalhos, o jogo é feito por muitas pessoas, com competências bastante diferentes. Cada uma dessas pessoas não produz um pedaço "tangível" do jogo. Ou seja, se você pegar o trabalho de 10% da equipe, você não sai com 10% do jogo. A soma do trabalho para se fazer um jogo é maior do que as partes individuais. Só que ninguém fazendo vestibular hoje sabe disso, nem sabe para qual dos 10% do jogo ele quer contribuir e que ele não pode contribuir em todas as etapas. Pior ainda se o indivíduo usou uma ferramenta do tipo maker, visual, que é uma ferramenta que não tem nada a ver com programação.

Para deixar mais claro, imagine a seguinte situação. Você está jogando pela primeira vez na sua vida uma partida de Super Mario Brothers (uma vez isso deve ter acontecido, então lembre-se da sensação). Em um dado momento o Mario "gigante" pula contra um bloco do cenário e quebra-o como se ele não fosse nada. Ao fazer isso, você vê que o Mario agora pode passar livremente por onde havia o bloco antes. Inclusive, inimigos podem fazê-lo. Um bloco que você podia até andar em cima, agora tinha virado um vazio no espaço. Você:

(a) Fica encantado, pensando nos novos caminho que você pode criar no cenário quebrando os blocos.

(b) Fica encantado, pensando na adequação da animação do bloco sendo quebrado e no efeito sonoro utilizado.

(c) Fica encantado, imaginando como aquela maquininha consegue dizer que ali tinha um bloco, mas que ele quebrou-se e agora o personagem pode passar por ali.

Se você se identificou mais com as duas primeiras respostas, pense duas vezes antes de fazer um curso de computação. Você pode fazer jogos, mas criando o enredo, fazendo a arte, o level design, etc. Para você, pode ser mais eficiente um curso design digital, que vai trabalhar exatamente com o que você se identifica e, melhor de tudo, vai permitir você fazer um jogo com o que você espera que seja fazer um jogo.

Você pode até argumentar "mas eu gosto de mexer com computador". Oras, usar um carro não torna uma pessoa habilidosa em mecânica. Saber usar as ferramentas do computador não é o mesmo que saber criá-las, que é o que um programador faz. Depois você pode dizer "mas eu sou craque em configurar o computador", ou melhor pro pessoal do Linux "eu sei recompilar o kernel". É o equivalente a dizer que você entende de mecânica porque instalou você mesmo os acessórios do seu carro. Configurar um sistema operacional não é o mesmo que escrever um, que é o que programadores (consideravelmente) avançados fazem.

A cartada final para quem responde as letras a e b é de que Shigero Miyamoto era programador. O Chris Crawford era programador. O Peter Molyneux era programador. Exceções não fazem a regra. Existem bons designers que também são bons programadores. Mas em geral, um bom designer é um péssimo programador, e vice-versa. Sem contar que na época do Atari e dos primórdios dos jogos de 8 bits (computador e videogame), só chegava perto de computador um programador, logo, só os poucos que tinham noção de design faziam jogos. Mas a medida que a coisa se profissionalizou, designers tomaram conta do campo da criação, enquanto programadores fincaram o pé no campo da realização.

Aí resta a pergunta indignada de quem respondeu a/b: e porque o sujeito que responde c pode fazer um curso de computação? Porque ele tem pensamento cartesiano. Para ele o mundo é visto como causa e efeito. Para ele, tudo o que ocorre naquele jogo tem uma razão de ser e interessa mais a ele como aquilo foi feito do que aquilo implica no jogo como um todo. É o sujeito que vai tornar possível na "maquininha" a visão do designer.

Um bom programador de jogos é o sujeito que gosta de matemática e conhece as principais técnicas computacionais, para aplicar isso em um jogo. É o sujeito que sabe a relação de um autômato finito e o personagem de um jogo. É quem sabe que um grafo pode servir para criar os caminhos dos personagens do PacMan a representar a hierarquia dos objetos de uma cena 3D. É quem escreve um pequeno compilador para ler do disco as configurações do seu personagem. É quem tem uma aula de álgebra linear e tem um click de como a placa de vídeo projeta os pontos de uma textura em um polígono na tela. É quem conhece a tese de Church-Turing para dizer que certa idéia no jogo não funciona, mas se limitar a certo contexto dá praticamente o mesmo resultado e torna o problema solúvel pelo computador. Enfim, é o cara que pensa em números antes de pensar em imagem na tela.

Claro, muitos que fazem um curso de computação podem argumentar que nenhum professor comente isso em sala. Bobagem. A área de computação é tão vasta que é utopia querer que um curso seja capaz de preparar um aluno especificamente para um setor sem que ele perca uma coisa importante: a habilidade de se adaptar a novas situações. Para quem duvida disso, basta ver anúncios de empresas estrangeiras de jogos no Gamasutra. Todas as posições iniciantes requerem sólida base de ciência da computação (ou de engenharia de computação). Profissionais que saem da universidade com a fundamentação para atuar com a computação como uma ferramenta para atingir um resultado.

Então, para que você não fique indignado como na tirinha do Nerdson, pense bem no tipo de sujeito que você é, porque ele vai dizer o curso que você deve fazer. Se você for o sujeito da resposta c e achar que a faculdade não está ajudando você a entender como o bloco do Mario desaparece, não se preocupe. Use o lado auto-ditata que a faculdade lhe dá e leia bastante, aí você vai agradecer que você aprendeu autômatos, álgebra linear e outras matérias que você não tinha a menor idéia para que serviam.

XIII Maratona de Curitiba

Fugindo da computação, participei no Domingo, dia 22, da 13a Maratona de Curitiba. Daquelas de 42km de distância que reza a lenda que o Pheidippides morreu depois de percorrer para anunciar a vitória dos Gregos sobre os Persas. Uma prova fascinante de resistência física e solidariedade. Dos voluntários da organização (tinha até ex-aluno) ao sujeito dando banho de mangueira de jardim nos corredores que passavam, o marcante da prova foi o espírito esportivo para empurrar os participantes um passo mais próximo da linha de chegada. Muito legal de ver os escoteiros nos postos de hidratação dando uma força para os participantes.

km27 da prova.

O percurso foi um passeio por boa parte da cidade, do Palácio Iguaçu, sede do governo estadual, até o terminal do Pinheirinho. Nem de longe foram as piores subidas e descidas que eu peguei numa prova, mas pela distância percorrida, qualquer morrinho virava desafio depois de 20km. O tempo parecia que não ia colaborar, fez sol a maior parte da prova. Mas, para sorte dos participantes, choveu no final da manhã, o que aliviou bastante para quem ainda estava correndo (eu estava pelo km 33).

O tempo total da prova foi bom, 4h57, quando eu estava esperando 5h30 pelas estimativas iniciais nos treinos longos. Não sei se vou virar fã da distância, até porque correr 42km não é a mesma coisa que correr 10km das provas mais comuns (só a prefeitura organiza 6 por ano). Mas é certo que ano que estou lá de novo :).

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

Esse problema eu fiquei "sentado em cima da solução" por um bom tempo (desde o dia da maratona), então vamos, sem mais rodeios, à solução do Problema H - Escultura a Laser. Esse problema tem uma solução quadrática simples, tanto que dos times que resolveram ele em Curitiba, boa parte sofreu com tempo limite excedido. Porém, a solução linear dele não é tão óbvia, tanto que algumas equipes não conseguiram resolvê-lo. A pergunta é simples, dado um histograma de alturas de uma peça recortada com um laser, quantas vezes é preciso ligar o laser para que o corte seja feito?

Vamos estabalecer as regras do jogo. Primeiro, o laser percorre na horizontal a peça, retirando uma camada de material por passada. Toda vez que o laser acaba uma passada ele é desligado, volta à posição inicial e, se for o caso, é ligado novamente. Não tem nenhuma pegadinha de otimização com o laser indo e vindo. Assim, caso exista uma protuberância no caminho, o único jeito de fazê-la é desligando o laser para que o material não seja cortado.

A solução ingênua é simular o funcionamento do laser, removendo as camadas em um for aninhado de altura A e largura C. Ingênua porque ela é quadrática e estoura o tempo de processamento. Os limites são de 10000 para cada dimensão, assim, são 100 milhões de comparações que devem ser realizadas. Como o juiz online é draconiano e tem uma entrada dessas, não precisa ser gênio para entender porque essa solução não serve.



A solução linear, por sua vez, requer um pouco de insight, já que devemos pensar "verticalmente". O fato do laser ir do começo ao final é traiçoeiro neste problema, já que ele nos induz ao uso de uma repetição para percorrer o bloco de material do início ao fim, de cima para baixo. Porém tal fato é irrelevante: Não precisamos saber quantas viagens o laser faz do início ao fim, mas sim quantas vezes ele é ligado no processo. Assim, basta considerar, para cada degrau descendente no objeto, que o laser foi ativado uma vez para cada unidade de altura, como na figura abaixo! Quando subimos, o laser é desligado, então não conta. Idem para quando mantém-se a altura, o laser vem ligado e pronto.



A solução deste problema usando apenas uma repetição simples usa uma variável auxiliar que marca a altura atual do objeto, inicialmente a altura máxima da peça (dado no problema), além de um contador de vezes em que o laser foi ligado (que começa com zero). Com uma repetição do começo ao final do histograma fornecido, observamos a variação da altura do bloco com a altura atual. Se ela permanece a mesma não fazemos nada. Se ela mudar, além de alterarmos a altura atual verificamos a diferença de altura: se subiu, ignoramos, mas se desceu, adicionamos ao contador o módulo da diferença. Ao encerrar a repetição, o contador tem o número de vezes em que o laser foi ligado.

O fonte do programa C que faz a solução linear encontra-se aqui. Agora é começar a implementar o resto que já tem esquematizado, mas nunca tive inspiração de codificar :).

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

Como hoje estou com paciência e tempo para escrever, vamos à solução do terceiro problema da XIV Maratona de Programação da SBC. O problema escolhido é o Problema C - Troca de Cartas. Este problema não exige nenhuma conta complexa. Ele é até bastante simples nesse quesito. Só que ele trabalha com conjuntos, coisa que os alunos não andam lá tão acostumados a trabalhar. Tanto que quase metade dos competidores de Curitiba não fez. Representar o conjunto de maneira adequada é o primeiro passo para se resolver o problema.

Como representamos o conjunto também influencia a solução, então vou descrever inicialmente a primeira solução que encontrei, bastante simples, e que funcionou nos quesitos de tempo do juiz online. Como isso é o que interessa na maratona, esta solução seria tão boa quanto qualquer outra 20 vezes mais elegante. No final eu discuto como poderia ser uma solução alternativa ao problema. Uma solução mais rápida, usando menos memória, porém bem mais complexa.

Pontos em Comum

Não importa qual método você escolha para resolver este problema, um fato que deve se tomar cuidado é que o interesse é na quantidade máxima de figuras que a Beatriz e a Alice podem trocar. Em nenhum momento menciona-se a quantidade máxima de cartas duplas que podem ser trocadas, que é o que pessoas normais fariam com suas coleções. Quando li a prova no dia da maratona esse foi o ponto que mais me intrigou quando fui ver as entradas exemplo e que possivelmente causou alguma dúvida. Tem que avisar quem fez este problema qual o comportamento padrão de colecionadores, o que seria um problema bem mais interessante do que o apresentado na maratona.

O problema no final consiste em verificar quantas cartas podem ser trocadas. Isto é, determinar quantas cartas a Alice tem que a Beatriz não tem, e vice-versa. O menor dos valores é o número de cartas que podem ser trocadas. Matematicamente, sendo A o conjunto de cartaz da Alice, B o conjunto de cartas da Beatriz, calculamos o conjunto de cartas que a Alice tem e que a Beatriz não tem como:

Dif_Alice = A - (A ∩ B)

Com a mesma lógica, determinamos o conjunto de cartas que a Beatriz tem e que a Alice não tem como:

Dif_Bia = B - (A ∩ B)

Se |Dif_Bia| < |Dif_Alice|, então o resultado é |Dif_Bia|. Caso contrário, o resultado é |Dif_Alice|. Lembrando que |i| é o número de elementos no conjunto i e que não há repetições em i (provavelmente disso saiu a idéia de não considerar figuras repetidas, o que denuncia que foi um matemático que fez o problema).

Primeira Solução

A primeira solução, nem de longe a mais eficiente em velocidade e uso de memória considera um "álbum virtual" a completar. Cada menina possui um vetor booleano com tamanho 100.000, sendo que verdade indica que ela possui a carta (quantas cópias é irrelevante) e falso que ela não possui. Como usamos inteiros na solução e a pilha é bem menor que a memória RAM, os vetores estáticos beatriz e alice são declarados como globais, já que cada um deles usa 400.000 bytes (lembrete: tem jeito melhor sim, discuto isso no segundo método).

Lembre-se que variáveis locais (dentro da main) são criadas na pilha, que tem um tamanho definido pelo linker. No caso do Visual Studio, por exemplo, esses dois vetores dariam stack overflow na pilha padrão. Por segurança, usamos alocação dinâmica, ou variáveis globais. Como sabemos o tamanho máximo dos conjuntos, dane-se, vamos de global mesmo.

Inicialmente, zeramos ambos os vetores com memset, para que nenhuma menina tenha cartas. Em seguida, lemos o número de cartas de cada menina, seguido da leitura das cartas em si. A cada número de carta lida (variável carta), associamos a posição equivalente do vetor (carta-1) o valor verdade (-1). Lembrete 1: as cartas vão de 1 a 100.000. O vetor vai de 0 a 99.999, então tem que subtrair 1. Lembrete 2: falso é zero e diferente de zero é verdade, converta -1 para bonário para entender porque usei ele como verdade.

Para contar quantas cartas cada menina tem que a outra não tem, usamos duas variáveis, m_bia e m_alice, ambas iniciadas com zero a cada caso testado. Como o álbum tem 100.000 figuras para ambas as meninas, basta fazer uma repetição e, para cada posição dos vetores, testamos se ela é verdade para apenas um deles. Se for verdade apenas em beatriz, incrementamos m_bia. Se for verdade apenas em alice, incrementamos m_alice. Se for verdade ou falso em ambos, não fazemos nada. No final do processo, imprimimos o menor valor, que é o número de cartas que podem ser trocadas.

O programa C que faz esta solução do problema está aqui.

Segunda solução

Essa eu não testei, então dou as linhas gerais. Ela só funciona bem (e rápido) porque as "caras estão em ordem não decrescente", jeito complicado de dizer que as cartas estão em ordem crescente, exceto as cartas iguais, que aparecem em sequência.

Um dos dados do problema é que as meninas possuem um limite de 10.000 cartas. Assim, dá pra resolver o problema com um vetor de 10.000 inteiros, lendo nele todas as cartas de acordo como o apresentado na entrada. Em seguida, lemos as posições dos vetores usando dois indexadores, de forma a avançar no vetor quando encontramos cartas iguais, parando o avanço em um deles quando temos uma carta diferente maior que a do segundo. A cada carta diferente encontrada, incrementamos um contador similar ao m_bia e m_alice da solução anterior.

Essa solução é mais chata porque usa dois indexadores, é uma repetição enquanto ambos valores forem menores que 10.000 e a atualização dos indexadores é uma chatice só. Ela é mais eficiente do ponto de vista uso de memória por usar vetores com 1/10 do tamanho, o que é óbvio. Já a repetição é bem mais enxuta porque ela é proporcional ao tamanho da entrada, enquanto no outro caso é sempre 100.000. Mas vale lembrar que a complexidade é bem mais alta e, francamente, por mais que eu ache essa solução computacionalmente mais interessante, não é o caso da maratona. O que vale é resolver em menos tempo e a primeira é bem mais fácil de imaginar e implementar.

Como dito inicialmente, esta solução não foi testada, mas quem a seguir conseguirá resolver o problema também.

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.

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

Vamos começar pelo problema mais fácil, o Problema B - Alarme Despertador. Primeiro, porque esse problema é o mais fácil de todos? Vamos aos detalhes: dada a hora atual e a hora que o despertador da Daniela vai tocar, temos que dizer quantos minutos ela dorme. Resolve isso com continha básica de multiplicação e soma, além de uma condicional para quando vira a data.

O problema apresenta uma entrada simples: a hora atual e a do despertador, dividida em quatro inteiros. Os dois primeiros para a hora atual (horas e minutos, respectivamente), repetindo a estrutura para a hora do despertador. Como nos interessa o número de minutos dormidos, a solução passa por um passo obrigatório: converter o valor de horas e minutos para o número de minutos corridos do dia (de um total de 1440, isto é, 24*60). Tal conta é feita da seguinte forma:

m_dia=hora*60+minutos

Se calcularmos a diferença desse valor em minutos da hora do despertador com a hora atual, temos os minutos que a Daniela vai conseguir dormir. Porém, temos um caso omisso: e se o despertador for tocar no dia seguinte? Por exemplo, se a Daniela dormir às 22:00 e acordar às 6:00, temos que a hora inicial em minutos é 1320, sendo a hora do despertador é 360. Se fizermos a diferença do final para o início, temos um valor negativo (360-1320=-960).

Aí entra o jogo de cintura do aluno, porquê ao fazer essa diferença, o valor negativo indica o número de minutos entre o horário do despertador e o horário do início do sono, ou seja, o complemento do valor que nós queremos em um dia (faz um círculo que é mais fácil de entender). Oras, se temos o complemento, basta somar a este valor o número de minutos total de um dia (1440) que temos o valor correto:

1440+(360-1320)=1440-960=480

Assim, a lógica tem que considerar o seguinte: se o resultado da conta em minutos for positivo, esse é o valor correto e é só imprimir. Se for negativo, basta somar 1440. E voilà, temos aqui o programa em C que resolve em tempo linear O(n) o prolema do alarme despertador. Q.E.D..