Podemos resolver esse problema utilizando um loop de repetição, como o while. Nesse caso, a solução esperada é realmente ir multiplicando o peso dos ursos até que o peso de Samuelito ultrapasse o de Loppamir, enquanto mantemos um contador para os anos. Então, basta multiplicar o peso dos ursos enquanto o peso de Samuelito for menor ou igual o peso de Loppamir e, a cada multiplicação, somar 1 no tempo. Dessa forma, assim que Samuelito for mais pesado, sairemos do loop.
Código com a solução do problema (Clique para expandir)
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
int t = 0;
while (a <= b) {
a = 3 * a;
b = 2 * b;
t++;
}
cout << t << '\n';
return 0;
Nesse problema queremos encontrar a maior diferença entre dois dos valores inseridos. Pra isso, basta encontrarmos o mínimo e o máximo no vetor e subtrair um do outro. Tudo ficará mais claro no código:
Código com a solução do problema (Clique para expandir)
#include <bits/stdc++.h>
using namespace std;
int v[100000];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Vamos inializar o maximo e o mínimo sendo iguais ao primeiro elemento do vetor.
int minimo = v[0];
int maximo = v[0];
// Agora, passaremos por todos os outros elementos...
for (int i = 1; i < n; i++) {
// Se o elemento na posição i for maior que máximo atual:
if (v[i] > maximo) {
maximo = v[i]; // Atualizamos o máximo.
}
// Se o elemento na posição i for menor que o mínimo atual:
if (v[i] < minimo) {
minimo = v[i]; // Atualizamos o mínimo.
}
}
// Imprimindo a diferença entre o maior e o menor elemento.
cout << maximo - minimo << '\n';
return 0;
}
Esse problema introduz algo muito útil na programação competitiva, o vetor de frequências. Uma forma de resolver o problema é armazenar na posição [número de palitos] o tanto de vezes que aquela quantidade de palitos apareceu, por exemplo:
Digamos que você tenha 5 sequências de palitos.
|||| -> 4
||||| -> 5
|||| -> 4
||| -> 3
||||| -> 5
Para encontrar a moda (valor mais frequente), podemos inicializar um vetor apenas com 0 -> [0, 0, 0, 0, 0, 0] e ir adicionando adicionando um na posição correta toda vez que lermos uma sequência, no nosso caso:
|||| -> adicionaremos 1 unidade na posição 4 (que é o número de palitos) do vetor.
||||| -> adicionaremos 1 unidade na posição 5 do vetor.
E assim por diante... no fim, teremos o seguinte vetor -> [0, 0, 0, 1, 2, 2] e então, basta verificarmos em que posição dele se encontra o maior elemento para sabermos a moda.
Código com a solução do problema (Clique para expandir)
#include <bits/stdc++.h>
using namespace std;
int freq[1010];
int main() {
string s;
int n;
cin >> n;
// Vamos olhar cada dia de uma vez. (n dias)
for (int i = 0; i < n; i++) {
cin >> s; // Ler a string dos palitos
int amount = s.size(); // Pegar o tanto de palitos na string = tamanho da string.
freq[amount]++; // Aumentamos a posição amount em uma unidade.
}
int mode = 0;
int mode_index = 0; // Será nossa resposta
// Vamos olhar para cada frequência do vetor e guardar o indice da maior.
for (int i = 1; i <= 1010; i++) {
// Se a frequência atual for maior que 'mode'
if (freq[i] > mode) {
mode_index = i; // Guardamos o indice em que isso ocorre.
mode = freq[i]; // Atualizamos o valor de mode
}
}
// Imprimindo o índice da maior frequência.
cout << mode_index << endl;
return 0;
}Bom, vamos analisar a afirmação: Toda carta que tem em um dos lados um número positivo par tem também, no seu verso, um número negativo ímpar.
É preciso, primeiramente, perceber que a afirmação não diz nada sobre cartas com número negativo ímpar. Toda carta com número positivo par precisa ter do outro lado um número negativo ímpar, mas uma carta com número negativo ímpar pode ter o que quiser do seu outro lado.
Então quais cartas precisamos virar?
Bom, precisamos olhar o outro lado de toda carta que tem um positivo par de um lado, para garantir que o outro lado é negativo ímpar.
Além disso, algo muito menos aparente, é que precisamos olhar o outro lado de toda carta par negativa, pois caso ela tenha um número positivo par no seu verso, saberemos que NEM TODA carta com positivo par tem do seu outro lado um número negativo ímpar.
Basicamente, precisamos apenas contar a quantidade de cartas com número par, seja ele negativo ou positivo.
Código com a solução do problema (Clique para expandir)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int ans = 0; // É muito importante inicializar seu contador.
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (x % 2 == 0) {
ans++;
}
}
cout << ans << '\n';
return 0;
}Para verificar se uma string é um palíndromo basta percorrer a string ao mesmo tempo partindo do começo e do final e garantir que as letras sendo olhadas atualmente sejam iguais, como foi mostrado em aula. A condição para a string ser um palíndromo é que ela seja igual se lida normalmente ou ao contrário.
Exemplos de palíndromos: abacaba, aba, ama, abcba.
Nesse problema, precisamos responder o número de letras que devem ser modificas para que a string se torne um palíndromo, para isto, vamos utilizar o mesmo algorítmo de verificação de palíndromo, mas somar 1 na resposta final toda vez que as letras forem diferentes. Isso vai ficar mais claro no código:
Código com a solução do problema (Clique para expandir)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n;
cin >> s;
int ans = 0;
// O índice i começa a percorrer a string normalmente e o índice j de trás pra frente
// Vamos comparar as letras nessas posições e, caso sejam diferentes, somar 1 na resposta.
// A condição de parada do if é quando os índices se cruzam.
for (int i = 0, j = n - 1; i < j; i++, j--) {
if (s[i] != s[j]) {
ans++;
}
}
cout << ans << endl;
return 0;
}
Disclaimer: eu estou escrevendo isso à 01h da manhã então me perdoem se não ficar muito claro. Podem tirar qualquer dúvida nas aulas!
Para resolver esse problema era necessário, antes de tudo, perceber que a sequência era equivalente a f(n) = 2^n.
A solução que realmente percorre todas as potências não passa no tempo, então era preciso encontrar um padrão no fim dos números.
O último digito dos números seguia a sequência: 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6...
Depois de perceber isso, podíamos apenas atribuir o número de ciclo completos à resposta final. Mas ainda precisamos lidar com o que sobrou, o ciclo imcompleto que não foi levado em consideração na conta. Podemos verificar até que ponto da sequência esse ciclo imcompleto chegou e somar esse valor nas respostas.
O código abaixo é de um cara fera demais que deu aula pra gente no ano passado e que já ta se formando, o Forbes. No código ele explica as coisas que falei acima de forma mais clara e gráfica, então eu espero que fique mais fácil.
Código com a solução do problema (Clique para expandir)
#include <bits/stdc++.h>
using namespace std;
// Esse vetor vai guardar a resposta para qualquer dígito k entre 0 e 9.
int ans[10];
/* O(1). */
int main(){
int n, k;
scanf("%d%d", &n, &k);
// A primeira coisa para se observar nesse problema é que a sequência pode ser simplificada tal que:
// Fn = 2^(n - 1)
//
// Observando o dígito das unidades dos primeiros termos da sequência, podemos ver que há um ciclo:
// F1 % 10 = 1
// F2 % 10 = 2 ---
// F3 % 10 = 4 |
// F4 % 10 = 8 |
// F5 % 10 = 6 ---
// F6 % 10 = 2 ---
// F7 % 10 = 4 |
// F8 % 10 = 8 |
// F9 % 10 = 6 ---
// ...
ans[1] = 1; // Sempre aparecerá apenas 1 vez para n >= 1 (em F1).
ans[2] = ans[4] = ans[6] = ans[8] = (n - 1) / 4; // O número de ciclos COMPLETOS entre 1 e n é igual a (n - 1) / 4.
// Essas linhas equivalem aos ifs abaixo.
ans[2] += ((n - 1) % 4 >= 1); // Se o ciclo incompleto já passou por mais um 2.
ans[4] += ((n - 1) % 4 >= 2); // Se o ciclo incompleto já passou por mais um 2 e 4.
ans[8] += ((n - 1) % 4 >= 3); // Se o ciclo incompleto já passou por mais um 2, 4 e 8.
// if ((n - 1) % 4 >= 1){
// ans[2]++;
// }
// if ((n - 1) % 4 >= 2){
// ans[4]++;
// }
// if ((n - 1) % 4 >= 3){
// ans[8]++;
// }
printf("%d\n", ans[k]);
return 0;
}Espero que tenham gostado do contest dessa semana, gente! Não desanime se não conseguiu fazer os problemas, ninguém começa bom e é preciso treino e persistência. Continue vindo nas aulas, tire todas suas dúvidas e se divirta, que vai dar tudo certo.
Se algo aqui não ficou muito claro, me avisa no telegram (@davidcairuz) que eu tento deixar melhor!
Até logo!