Implémentation d'une calculatrice basique prenant en charge les quatre opérations arithmétiques à partir d'une entrée formatée.

#include <stdio.h>

int main(void) {
    int x, y, res;
    char op;
    scanf("%d%c%d", &x, &op, &y);
    switch(op) {
        case '+': res = x + y; break;
        case '-': res = x - y; break;
        case '*': res = x * y; break;
        case '/': res = x / y; break;
    }
    printf("%d\n", res);
    return 0;
}

Tarification du métro

Le prix d'un billet dépend de la distance parcourue, avec une réduction applicable selon le montant cumulé des dépenses.

#include <stdio.h>

int main(void) {
    int total, dist;
    scanf("%d%d", &total, &dist);
    double fare;
    if (dist <= 6)      fare = 3;
    else if (dist <= 12) fare = 4;
    else if (dist <= 22) fare = 5;
    else if (dist <= 32) fare = 6;
    else {
        int extra = dist - 32;
        fare = 6 + (extra + 9) / 10;
    }
    if (total >= 150)      fare *= 0.5;
    else if (total >= 100) fare *= 0.8;
    printf("%.2lf\n", fare);
    return 0;
}

Coexistence bactérienne

Étant donné une population de bactéries, on cherche le nombre d'individus dont la valeur dépasse la moitié du maximum observé, puis on en déduit la quantité restante.

#include <stdio.h>

int vals[4000];

int main(void) {
    int count, peak = 0, weak = 0;
    scanf("%d", &count);
    for (int i = 0; i < count; ++i) {
        scanf("%d", &vals[i]);
        if (vals[i] > peak) peak = vals[i];
    }
    for (int i = 0; i < count; ++i)
        if (vals[i] <= peak / 2)
            ++weak;
    printf("%d\n", count - weak);
    return 0;
}

Classement d'examen

Tri des candidats selon leur score décroissant, avec l'identifiant comme critère secondaire en ordre croissant en cas d'égalité.

#include <stdio.h>

typedef struct {
    int id;
    int score;
} Candidate;

Candidate arr[400];

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &arr[i].id, &arr[i].score);
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j) {
            int swap = 0;
            if (arr[i].score < arr[j].score) swap = 1;
            else if (arr[i].score == arr[j].score && arr[i].id > arr[j].id) swap = 1;
            if (swap) {
                Candidate tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    for (int i = 0; i < n; ++i)
        printf("%d\n", arr[i].id);
    return 0;
}

Décodage de texte

Chaque caractère du texte original est décalé par une valeur donnée dans un tableau de'ntiers. Le texte source est étendu par modulo pour couvrir tous les indices nécessaries.

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

int shifts[200];

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &shifts[i]);
    scanf("\n");
    char text[200];
    scanf("%s", text);
    int len = strlen(text);
    for (int i = 0; i < n; ++i)
        printf("%c", text[i % len] + shifts[i]);
    printf("\n");
    return 0;
}

Empilement d'assiettes

On dispose une grille et on incrémente les cellules voisines (incluant la cellule elle-même) pour chaque position d'assiette. On cherche ensuite la valeur maximale et son nombre d'occurrences.

#include <stdio.h>

int grid[2000][2000];
const int dx[9] = {0, 0, 0, 1, 1, 1, -1, -1, -1};
const int dy[9] = {0, 1, -1, 0, 1, -1, 0, 1, -1};

void place(int r, int c) {
    for (int i = 0; i < 9; ++i)
        ++grid[r + dx[i]][c + dy[i]];
}

int main(void) {
    int rows, cols, k, best = 0, freq = 1;
    scanf("%d%d%d", &rows, &cols, &k);
    for (int i = 0; i < k; ++i) {
        int r, c;
        scanf("%d%d", &r, &c);
        place(r, c);
    }
    for (int i = 1; i <= rows; ++i)
        for (int j = 1; j <= cols; ++j) {
            if (grid[i][j] == best) ++freq;
            else if (grid[i][j] > best) {
                best = grid[i][j];
                freq = 1;
            }
        }
    printf("%d %d\n", best, freq);
    return 0;
}

Mèmes réseau

On dispose d'un ensemble de paires de chaînes équivalentes. L'objectif est de déterminer si deux mots donnés appartiennent à la même classe d'équivalence. Une aproche par parcours en largeur (BFS) permet d'explorer toutes les chaînes connectées à partir d'un mot source.

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

char left[200][200], right[200][200];
char start[200], target[200];
char queue[4000][200];
int visited[200];
int n, head, tail;

int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%s%s", left[i], right[i]);
    scanf("%s%s", start, target);
    if (strcmp(start, target) == 0) {
        printf("Yes\n");
        return 0;
    }
    strcpy(queue[0], start);
    head = 0; tail = 1;
    while (head < tail) {
        char *cur = queue[head++];
        if (strcmp(cur, target) == 0) {
            printf("Yes\n");
            return 0;
        }
        for (int i = 0; i < n; ++i) {
            if (visited[i]) continue;
            if (strcmp(cur, left[i]) == 0 || strcmp(cur, right[i]) == 0) {
                char *next = (strcmp(cur, left[i]) == 0) ? right[i] : left[i];
                strcpy(queue[tail++], next);
                visited[i] = 1;
            }
        }
    }
    printf("No\n");
    return 0;
}

Mot de passe téléphonique

Génération récursive de toutes les combinaisons de lettres possibles à partir d'une séquence de chiffres, en utilisant le clavier téléphonique traditionnel.

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

const char *keymap[] = {"", "", "abc", "def", "ghi",
                        "jkl", "mno", "pqrs", "tuv", "wxyz"};
const int sizes[] = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4};

char input[20], output[20];
int len;

void backtrack(int pos, int depth) {
    if (pos == len) {
        output[depth] = '\0';
        printf("%s\n", output);
        return;
    }
    int digit = input[pos] - '0';
    for (int i = 0; i < sizes[digit]; ++i) {
        output[depth] = keymap[digit][i];
        backtrack(pos + 1, depth + 1);
    }
}

int main(void) {
    scanf("%s", input);
    len = strlen(input);
    backtrack(0, 0);
    return 0;
}

Probabilité de faces consécutives

On modélise le lancer de \(n\) pièces et l'on cherche le nombre de séquences où le plus long run de faces consécutives vaut exactement \(m\).

Soit \(dp[i][j][k]\) le nombre de façons d'arranger \(i\) lancers tels que le maximum de faces consécutives soit \(j\), et qu'il y ait actuellement \(k\) faces consécutifs en fin de séquence.

Les transitions sont les suivantes :

• \(k = 0\) : le dernier lancer est pile, donc tout état précédent est admissible : \(dp[i][j][0] = \sum_{k=0}^{j} dp[i-1][j][k]\)
• \(0 < k < j\) : on ajoute une face à une séquence existante : \(dp[i][j][k] = dp[i-1][j][k-1]\)
• \(k = j\) : soit on étend un run de longueur \(j-1\), soit on en démarre un nouveau à partir d'un état où le maximum était déjà \(j\) : \(dp[i][j][j] = dp[i-1][j-1][j-1] + dp[i-1][j][j-1]\)

La réponse finale est \(\sum_{k=0}^{m} dp[n][m][k]\).

#include <stdio.h>

int dp[200][200][200];

int main(void) {
    int N, M, result = 0;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        dp[i][0][0] = 1;
        dp[i][i][i] = 1;
    }
    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j < i; ++j) {
            for (int k = 0; k <= j; ++k)
                dp[i][j][0] += dp[i-1][j][k];
            for (int k = 1; k < j; ++k)
                dp[i][j][k] += dp[i-1][j][k-1];
            dp[i][j][j] += dp[i-1][j-1][j-1] + dp[i-1][j][j-1];
        }
    }
    for (int k = 0; k <= M; ++k)
        result += dp[N][M][k];
    printf("%d\n", result);
    return 0;
}