Google Code Jam 2016 - Qualification Round

요즘 회사도 자주 옮겨다니고 여러모로 심란한가운데..

몇년만에 GCJ 를 참가해보았다.. 

이제 마음을 추스리고 다시 문제풀이를 해볼 생각이다..

https://code.google.com/codejam/contest/6254486/dashboard

A. Counting Sheep

문제에서 시키는데로 simulation 했다. 결과가 x10 이전에 항상 나오는 것 같다.

#include <stdio.h>

#include <string.h>

int main()

{

    int tc, cn;

    int i, j, k;

    int n;

    long long temp;

    int check[10];

    scanf("%d", &tc);

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

        scanf("%d", &n);

        if (n == 0) {

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

            continue;

        }

        memset(check, 0, sizeof(check));

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

            temp = (long long)n * i;

            while (temp) {

                check[temp%10] = 1;

                temp /= 10;

            }

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

                if (check[j] == 0)

                    break;

            }

            if (j == 10) {

                break;

            }

        }

        if (i == 10000000)

            printf("error\n");

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

    }

    return 0;

}

B. Revenge of the Pancake

이 문제도 그냥 simulation 하면 되는데, 전략을 잘 짜야 한다.

맨 앞이 '-' 이면 '+' 가 나올때까지 뒤집고,

맨 앞이 '+' 이면 '-' 가 나오는 구간의 맨 끝까지 뒤집는다.

예)

+--+++-+

=> -+++++-+

=> ++++++-+

=> ------++

=> ++++++++

#include <stdio.h>

#include <string.h>

int check(char* str, int len, int* s, int* e)

{

    int i, j;

    int start, end;

    int fl;

    start = end = -1;

    fl = 0;

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

        if (str[i] == '-') {

            start = i;

            end = i;

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

                if (str[j] == '+')

                    break;

                end = j;

            }

            fl = 1;

            break;

        }

    }

    *s = start;

    *e = end;

    return fl;

}

int main()

{

    int tc, cn;

    int i, j, k;

    int len;

    char str[110];

    int s, e;

    int cnt;

    scanf("%d", &tc);

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

        scanf("%s", str);

        len = strlen(str);

        s = e = -1;

        cnt = 0;

        while (check(str, len, &s, &e)) {

            if (s == 0) {

                for (i = s; i <= e; i++) {

                    str[i] = '+';

                }

            }

            else {

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

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

                        str[i] = '-';

                    else

                        str[i] = '+';

                }

            }

            cnt++;

        }

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

    }

    return 0;

}

check 함수는 최초 '-' 가 시작되는 구간의 시작지점과 끝지점을 return 하는 함수이다.

C. Coin Jam 

OTL ㅠ_ㅠ; small input 에 대해서만 풀었다.

단순무식하게 푼다고 하면 N=16 이기 때문에 최대 1억까지의 prime 만 구하면 된다.. -_-;;;

에라토스테네스의체로 소수 구하고, 진수 변환해서 prime 인지 아닌지 구했다.

small input only

#include <stdio.h>

#include <string.h>

char is_prime[100000010];

int prime_cnt;

int prime[6000000];

void sieve()

{

    int i, j;

    memset(is_prime, -1, sizeof(is_prime));

    prime_cnt = 0;

    is_prime[0] = is_prime[1] = 0;

    for (i = 2; i < 100000010; i++) {

        if (is_prime[i]) {

            for (j = 2; i*j < 100000010; j++) {

                is_prime[i*j] = 0;

            }

            prime[prime_cnt] = i;

            prime_cnt++;

        }

    }

}

void change_to(int n, int base, char* str)

{

    int i, j, len;

    char temp[100];

    char ch;

    len = 0;

    while (n > 0) {

        ch = (n % base) + '0';

        if (ch > '9')

            ch += 7;

        temp[len++] = ch;

        n /= base; 

    }

    for (i = 0, j = len-1; i < len; i++, j--) {

        str[i] = temp[j];

    }

    str[i] = 0;

}

long long str_to_num(char* str, int base)

{

    int len;

    int i;

    long long res;

    len = strlen(str);

    res = 0;

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

        res *= (long long)base;

        res += (long long)(str[i] - '0');

    }

    return res;

}

int main()

{

    int tc, cn;

    int n, j;

    int max1, min1;

    int i, b, a;

    long long k;

    char buf[100];

    int div[11];

    int cnt;

    int fl;

    sieve();

    scanf("%d", &tc);

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

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

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

        cnt = 0;

        max1 = (1 << n) - 1;

        min1 = (1 << (n-1)) + 1;

        for (i = min1; i <= max1; i += 2) {

            change_to(i, 2, buf);

            for (b = 2; b <= 10; b++) {

                k = str_to_num(buf, b);

                fl = 0;

                for (a = 0; (long long)prime[a]*prime[a] <= k && a < prime_cnt; a++) {

                    if (k % prime[a] == 0) {

                        div[b] = prime[a];

                        fl = 1;

                        break;

                    }

                }

                if (fl == 0)

                    break;

            }

            if (b == 11) {

                printf("%s", buf);

                for (b = 2; b <= 10; b++) {

                    printf(" %d", div[b]);

                }

                printf("\n");

                cnt++;

                if (cnt == j)

                    break;

            }

        }

    }

    return 0;

}