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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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 | |
| } |