Como indicado no artigo anterior, neste artigo apresentamos 4 problemas simples, com nível de dificuldade crescente, para irem aplicando os vários conceitos de programação que aprenderem. Cada problema tem uma pequena nota indicando o que necessitam de saber. Todos os problemas requerem os conceitos mais básicos de C++, incluindo a estrutura de um programa, váriaveis e tipos e ainda leitura e escrita de dados. Adicionalmente, o que for necessário para um problema é necessário para os problemas seguintes.

Ao contrário do artigo anterior, não incluímos a solução dos problemas aqui, tentem resolvê-los vocês mesmo.

Problema 1

Para este problema apenas precisam de saber controlo de fluxo de programas, ou seja, condições if, assim como operadores Booleanos, como && (operador "e") e || (operador "ou").

O Pedro trabalha no controlo de qualidade da empresa "Caixas Azevedo e Irmãos" que, como o nome indica, fabricam todo o tipo de caixa, sendo que cada caixa tem o formato de um paralelepípedo. Hoje está-se a produzir caixas para diversos eletrodomésticos. Para que uma caixa destas passe o controlo de qualidade é importante que as suas dimensões estejam corretas. Cada caixa tem uma altura de A centímetros, uma largura de L centímetros e um comprimento de C centímetros. Para passar o controlo de qualidade, é importante que a caixa tenha volume pelo menos 50 centímetros cúbicos e que a altura seja pelo menos 3 centímetros. Dadas as dimensões de uma caixa, consegues ajudar o Pedro a determinar se a caixa passa o controlo de qualidade (indicado pelo número 1 no output) ou não (indicado pelo número 0 no output)?

Como anteriormente, o enunciado do problema no Mooshak inclui informações extra sobre o formato do input e output, restrições e ainda dois exemplos.

Problema B: Pedro o trabalhor

Este problema está disponível no Mooshak de treino como o problema B

Problema 2

Para este problema apenas precisam de saber ciclos (for ou while).

O Afonso está na fila para comprar bilhetes para o concerto da sua banda favorita. O Afonso está no fim da fila, por isso o tempo de espera parece interminável. Para passar o tempo, o Afonso decidiu contar as pessoas que se encontram há sua frente, há exatamente N pessoas. Adicionalmente, o Afonso anotou a altura de cada pessoa, por ordem desde o primeiro da fila até ao último. É sabido que uma pessoa consegue ver a bilheteira se não houver ninguém à sua frente com a mesma altura ou superior. Dada a lista das alturas N pessoas na fila à frente do Afonso, por ordem desde o primeiro da fila até ao último (que se encontra imediatamente à frente do Afonso), consegues contar quantas pessoas conseguem ver a bilheteira?

Para ajudar a compreender o problema, vamos olhar para um exemplo. Vamos supor que há N = 5 pessoas na fila, com alturas 170, 153, 170, 180 e 175, pela ordem indicada no enunciado. Há exatamente duas pessoas que conseguem ver a bilheteira, a primeira (de altura 170) e a quarta (de altura 180). A segunda pessoa (de altura 153) tem a primeira pessoa a bloquear-lhe a vista e o mesmo acontece para a terceira (de altura 170). Já a última (de altura 175) tem a quarta pessoa a bloquear-lhe a vista. Assim, a resposta para este caso seria 2.

Problema C: Afonso na fila

Este problema está disponível no Mooshak de treino como o problema C

Problema 3

Para este problema precisam de saber arrays e strings (ou arrays de caracteres).

A grande floresta de Baguim do Monte é conhecida pela beleza natural das várias árvores que contém. O mapa da floresta é uma grelha de N unidades por N unidades em que em cada célula ou existe uma árvore ou um espaço vazio. Representamos cada árvore por um carácter # e cada espaço vazio por um .. Um exemplo de uma tal grelha, para N = 4 é o seguinte:

...#
.#..
...#
..#.

Este exemplo tem 4 árvores e 12 espaços vazios. O Alberto é um assíduo visitante da floresta e como tal pretende instalar um banco para ele e os seus amigos se sentarem. O grupo de amigos do Alberto é constituido por K pessoas (incluindo o Alberto) e por isso o Alberto quer construir um banco com K lugares. Este banco terá de ser constituido por um conjunto contíguo de K células horizontais desobstruídas (sem árvores) da grelha que representa a floresta, ou seja, terá de estar em K células com espaços vazios seguidas numa única linha. Por exemplo, se a floresta fosse a dada anteriormente e o grupo tivesse K = 3 pessoas, o Alberto poderia construir o seguinte banco (representado por caracteres *) na primeira linha da floresta:

***#
.#..
...#
..#.

Infelizmente, nem sempre é possível construir um banco assim, se o grupo tivesse K = 4 pessoas, seria impossível construir um banco como descrito para a grelha acima. Dados os valores de N e K assim como a descrição da grelha da floresta, consegues determinar se é possível construir um banco para o número de amigos indicado (indicado pelo número 1 no output) ou não (indicado pelo número 0 no output)?

Tenham atenção aos detalhes do enunciado. O banco tem de ser construido sempre na horizontal, ou seja, numa unica linha. Logo, não precisam de tentar colocar o banco de várias formas.

Problema D: A floresta de Baguim

Este problema está disponível no Mooshak de treino como o problema D

Problema 4

Para este problema, teoricamente, não necessitam de saber mais nenhum conceito. Porém, será útil saber usar funções para organizar melhor o vosso programa, assim como estruturas. Sendo assim, recomendamos resolvê-lo quando conhecerem estes tópicos.

O Miguel prepara-se para mais uma viagem de avião. Visto que é alguém que viaja muito, o Miguel sabe exatamente os aviões que se encontram a voar neste preciso momento, assim como as suas coordenadas. Os aviões movem-se numa grelha bidimensional infinita e ocupam exatamente uma célula da grelha. Cada avião é identificado com uma coordenada X e uma coordenada Y e move-se pelo plano. Por exemplo, se houver um avião na posição (2, 3) e um na posição (1, 2) a grelha será algo como:

....
A...
.A..
....

Onde os . representam espaço vazio e os A aviões, sendo que a primeira célula representa a posição (1, 1). Adicionalmente, existem nuvens que ocupam também uma célula da grelha cada uma. Assim como os aviões, cada nuvem é identificada por uma coordenada X e uma coordenada Y, mas mantém-se sempre na mesma posição. Por exemplo, se além dos aviões do exemplo anterior tivermos uma nuvem na posição (2, 2) a grelha será algo como:

....
AN..
.A..
....

Onde o N representa a nuvem.

O Miguel quer estudar o movimento dos aviões, para tal ele sabe que inicialmente todos os aviões têm um sentido de movimento e movem-se à mesma velocidade de uma célula por unidade de tempo, sendo que o Miguel apenas está interessado nas primeira K unidades de tempo. Inicialmente, os aviões movem-se no sentido este (ou seja, no sentido positivo do eixo dos X). O movimento dos aviões é independente entre si (um avião não afeta o movimento de ninguém), mas as nuvens podem afetar o movimento dos aviões. Se por se mover para uma célula, um avião colidir com uma nuvem (ocupar a mesma posição), em vez de se mover o avião faz uma viragem à direita nessa unidade de tempo, ou seja, se se movia no sentido este passará a mover-se no sentido sul (sentido negativo do eixo dos Y), se se movia no sentido sul passará a mover-se no sentido oeste (sentido negativo do eixo dos X), se se movia no sentido oeste passará a mover-se no sentido norte (sentido positivo do eixo dos Y) e finalmente se se movia no sentido norte passará a mover-se no sentido este.

A título de exemplo, vamos ver o que acontece com o exemplo anterior após uma unidade de tempo:

....
AN..
..A.
....

O primeiro avião iria colidir com a nuvem, por isso virou à direita e movimentar-se-à agora para o sentido sul. O segundo a avião moveu-se uma unidade para a direita. Após mais uma unidade de tempo a grelha ficará da seguinte forma:

....
.N..
A..A
....

Como foi dito, o movimento dos aviões é independente, por isso pode acontecer que estejam dois aviões na mesma posição. O Miguel quer contar quantos pares distintos de aviões se encontram na mesma posição em algum momento do seu movimento durante as primeiras K unidades de tempo. Nota que pares distintos implica que se dois aviões se cruzarem várias vezes, só devem contar como um único par para a resposta. Consegues ajudar o Miguel?

Este problema tem vários pormenores, por isso leiam bem todo o enunciado. Por exemplo, três aviões podem estar na mesma posição, ou dois aviões podem estar na mesma posição em dois momentos de tempo diferentes (o que só deve contar como um par). Outro caso que é fácil esquecer é se dois aviões se cruzarem numa posição fora da grelha. Por exemplo, imaginem os seguintes dois aviões em que o primeiro está virado para este (direita) e o segundo para oeste (esquerda):

....
.AA.
....

Passada uma unidade de tempo a grelha terá a mesma configuração, mas os aviões trocaram de posição, mas a meio do seu movimento estiveram na mesma posição e por isso contam como um par. Este problema pode ser um pouco frustrante porque requer acertar muitos pormenores, por isso se ficarem presos passem à frente, mas é um bom exercício de programação.

Problema E: Viagem do Miguel

Este problema está disponível no Mooshak de treino como o problema E