13.6 แบบฝึกหัด

#include <stdio.h>

int height[1000];

void insertion_sort(int a[], int n)
{
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &height[i]);
    }
    insertion_sort(height, n);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", height[i]);
    }
    printf("\n");
    return 0;
}

#include <stdio.h>

int seconds[1000];

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void selection_sort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        swap(&a[i], &a[min_index]);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &seconds[i]);
    }
    selection_sort(seconds, n);
    printf("%d\n", seconds[n / 2]);
    return 0;
}

#include <stdio.h>

int code[1000];
int found[1000];

int main()
{
    int n, target;
    scanf("%d %d", &n, &target);
    for (int i = 0; i < n; i++) {
        scanf("%d", &code[i]);
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (code[i] == target) {
            found[count] = i + 1;
            count++;
        }
    }
    printf("%d\n", count);
    if (count > 0) {
        for (int i = 0; i < count; i++) {
            if (i > 0) {
                printf(" ");
            }
            printf("%d", found[i]);
        }
        printf("\n");
    }
    return 0;
}

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

char text[1005], word[105];

void strip_newline(char s[])
{
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '\n' || s[i] == '\r') {
            s[i] = '\0';
        }
    }
}

int main()
{
    fgets(text, sizeof text, stdin);
    fgets(word, sizeof word, stdin);
    strip_newline(text);
    strip_newline(word);
    int n = strlen(text);
    int m = strlen(word);
    int count = 0;
    int first = -1;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && tolower(text[i + j]) == tolower(word[j])) {
            j++;
        }
        if (j == m) {
            if (count == 0) {
                first = i + 1;
            }
            count++;
        }
    }
    printf("%d %d\n", count, first);
    return 0;
}

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

int plate[100000];

int compare_int(const void *p, const void *q)
{
    int x = *(const int *)p;
    int y = *(const int *)q;
    if (x < y) {
        return -1;
    }
    if (x > y) {
        return 1;
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &plate[i]);
    }
    qsort(plate, n, sizeof(int), compare_int);
    int distinct = 0;
    int most = 0;
    int start = 0;
    for (int i = 1; i <= n; i++) {
        if (i == n || plate[i] != plate[i - 1]) {
            distinct++;
            if (i - start > most) {
                most = i - start;
            }
            start = i;
        }
    }
    printf("%d %d\n", distinct, most);
    return 0;
}

#include <stdio.h>

int count[101];

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        int score;
        scanf("%d", &score);
        count[score]++;
    }
    for (int i = 0; i < q; i++) {
        int k;
        scanf("%d", &k);
        int passed = 0;
        int score = 100;
        while (passed + count[score] < k) {
            passed += count[score];
            score--;
        }
        printf("%d\n", score);
    }
    return 0;
}

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

struct contestant {
    char name[11];
    int solved;
    int penalty;
};

struct contestant list[50000];

int compare_rank(const void *p, const void *q)
{
    const struct contestant *a = p;
    const struct contestant *b = q;
    if (a->solved != b->solved) {
        return a->solved > b->solved ? -1 : 1;
    }
    if (a->penalty != b->penalty) {
        return a->penalty < b->penalty ? -1 : 1;
    }
    return strcmp(a->name, b->name);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s %d %d", list[i].name, &list[i].solved, &list[i].penalty);
    }
    qsort(list, n, sizeof(list[0]), compare_rank);
    int rank = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || list[i].solved != list[i - 1].solved || list[i].penalty != list[i - 1].penalty) {
            rank = i + 1;
        }
        printf("%d %s\n", rank, list[i].name);
    }
    return 0;
}

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

int when[100000];

int compare_int(const void *p, const void *q)
{
    int x = *(const int *)p;
    int y = *(const int *)q;
    if (x < y) {
        return -1;
    }
    if (x > y) {
        return 1;
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &when[i]);
    }
    qsort(when, n, sizeof(int), compare_int);
    long long best = (long long)when[1] - when[0];
    for (int i = 2; i < n; i++) {
        long long gap = (long long)when[i] - when[i - 1];
        if (gap < best) {
            best = gap;
        }
    }
    long long pairs = 0;
    if (best > 0) {
        for (int i = 1; i < n; i++) {
            if ((long long)when[i] - when[i - 1] == best) {
                pairs++;
            }
        }
    } else {
        int start = 0;
        for (int i = 1; i <= n; i++) {
            if (i == n || when[i] != when[i - 1]) {
                long long size = i - start;
                pairs += size * (size - 1) / 2;
                start = i;
            }
        }
    }
    printf("%lld %lld\n", best, pairs);
    return 0;
}

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

char key[100000][9];

void sort_letters(char s[])
{
    int length = strlen(s);
    for (int i = 1; i < length; i++) {
        char letter = s[i];
        int j = i - 1;
        while (j >= 0 && s[j] > letter) {
            s[j + 1] = s[j];
            j--;
        }
        s[j + 1] = letter;
    }
}

int compare_key(const void *p, const void *q)
{
    return strcmp((const char *)p, (const char *)q);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", key[i]);
        sort_letters(key[i]);
    }
    qsort(key, n, sizeof(key[0]), compare_key);
    long long pairs = 0;
    int start = 0;
    for (int i = 1; i <= n; i++) {
        if (i == n || strcmp(key[i], key[i - 1]) != 0) {
            long long size = i - start;
            pairs += size * (size - 1) / 2;
            start = i;
        }
    }
    printf("%lld\n", pairs);
    return 0;
}

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

char card[100000][11];

int compare_card(const void *p, const void *q)
{
    const char *a = p;
    const char *b = q;
    char ab[21], ba[21];
    strcpy(ab, a);
    strcat(ab, b);
    strcpy(ba, b);
    strcat(ba, a);
    return strcmp(ba, ab);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", card[i]);
    }
    qsort(card, n, sizeof(card[0]), compare_card);
    if (strcmp(card[0], "0") == 0) {
        printf("0\n");
        return 0;
    }
    for (int i = 0; i < n; i++) {
        printf("%s", card[i]);
    }
    printf("\n");
    return 0;
}