Le problème du déport maximal de cartes explore la distance maximale à laquelle une pile de cartes peut dépasser le bord d'une table. En supposant que les cartes sont toujours perpendiculaires à la table, une seule carte peut déborder d'une lognueur équivalente à la moitié de sa propre longueur.

Lorsque deux cartes sont utilisées, la carte supérieure peut dépasser la carte inférieure de la moitié de sa longueur. La carte inférieure, à son tour, peut déborder de la table d'un tiers de sa longueur. Le déport total maximal atteint alors 1/2 + 1/3 = 5/6 de la longueur d'une carte.

De manière générale, avec N cartes, le déport maximal cumulé est donné par la somme des fractions harmoniques modifiées : 1/2 + 1/3 + 1/4 + ... + 1/(N + 1). Dans cette configuration, chaque carte supérieure dépasse la suivante de 1/(k+1) si c'est la k-ième carte en partant du haut, et la carte du bas dépasse la table de 1/(N + 1).

Le défi consiste à détermnier le nombre minimal de cartes requises pour atteindre un déport cumulé d'au moins une longueur cible spécifiée.

Spécifications d'Entrée

Chaque ligne d'entrée représente un cas de test, contenant un nombre flottant positif C. Cette valeur représente la longueur de déport minimale souhaitée. C sera toujours comprise entre 0.01 et 5.20 (inclus) et aura exactement trois chiffres après la virgule. La lecture des entrées se termine par une ligne contenant la valeur 0.00.

Spécifications de Sortie

Pour chaque cas de test, la sortie doit indiquer le nombre minimal de cartes nécessaires pour obtenir un déport d'au moins C. Le format de sortie doit suivre l'exemple fourni : X carte(s).

Exemple d'Entrée

1.00
3.71
0.04
5.19
0.00

Exemple de Sortie

3 carte(s)
61 carte(s)
1 carte(s)
273 carte(s)

Une stratégie efficace pour résoudre ce problème consiste à pré-calculer les longueurs de déport cumulées pour un nombre croissant de cartes et à stocker ces valeurs dans une table. Ensuite, pour chaque longueur cible, une recherche binaire peut être effectuée sur cette table pour trouver rapidement le nombre minimal de cartes correspondantes.

Implémentation en C++

#include <iostream>
#include <vector>
#include <iomanip> // Pour std::fixed et std::setprecision
#include <algorithm> // Pour std::lower_bound
#include <cmath> // Pour std::abs

// Précision pour les comparaisons en virgule flottante
const double EPSILON = 1e-9; 

// Vecteur pour stocker les longueurs de déport pré-calculées
std::vector<double> longueurs_deport_cumulees;

/**
* @brief Prépare le tableau des longueurs de déport cumulées.
* La pré-calcul des valeurs permet une recherche rapide ultérieure.
* Le déport pour N cartes est 1/2 + 1/3 + ... + 1/(N+1).
*/
void precalculerDeports() {
   longueurs_deport_cumulees.push_back(0.0); // 0 cartes = 0 déport
   double cumul_actuel_deport = 0.0;
   int nombre_cartes = 0;

   // On pré-calcule les déports jusqu'à dépasser la valeur maximale d'entrée (5.20)
   while (cumul_actuel_deport < 5.20 + EPSILON) { 
       nombre_cartes++;
       cumul_actuel_deport += 1.0 / (static_cast<double>(nombre_cartes) + 1.0);
       longueurs_deport_cumulees.push_back(cumul_actuel_deport);
   }
}

int main() {
   // Optimisation des entrées/sorties
   std::ios_base::sync_with_stdio(false);
   std::cin.tie(NULL);

   precalculerDeports(); // Appel de la fonction de pré-calcul

   double cible_longueur;
   // Lire les entrées tant que la valeur n'est pas 0.00
   while (std::cin >> cible_longueur && std::abs(cible_longueur - 0.00) > EPSILON) {
       // Utilisation de std::lower_bound pour trouver le premier élément
       // dans le vecteur qui est supérieur ou égal à la cible_longueur.
       // Cela retourne un itérateur vers l'emplacement du nombre minimal de cartes.
       auto it = std::lower_bound(longueurs_deport_cumulees.begin(), 
                                  longueurs_deport_cumulees.end(), 
                                  cible_longueur);
       
       // La distance entre l'itérateur retourné et le début du vecteur
       // donne l'indice, qui correspond au nombre de cartes.
       int cartes_requises = std::distance(longueurs_deport_cumulees.begin(), it);
       
       std::cout << cartes_requises << " carte(s)\n";
   }

   return 0;
}