Bonjour, J'ai fait une recherche rapide sur le forum (avec l'outil recherche à disposition) et je n'ai trouvé aucun sujet sur ce concours de programmation pourtant connu. Je me permets donc d'en créer un ici, qui peut regrouper les différents questions qu'il y aurait à propos de ce concours.

J'ai moi-même une question. Pour le premier exercice, je pense voir comment faire, mais cependant je me demandais si l'on pouvait utiliser la totalité des fonctions du langage à notre disposition (comme par exemple une fonction pour classer un tableau par ordre décroissant), où faut-il créer nous même cette fonction ?

Merci de vos réponses, et si ce sujet perdure, bon concours à tous !

eZily0

Alors personnellement j'ai fait moi-même la fonction qui trie le tableau (qui ne prend pas plus que 10 lignes d'ailleurs), donc aucun problème de ce côté-là.

Ce qui pose problème de mon côté c'est l'énoncé de l'exercice 3 qui est incompréhensible et pour ajouter du piment dans tout ça, les exemples de sorties ne sont pas commentés (ce qui aurait aidé à la compréhension).

Ricocotam a écrit:

Euh.. Vous etes mal parti si vous voulez faire un tri de tableau pour l'exo 1

Salut tout le monde,

Les présélections sont maintenant finies.

Pour ma part, je n'ai pas réussi à faire tous les exercices et j'étais seulement au 3ème lorsque le serveur a crash.

J'aimerais savoir si on pouvait s'échanger un peu nos codes afin de voir ce que vous avez fait de votre côté.

Sinon voici l'exercice "Croissance" que je n'ai pas réussi à terminé (ou du moins qui posait des problèmes mais j'ignore lesquels).

// Code par Dardanboy
// Ce code n'est malheureusement pas fonctionnel à 100%, j'ignore pourquoi.
// Si les entrées étaient affichés sur le site d'entraînement, cela m'aurait sûrement permis de savoir où se trouve l'erreur

#include <stdio.h>
#include <stdlib.h>
#include <string.h>



void initialize_numbers(int *tabNumbers, int finalLen){ // Intialiastion des valeures du tableau à -1
    int i;
    for(i = 0; i < finalLen; i ++){
        tabNumbers[i] = -1;
    }
}

int in_value(int x, int len){ // retour de i ou j entre le débordement gauche et droite de len
    if(x < 0){
        do{
            x += len;
        }while(x < len);
    }
    else if(x > len - 1){ // - 1 car le zéro n'est pas compris
        do{
            x -= len;
        }while(x > len);
    }

    return x;
}

int test_ordre(int finalLen, int posP1, int* valueNumbers, int** numberDouble, int* numberOfDoubleUsed, int len){
    int i, j, k, lastValue = valueNumbers[posP1];
    for(i = posP1, k = 0; k < len; i++, k ++){
        i = in_value(i, finalLen);

        if(valueNumbers[i] != -1){
            if(valueNumbers[i] == -2){
                for(j = 0; j < numberOfDoubleUsed[i]; j ++){
                    if(lastValue < numberDouble[i][j])
                    {
                        lastValue = numberDouble[i][j];
                    }
                    else
                    {
                        return 0;
                    }
                }
            }else{
                if(lastValue < valueNumbers[i]){
                    lastValue = valueNumbers[i];
                }else{
                    return 0;
                }
            }

        }
    }
    return 1;
}

void croissance(int* deltas, int len){
    int i, j, k, oldNumb, finalLen = len, used = 0, *temp = NULL, *tabNumbers = calloc(finalLen*finalLen, sizeof(int)), **numberDouble = calloc(finalLen*finalLen, sizeof(int)), *numberOfDoubleUsed = calloc(finalLen*finalLen, sizeof(int));
    int posP1 = 0 + deltas[0];

    for(i = 0; i < (finalLen*finalLen); i++)
    {
        numberDouble[i] = calloc(finalLen*finalLen, sizeof(int));
        if(numberDouble[i] == NULL){
            exit(1);
        }
    }

    initialize_numbers(tabNumbers, finalLen*finalLen);

    for(i = 0, j = 0; i < len; j ++, i ++){
        j = i + deltas[i];
        j = in_value(j, finalLen);

        if(tabNumbers[j] == -1){
            tabNumbers[j] = i+1;
        }
        else{ // Sinon on met tout dans un autre tableau où les éléments se regroupant sur la même case tabNumbers[j] vont y paraître allignés
            if(numberOfDoubleUsed[j] == 0){
                numberDouble[j][numberOfDoubleUsed[j]] = tabNumbers[j];
                numberOfDoubleUsed[j] ++;
            }

            numberDouble[j][numberOfDoubleUsed[j]] = i+1;
            numberOfDoubleUsed[j] ++;


            tabNumbers[j] = -2; // On signale qu'il y a plusieurs variables possibles pour cette case et qu'on va stocker tout ceci dans un autre tablea
        }
    }

    printf("%d", test_ordre(finalLen, posP1, tabNumbers, numberDouble, numberOfDoubleUsed, len));
}

int is_number(char c)
{
    return c <= '9' && c >= '0';
}

int* read_deltas(int len)
{
    int *result = malloc( len * sizeof(int));
    int index;

    for (index = 0 ; index < len; index++)
    {
        int num = 0;
        char current_char = '\0';
        scanf("%c", &current_char);

        do
        {
            num = num * 10 + current_char - '0';
            scanf("%c", &current_char);
        }while(is_number(current_char));
        result[index] = num;
    }

    return result;
}

int main(void)
{
    int len = 5;
    scanf("%d", &len);
    scanf("%*[ \t\r\n]c");
    int* deltas = read_deltas(len);

    croissance(deltas, len);

    return 0;
}

le code suivant ne fonctionne pas, j'ai pas réussi à le faire, je me suis précipité et forcément ca marche moins bien

#include <cstddef>
#include <iostream>
#include <vector>

int croissance(std::size_t n, std::vector<int> &tuyaux){	
	/* On fait avancer les plombiers */
	for(int i = 0; i < n; ++i){
		tuyaux[i] = (i + tuyaux[i]) % n;
	}

	/* On range les plombiers dans l'ordre */
	std::vector<int> plombier(n);
	int min;
	for(int i = 0; i < n; i++){
		min = i;
		for(int j = (i + 1); j < n; ++j){
			if(tuyaux[j] < tuyaux[min])
				min = j;
		}
		tuyaux[min] = tuyaux[i];		
		tuyaux[i] = min;
	}

	unsigned int k;
	for(k = 1; (k < n) && (tuyaux[k] >= tuyaux[k - 1]); ++k);

	if(k == n){
		return 1;
	}
	else if(k != n)
		return 0;
}

int main(){
	std::size_t n;
	std::cin >> n;
	std::vector<int> tuyaux(n);
	for(std::size_t i=0; i<n; ++i)
		std::cin >> tuyaux[i];
	std::cout << croissance(n, tuyaux) << '\n';
}

Sinon, j'ai eu 64 et 236 au deux premiers sur le serveur d'entrainement

.

-
Edité par Tonguy 8 janvier 2014 à 11:32:34

Dardanboy t'as serieusement fait 138 ligne ?

J'ai vraiment dû mal comprendre l'exercice...

# -*- coding: latin1 -*-
# le désordre se créer a partir du moment ou le tuyaux Tn est supérieur de 2 a un tuyaux Tn+1
nbr_tuyaux = 5 # simulation du nombre de tuyaux
liste_tuyaux = [1,2,3,2,2]
ordonner = 1
n=0
while n < nbr_tuyaux:
    tuyaux_suivant = n+1
    if tuyaux_suivant >= nbr_tuyaux:
        tuyaux_suivant = 0
    if liste_tuyaux[n] - liste_tuyaux[tuyaux_suivant] >=2: # si le tuyaux n moins le tuyaux n+1 est superieur a 2...
        ordonner = 0 # ....alors il y as du désordre, car les plombiers passe devant les plombiers de devant
    n+=1
print ordonner

Et sinon j'ai une question. Quand es-ce qu'on sauras si on est pris ou pas ?

-
Edité par Adrenaline Chalenger 23 janvier 2014 à 19:21:32

Personnellement, j'ai fait Repli en ~70 lignes

Sinon pour vos exo croissance, testez :

4
3 0 0 0

-
Edité par Uriopass 25 janvier 2014 à 21:24:34

Salut. Tu peux me dire comment tu as fait Repli s'il te plaît ?

Moi j'ai réussi tous les exercices sauf celui-là U_U...

En fait, j'ai un peu la flemme d'expliquer Repli mais en gros :

• A : {2..4}
• R : {0..2}
• T : {3..5} ?

Il suffit ensuite de faire un tableau bidimensionnel et de tester toutes les possibilités et en comptant (comme pour l'éxo 4) et dire le chiffre trouvé a l'intervalle {0..0}.

Oui je sais c'est difficile a comprendre, (et à expliquer en même temps).

Bon bah j'ai retrouvé le code source ^^.

Donc voici le code de Repli (oui je sais ça fait pas 38 lignes, je confond avec hâte)

#include<stdio.h>
#include<stdlib.h>
 
int len;
 
int A(int x)
{
    return (x/len);
}
int B(int x)
{
    return (x%len);
}
int X(int a,int b)
{
    return (a%len)*len + b%len;
}
int doit(int* resultat , int* travail , int* mem2ptr , int val , int k , char act) {
    //printf("%c : a.b : %d.%d  k : %d  mem2 : %d %s\n",act,A(val),B(val),k,*mem2ptr,resultat[val]==-1?"ok":"");
    if(val == 0)
        return 1;
    if(resultat[val]==-1)
    {
        resultat[val] = k+1;
        travail[*mem2ptr] = val;
        (*mem2ptr)++;
    }
    return 0;
}
int repli(int* deltas)
{
    int len2 = len*len;
    int* resultat = malloc(sizeof(int) * len2);
    int* travail = malloc(sizeof(int) * len2);
 
    int mem1 = len, mem2 = len;
    int j, k=0, a, b, found = 0;
 
    int i;
    for(i=0;i<2*len;i++)
        if(deltas[i%len]<deltas[(i+len-1)%len]-1)
            deltas[i%len]+=len;
 
    for(j=0;j<len2;j++)
        resultat[j] = -1;
 
    for(j=0;j<len;j++)
    {
        int x = X(j, j+len-1);
        travail[j] = x;
        resultat[x] = 0;
    }
 
    for(j=0;j<len2;j++)
    {
        int c = travail[j] ;
        if (j==mem1)
        {
            k++ ;
            if(mem1 == mem2)
                return -1;
            else
                mem1 = mem2;
        }
        a = A(c);
        b = B(c);
        if (b<a)
            b+=len;
        //printf("--------- doing %d.%d\n",a,b);
        found =
                                                   doit(resultat,travail,&mem2,X(a+1        ,b+1            ),k,'A') // A
        ||                                         doit(resultat,travail,&mem2,X(a+len-1    ,b+len-1        ),k,'R') // R
        || (a+deltas[a])+len!=(b+deltas[b%len]) && doit(resultat,travail,&mem2,X(a+deltas[a],b+deltas[b%len]),k,'T') // T
        ;
        if(found)
            return k+1;
    }
    return -1;
}
 
int main(void){
    int i, *deltas,res;
 
    scanf("%d\n", &len);
    deltas = malloc(len * sizeof(int));
    for(i = 0;i<len;i++)
        scanf(" %d", deltas+i);
 
    res = repli(deltas);
    printf("%d", res);
    return 0;
}

-
Edité par Uriopass 25 janvier 2014 à 21:20:30