Aujourd'hui Dans la ville portugaise de Porto, aura lieu la finale du concours international de programmation ICPC 2019. Des représentants de l'Université ITMO et d'autres équipes d'universités de Russie, de Chine, d'Inde, des États-Unis et d'autres pays y participeront. Disons-le plus en détail.
icpcnews /flickr/ CC BY / Photos de la finale ICPC-2016 à Phuket
Qu'est-ce que le CIPC
ICPC est un concours international de programmation entre étudiants. Ils ont lieu depuis plus de 40 ans - la première finale passé en 1977. La sélection s'effectue en plusieurs étapes. Les universités sont réparties par région (Europe, Asie, Afrique, Amérique, etc.). Chacun d'eux accueille des étapes intermédiaires, notamment les demi-finales nord-eurasiennes a eu lieu dans notre université. Les vainqueurs des étapes régionales participent à la finale.
À l'ICPC, des équipes de trois participants sont invitées à résoudre un certain nombre de problèmes à l'aide d'un seul ordinateur (non connecté à Internet). Ainsi, outre les compétences en programmation, les compétences en matière de travail en équipe sont également testées.
Les équipes de l'Université ITMO ont remporté sept fois le prix principal du CIPC. Il s'agit d'un record absolu qui dure depuis de nombreuses années. Ils s'affronteront dans la bataille pour la Coupe ICPC 2019 135 groupes venus de toute la planète. L'Université ITMO est représentée cette année par Ilya Poduremennykh, Stanislav Naumov и Romain Korobkov.
Comment se déroulera la finale ?
Pendant la compétition, les équipes recevra un ordinateur pour trois personnes. Il exécute Ubuntu 18.04 et a vi/vim, gvim, emacs, gedit, geany et kate préinstallés. Vous pouvez écrire des programmes en Python, Kotlin, Java ou C++.
Lorsqu'une équipe résout un problème, elle le transmet au serveur de test, qui évalue le code. Les participants ne savent pas quels tests la machine effectue. Si tous réussissent, l’équipe reçoit des points bonus. Sinon, une erreur est générée et les étudiants sont envoyés pour corriger le code.
Selon les règles du CIPC, l'équipe qui résout le plus de problèmes gagne. S'il y a plusieurs équipes de ce type, le vainqueur est déterminé par le temps de pénalité le plus petit. Les participants reçoivent des minutes de pénalité pour chaque problème résolu. Le nombre de minutes est égal au temps écoulé depuis le début du concours jusqu'à l'acceptation de la tâche par le serveur de test. Si l'équipe trouve une solution, elle reçoit alors vingt minutes de pénalité supplémentaires pour chaque tentative incorrecte de la dépasser.
icpcnews /flickr/ CC BY / Photos de la finale ICPC-2016 à Phuket
Exemples de problèmes
Les objectifs du championnat nécessitent de la coordination et de la concentration des équipes. De plus, ils testent la connaissance des algorithmes mathématiques individuels. Voici un exemple de tâche qui a été proposée aux participants du ICPC 2018 :
En typographie, il existe un terme « rivière » - il s'agit d'une séquence d'espaces entre les mots, formée de plusieurs lignes de texte. Un certain expert en rivières (en vrai) souhaite publier un livre. Il souhaite que les rivières typographiques les plus longues se « forment » sur la page lors de l’impression en police à espacement fixe. Les participants devaient déterminer la largeur des champs pour laquelle cette condition serait remplie.
En entrée, le programme a reçu un entier n (2 ≤ n ≤ 2 500), qui détermine le nombre de mots dans le texte. Ensuite, le texte était saisi : les mots sur une ligne étaient séparés par un espace et ne pouvaient pas comporter plus de 80 caractères.
En sortie, le programme devait montrer la largeur des champs au niveau desquels se forme la plus longue « rivière » et la longueur de cette rivière.