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 : #include   si 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 ».