Pour commencer la session d’hiver, nous étudierons une belle série de problèmes qui mêlent algorithmique et mathématiques.
Bienvenue aux personnes qui rejoignent le club aujourd’hui! Jetez un œil à la présentation du club qui s’est donnée en septembre. Pour pouvoir vous attaquer aux problèmes de cette semaine, commencez par vous créer un compte sur Kattis. N’hésitez pas à poser des questions autour de vous!
Les problèmes de cette série font appel à différents concepts mathématiques, notamment l’arithmétique modulaire. La liste est en ordre croissant de difficulté.
“Das Blinkenlights” — Déterminez si deux lumières clignotantes finiront par s’allumer simultanément avant un instant donné.
“Three Powers” — Considérez la liste des sous-ensembles de puissances de 3, dans l’ordre croissant de la somme de leurs éléments. Quel est le \(n\)-ème ensemble dans cette liste?
“Cracking RSA” — Calculez la clé privée correspondant à une clé publique de chiffrement RSA, pour des petits nombres premiers (clé de 20 bits).
“Bachet’s Game” — Dans cette variante du jeu de Nim, les deux joueurs ôtent chacun leur tour \(x\) roches d’un unique tas de \(n\) roches, où \(x\) doit être choisi parmi un ensemble de possibilités données. Le joueur qui retire la dernière roche gagne. Existe-t-il une stratégie gagnante pour le premier joueur?
“XOR max” — Quelle est la plus grande valeur pouvant être obtenue en choisissant des nombres parmi un ensemble de nombres et en calculant leur somme XOR?
Bonus: “Tetration” (un problème purement mathématique).