Les USACO
Présentation
L'homologue américain de France-IOI organise tout au long de l'année des concours en ligne ouverts à tous. Trois divisions sont proposées en fonction du niveau des candidats : Bronze, Argent et Or. Les sujets sont traduits en français par France-IOI.
Participation
Pour participer à ces concours, inscrivez-vous sur contest.usaco.org. Pour plus de renseignements, allez sur http://www.usaco.org.
Règlement
Ce qui suit est le règlement d'un concours USACO récent. La majeure partie est commune à tous les concours USACO.
USACO NOVEMBRE 2009 CONCOURS ELITE Traduction par France-IOI (www.france-ioi.org) ***************************** RÈGLEMENT *********************************** Ce document décrit les règles pour la division « elite » du concours USACO NOVEMBRE 2009 TROIS DIVISIONS POUR CE CONCOURS, DONT DEUX SUR INVITATION Tout le monde peut participer à la division BRONZE. Les divisions OR et ARGENT sont sur invitation uniquement. Allez sur http://contest.usaco.org/showdiv pour connaître la division d'un utilisateur d'ID donné. LA DURÉE DU CONCOURS EST DE TROIS HEURES POUR TOUT LE MONDE Les candidats doivent consacrer TROIS heures de suite (pas de pause) au concours. NE TRICHEZ PAS N'utilisez pas un autre login pour lire les problèmes (ou pour toute autre raison) et tricher. Ne collaborez pas avec d'autres candidats. Vous devez annoter tout code source que vous n'avez pas écrit vous-même entièrement. SI VOUS ÊTES SURPRIS·E À TRICHER, VOUS SEREZ BANNI·E À VIE DE TOUTES LES ACTIVITÉS USACO. NE TRICHEZ PAS, IL N'Y A PAS DE DEUXIÈME CHANCE. CONTACTER LES ORGANISATEURS DU CONCOURS MAIL : Si vous envoyez des e-mails relatifs au concours à l'adresse questions@ace.delos.com, assurez-vous que le sujet contient le mot « USACO » pour qu'il apparaisse en évidence dans notre boîte aux lettres et ne soit pas classé comme étant du spam. Attention au décalage horaire : aucune réponse ne viendra pendant la nuit dans la zone USA Mountain. USACO mail : Un lien au bas de la page permet d'envoyer un message rapide au directeur de concours. Lorsque la réponse est reçue, un lien apparaîtra bien en évidence lors du prochain chargement d'une page du concours USACO. UTILISATION DE CODE VENANT D'AUTRES SOURCES Si vous utilisez du code venant d'internet, un livre ou une autre source pendant le concours, insérez un commentaire dans le code indiquant sa source, sinon vous serez disqualifié·e et banni·e. ****************** INFORMATION SPÉCIFIQUE À CE CONCOURS ******************* NOM : Concours USACO NOVEMBRE 2009 DATES : 4 h GMT Vendredi 6 Nov — 13 h GMT Mardi 9 Nov 21 h MDT Jeudi 5 Nov — 6 h MDT Mardi 9 Nov Notez que vous devez commencer ce concours plusieurs heures avant l'heure de fin, si vous souhaitez avoir assez de temps pour résoudre les problèmes. DURÉE : Trois heures consécutives pour résoudre tous les problèmes. STYLE : Individuel, pas de travail de groupe. SITE : http://ace.delos.com/contestgate DIRECTEUR : Rob Kolstad (kolstad@ace.delos.com) RESP QUESTIONS : questions@ace.delos.com Assurez-vous d'inclure le mot « USACO » dans le sujet, pour éviter le filtre anti-spam. Posez vos questions en anglais. RESP ÉVAL : Rob Kolstad (kolstad@ace.delos.com) HOTLINE : Aux USA et au Canada, appelez la Hotline du concours USACO au +1 719-481-6542 gratuitement, en cas de problèmes pendant le concours (07:00 à 23:00 MST uniquement, merci). LIMITE DE COMPILATION : Votre programme doit compiler en 30 secondes ou moins. LIMITE D'EXÉCUTION : 1 seconde maximum par fichier test (sauf indication contraire) NOTE : les utilisateurs de Java ont 2,7× la limite de temps d'exécution normale, puisque le code Java tourne plus lentement. Les juges se réservent le droit de changer cette constante à tout moment, pour toute raison. Les temps Java sont cependant mis à l'échelle et affichés comme étant entre 0 et 1,0 seconde. MACHINE D'ÉVALUATION : 2,4 GHz Intel Core2 Quad Processor COMPILATEURS : gcc version 4.3.2 (Ubuntu 4.3.2-1ubuntu12) Free Pascal Compiler version 2.2.4 [2009/03/28] for i386 Sun JAVA 1.5.0 GRADING_OS : Linux delos.DELOS.COM 2.6.27-14-generic #1 SMP Mon Aug 31 13:01:41 UTC 2009 i686 SURVEILLANCE : Non requise quelle que soit la division. ASSISTANCE : Les livres, sites web, anciens fichiers et toute autre aide non humaine sont acceptés. Ajoutez un commentaire d'explication à tout code extrait d'un livre, d'un ancien fichier ou du web (ne pas le faire peut entraîner une disqualification). Ne cherchez pas de solutions exactes sur le web et n'utilisez pas les solutions postées sur le site de l'USACO ou des sites similaires. DIVISIONS : Trois divisions : OR, ARGENT et BRONZE. Les divisions OR et ARGENT sont accessibles sur invitation uniquement. MODE D'ANALYSE : Un « mode d'analyse » sera disponible après la fin du concours. Vous pouvez re-tester vos programmes pour déterminer comment ils se seraient comportés avec diverses modifications. ************* INFORMATIONS GÉNÉRALES POUR TOUS LES CONCOURS USACO ************ Ces détails n'ont pas changé depuis les premiers concours 2003–2004. QUOI : Ce « USA Computer Olympiad Contest » est un concours de programmation ouvert à tous les étudiants pré-universitaires du monde. Plusieurs problèmes sont proposés dans chacune des deux catégories. Les résultats de ce concours et d'autres concours feront partie des données utilisées pour choisir les candidats USA sélectionnés au camp d'entraînement américain, et potentiellement aux IOI. Les gagnants de la division or recevront des certificats. QUI : Tous les étudiants pré-universitaires, dans le monde entier, sont éligibles pour concourir. Ceci est un concours individuel et non un concours par équipe. Les candidats visiteurs/observateurs/« pour le fun » seront notés et classés séparément. QUAND : Consultez l'emploi du temps plus haut pour les dates du concours. Tout le travail doit être fait en une seule session. OÙ : Pour les concours non surveillés, les étudiants peuvent travailler sur les solutions des problèmes où ils le souhaitent. Les concours surveillés nécessitent une supervision par un surveillant, bien sûr. COMMENT : Les solutions doivent être écrites en GNU C, GNU C++, FreePascal ou GNU JAVA et être soumises sur le web avant la limite de temps. Dès que la machine d'évaluation reçoit votre programme, elle le compile et lui fait passer un petit nombre de fichiers de tests très simples. Les résultats vous seront envoyés très rapidement. Cela vous permettra de corriger les incompatibilités, noms de fichiers erronés et autres problèmes de ce genre. Cela signifie que les juges feront rarement, voire jamais de modifications à votre programme lors de l'évaluation. Assurez-vous de poser des questions si vous pensez que les compilateurs ont un comportement erroné. PRIX : Dans la division or, chaque gagnant nord-américain recevra un beau certificat et tous les gagnants seront immortalisés sur les pages web de l'USACO. Pour les gagnants plus éloignés, rien n'est déterminé pour le moment. FRAIS : Aucun frais de participation n'est demandé. RÈGLES : La consultation de personnes autres que le directeur du concours est interdite. Travaillez seul·e, pas par équipe. Soumettez vos questions (une seule question par e-mail s'il vous plait) en anglais, à l'adresse indiquée plus haut (RESP QUESTIONS). Cette personne essaiera de vous donner une réponse appropriée (et la postera sur la liste de diffusion électronique hs-computing, ou sur la page web « message-of-the-day », si nécessaire). Sauf indication contraire, votre programme doit s'exécuter en moins de temps que la limite de temps par défaut sur chaque fichier de test, sur la machine du juge. Sauf mention contraire, il n'est PAS garanti que tous les jeux de tests légaux possibles puissent être résolus dans la limite de temps. De même, sauf mention contraire, il n'est PAS garanti que les réponses tiennent dans un type de donnée d'un ordinateur traditionnel (i.e. les résultats entiers peuvent nécessiter une représentation sur plus de 32 bits). Les juges se réservent le droit d'augmenter les limites de temps lors de l'évaluation. Les décisions des juges sont définitives. Ne trichez pas, ce n'est amusant pour personne. Les tricheurs sont souvent disqualifiés et bannis à vie. N'accédez pas au concours en utilisant plus d'un login. N'utilisez pas d'instructions assembleur inline. Ne soumettez pas de programmes utilisant des fichiers de données qui ne sont pas fournis par les organisateurs du concours. Lisez uniquement les fichiers d'entrée indiqués et écrivez uniquement les fichiers de sortie indiqués. Ne soumettez pas de programmes plus longs que 1 000 000 octets. N'utilisez pas de fichiers de données « temporaires ». Ne soumettez pas de programmes que vous avez écrits lors d'une collaboration passée avec d'autres personnes. Souvenez-vous que le concours n'a ni une « entrée spéciale » ni une « sortie spéciale ». En général, les formats d'entrée et de sortie sont directs, bien que les valeurs d'entrée puissent poser des problèmes à votre programme. Sauf mention contraire, les programmes doivent être déterministes par nature et produire des résultats identiques à chaque fois qu'ils sont exécutés avec des entrées identiques. Les programmes qui ne sont pas déterministes seront disqualifiés. Remarquez que des programmes basés sur des nombres aléatoires peuvent toujours être proposés — ils doivent utiliser une graine fixe, pour obtenir la même réponse à chaque fois. Les problèmes sont faits pour être algorithmiques par nature, et des algorithmes et/ou structures de données intelligentes peuvent être nécessaires pour résoudre tous les fichiers de tests correctement et dans les limites de temps. Tous les énoncés de problèmes sont faits pour être directs (même s'ils peuvent être difficiles) ; aucun problème n'est fait de telle sorte qu'il y ait des « pièges cachés » dans l'énoncé du problème. Des jeux de tests légaux, mais complexes pourront être utilisés pour l'évaluation. Si vous trouvez qu'un problème a un énoncé peu clair ou une ambiguïté, documentez vos suppositions précisément, et continuez. Envoyez-nous un e-mail, nous répondrons si nous le pouvons. REMARQUES : Soumettez vos solutions via le web à l'adresse indiquée plus haut. Inscrivez-vous également au concours sur le site web. Si vous vous êtes déjà inscrit·e plus tôt, votre inscription devrait toujours être valide. Vous pouvez demander au site web de vous envoyer vos anciens identifiant et mot de passe à l'adresse e-mail que vous avez fournie lors de votre inscription. Merci d'utiliser le même login pour chaque concours, pour que nous puissions garder une trace des progrès de tout le monde. L'information de description du problème au début de chaque solution doit être exactement au format requis ci-dessous. Les programmes qui ne consistent en rien d'autre que des instructions d'affichage ne seront pas notés. Les programmes doivent calculer les réponses requises. N'utilisez pas de précalcul pour résoudre ces problèmes. Le compilateur C/C++ utilise 32 bits pour un int. Programmeurs C/C++ : Assurez-vous d'exécuter exit(0) lorsque votre programme se termine. Le programme d'évaluation demande à ce que votre programme compile sans erreurs. Vous devez retirer toutes les erreurs pour que votre programme soit noté. Il n'est pas nécessaire d'élaguer les avertissements du compilateur. Les personnes qui soumettent des programmes essayant de détourner les procédures d'évaluation seront disqualifiées définitivement des concours USACO. Ne joignez pas ce club d'élite ! Tous les programmes lisent leur entrée à partir d'un fichier nommé dans l'énoncé du problème (par exemple « cow.in »). N'indiquez pas de chemin complet dans votre instruction « open », mais seulement « cow.in ». Notez que les noms de fichier sont sensibles à la casse. Si le problème indique « cow.in », vous devez utiliser « cow.in », car « CoW.In » et « COW.IN » ne fonctionneront pas. Tous les programmes écrivent leur sortie dans un fichier nommé dans l'énoncé du problème (par ex. « cow.out »). Ne donnez pas de chemin dans votre instruction « open », seulement « cow.out ». Comme pour les fichiers d'entrée, les fichiers de sortie sont sensibles à la casse. Virtuellement, la sortie de tout programme est sous la forme de « lignes ». Une ligne se termine par un caractère de retour à la ligne ('\n' en C ; utilisez writeln en Pascal). Si votre sortie ne contient pas de retour à la ligne à la fin de chaque ligne, il sera noté comme étant incorrect. Les petites quantités de texte que vous écrivez sur stdout ou stderr sont ignorées par la procédure d'évaluation. Elles vous sont cependant retournées, lors de la phase initiale de compilation/test, s'il se produit des erreurs. Notez que les données de test utilisées par les juges pour l'évaluation seront sûrement plus difficiles que les deux exemples de données fournis avec chaque problème et que les données utilisées pour vérifier que votre programme a été soumis correctement. Les juges pourront appliquer des pénalités dans le calcul du score, si des abus sont constatés pour certaines règles. Sauf mention contraire, vos programmes sont limités à 16 Mo de mémoire totale utilisée. Ceci inclut une limite de taille de pile de 1 Mo et une limite (globale) de taille des données d'environ 15 Mo. Ceci signifie que vous ne pouvez pas placer de très grandes quantités de données sur la pile, où sont allouées toutes les variables locales. Notez que tous les exemples sont censés être corrects et sont là pour vous aider. Si vous pensez avoir trouvé une erreur, contactez l'adresse indiquée à RESP QUESTIONS afin que le problème puisse être corrigé. Certains des exemples ont été vérifiés seulement deux fois, et non trois fois. Le programme d'évaluation compilera votre programme avec les optimisations activées. Pour les programmeurs C/C++, le #pragma -fhandle-exceptions est traité correctement. Programmeurs C : #includesi vous utilisez des fonctions mathématiques #include pour srandom/random #include pour srandom/random #include pour srandom/random qui sont appelées comme suit : srandom(seed); randominteger = random(); où randominteger est dans l'intervalle 0..2^31-1. Notez que random()%N sera un entier aléatoire dans l'intervalle 0..N-1. Il y a peu de chances que vous souhaitiez utiliser une graine autre qu'une constante, car cela aurait comme conséquence que votre programme produise un résultat différent d'une exécution à l'autre. Si, au cours du temps, vous soumettez plus d'une solution pour un même problème, seule la dernière soumise sera évaluée. Cela signifie que si vous trouvez un bug après votre soumission, vous pouvez re-soumettre. Il n'y a pas de pénalité lorsque vous re-soumettez — en fait, vous pouvez utiliser cette technique pour vérifier que notre compilateur accepte votre programme, ou même pour effectuer des tests de performances. Essayez de ne pas soumettre plus de 25 solutions, pour que le serveur puisse toujours rester accessible à tout le monde. Toute soumission est confirmée presque instantanément par un programme d'évaluation automatique. ** Mesure du temps CPU intermédiaire utilisé par un programme. ** Utilisateurs de Pascal Le système d'évaluation observera le temps d'exécution de votre programme de l'extérieur. Si vous souhaitez vérifier des temps d'exécution intermédiaires, lors des exécutions de tests ou lors de la soumission, vous pouvez inclure cette ligne dans votre code : {\$i extime.inc} pour inclure la fonction d'exécution appelée « exectime ». Cette fonction n'a pas de paramètre et se manipule comme un entier. Sa valeur est le nombre de millisecondes d'exécution utilisées jusqu'à présent. Voici un exemple de programme montrant cette utilisation : program timetest; {\$i extime.inc} var i, j, k:longint; begin for i := 1 to 100 do begin for j:=1 to 1000000 do begin k := i + j + k; end; end; writeln(exectime); end. Cette fonctionnalité n'est disponible que lors des exécutions de test et des exécutions lors de soumissions. Mesure du temps CPU intermédiaire utilisé par un programme. Utilisateurs de C/C++ Le système d'évaluation observera le temps d'exécution de votre programme de l'extérieur. Si vous souhaitez vérifier des temps d'exécution intermédiaires, lors des exécutions de tests ou lors de la soumission, vous pouvez utiliser la fonction « exectime », qui retourne le nombre de millisecondes que votre programme a utilisé jusqu'à présent. Voici un programme d'exemple, pour montrer son utilisation : int exectime(); main() { long i, j, k; for (i = 0; i < 100; i++) for (j = 0; j < 1000000; j++) k = i + j + k; printf("%d ms\n", exectime()); } Cette fonctionnalité n'est disponible que lors des exécutions de test et des exécutions lors de soumissions. **************** COMMENT UTILISER LA SOUMISSION WEB ****************** Ajoutez des lignes d'identification comme celles-ci au début du fichier source de votre programme (omettez les explications fournies à droite, entre parenthèses) : Pour le C, le C++, le Java (n'incluez pas les commentaires entre parenthèses) : /* PROG: cowfun (le nom du problème, quel qu'il soit) LANG: C++ (choisissez : C, C++, JAVA) ID: votre_id (mettez votre login USACO) */ N'utilisez pas les commentaires //de fin de ligne en C++ pour ces en-têtes, ils ne seront pas acceptés. Pour le Pascal (n'incluez pas les commentaires entre parenthèses) : { PROG: cowfun (le nom du problème, quel qu'il soit) LANG: PASCAL ID: votre_id (mettez votre login USACO) } Ensuite, entrez le nom de fichier dans le formulaire « browser », puis cliquez sur « Send It In ». Vos résultats seront ensuite affichés rapidement. Vous pouvez soumettre des solutions pour un problème simple, avant de commencer le concours, pour vous assurer que tout fonctionne bien. Le nom du programme est « test », les fichiers sont « test.in » et « test.out ». Le fichier d'entrée contient deux nombres sur une seule ligne. Additionnez-les et affichez le résultat sur une seule ligne, dans le fichier « test.out ».