GCJ 2017 Qualification Round

올해도 역시 Qual 라운드만 참가했다~!! 25점만 넘기는걸 목표로 했는데..

어쩌다보니 50점을 얻어서 5790등을 기록했다 -_-;;;

문제링크: https://code.google.com/codejam/contest/3264486/dashboard

A. Oversized Pancake Flipper (small, large)

small input 을 보니 모든 임의의 위치에다 다 뒤집어보면 최대 2^10 개의 상태공간밖에 안나오기때문에

backtracking 으로 해볼까 하다가..

large input 까지 고려해서 그냥 greedy 로 앞에서부터 - 가 나오면 뒤집는 방법으로 했다..

small 이 pass 하길래 그냥 large 도 submit 했는데.. 왜 greedy 가 맞는 solution 인지 모르겠움;;

#include <stdio.h>

#include <string.h>

int main()

{

    int tc, cn;

    int i, j, k;

    int len, cnt;

    char buf[1010];

    scanf("%d", &tc);

    for (cn = 1; cn <= tc; cn++) {

        scanf("%s%d", buf, &k);

        len = strlen(buf);

        cnt = 0;

        for (i = 0; i < len ;i++) {

            if (buf[i] == '+')

                continue;

            if (i+k-1 >= len)

                break;

            for (j = 0; j < k; j++) {

                buf[i+j] = (buf[i+j] == '-') ? '+' : '-';

            }

            cnt++;

        }

        for (i = 0; i < len; i++) {

            if (buf[i] == '-')

                break;

        }

        if (i == len)

            printf("Case #%d: %d\n", cn, cnt);

        else

            printf("Case #%d: IMPOSSIBLE\n", cn);

    }

    return 0;

}

B. Tidy Numbers (small)

그냥 1씩 빼가면서 숫자가 정렬될때까지 loop 를 돌았다..

#include <stdio.h>

#include <string.h>

int check(int n)

{

    char buf[100];

    int len;

    int i;

    sprintf(buf, "%d", n);

    len = strlen(buf);

    for (i = 1; i < len ;i++) {

        if (buf[i] < buf[i-1])

            break;

    }

    if (i == len)

        return 1;

    return 0;

}

int main()

{

    int tc, cn;

    int n, i;

    scanf("%d", &tc);

    for (cn = 1; cn <= tc; cn++) {

        scanf("%d", &n);

        for (i= n; i >= 1; i--) {

            if (check(i))

                break;

        }

        printf("Case #%d: %d\n", cn, i);

    }

    return 0;

}

B. Tidy Numbers (large)

1씩 빼면서 확인하면 세월아 네월아이고..

잘 생각해보면 앞에서부터 숫자를 비교하다가..

숫자가 뒤집히는 경우가 나오면 현재 숫자를 1 빼고, 그 뒤부터는 모두 9로 바꾸면 된다..

#include <stdio.h>

#include <string.h>

int main()

{

    int tc, cn;

    int i, j, k;

    char buf[100];

    int len;

    int carry;

    scanf("%d", &tc);

    for (cn = 1; cn <= tc; cn++) {

        scanf("%s", buf);

        len = strlen(buf);

        carry = 0;

        for (i = 1; i < len; i++) {

            if (buf[i] > buf[i-1])

                continue;

            j = i;

            while (j < len && buf[j-1] == buf[j]) {

                j++;

            }

            if (j == len)

                continue;

            if (buf[j] < buf[j-1]) {

                buf[i-1]--;

                for (j = i; j < len; j++)

                    buf[j] = '9';

                break;

            }

        }

        i = 0;

        if (buf[0] == '0')

            i = 1;

        printf("Case #%d: %s\n", cn, buf+i);

    }

    return 0;

}

C. Bathroom Stalls (small-1)

음.. 문제출제자의 고충은 이해하겠다만.. 문제 description 이.. 좀 지저분한 화장실 문제라니 -_-

매번 들어오는 순서대로 simulation 했다.. 가장 사이가 넓은공간 중간에 끼워넣고 position 을 기록했다.

하지만 매번 position 을 sort 해야하는 부담이 있다.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define min(x, y) ((x) > (y) ? (y) : (x))

#define max(x, y) ((x) > (y) ? (x) : (y))

int num[1000010];

int cnt;

int comp(const void* x, const void* y)

{

    int* a = (int*)x;

    int* b = (int*)y;

    return *a - *b;

}

int main()

{

    int tc, cn;

    int i, j;

    int n, k;

    int maxlen, pos;

    int ls, rs;

    scanf("%d", &tc);

    for (cn = 1; cn <= tc; cn++) {

        scanf("%d%d", &n, &k);

        cnt = 2;

        num[0] = 0;

        num[1] = n+1;

        while (k--) {

            maxlen = 0;

            for (i = 1; i < cnt; i++) {

                if (num[i]-num[i-1] > maxlen) {

                    maxlen = num[i]-num[i-1];

                    pos = num[i-1]+(num[i]-num[i-1])/2;

                    ls = pos-num[i-1];

                    rs = num[i]-pos;

                }

            }

            num[cnt++] = pos;

            qsort(num, cnt, sizeof(int), comp);

        }

        printf("Case #%d: %d %d\n", cn, max(ls,rs)-1, min(ls,rs)-1);

    }

    return 0;

}

C. Bathroom Stalls (small-2)

잘 생각해보면 position 을 계속 저장하면서 매번 segment 길이를 구할 필요 없이,

segment 길이를 저장해두면 된다..

매번 수행마다 가장큰 segment 를 찾아서 제거하고 길이를 반으로 나눈 두개의 segment 를 다시 넣어야하므로

max heap 같은 자료구조가 필요하다.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

struct comp {

    bool operator() (const int& a, const int&b)

    {

        return a > b;

    }

};

int main()

{

    int tc, cn;

    int n, k;

    int i, j;

    int maxlen, ls, rs;

    scanf("%d", &tc);

    for (cn = 1; cn <= tc; cn++) {

        multiset<int, comp> ss;

        multiset<int, comp>::iterator it;

        scanf("%d%d", &n, &k);

        ss.insert(n+1);

        while (k--) {

            it = ss.begin();

            maxlen = *it;

            ss.erase(it);

            ls = maxlen/2;

            rs = maxlen-maxlen/2;

            ss.insert(ls);

            ss.insert(rs);

        }

        printf("Case #%d: %d %d\n", cn, max(ls,rs)-1, min(ls,rs)-1);

    }

    return 0;

}