Présentation  | L'homologue américain de France-IOI organise tout au long de l'année des concours online 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. |
Pour participer à ces concours, inscrivez-vous sur contest.usaco.org. Pour plus de renseignements, allez sur www.usaco.org Règlement Ce qui suit est le règlement du concours du mois de novembre 2009. La majeure partie est commune à tous les concours USACO.
USACO NOVEMBRE 2009 CONCOURS ELITE
Traduction par France-IOI (www.france-ioi.org)
***************************** REGLEMENT ***********************************
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é.
CONTEST LENGTH IS THREE HOURS FOR EVERYONE
All contestants should devote THREE consecutive hours to the
contest.
LA DUREE 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 ETES SURPRIS A TRICHER, VOUS SEREZ BANNI A VIE DE TOUTES LES
ACTIVITES USACO. NE TRICHEZ PAS, IL N'Y A PAS DE DEUXIEME 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és et bannis.
****************** INFORMATION SPECIFIQUE A CE CONCOURS *******************
NOM : Concours USACO NOVEMBRE 2009
DATES: 04h00 GMT Vendredi 6 Nov - 13h00 GMT Mardi 9 Nov
21h00 MDT Jeudi 5 Nov - 06h00 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.
DUREE : 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)
QUESTIONDUDE: 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 EVAL : 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'EXECUTION : 1 seconde maximum par fichier test
(sauf indication contraire)
NOTE : les utilisateurs de Java ont 2.7x 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 secondes.
MACHINE D'EVALUATION: 2.400 GHz Intel Core2 Quad Processor
COMPILERS: 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 GENERALES A 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 erronné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 erronné.
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é.
REGLES : La consultation de personnes autres que le directeur du
concours est interdite.
Travaillez seul, pas par équipe.
Soumettez vos questions (une seule question par e-mail,
s'il-vous plait) en anglais, à l'adresse indiquée plus haut
(QUESTIONDUDE).
Cette personne essaiera de vous donner une réponse appropriée
(et la postera sur la mailing-list 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 peuvent ê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 limite 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 ceci n'est ni un concours avec une
'entrée spéciale', ou une 'sortie spéciale'. En général, les
formats d'entrée et de sortie sont directs, bien que les
valeurs d'entrées peuvent 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 êtres 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
ambiguité, 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à inscrits plus tôt, votre
inscription devrait toujours être valide. Vous pouvez demander
au site web de vous envoyer votre ancien id 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 exactment 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 de
supprimer tous les warnings de compilation.
Les personnes qui soumettent des programmes essayant de
détourner les procédures d'évaluation seront disqualifiés
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
fichiers 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 fichiers
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 à 16MB de
mémoire totale utilisée. Ceci inclut une limite de taille de
pile de 1MB et une limite (globale) de taille des données
d'environ 15MB. 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 'RESP_QUESTIONS', pour qu'il puisse
corriger le problème. 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és comme suit :
srandom(seed);
randominteger = random();
où randominteger vaut entre 0..2^31-1. Notez que random()%N
sera un entier aléatoire dans l'intervalle 0..N-1. Il y a peu
de chaces 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, seul 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(s), 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 éxécutions
de tests, ou lors de la soumission, vous pouvez inclure cette
ligne dans votre code :
{$i extime.inc}
pour inclure la fonction d'éxé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écutions 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 éxé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, C++, JAVA (retirez 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 type //commentaires en C++, pour ces
headers, ils ne fonctionneront pas.
Pour le Pascal (retirez 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", et
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'.
| 