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

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

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

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