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