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