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 d'Octobre 2006. La majeure partie est commune à tous les concours USACO.
******************************** NOUVEAUTES *******************************
Le but de ce concours est de répartir les candidats en divisions. Tout
candidat peut y participer et essayer de résoudre des problèmes. Les
candidats seront classés en fonction du problème le plus difficile
qu'ils ont résolu (ou au moins résolu suffisamment correctement) ou de
leur division actuelle, selon celle qui est la plus élevée. PERSONNE
NE SERA PASSE A UNE DIVISION INFERIEURE A SA DIVISION ACTUELLE.
Ce concours est OPTIONNEL -- pour tout le monde. Si vous êtes déjà
affecté à une division, soit vous resterez dans cette division, ou si
vous résolvez des problèmes correctement, pourrez passer à une division
supérieure.
RESULTATS PUBLIES LIMITES
Les seuls résultats publiés pour ce concours sont la division à laquelle
chaque candidat se qualifie. Le concours ne sera pas utilisé pour les
classements de cette saison.
LA DUREE DU CONCOURS EST DE TROIS HEURES
Les candidats doivent consacrer QUATRE heures de suite (pas de pause)
au concours.
CHOIX DES PROBLEMES A RESOUDRE
Vous pouvez choisir les problèmes que vous souhaitez résoudre. Ils
sont présentés par ordre de difficulté (les problèmes les plus simples
d'abord). La deuxième moitié des problèmes sert de filtres pour les
candidats de la division OR. Les deux premiers problèmes sont plutôt
pour la division BRONZE.
NE TRICHEZ PAS
n'utilisez pas un autre login pour lire les problèmes et tricher.
Ne collaborez pas avec d'autres candidats. 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. Vous pouvez aussi utiliser
le lien en bas de l'écran pour une réponse rapide à l'écran (si le
directeur du concours est connecté).
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 octobre 2006
DATES : 08h00 GMT Vendredi 13 Octobre - 15h00 GMT Mardi 17 Octobre
01:00 MDT Vendredi 14 Octobre - 08:00 MDT Mardi 18 Octobre
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 le(s) problème(s)
de votre choix.
STYLE : Individuel, pas de travail de groupe.
SOLUTIONS A : http://contest.usaco.org
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 877-753-3567 gratuitement, pour les
problèmes pendant le concours (07:00 à 23:00 MDT
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 1.5x 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 mis à l'échelle et affichés comme
0..1.0 secondes, cependant.
MACHINE D'EVALUATION: 700 MHz Duron
COMPILATEURS : gcc version 4.1.0 20060304 (Red Hat 4.1.0-3)
Sun JAVA 1.5.0
Free Pascal Compiler version 2.0.2 [2005/12/07]
for i386.
OS D'EVALUATION : Linux version 2.6.15-1.2054_FC5smp
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 : Pas de divisions, tout le monde peut essayer de résoudre
les problèmes qu'il souhaite.
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 Octobre 2003.
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 chaque catégorie
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 : 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 <math.h> si vous utilisez
des fonctions mathématiques
#include <stdlib.h> pour srandom/random
#include <sys/types.h> pour srandom/random
#include <unistd.h> 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 :
/*
PROG: cowfun (le nom du problème, quel qu'il soit)
LANG: C++ (Choisissez : C, C++, JAVA)
*/
N'utilisez pas les commentaires de type //commentaires en C++, pour ces
headers, ils ne fonctionneront pas.
Pour le Pascal :
{
PROG: cowfun (le nom du problème, quel qu'il soit)
LANG: PASCAL
}
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'.
|
