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

FTIf Journey 2016

Apa sih FTIf Journey itu? FTIf Journey adalah kegiatan yang mendekatkan mahasiswa baru Teknik Informatika (TC) ITS dan Sistem Informasi (SI) ITS (dalam hal ini angkatan 2015). Kegiatan ini juga merupakan salah satu program kerja dari Departemen Student Development BEM FTIf ITS. FTIf Journey juga termasuk kegiatan pasca pelatihan (KPP) LKMM Pra-TD FTIf ITS tahun 2015.

FTIf adalah singkatan dari Fakultas Teknologi Informasi. Fakultas ini memiliki 2 jurusan, yaitu TC dan SI. Walaupun termasuk dalam fakultas yang sama, secara fisik, letak bangunan SI jauh dari TC. SI terletak di sebelah barat sedangkan TC di sebelah timur. SI justru satu bangunan dengan D3 Mesin, D3 Elektro, S1 Teknik Industri, dan S1 Manajemen Bisnis. Sedangkan jurusan terdekat dari TC yaitu S1 Desain Produk Industri. Perbedaan unik lainnya ialah ruangan di SI bernama TC. Sedangkan ruangan di TC bernama IF (untung bukan SI :)).

FTIf Journey dilaksanakan pada hari Sabtu-Minggu, 27-28 Februari 2016. Tadinya, kegiatan ini akan dilaksanakan di gedung TC dan SI. Namun, kegiatan ini tidak jadi dilaksanakan di gedung TC karena ada pemusatan pelatihan nasional tim olimpiade komputer.

Tema FTIf Journey kali ini adalah ‘to be social hero’. Tema ini memiliki kemiripan dengan tujuan dari Departemen Social Responsibility BEM FTIf ITS. Tema dan serangkaian kegiatan FTIf Journey 2016 jauh berbeda dari tahun-tahun sebelumnya. Pada hari pertama, kami have fun. Sedangkan pada hari kedua, kami melakukan kegiatan social responsibility.

Pengelompokan

Kami dibagi menjadi 2 kelompok besar yaitu Dinasti Mahabaratha dan Dinasti Ramayana. Di setiap dinasti, ada 7 kelompok kecil. Saya masuk ke Dinasti Mahabaratha dan kelompok kecil (kelompok 1) yang bernama Arjuna.

Walaupun dibagi menjadi banyak kelompok, kami tidak merasa ada kelompok pada sebagian besar kegiatan FTIf Journey ini. Kelompok besar hanya berfungsi untuk penugasan saja. Sedangkan kelompok kecil berfungsi pada saat sesi kecil (sesi sharing), bermain games, dan kegiatan observasi. Selebihnya, kami membaur antara TC dan SI sebagai mahasiswa FTIf ITS.

Hari Pertama (Sabtu, 27 Februari 2016)

Hari pertama, kami disuruh kumpul jam 06.30 di SI. Tapi, hampir tidak ada orang di sekitar plasa SI. Ternyata, sebagian besar peserta berkumpul di parkiran motor. Lalu, ada pengarahan untuk berbaris sesuai kelompok kecilnya di parkiran mobil. Kemudian, ada pengarahan ke plasa SI (tetap dalam barisan per kelompok), lalu ke kelas TC 103-104.

Di sana, rangkaian acara pembuka dilaksanakan. Kami semua duduk di lantai. Di sana, ada penunjukan komting FTIf. Setelah terpilih, kami diminta membuat jargon FTIf Journey.

Sekitar jam 8.15-8.45, ada sambutan dari Ketua Pelaksana FTIf Journey Mas Fandhi, Ketua BEM FTIf Mas Nanda, dan Wakil Dekan FTIf sebagai pembuka kegiatan FTIf Journey 2016 (karena Dekan FTIf berhalangan hadir).

Sesi pertama yang kami dapat yaitu sesi inspiratif dari YPAB Surabaya. Pertama-tama, mereka menyajikan penampilan bermusik. Kemudian, ada sesi talk show. Mereka menceritakan kegiatan mereka dan bagaimana hidup dalam keterbatasan. Ternyata, walaupun tunanetra, mereka juga bermain sepak bola. Mungkin ada yang bertanya-tanya bagaimana caranya. Caranya dengan menggunakan suara. Dan ketika mereka bermain bola, mereka sering berpeluk-pelukan. Selain itu, ada juga yang menempuh pendidikan guru di Unesa. Namun, barangnya sering hilang saat berada di asrama. Selain itu, yang perempuan juga pintar memasak. Ketika sesi bertanya tiba, ada yang bertanya apakah cita-citanya. Ada yang ingin menjadi pilot dan juga ada yang ingin menjadi koki dan penyanyi. Sesi ini diakhiri dengan penampilan bermusik lagi.

Setelah sesi inspiratif, kami dibagi per kelompok kecil ke plasa SI. Ada juga yang di selasar SI. Kami kedatangan kakak pendamping yang bernama Mas Ahsan. Kami menunggu beberapa saat untuk sesi selanjutnya yaitu sesi diskusi. Sebelumnya, Mas Ahsan memperkenalkan diri. Lalu, kami memperkenalkan diri. Dalam perkenalan diri kami ada nama, asal daerah, masuk lewat jalur SNMPTN atau SBMPTN, dan alasan masuk TC/SI.

Akhirnya, ada kakak pendamping yang memoderasi sesi diskusi kami yang bernama Kak Theta. Dalam sesi diskusi ini, beliau menyampaikan materi tentang gengsi. Kami diperlihatkan 2 video tentang gengsi. Jadi, intinya kita tidak boleh gengsi melakukan perbuatan yang baik. Misalnya, membuang sampah di tempatnya, memindahkan pot bunga ke tetesan air, dan memberi sedekah. Sesi tersebut cukup santai. Kami juga diajak berdiskusi dan mendengar pengalaman tentang aplikasi mobile untuk membantu masyarakat dalam menghadapi bencana dari Kak Theta. Materi ini sesuai dengan tema FTIf Journey kali ini. Isi materi tersebut cukup bagus walaupun fasilitas presentasi kurang mendukung.

Kami kumpul kembali ke kelas TC 103-104. Kemudian, ada ishoma (istirahat, sholat, makan). Setelah itu, kami bersiap-siap mengikuti games.

Sarung Keseimbangan. Ini merupakan game pertama yang kelompok saya mainkan. Sebelum game dimulai, kami diperkenalkan dengan kakak tingkat. Ada juga pengenalan departemen BEM FTIf. Cara bermain: Ada 1 gelas berisi batu dan gelas itu tidak boleh jatuh, harus diseimbangkan di atas sarung. Kemudian setiap tim harus memindahkan gelas itu dari garis start sampai finish. Ada teman saya yang terus menyemangati para peserta. Tapi, sayangnya, kelompok saya kalah.

Breaking the Collision. Ini game kedua yang kelompok saya mainkan. Game ini dilakukan di plasa SI. Setiap tim berbaris 1 baris dan matanya ditutupi slayer. Hanya mata orang paling belakang yang tidak ditutupi. Ia harus menuntun barisannya mengelilingi rintangan yang ada (dari kursi dan orang). Caranya dengan menepuk pundak kanan untuk ke arah kanan dan pundak kiri untuk ke arah kiri. Akhirnya kelompok saya menang walaupun kurang kompak.

Folding Carpet. Ini merupakan game yang paling seru. Game ini dilaksanakan di dalam ruang kelas. Ada 1 karpet dan 13 orang harus berdiri di atasnya. Setiap tim harus membalikkan karpet itu tanpa ada anggota dari kelompoknya yang menyentuh lantai. Jika menyentuh, karpet akan dibalikkan menjadi posisi semula. Karena ukuran karpet yang terbatas, akibatnya setiap orang pasti pernah berpelukan dengan yang lain (kecuali mereka yang tidak bermain). Di satu waktu, entah apa sebabnya, anggota kelompok saya yang berdiri di atas karpet jatuh semua, termasuk saya. Game ini seru karena memerlukan strategi untuk membalikkan karpet ditambah dengan tidak boleh menyentuh lantai. Akhirnya kelompok saya menang. Walaupun di dalam ruangan dan ber-AC, semua peserta yang bermain mandi keringat.

Lingkaran Kecil dan Besar. Cara bermain: setiap kelompok membentuk lingkaran kecil dan harus berubah menjadi lingkaran besar dengan cara berpegangan tangan. Entah bagaimana caranya menjadi lingkaran besar, pegangan tangannya tidak boleh terlepas. Game ini lumayan seru. Akhirnya, kelompok saya kalah karena posisi tangan sudah terkunci dari awal.

Tebak Kata. Ini merupakan game terakhir yang kelompok saya mainkan. Game ini dilakukan di TC 103-104. Setiap kelompok berbaris berhadapan dengan kelompok lain. Kemudian, setiap kelompok diberi kertas yang isinya potongan kalimat. Setiap orang dari masing-masing kelompok harus menyebutkan potongan kalimat itu secara bersamaan. Sedangkan kelompok lawan harus mendengar salah satu potongan kalimat dan berdiskusi untuk menyatukan kalimat itu. Kelompok saya kalah karena salah menentukan permulaan kalimat.

Setelah game Tebak Kata, kelompok kami menunggu di tangga yang menghadap ke arah taman SI melihat game memindahkan sarung dalam lingkaran besar yang setiap pesertanya berpegangan tangan. Seharusnya ada 2 games lagi. Namun, kehabisan waktu karena molor.

Akhirnya, sekitar jam 16.00, kami kumpul kembali ke kelas TC 103-104. Sebelum pulang, ada evaluasi untuk peserta dan panitia.

Hari Kedua (Minggu, 28 Februari 2016)

Hari kedua, kami dijadwalkan kumpul jam 6.30 di SI. Namun, gerbang parkiran motor SI baru dibuka sekitar jam 07.00. Lalu, ada pengarahan ke plasa SI. Di sana, kami duduk sesuai kelompok kecil (sebenarnya tidak karena para peserta membaur) dan menandatangani absen kehadiran.

Sekitar jam 07.30 – 09.00 ada sharing kesan-kesan dari peserta dengan kakak OC mengenai hari pertama FTIf Journey. Kemudian, dilanjutkan dengan sharing pengalaman akademik dari kakak tingkat dari TC. Dalam waktu itu, plottingan daerah observasi social responsibility sedang disusun.

Sekitar jam 09.00, ada briefing sebelum melakukan observasi. Kami disuruh berkumpul per kelompok kecil di tempat yang ditentukan (di sekitaran plasa SI). Ada kakak pendamping baru yang menjelaskan tentang plottingan observasi untuk kelompok kami. Daerah yang menjadi tempat observasi kami adalah di antara minimarket Sakinah sampai lapangan futsal Fifa dan harus ada dokumentasi dalam bentuk foto dan video. Kami diberi waktu observasi sampai dengan jam 11.30. Setelah itu, kami harus sudah berada di SI kembali.

Kami berangkat dengan menggunakan 5 motor berboncengan. Orang yang duduk di belakang bertugas mendokumentasi. Setelah melewati daerah plotingan kami, kami berkumpul di depan Fifa untuk mendiskusikan siapa yang hendak kami bantu. Kemudian, kami memutuskan untuk membantu seorang ibu yang berjualan jamu tepat di depan pertigaan perumahan Bumi Marina Emas.

Di sana, kami bertukar cerita dengan ibu tersebut. Selain itu, juga ada yang merekam pembicaraan dan mendokumentasi. Setelah selesai, kami memberikan bantuan sembako kami dan berfoto bersama. Sayangnya, ada anggota kelompok kami yang berhalangan sehingga tidak semua anggota masuk ke dalam foto.

Kami kembali sekitar jam 10.15 ke parkiran motor SI. Karena waktu masih cukup lama, saya bermain ke kos teman saya sampai jam 11.30 lalu kembali ke SI. Kemudian, ada ishoma sampai jam 13.10. Pada waktu itu, kami bersantai dalam ruang kelas yang ber-AC.

Jam 13.10, kami dikumpulkan kembali ke plasa SI. Kemudian kami dibagi per kelompok kecil dengan 1 kelompok kecil lain untuk sesi diskusi (sesi terakhir) di sekitaran plasa SI. Sesi itu mendiskusikan tentang kegiatan observasi social responsibility sebelumnya dengan salah satu kakak pendamping. Di sana, kami mensharingkan kesan dan pengalaman kami. Kami diberitahu bahwa kita seharusnya bersyukur karena kita mungkin tidak perlu bekerja keras untuk bisa kuliah. Sebab, mungkin anak-anak dari mereka yang kami temui tadi tidak bisa kuliah. Selain itu, saya mengetahui dari sesi ini bahwa acara FTIf Journey kali ini berbeda dari tahun-tahun sebelumnya.

Akhirnya, tibalah penghujung acara atau simulasi total (simtot). Kami berkumpul ke bagian taman SI. Di sana kembali ditunjuk 3 komting (1 sebagai komting TC, 1 sebagai komting SI, dan 1 sebagai komting FTIf) karena komting FTIf sebelumnya berhalangan hadir. Lalu, mereka mendapat penjelasan tentang kegiatan terakhir ini dari salah satu OC. Setelah itu, salah satu dari mereka menjelaskan kegiatan terakhir ini ke angkatan FTIf 2015.

Kami harus mencari semua papermob yang telah disembunyikan di lantai 1 SI. Kemudian, kami harus membentuk tulisan ‘FTIf’ dan ‘2015’ dari papermob tersebut di parkiran mobil SI. Cukup mudah untuk mencari semua papermob. Namun, sulit untuk membentuk tulisan tersebut dari papermob. Selain 3 komting tersebut, ada beberapa orang yang berinisiatif mengarahkan angkatan FTIf 2015 untuk membentuk tulisan tersebut.

Panduan yang kurang jelas karena dipandu oleh OC dari atap SI ditambah dengan peserta yang sudah lelah semakin menyulitkan pembentukan tulisan itu. Akhirnya, setelah beberapa lama, kami sukses melakukannya. Dengan selesainya tulisan ‘2015’, kegiatan FTIf Journey ditutup, diakhiri dengan Vivat FTIf!, awan hitam, serta gerimis yang perlahan-lahan mulai lebat.

Sebelum pulang, sekitar jam 16.00, kami kembali ke kelas untuk membawa semua barang bawaan kami. Kemudian, kami dikumpulkan di plasa SI untuk terakhir kalinya. Di sana ada penjelasan mengenai KPP yang harus kami lakukan, yaitu, mengupload foto observasi terbaik ke instagram, menceritakan kembali kegiatan FTIf Journey 2016 selama 2 hari ini dalam bentuk blog atau notes facebook, dan mengikuti serangkaian kegiatan FTIf Festival.

Kesimpulan

Hari pertama: sesi inspiratif dan games.

Hari kedua: social responsibility dan membentuk tulisan ‘FTIf’ dan ‘2015’.

Kegiatan ini seru dan menjadi kesempatan terbaik untuk mengenal dan mengakrabkan diri antara TC dan SI khususnya mahasiswa baru (maba). Namun, sayangnya, kegiatan semacam ini hanya diadakan sekali saja untuk maba.