Concours d'algorithmie : Prologin 2004 - Page 1

Le questionnaire de sélection est disponible sur le site oficiel : http://www.prologin.org/qcm.php
Voici les questions d'algo, pour ceux qui ont la flemme de cliquer (je trouve que les questions de culture générale n'ont pas de sens pour un concours d'algo...) :

1 Écrire une fonction qui prend un nombre de secondes en argument (inférieur à 86400), et affiche le nombre d'heures, de minutes, et de secondes correspondant, au format "hh:mm:ss". (3 points)

2 Écrire une fonction qui prend en argument un tableau d'entiers, et qui retourne la longueur de la zone la plus grande de ce tableau, qui ne contienne que des nombres consécutifs, dans l'ordre croissant. (3 points)

3 Écrire une fonction qui prend en argument une chaîne de caractères S, et qui retourne le nombre de sous-chaînes de S commençant par le caractère 'a', et se terminant par le caractère 'b'. (4 points)

4 Soient un tableau d'entiers positifs et un entier positif N. Écrire une fonction prenant en arguments ce tableau et cet entier, et retournant la taille du plus grand sous-tableau dont la somme des éléments est un multiple de N. On précise que le tableau contient au plus 10000 éléments, et que N est inférieur a 1000. (4 points)

5 Écrire une fonction qui prend en argument un tableau à deux dimensions rempli de 0 et de 1, et qui retourne le nombre de cases du plus grand sous-tableau ne contenant que des 0. (6 points)

Pas de solutions SVP. On peut s'aider, mais pas cracher du code tout prêt.

Pour la question 5 je ne comprends pas l'énoncé, c'est à cause du fait qu'il est précisé que le tableau a 2 dimensions. Je ne comprends pas quel effet ça a pour la suite

bah le sous tableau peut avoir 2 dimensions aussi je vois pas le pb

en gros fo trouver le + grand carré de 0

OK, je ne comprenais pas si les sous-tableaux de 0 devaient être des rectangles ou non...
Enfin, vu le barême de cet exercice, ça paraît p^lus ou moins évident, sinon il serait plus simple que d'autres exercices qui comptent moins de points.

Ben je trouve que ces questions sont un peu moins difficiles que celles de l'année dernière. Je me souviens que l'année dernière, la dernière question du QCM était assez difficile.

Tiens je vais peut-être participer cette année
Et y a un thème spécifique à chaque année ou c'est la surprise?

yAro> Est-ce que c'est un carré ou le produit cartésien d'un ensemble de lignes par un ensemble de colonnes? J'ai déjà vu la définition d'un sous-mot comme étant un certain nombre de caractères pris dans l'ordre (i.e. a[i1]a[i2]..a[in], avec 1 <= i1 < i2 < ... < in <= p), donc c'est ambigu...

C'est la surprise en ce qui concerne le thème.

Ué je sais c ambigu mais c le 1er truc auquel g pensé ... et qui me parait le + logique ...

0000
0000
0000 0000

Me parait + logique

0000
000
0000 0

Ou

0000
0 0
0000 0

La première question me rappel un TP de programmation en C sur ATMEL.
La dernière ne mérite pas 6 points je trouve.

Produit cartésien d'un ens de lignes et de colonnes = on choisit les colonnes qu'on veut et les lignes qu'on veut, et on prend les cases qui sont à la fois sur une de ces lignes et sur une de ces colonnes. Ca me paraît être l'autre possibilité, avec celle du ./4.

> La dernière ne mérite pas 6 points je trouve.
Parce que tu trouves que les autres les méritent, les leurs?

de tte 90% des gens qui on tenté le questionnaire passe en demi final, la selection, la vrai se fait sur l'entretiens, le reste permet de départager et de décourager certain (surtout la scéance d'algo le matin poru les 1/2 finale, les question sont de plus en plus "hard" pour en décourager certain, mais sinon c'est assé sympa comme ambiance )

la selection, la vrai se fait sur l'entretien

C'est même pas drôle Surtout, je ne vois pas trop comment ils peuvent juger quoi que ce soit sur 20 minutes d'entretien?


Et sinon, qui est-ce qui a déjà participé? Vous comptez participez cette année?

[EDIT : je lis "Le critère principal de sélection est l'épreuve algorithmique", on m'aurait menti ? ]

j'ai déja participé 3ans de suite, mais moi avoir plus de 20ans, bref peu plus participer depuis 2ans...

Pollux> J'ai déjà participé l'année dernière, et effectivement on a un petit entretien de 20 minutes, mais les gars m'ont dit que ça ne compte pas trop pour la note, c'est pour l'ajuster. On a une épreuve d'algo le matin qui est moyennement difficile (enfin, il faut avoir de bonnes notions d'algo pour s'en sortir, je ne pense pas que tu auras trop de difficultés).
Et l'après midi, il y a une "épreuve machine", c'est-à-dire qu'on te met sur un PC et tu as une série d'exercices d'algo de difficulté croissante, et les derniers là sont vraiment difficiles.

Faudrait que je les fasses pour améliorer mon algorithmique merdique...

Pour la question 6, je pense qu'une simplification du problème est que si on a une case 1 de coordonnées (x, y), la solution se trouve forcément dans l'un des domaines {(i<x,j)}, {(x<i,j)}, {(i,j<y)}, {(i,y<j)}. Ca simplifie pas mal le problème car on n'a plus à étudier tous les sous-tableaux, mais simplement à trouver la première case noire du tableau à étudier, et à récurer... Bien sur, si on veut améliorer, on peut essayer de trouver la case noire la plus proche du milieu de la zone, il
faudrait voir ce qu'on gagne, par rapport à la perte due à la recherche.

Tiré du site d'entraînement:

PROBLEME 
Écrire une fonction qui prend en argument un tableau à deux dimensions rempli de 0 et de 1, et qui retourne le nombre de cases du plus grand sous-tableau ne contenant que des 0.

On appelle sous-tableau, une zone rectangulaire, à l'intérieur du tableau d'origine, constitué d'un certain nombres de colonnes consécutives, et d'un certain nombre de lignes consécutives de ces colonnes. 

LIMITES DE TEMPS ET DE MEMOIRE 
Temps : 10 s sur une machine à 1Ghz.
Mémoire : 10000 Ko. 

CONTRAINTES 
1 <= L, C <= 1000, où L, C sont respectivement le nombre de lignes et de colonnes du tableau.

ENTREE 
La première ligne de l'entrée contient deux entiers, séparés par un espace : L et C, respectivement le nombre de lignes et de colonnes du tableau.

Chacune des L lignes suivantes contient C entiers (0 ou 1), séparés par des espaces : le contenu du tableau.

SORTIE 
Vous devez écrire un entier sur la sortie : le nombre de cases du plus grand sous-tableau ne contenant que des 0. 

EXEMPLE(S) D'ENTREE / SORTIE 
Exemple 1 : 
en entrée ... 
5 4 
0 1 0 1 
1 0 0 0 
0 0 0 0 
0 0 0 0 
1 1 0 1 
 
en sortie ... 9 

COMMENTAIRES 
Dans l'exemple, le sous tableau considéré est celui qui est marqué par des # :

0 1 0 1
1 # # #
1 # # #
0 # # #
1 1 0 1

Tiens j'ai glandé pendant 3 heures sur les 5 premiers sujets d'entraînement aux Olympiades d'info, c'est marrant

Tu es en âge de participer Pollux ? Il faut être né après Mai 1983.
Moi j'ai participé deux ans. J'ai été admis en finale l'année dernière. L'ambiance est excellente... tellement que je n'avais pas envie de me perndre la tête sur le sujet et que j'ai rien glandé des 3 jours
Prévoir une serviette de bain...

Je ne sais pas si je vais y aller cette année. Je participe au concours de robotique E=M6. Ca ferait payer à mes parents 2 voyages à Paris.

Tu es en âge de participer Pollux ? Il faut être né après Mai 1983.

Janvier 1986

Prévoir une serviette de bain...

Y a même une piscine?

Je participe au concours de robotique E=M6

Tiens, toi aussi? Alors, essai ou drop?

Ca ferait payer à mes parents 2 voyages à Paris.

Hé hé, l'un des nbx avantages d'être sur Paris

Tu es plus jeune que moi ! J'étais convaincu du contraire
Tu as sauté combien de classes mon petit ?

t'as que 17 ans Pollux?!

Euh, ouais

Tu as sauté combien de classes

2 ou 3, selon que tu estimes que je suis de 85 ou de 86.

mon petit

Tu n'as pas aimé
Tu sais bien ce que je pense de toi, on discute assez par mini-messages. Ton âge ne change évidemment rien à mon avis ! C'est un nombre qui n'indique rien de plus que le nombre d'années vécues, et rien d'autre. Pour moi c'est clair.

Tu n'as pas aimé

Non, je savais bien que c'était de la provoc pure et simple

Même pas. C'était pour ironiser. C'est tellement jouissif de pouvoir dire "mon petit" à un maître

NiPuteNiSoumise: pkoi deux voyages sur Paris ? e=m6 c à la ferté-bernard (on s'y retrouve en finale ? )

Erf vous êtes dans des grosses teams tous les deux? Nous en tous cas on vise plus l'homologation qu'autre chose (bon, peut-être pas, mais presque)

L'année dernière, ils ont pas passé l'homologation à cause de leurs batteries
Cette année, on vise les 16emes pke on voit tres loins