France IOI: Qui a été sélectionné pour le stage du 6 au 12 juillet ?

Les tuples !

Une autre étrangeté...

Je ne sais pas si c'est une véritable classe avec soni implémentation, etc... ou si c'est juste un "Ta gueule c'est magique", autrement dit un truc que le compilo transforme direct en code assembleur.

Parce que la question que je me pose c'est : comment avoir une clsse template avec un nombre de paramètres template variables.

"Edit epsilon012 : les !" -> Hein ? Depuis quand est-ce que tu peux modifier mes messages, toi ? Ou alors je suis schizophrène ? o_Ø

@lgoythme> C'est probablement une véritable classe, cf. les headers de ta libstdc++. En tout cas, c'est facile à implémenter avec les variadic templates, hein. (Ce qui répond à ta deuxième question.) D'ailleurs, boost.MPL l'avait déjà fait avant, mais c'était une solution particulièrement moche : surcharge de la classe pour tous les nombres d'arguments templates... thx préprocesseur.

jeu, 28/06/2012 - 19:02 — @lgorythme

> Parce que la question que je me pose c'est : comment avoir une clsse
> template avec un nombre de paramètres template variables.
En C++11 : il y a un nouveau truc magique qui permet de le faire.
En C++03 : il est possible de le faire en se posant la question différemment.

Un tuple (pour faire simple), c'est juste une struct non nommé.

C'était déjà faisable en C++03 avec les TypeLists et avec C++11, c'est faisable avec les template parameter packs.
Pour les TL, il faut à tout prix lire Modern C++ Design: Generic Programming and Design Patterns Applied d'Andrei Alexandrescu ( amazon )

Par exemple, j'ai une fonction qui doit retourner un double, un int et un std::string.

Une première méthode est d'utiliser une struct :

1
2
        struct s { double d; int i; std::string s; };
        s f();

On aimerait faire :
struct { double d; int i; std::string s; } f(); // Pas valide en C++
Mais ce n'est pas possible à cause de

FDIS (n3290) §8.3.5 [dcl.fct] ¶9

:
> Types shall not be defined in return or parameter types. […]
Et en plus, les membres de la structure sont nommés là.

Mais il y a mieux, en C++11, on peut faire :
std::tuple<double,int,std::string> f();

Et en C++03 :
cons<double, cons<int, cons<std::string, empty> > > f();
En définissant cons et empty comme :

1
2
3
4
5
        struct empty{};
        template <typename Head, typename Tail>
        struct cons: Tail{ // Version trop simple pour être vrai.
                Head val;
        };

Pour que ça soit joli, on utilisait des macros, ça donnait un truc du genre :
TL3(double, int, std::string) f();
Et donc en fait, le template cons a toujours deux paramètres, c'est juste que ces paramètres sont plus où moins compliqués. Je l'ai appelé cons comme en lisp pour ceux qui connaissent… Mais sinon, pense à une liste en C : struct list { int valeur; struct list *suivant; }; … il n'y a que deux éléments mais la liste peut être de n'importe quelle longueur.

En C++11, la déclaration d'un tuple c'est quelque chose comme :

1
2
        template <typename... Types>
        struct tuple;

Comme définie dans le

FDIS (n3290) §20.4.2 [tuple.tuple]

.
En fait, le principe sera le même qu'en C++03 (on a un membre Head et on hérite du tuple formé du reste).

Le ... pour un template parameter c'est à peu près la même chose qu'un ... pour un function parameter. D'ailleurs c'est marrant puisque du coup on peut faire suivre un template parameter pack d'une function parameter list, ça donne des trucs du genre :
void(T......)

mer, 27/06/2012 - 19:01 — @lgorythme

> A quoi sert constexpr ?
Au début des templates en C++, les gens pensait : « Oh cool ! plus besoin de void* dans nos containers ». Et puis (après leur intégration, c'est ça le plus drole) ils se sont rendu compte que les templates étaient en fait un langage turing-complet exécuté à la compilation. En gros, ça permet d'utiliser gcc comme un interpréteur (et non compilateur) ! Mais les templates ne sont pas vraiment fait pour ça alors la syntaxe est assez barbare, constexpr permet de faire ça en moins barbare (mais c'est un mauvais moyen de le définir).

ven, 29/06/2012 - 23:01 — Ekleog

> "Edit epsilon012 : les \< > !" -> Hein ? Depuis quand est-ce que tu
> peux modifier mes messages, toi ? Ou alors je suis schizophrène ? o_Ø
Depuis que je suis vilain organisateur, je peux prendre controle de l'esprit des candidats, la nuit dernière, je t'ai réveillé sans que tu t'en rendes compte.

> Depuis que je suis vilain organisateur, je peux prendre controle de l'esprit des
> candidats, la nuit dernière, je t'ai réveillé sans que tu t'en rendes compte.
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAH !

C'est vrai que sur le forum il n'y a plus les bandeaux orga, alors je ne me suis pas rendu compte qu'ils t'avaient passé ton compte en orga.

Bon... Je vais prendre des cours d'hypnose, pour tenter de te contrôler à la prochaine finale / DF ; comme ça je pourrai aussi prendre le contrôle de l'esprit des candidats ! :mouarf:

Je reviens au sujet initial.

Donc ça y est, vous y êtes, au stage ! Vous nous direz comment ça s'est passé ! Je vois qu'il y en a qui sont passés niveau 4 (tu es particulièrement visé, @lgorythme) !

Ah ! Tu es rapide a reagir, dis-donc ! En effet je suis niveau 4 depuis ce matin.

Franchement c'est genial ! On y est depuis 3 jours et c'est l'eclate.
Actuellement je suis en salle machine. On y a acces quand on veut.

D'ailleur, je pensais, ca serait bien si on pouvait se voir au stage de la toussain, on s'y verrait ! J'espere que j'aurais le niveau pour participer...

PS : desole pour les accent je suis sous qwerty.

PPS : Artix (qualifie aujourd'hui pour les IOI 2012 bravo a lui !) te soupconne d'avoir utilise "std::sort" a la partie 'tris efficaces" car tu as resolu les sujets a 30mn d'intervalle.

>> C'est où qu'il voit l'heure à laquelle j'ai fini l'exercice ?

Dans l'onglet a droite on voit les dernieres soumissions. Il etait co au moment ou tu les as resolu et il t'a vu.

D'ailleurs, moi c'est au niveau 2 que j'ai triche. Tout les problemes de tri je les ai resolu avec un std::set. Honte a moi !

Je vais voir si je ne peux pas essayer de tout implementer moi meme pour le niveau 4, histoire de jouer le jeu.

Essayes déjà de résoudre normalement ceux du niveau 2... Et il y a quand même beaucoup plus joli qu'un set pour trier.

Je suis bloqué à la maison à cause d'une opération donc je n'ai que ça à faire…
Je communique avec Loïc actuellement. Je participe à l'amélioration de France-IOI !

Bien sûr que tu as le niveau pour le stage de la Toussaint ! J'espère qu'on s'y verra, oui !

Je connais l'ÉPITA (je suis allé à Prologin 2011), je sais bien que vous êtes sous QWERTY !

Pour les tris efficaces, ben oui, il n'y a aucune sécurité… C'est où qu'il voit l'heure à laquelle j'ai fini l'exercice ?
(Veuillez ne pas lire la suite si vous n'avez pas atteint le niveau 4 : spoiler details below.)
En fait, j'ai commencé par Tri par tas (bibliothèque). Je n'ai rien compris ; j'ai utilisé push_heap et sort_heap à la place du conteneur voulu… En même temps il n'y a rien d'expliqué.
Ensuite, j'ai fait Tri par tas, et effectivement, je ne savais pas faire un tas. J'ai cherché plusieurs heures comment ça fonctionnait mais ma structure n'était pas suffisamment optimisée. J'ai donc triché avec un std::sort . La correction m'a aidé mais c'est vrai qu'il faudrait que je relise mon code pour voir comment j'ai fait un tas optimisé ; j'avoue que je ne m'en rappelle plus…
Pour le tri rapide, j'ai eu un peu de mal mais j'ai réussi.
Le tri postal s'implémente en deux temps.
Le tri base, je l'ai fait sans trop de problèmes.
Pour la variante du tri base, oui, j'ai encore triché avec un pur std::sort !! En même temps ils n'ont pas précisé qu'on pouvait utiliser un second tableau ; je pensais qu'il fallait absolument faire un tri en place !

Note : peut-être n'ai-je rien compris aux exercices parce que j'ai voulu voir les tris efficaces avant les arbres binaires.

Bah, on est dans un campus. Si on en en a envie on peut coder toute la nuit. Meme a 3h du mat (mais il deconseillent ca pour qu'on en soit pas fatigue).

Sinon, en effet, j'ai trouve plsu adapte de choisir un avatar en rapport avec le jeu de mot de mon pseudo.

Personnellement, je trouve les set très beaux pour le tri... (À ce niveau-là, je comprendrais que j'aie tort.)
Je les ai souvent utilisés, avec les map , pour résoudre des problèmes dès le niveau 2, ce qui m'a souvent bien éloigné de la correction, pour un programme parfois plus lent.
Cela dit, je ne comprends pas comment tu as pu t'en servir pour résoudre les problèmes sur les tris simples.

Pas mal, ta nouvelle image.
Ils vous laissent veiller dis donc ! Kayak II résolu à minuit vingt !

Répondre au sujet

Vous devez vous enregistrer ou vous connecter pour poster des messages.