Rencontre #22: Problèmes du NWERC 2022

Les problèmes de cette semaine sont tirés du concours régional NWERC 2022 de l’ICPC, qui s’est tenu en novembre dernier. La thématique des problèmes alterne principalement entre géométrie et combinatoire.

Problèmes

Les problèmes suivants sont triés par ordre croissant de difficulté.

1. “Bottle Flip” — À quel niveau doit-on remplir une bouteille d’eau afin que son centre de masse soit le plus bas possible?
2. “Circular Caramel Cookie” — Calculez la dimension minimale d’un disque pour qu’il puisse contenir \(s\) carrés d’aire unitaire.
3. “High-quality Tree” — Combien de fois au moins faut-il retirer une feuille d’un arbre binaire pour le rendre équilibré?
4. “ETA” — Construisez un graphe dont la distance moyenne à un sommet donné égale une quantité voulue.
5. “Last Guess” — Résolvez le jeu Wordle.