Solução Informática - Nível Intermediário - Semana 9

Solução por Anita Ramos

Para este problema utilizaremos uma nova função que irá calcular em quantas empresas E João vai investir. Tudo isso fora da int main(). Esse recurso facilita na produção de um programa mais compacto, organizado e eficiente.

Iniciando a programação então, após adicionar a biblioteca, temos a função int acao(), responsável por toda a lógica, que irá receber dois inteiros n e k e tem 3 possibilidades de retorno:

  • 1, se n \leq k
  • retorna a acao() de cada metade de n (nesse caso as metades são iguais), se n \geq k e n é par
  • retorna a acao() de cada metade de n (nesse caso as metades são diferentes (n/2) e (n/2 + 1), se n é ímpar

Assim, a ideia consiste em realizar a função acao várias vezes até todas as parcelas serem menores ou iguais a k. Temos o seguinte exemplo para n=18 e k=4:

18 = 9 + 9 (E=2) <=>

18 = (4 + 5) + (4 + 5) (E=4) <=>

18 = (4 + [3 + 2]) + (4 + [3 + 2]) (E=6)

Logo, E=6.

Em seguida, o programa executa apenas a int main() que irá ler as linhas de entrada e imprimir, a cada caso de teste, o resultado obtido na função acao()  de n e k, enquanto eles forem diferente de 0.

Segue o código comentado para melhor compreensão da solução:


#include<bits/stdc++.h> //biblioteca utilizada
using namespace std;
int acao(int n, int k) //função 'acao' que recebe dois inteiros
{
if(n<=k)return 1; //se 'n' menor ou igual a 'k' retorna 1
if(n%2==0)return acao(n/2,k) + acao(n/2,k); //se 'n' é par retorna 'acao' de metade de 'n' + 'acao' de metade de 'n'
else return acao(n/2,k)+acao(n/2+1,k); //se 'n' é ímpar retorna 'acao' de metade de 'n' + 'acao' de metade de 'n' + 1
}
int main()
{
int n,k; //declara variáveis
scanf("%d %d", &n, &k); //lê o primeiro caso de teste
while(n!=0 && k!=0) //enquanto a entrada for diferente de 0
{
printf("%d\n", acao(n,k)); //imprimi o resultado da função 'acao' de 'N' e 'K'
scanf("%d %d", &n, &k); //lê um novo caso de teste
}
return 0; //retorna a 0
}

view raw

Ações 1.cpp

hosted with ❤ by GitHub