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

SDITSAVL - AVL Tree

AC 0.51 s

Problem url: spoj.com/problems/SDITSAVL

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

typedef struct _node {
    int v, h, idx, pl, pr;
    struct _node *l, *r;
} Node;

typedef struct {
    Node *r;
} Tree;

int height(Node *n) {
    return n? n->h: 0;
}

int max(int h1, int h2) {
    return h1 > h2? h1: h2;
}

void fixheight(Node *n) {
    if(n) n->h = max(height(n->l), height(n->r)) + 1;
}

Node *RR(Node *n) {
    Node *a = n->l;

    n->l = a->r;
    a->r = n;

    fixheight(n);
    fixheight(a);

    a->idx += n->pl;
    a->pl += n->pl;
    n->pl += a->pr;
    a->pr = 0;

    return a;
}

Node *RL(Node *n) {
    Node *a = n->r;

    n->r = a->l;
    a->l = n;

    fixheight(n);
    fixheight(a);

    a->idx += n->pr;
    a->pr += n->pr;
    n->pr += a->pl;
    a->pl = 0;

    return a;
}

int GetBal(Node *n) {
    return n? height(n->l) - height(n->r): 0;
}

Node *Bal(Node *n) {
    fixheight(n);
    int bl = GetBal(n);

    if(bl < -1) {
        if(GetBal(n->r) > 1) n->r = RR(n->r);
        return RL(n);
    } else if(bl > 1) {
        if(GetBal(n->l) < -1) n->l = RL(n->l);
        return RR(n);
    }

    return n;
}

Node *CreateNode(int val, int idx) {
    Node *tmp = (Node*)malloc(sizeof(Node));

    tmp->v = val;
    tmp->idx = idx;
    tmp->h = 1;
    tmp->pl = tmp->pr = 0;
    tmp->l = tmp->r = NULL;

    return tmp;
}

Node *Add(Node *n, int val, int idx) {
    if(!n) return CreateNode(val, idx);
    else if(val < n->v) {
        n->idx += 1;
        n->pr += 1;

        if(n->l) n->l = Add(n->l, val, idx);
        else {
            n->l = Add(n->l, val, n->idx - 1);
            n->pl = 0;
        }
    } else {
        if(n->r) n->r = Add(n->r, val, idx);
        else {
            n->r = Add(n->r, val, n->idx + 1);
            n->pr = 0;
        }
    }

    return Bal(n);
}

void Find(Node *n, int val) {
    Node *i = n;

    while(i)
        if(val == i->v) {
            printf("%d\n", i->idx);
            return;
        } else if(val < i->v) {
            if(i->pl) {
                if(i->l) {
                    i->l->idx += i->pl;
                    i->l->pl += i->pl;
                    i->l->pr += i->pl;
                }
                i->pl = 0;
            }

            i = i->l;
        } else {
            if(i->pr) {
                if(i->r) {
                    i->r->idx += i->pr;
                    i->r->pl += i->pr;
                    i->r->pr += i->pr;
                }
                i->pr = 0;
            }

            i = i->r;
        }

    printf("Data tidak ada\n");
}

int main() {
    Tree *t = (Tree*)malloc(sizeof(Tree));
    t->r = NULL;

    int T, cmd, n;
    scanf("%d", &T);

    while(T--) {
        scanf("%d %d", &cmd, &n);
        if(cmd == 1) t->r = Add(t->r, n, 1);
        else Find(t->r, n);
    }
}

SDITSBST - Binary Search Tree

AC 0.05 s

Problem url: spoj.com/problems/SDITSBST

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

typedef struct _tree
{    char v[18];
    int len, index, plus_l, plus_r;
    struct _tree *l, *r;
} Tree;

void Ins(Tree **t, char *val, int val_len, int indeks)
{    if(!(*t))
    {    *t = (Tree*)malloc(sizeof(Tree));

        strcpy((*t)->v, val);

        (*t)->len = val_len;
        (*t)->index = indeks;

        (*t)->plus_l = (*t)->plus_r = 0;
        (*t)->l = (*t)->r = NULL;
    }
    else if(((*t)->len > val_len) || (((*t)->len == val_len) && (strcmp((*t)->v, val) > 0)))
    {    if((*t)->r) Ins(&(*t)->r, val, val_len, 1);
        else
        {    Ins(&(*t)->r, val, val_len, (*t)->index + 1);
            (*t)->plus_r = 0;
        }
    }
    else
    {    (*t)->index += 1;
        (*t)->plus_r += 1;

        if((*t)->l) Ins(&(*t)->l, val, val_len, 1);
        else
        {    Ins(&(*t)->l, val, val_len, (*t)->index - 1);
            (*t)->plus_l = 0;
        }
    }
}

int Find(Tree **t, char *val, int val_len)
{    if(*t)
    {    if(strcmp((*t)->v, val) == 0)
        {    printf("%d\n", (*t)->index);
            return 1;
        }

        else if(((*t)->len > val_len) || (((*t)->len == val_len) && (strcmp((*t)->v, val) > 0)))
        {    if((*t)->plus_r)
            {    if((*t)->r)
                {    int t_plus_r = (*t)->plus_r;

                    (*t)->r->index += t_plus_r;
                    (*t)->r->plus_l += t_plus_r;
                    (*t)->r->plus_r += t_plus_r;
                }

                (*t)->plus_r = 0;
            }

            return Find(&(*t)->r, val, val_len);
        }

        else
        {    if((*t)->plus_l)
            {    if((*t)->l)
                {    int t_plus_l = (*t)->plus_l;

                    (*t)->l->index += t_plus_l;
                    (*t)->l->plus_l += t_plus_l;
                    (*t)->l->plus_r += t_plus_l;
                }

                (*t)->plus_l = 0;
            }

            return Find(&(*t)->l, val, val_len);
        }
    }
    else return 0;
}

int main()
{    int T, cmd, len;
    scanf("%d", &T);

    Tree *t = NULL;
    char val[18];

    while(T--)
    {    scanf("%d %s", &cmd, val);
        len = strlen(val);

        if(cmd == 1) Ins(&t, val, len, 1);
        else if(!Find(&t, val, len)) printf("Data tidak ada\n");
    }

    return 0;
}