ATOMS - Atoms in the Lab

AC 0.01 s

Problem url: spoj.com/problems/ATOMS

#include <stdio.h>

int main()
{
    int T, time;
    scanf("%d", &T);
   
    long long n, m, k;
   
    while(T--)
    {
        scanf("%lld %lld %lld", &n, &k, &m);
       
        time = 0;
       
        if(k <= m/n)
            while(k <= m/n)
            {
                n *= k;
                time++;
            }
       
        printf("%d\n", time);
    }
}

EKO - Eko

AC 0.50 s

Problem url: spoj.com/problems/EKO

#include <stdio.h>
#define ll long long

ll getM(int *list, int n, int H) {
    ll sum = 0;
    int i;

    for(i = 0; i < n; i++)
        if(list[i] > H)
            sum += list[i] - H;

    return sum;
}

int maks(int a, int b) {
    return a > b? a: b;
}

int h(int *list, int n, ll m) {
    int low = 0, mid, high = 1000000, an = 0;
    ll cek;

    while(low < high) {
        mid = (low + high) / 2;
        cek = getM(list, n, mid);

        if(cek >= m) {
            an = maks(an, mid);
            low = mid + 1;
        } else high = mid;
    }

    return an;
}

int main() {
    int n;
    ll m;

    scanf("%d %lld", &n, &m);

    int list[n], i;
    for(i = 0; i < n; i++) scanf("%d", &list[i]);

    printf("%d\n", h(list, n, m));
}

CODESPTB - Insertion Sort

AC 4.04 s

Problem url: spoj.com/problems/CODESPTB

#include <stdio.h>

int main()
{   int T, n, i, j, swap, tmp;
    scanf("%d", &T);

    while(T--)
    {   scanf("%d", &n);

        int arr[n];
        for(i = 0; i < n; i++)
            scanf("%d", &arr[i]);

        swap = 0;
        if(n == 1) goto end;

        for(i = 1; i < n; i++)
        {   tmp = arr[i];
            j = i - 1;

            while(j > -1 && arr[j] > tmp)
            {    arr[j + 1] = arr[j];
                swap++;
                j--;
            }

            arr[j + 1] = tmp;
        }

end:
        printf("%d\n", swap);
    }
}

Quick Sort

Quick Sort adalah salah satu teknik mengurutkan data dengan cara memindahkan suatu data ke indeks yang benar.

Kelebihan: Cepat untuk jumlah data yang banyak dan acak
Kekurangan: Tidak efektif untuk list data yang hampir terurut

Kompleksitas: O(n.log n)

Animasi visualnya dapat dilihat di visualgo.net/sorting.html

Berikut implementasinya dalam bahasa C.

#include <stdio.h>

void QuickSort(int *arr, int kiri, int kanan);
void swap(int *arr, int i, int j);

int main()
{   /* Input */
    int n;
    scanf("%d", &n);

    int arr[n], i;
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
   
    /* Process */
    QuickSort(arr, 0, n - 1);
   
    /* Output */
    for(i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

/* Fungsi utama Quick Sort */
void QuickSort(int *arr, int kiri, int kanan)
{   if(kiri >= kanan) return;

    int indeks_pivot = kiri, pivot = arr[indeks_pivot];
    int i = kiri + 1, j;

    for(j = i; j <= kanan; j++)
        if(arr[j] < pivot)
            swap(arr, i++, j);

    swap(arr, indeks_pivot, i - 1);
    indeks_pivot = i - 1;

    QuickSort(arr, kiri, indeks_pivot - 1);
    QuickSort(arr, indeks_pivot + 1, kanan);
}

/* Fungsi untuk menukar nilai array di indeks 'i' dengan nilai array di indeks 'j' */
void swap(int *arr, int i, int j)
{   int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Contoh Input:
8
56 74 23 12 11 16 23 41

Contoh Output:
11 12 16 23 23 41 56 74

Merge Sort

Merge Sort adalah salah satu teknik mengurutkan data dengan cara memisahkannya, mengurutkan, dan menyatukan kembali data yang sudah urut.

Kelebihan: Efektif untuk jumlah data yang sangat banyak
Kekurangan: Membutuhkan ruang memori yang besar

Kompleksitas: O(n.log n)

Animasi visualnya dapat dilihat di visualgo.net/sorting.html

Berikut implementasinya dalam bahasa C.

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

void MergeSort(int *arr, int len)
{   if(len < 2) return;

    int mid = len / 2, right_len = len - mid;

    int *left = (int*)malloc(mid * sizeof(int));
    int *right = (int*)malloc(right_len * sizeof(int));

    int i;
    for(i = 0; i < mid; i++) left[i] = arr[i];
    for(; i < len; i++) right[i - mid] = arr[i];

    MergeSort(left, mid);
    MergeSort(right, right_len);

    int a = 0, b = 0;
    i = 0;

    while(a < mid && b < right_len)
        if(left[a] < right[b]) arr[i++] = left[a++];
        else arr[i++] = right[b++];

    while(a < mid) arr[i++] = left[a++];
    while(b < right_len) arr[i++] = right[b++];

    free(left);
    free(right);
}

int main()
{   /* Input */
    int n;
    scanf("%d", &n);

    int arr[n], i;
    for(i = 0; i < n; i++) scanf("%d", &arr[i]);

    /* Process */
    MergeSort(arr, n);

    /* Output */
    for(i = 0; i < n; i++) printf("%d ", arr[i]);
}

Contoh Input:
6
9 8 7 6 5 4

Contoh Output:
4 5 6 7 8 9