Modular Exponentation

Modular Exponentation digunakan untuk menemukan nilai sisa pembagian.

Ada 3 cara untuk melakukan modular exponentation, yaitu: Straightforward Method, Memory Efficient Method, dan Bit Shift Method.

1. Straightforward Method

Berikut kode untuk metode straightforward.

#include <stdio.h>

int ModEx1(int a, int b, int c)
{   int i, res = a;

    for(i = b; i > 0; i--) res *= a;

    return res % c;
}

int main()
{   int a, b, c;
    scanf("%d %d %d", &a, &b, &c);

    printf("%d\n", ModEx1(a, b, c));
}

2. Memory Efficient Method

3. Bit Shift Method

Convert Int to String

Kadang kala kita harus mengubah suatu tipe data menjadi tipe data lain dengan isi yang sama. Misalnya, kita ingin mengubah tipe data int menjadi string. Untuk mengubah tipe data menjadi string (char*), kita bisa menggunakan perintah ini.

sprintf(char *dest, const char *Format, ...);

Catatan
Perintah tersebut hanya bisa digunakan untuk mengubah tipe data lain menjadi string (char*) saja dan tidak bisa sebaliknya. Misalnya, tidak bisa dari string (char*) menjadi int.

Berikut contoh implemetasinya.

#include <stdio.h>

int main()
{
    char string[10];
    int number = 10341;
  
    sprintf(string, "%d", number);
  
    printf("%s\n", string);
}

Berikut contoh kode untuk mengubah tipe data long long int menjadi string.

#include <stdio.h>

int main()
{
    char string[10];
    long long int number = 41798654817561947;
   
    sprintf(string, "%lld", number);
   
    printf("%s\n", string);
}

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;
}

MAXLN - The Max Lines

AC 0.00 s.

Problem url: spoj.com/problems/MAXLN

#include <stdio.h>

int main()
{   int T, i;
    double r;

    scanf("%d", &T);
   
    for(i = 1; i <= T; i++)
    {   scanf("%lf", &r);
        printf("Case %d: %.2lf\n", i, 4*r*r + 0.25);
    }
}

NPC2015A - Eefun Guessing Words

AC 0.91 s.

Problem url: spoj.com/problems/NPC2015A

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

void Create(char *s, char kar[90][90])
{   int i, j;
    char *a;
   
    for(i = 'A'; i <= 'Z'; i++)
    {   a = strchr(s, i);
       
        if(a)
        {   a++;
           
            for(j = 'A'; j <= 'Z'; j++)
                if(strchr(a, j)) kar[i][j] = 1;
                else kar[i][j] = 0;
        }
        else for(j = 'A'; j <= 'Z'; j++) kar[i][j] = 0;
    }
}

int main()
{   char s[1000100], kar[90][90], x, y, t;
    scanf("%s", s);
   
    int T;
    scanf("%d%c", &T, &t);
   
    Create(s, kar);
   
    while(T--)
    {   scanf("%c%c%c%c", &x, &t, &y, &t);
       
        if(kar[x][y] == 1) printf("YA\n");
        else printf("TIDAK\n");
    }
}

Tree Sort

Tree sort adalah teknik mengurutkan data dengan menggunakan struktur data tree.

Kelebihan: Data langsung urut begitu dimasukkan, efektif untuk jumlah data yang kecil.
Kekurangan: Tidak efektif untuk jumlah data yang besar.

Berikut code dan implementasinya dalam bahasa pemrograman C.

// Tree Sort
#include <stdio.h>
#include <stdlib.h>

typedef struct _tree
{   int v;
    struct _tree *p, *l, *r;
} Tree;

void Ins(Tree **t, int val)
{   if(!(*t))
    {    *t = (Tree*)malloc(sizeof(Tree));
   
        (*t)->p = (*t)->l = (*t)->r = NULL;
        (*t)->v = val;
    }
    else if((*t)->v > val)
    {    Ins(&(*t)->l, val);
        (*t)->l->p = *t;
    }
    else
    {    Ins(&(*t)->r, val);
        (*t)->r->p = *t;
    }
}

void Print(Tree *t)
{   if(t)
    {    Print(t->l);
        printf("%d ", t->v);
        Print(t->r);
    }
}

int main()
{   Tree *t = NULL;
    int n;
   
    while(scanf("%d", &n) && n != 0)
        Ins(&t, n);
   
    Print(t);
}

Contoh Input:
123 72 16 26 38 18 61 35 1 5 2 6 0

Contoh Output:
1 2 5 6 16 18 26 35 38 61 72 123

TREEORD - Tree Order

Code di bawah ini merupakan penyelesaian dari salah satu problem SPOJ yang bernama Tree Order dalam bahasa C. Accepted 0.00 s.

Problem url: spoj.com/problems/TREEORD

#include <stdio.h>

int Cek(int *pre, int *post, int *in, int n)
{    if(pre[0] != post[n - 1]) return 0;

    if(n == 1)
        if(pre[0] == post[0] && post[0] == in[0]) return 1;
        else return 0;

    int i;
    for(i = 0; i < n; i++)
        if(in[i] == pre[0]) break;

    if(i == n) return 0;

    int j, result = 1, post_r = post[n - 2], leftn = 0;

    for(j = 0; j < n; j++)
        if(pre[j] == post_r)
        {    if((result *= Cek(pre + j, post + j - 1, in + i + 1, n - j)) == 0) return 0;
            leftn = j - 1;
            break;
        }

    if(i != 0) result *= Cek(pre + 1, post, in + 1, leftn);
   
    return result;
}

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

    int pre[T], post[T], in[T];

    for(i = 0; i < T; i++) scanf("%d", &pre[i]);
    for(i = 0; i < T; i++) scanf("%d", &post[i]);
    for(i = 0; i < T; i++) scanf("%d", &in[i]);

    if(Cek(pre, post, in, T)) printf("yes\n");
    else printf("no\n");
}

Beiju Text

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

typedef struct  _data
{    char c;
    struct _data *back, *next;
} Data;

void Add(Data *d, char ch)
{    Data *tmp = (Data*)malloc(sizeof(Data));
    tmp->c  = ch;
    tmp->back = d;
    tmp->next = d->next;

    d->next->back = tmp;
    d->next = tmp;
}

void PrintOut(Data *first, Data *last)
{    Data *iter = first->next;
    while(iter != last)
    {    printf("%c", iter->c);
        iter = iter->next;
        free(iter->back);
    }
    free(iter);
    printf("\n");
}

int main()
{    Data *first, *iter, *last;
    char inp[500000];
    int i, len;

    while(scanf("%s", inp) != EOF)
    {    first = (Data*)malloc(sizeof(Data));
        last = (Data*)malloc(sizeof(Data));

        first->back = NULL;
        first->next = last;

        last->back = first;
        last->next = NULL;

        iter = first;
        len = strlen(inp);

        for(i = 0; i < len; i++)
        {    switch(inp[i])
            {    case '[':
                    iter = first;
                    break;
                case ']':
                    iter = last->back;
                    break;
                default:
                    Add(iter, inp[i]);
                    iter = iter->next;
            }
        }

        PrintOut(first, last);
    }
    return 0;
}

SBE201P2 - Linked List

Code di bawah ini merupakan penyelesaian dari salah satu problem SPOJ yang bernama Linked List dalam bahasa C. Accepted 0.00 s.

Problem url: spoj.com/problems/SBE201P2

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

typedef struct _data
{    int val;
    struct _data *next;
} Data;

typedef struct
{    Data *first;
    int size;
} Stack;

void Ins(Stack *s, int value, int index)
{    Data *tmp = (Data*)malloc(sizeof(Data));

    if((index == 0) || (s->first == NULL))
    {    tmp->val = value;
        tmp->next = s->first;
        s->first = tmp;
    }
    else
    {    Data *iter = s->first;
        tmp->val = value;

        int i;
        if(index >= s->size) i = s->size - 1;
        else i = index - 1;
        while(i--) iter = iter->next;

        tmp->next = iter->next;
        iter->next = tmp;
    }

    (s->size)++;
}

void Del(Stack *s, int index)
{    Data *iter = s->first;

    if((index >= s->size) || (s->first == NULL)) return;
    else if(index == 0)
    {    s->first = iter->next;
        free(iter);
    }
    else
    {    Data *iter2;

        int i = index - 1;
        while(i--) iter = iter->next;

        iter2 = iter->next->next;
        free(iter->next);
        iter->next = iter2;
    }

    (s->size)--;
}

void PrintOut(Stack *s)
{    if(s->first == NULL) printf("empty\n");
    else
    {    Data *iter = s->first;

        while(iter != NULL)
        {    printf("%d ", iter->val);
            iter = iter->next;
        }
        printf("\n");
    }
}

int main()
{    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->first = NULL;
    s->size = 0;

    char tmp;
    int M, N;

    while(scanf("%c", &tmp) && (tmp != 'q'))
    {    switch(tmp)
        {    case 'f':
                scanf("%d", &N);
                Ins(s, N, 0);
                break;
            case 'i':
                scanf("%d %d", &M, &N);
                Ins(s, N, M);
                break;
            case 'r':
                Del(s, 0);
                break;
            case 'd':
                scanf("%d", &M);
                Del(s, M);
        }

        scanf("%c", &tmp);
        PrintOut(s);
    }
}

PQUEUE - Printer Queue

Code di bawah ini merupakan penyelesaian dari salah satu problem SPOJ yang bernama Printer Queue dalam bahasa C. Accepted 0.00 s.

Problem url: spoj.com/problems/PQUEUE/

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

typedef struct _data
{    int value;
    int ini;
    struct _data *back;
} Data;

typedef struct
{    Data *front;
    Data *back;
} Queue;

void Init(Queue *q)
{    q->front = NULL;
    q->back = NULL;
}

void Enqueue(Queue *q, int val, int iin)
{    Data *tmp = (Data*)malloc(sizeof(Data));

    tmp->value = val;
    tmp->ini = iin;
    tmp->back = NULL;

    if(q->back != NULL)
        q->back->back = tmp;

    q->back = tmp;

    if(q->front == NULL)
        q->front = tmp;
}

void Dequeue(Queue *q)
{    Data *iter = q->front;
    q->front = iter->back;
    free(iter);
}

void Shift(Queue *q)
{    Data *iter = q->front;

    q->front = iter->back;
    q->back->back = iter;
    q->back = iter;
    q->back->back = NULL;
}

void FreeMem(Queue *q)
{    Data *iter = q->front, *iter2;
   
    while(iter != NULL)
    {    iter2 = iter;
        iter = iter->back;
        free(iter2);
    }
}

void Process(Queue *q)
{    if(q->front == q->back)
    {    printf("1\n");
        return;
    }

    Data *iter, *iter2;
    int st, time = 0;

    for(iter = q->front; iter != NULL; iter = q->front)
    {    st = 0;

        for(iter2 = iter->back; iter2 != NULL; iter2 = iter2->back)
            if(iter->value < iter2->value)
            {    Shift(q);
                st = 1;
                break;
            }

        if(st == 0)
        {    time++;
            if(iter->ini) break;
            Dequeue(q);
        }
    }

    printf("%d\n", time);
    FreeMem(q);
}

int main()
{    Queue *q;

    int T, n, m, i, tmp;
    scanf("%d", &T);

    while(T--)
    {    scanf("%d %d", &n, &m);
       
        q = (Queue*)malloc(sizeof(Queue));
        Init(q);

        for(i = 0; i < n; i++)
        {    scanf("%d", &tmp);
            Enqueue(q, tmp, (i == m));
        }

        Process(q);
    }
}

STPAR - Street Parade

Code di bawah ini merupakan penyelesaian dari salah satu problem SPOJ yang bernama Street Parade dalam bahasa C. Accepted 0.00 s.

Problem url: spoj.com/problems/STPAR/

#include <stdio.h>
#define MAX 1001

void Push(int *stack, int val, int *top)
{    stack[++(*top)] = val;
}

void Process1(int *input, int n)
{    int stack[MAX], top = -1, i, go = 0;

    for(i = 0; i < n; i++)
    {    while(top != -1 && stack[top] == go + 1)
        {    top--;
            go++;
        }

        if(input[i] == go + 1) go++;
       
        else if(top != -1 && input[i] > stack[top])
        {    printf("no\n");
            return;
        }
       
        else Push(stack, input[i], &top);
    }

    printf("yes\n");
}

int main()
{    int input[MAX], n, i;

    while(scanf("%d", &n) && n != 0)
    {    for(i = 0; i < n; i++)
            scanf("%d", &input[i]);

        Process1(input, n);
    }
}

ONP - Transform The Expression

Code di bawah ini merupakan penyelesaian dari salah satu problem SPOJ yang bernama Transform The Expression dalam bahasa C. Accepted 0.00 s.

Problem url: spoj.com/problems/ONP

#include <stdio.h>
#define MAX 500

void Push(char arr[], char in, int *top)
{    arr[++(*top)] = in;
}

char Pop(char arr[], int *top)
{    return arr[(*top)--];
}

void PrintData(char *arr, int top)
{    int i;
    for(i = 0; i <= top; i++)
        printf("%c", arr[i]);
    printf("\n");
}

void Process(char *ar1, char *ar2)
{    // 1 = var; 2 = operator
    int top1 = -1, top2 = -1;
    char temp, tmp;
   
    while(scanf("%c", &temp) && temp != '\n')
    {    switch(temp)
        {    case '(':
                Push(ar2, temp, &top2);
                break;

            case ')':
                while((tmp = Pop(ar2, &top2)) != '(')
                    Push(ar1, tmp, &top1);
                break;

            case '+':
            case '-':
                if((top2 != -1) && (ar2[top2] == '*' || ar2[top2] == '/' || ar2[top2] == '^'))
                    Push(ar1, Pop(ar2, &top2), &top1);

                Push(ar2, temp, &top2);
                break;

            case '*':
            case '/':
                if(top2 != -1 && ar2[top2] == '^')
                    Push(ar1, Pop(ar2, &top2), &top1);
           
            case '^':
                Push(ar2, temp, &top2);
                break;
           
            default:
                Push(ar1, temp, &top1);
                break;
        }
    }

    while(top2 != -1)
        Push(ar1, Pop(ar2, &top2), &top1);

    PrintData(ar1, top1);
}

int main()
{   char ar1[MAX], ar2[MAX];
    int T;

    scanf("%d", &T);
    getchar();
   
    while(T--)
        Process(ar1, ar2);
}

Mengecek Bilangan Prima

Bilangan prima adalah bilangan yang habis dibagi oleh 1 dan bilangan itu sendiri.

Ada banyak cara untuk mengecek apakah suatu bilangan prima atau bukan. Berikut ini merupakan algoritma yang sering kita jumpai.
1. Bilangan x dibagi 2, 3, 4, ..., sampai x/2

Kekurangan dari algoritma di atas ialah prosesnya sangat lambat dan tidak efektif untuk bilangan yang besar.

Solusinya, gunakan algortima berikut ini.
1. Bilangan x dicek apakah kurang dari 2 atau merupakan bilangan kelipatan 2.
2. Jika ya, maka bukan bilangan prima.
3. Jika tidak, maka bilangan x dibagi 3, 5, 7, ..., sampai akar dari x.

Algoritma ini sangat efektif untuk mengecek bilangan yang sangat besar. Misalnya, 2147483647. Bilangan tersebut merupakan batas atas dalam variabel signed integer. Untuk mengecek bilangan tersebut, biasanya program membutuhkan waktu beberapa detik. Namun, jika menggunakan algoritma ini, pengecekan bisa selesai dalam seketika.

Berikut implementasinya dalam bahasa C.

// Cek Bilangan Prima
#include<stdio.h>
#include<math.h>

int main()
{    int N, akar, i;
    scanf("%d", &N);

    if(N < 2 || N % 2 == 0)
    {    printf("Bukan bilangan prima");
        return 0;
    }

    akar = sqrt(N);
    for(i = 3; i <= akar; i+=2)
        if(N % i == 0)
        {    printf("Bukan bilangan prima");
            return 0;
        }
       
    printf("Bilangan prima");
}

Contoh input:
2147483647

Output:
Bilangan prima

Greatest Common Divisor

Greatest Common Divisor (GCD) adalah faktor persekutuan terbesar (FPB) dalam bahasa Indonesia.

Berikut implementasinya dalam bahasa C.

// Greatest Common Divisor (GCD)
#include<stdio.h>

int gcd(int m, int n)
{  
    if(n == 0) return m;
    return gcd(n, m%n);
}

int main()
{  
    int m, n;
    printf("Masukkan 2 angka dipisah spasi: ");
    scanf("%d %d", &m, &n);
  
    printf("FPB: %d\n", gcd(m, n));
}

Contoh Input:
15 9

Output:
3