France-IOI
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 ».