Problème A : Shizuku Hoshikawa et les Pattes de la Ferme
C'est un problème classique de coqs et de lapins (ou poules et lapins). L'objectif est de compter le nombre de combinaisons possibles d'animaux (coqs et lapins) ayant un nombre total de pattes égal à n. Il faut noter que le nombre d'animaux peut être nul.
La solution consiste à itérer sur tous les nombres possibles de lapins (ayant 4 pattes), calculer le nombre correspondant de coqs (ayant 2 pattes), et vérifier si le total des pattes est correct.
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int solutions = 0;
for (int rabbits = 0; rabbits * 4 <= n; rabbits++) {
int remainingLegs = n - rabbits * 4;
if (remainingLegs % 2 == 0 && remainingLegs >= 0) {
solutions++;
}
}
cout << solutions << endl;
}
return 0;
}
La boucle for parcourt les valeurs de rabbits (nombre de lapins). Pour chaque itération, on calcule les pattes restantes pour les coqs. Si ce nombre restant est positif et divisible par 2, on a une combinaison valide.
Problème B : Yuu Koito et la Somme Absolue Minimale
Étant donné une séquence contenant des valeurs connues et des -1 à remplacer, on doit déterminer les valeurs à placer aux positions -1 de manière à minimiser la valeur absolue de la somme cumulée des différences successives. De plus, la séquence finale doit être la plus petite possible en ordre lexicographique.
L'observation clé est que les éléments -1 au milieu de la séquence n'affectent pas la somme cumulée globale, car les termes se simplifeint. Ainsi, on peut les initialiser à 0 pour satisfaire l'ordre lexicographique. Le traitement spécifique se porte sur les premier et dernier éléments s'ils sont -1.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
int n;
cin >> n;
vector<long long> a(n + 1), prefixSum(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == -1 && i != 1 && i != n) {
a[i] = 0;
}
}
for (int i = 2; i <= n; i++) {
if (a[i] != -1 && a[i - 1] != -1) {
prefixSum[i] = prefixSum[i - 1] + (a[i] - a[i - 1]);
} else {
prefixSum[i] = prefixSum[i - 1];
}
}
if (a[1] == -1) {
a[1] = max(0LL, a[2] + prefixSum[n]);
prefixSum[n] = prefixSum[n] + (a[2] - a[1]);
}
if (a[n] == -1) {
a[n] = max(0LL, a[n - 1] - prefixSum[n]);
prefixSum[n] = prefixSum[n] + (a[n] - a[n - 1]);
}
cout << abs(prefixSum[n]) << endl;
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
La logique des conditions pour le premier et le dernier élément vise à choisir la valeur qui minimise l'impcat sur la somme prefixSum[n], tout en respectant l'ordre lexicographique via la fonction max.
Problème C1 : Renako Amaori et le Jeu XOR (version facile)
Dans ce jeu, deux joueurs contrôlent des séquences de bits (0 ou 1). Ils peuvent échanger des bits à certaines positions selon des règles. Le joueur gagnant est celui dont la parité (nombre impair ou pair de 1) est différente de celle de son adversaire.
La stratégie optimale consiste pour chaque joueur à tenter d'échanger pour ajuster la parité de son propre nombre de 1 lorsque c'est son tour et que l'échange est possible.
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
int countA = 0, countB = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] == 1) countA++;
}
for (int i = 0; i < n; i++) {
cin >> b[i];
if (b[i] == 1) countB++;
}
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) continue;
if (i % 2 == 0 && countA % 2 == 0) { // Tour du joueur A
if (a[i] == 0) { countA++; countB--; }
else { countA--; countB++; }
}
if (i % 2 == 1 && countB % 2 == 0) { // Tour du joueur B
if (b[i] == 0) { countB++; countA--; }
else { countB--; countA++; }
}
}
if (countA % 2 == countB % 2) {
cout << "Tie" << endl;
} else if (countA % 2 == 0 && countB % 2 == 1) {
cout << "Mai" << endl;
} else {
cout << "Ajisai" << endl;
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
La boucle principale applique la stratégie gloutonne décrite. La décision finale se base sur la comparaison des parités finales des comptages de 1 pour chaque joueur.
Problème D : Rae Taylor et les Arbres (version facile)
Le problème demande de déterminer si, pour une séquence donnée, on peut connecter chaque élément à un autre élément selon deux règles : un élément peut se connecter à un élément plus grand situé après lui, ou à un élément plus petit situé avant lui. La connectivité doit être telle qu'il existe un chemin entre n'importe quelle paire d'éléments.
L'idée est de parcourir la séquence de gauche à droite en maintenant la valeur minimale vue jusqu'à présent. Lorsqu'on rencontre un élément supérieur à cette valeur minimale, on peut considérer que tous les éléments vus jusqu'ici (y compris les précédents plus petits) forment un groupe connecté.
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int currentMin = a[0];
int candidateMin = a[0];
int lastConnectPos = 0;
for (int i = 1; i < n; i++) {
if (a[i] > currentMin) {
lastConnectPos = i;
currentMin = candidateMin;
candidateMin = a[i];
} else {
if (a[i] < candidateMin) {
candidateMin = a[i];
}
}
}
if (lastConnectPos == n - 1) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
La variable lastConnectPos mémorise la dernière position où une connexion "saut" vers un groupe connecté a eu lieu. Si cette position correspond au dernier élément, toute la séquence est connectée.
Problème F : Rae Taylor et les Arbres (version difficile)
Cette version étend le problème D en demandant non seulement de répondre par "Yes" ou "No", mais aussi de produire explicitement les connexions (paires d'indices) qui réalisent la connectivité si elle est possible.
La logique reste similaire à la version facile. On parcourt la séquence, on groupe les éléments par "sauts" connectés, et on enregistre les connexions entre le groupe actuel et le groupe précédent lorsqu'un saut se produit.
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<pair<int, int>> connections;
int currentMin = a[0];
int candidateMin = a[0];
int lastConnectPos = 0;
vector<int> pendingElements = {a[0]};
for (int i = 1; i < n; i++) {
if (a[i] > currentMin) {
lastConnectPos = i;
for (int elem : pendingElements) {
connections.push_back({a[i], elem});
}
currentMin = candidateMin;
candidateMin = a[i];
pendingElements.clear();
} else {
if (a[i] < candidateMin) {
candidateMin = a[i];
}
pendingElements.push_back(a[i]);
}
}
if (lastConnectPos == n - 1) {
cout << "Yes" << endl;
for (auto &p : connections) {
cout << p.first << " " << p.second << endl;
}
} else {
cout << "No" << endl;
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Le vecteur pendingElements accumule les valeurs des éléments qui n'ont pas encore été connectés par un saut. Lorsqu'nu élément supérieur au minimum courant est trouvé, il est connecté à tous les éléments en attente, formant ainsi un groupe connecté complet.