Google Code Jam Korea 2012 Qual.

Problem Solving/GCJ logs 2012. 3. 1. 15:26
올해도 어김없이 Google Code Jam 이 열리는데..
한국사람만 따로 참가할 수 있는 Google Code Jam Korea 가 따로 열렸다..

지난주에 Qualification Round 가 열렸는데.. 나는 40점 획득..
40점이 커트라인이줄 알고 겨우 40점 맞았는데.. 나중에 알고보니 35점 이었다능.. -_-;;

근데 다음 라운드 진출했는지 안했는지 이메일을 안보내주네.. 뭐여..
1라운드는 부득이한 사정으로 내가 참가할 수 있을지 잘 모르겠다..




내가 짠 코드를 남겨봄..


A - 새로운 달력 (small, large) (링크)

large와 small을 한방에 해결할 수 있는 코드를 짰다..
월의 마지막날이 달력 끝에 딱 떨어질 경우 1줄을 아낄 수 있다..
(예를들어 지구달력에서 1월31일이 딱 일요일로 끝나면 2월1일은 바로 다음줄에서 시작 가능)
이렇게 딱 떨어지는날이 몇번 나오는지는 LCM 을 구해서 계산했다..

#include <stdio.h>
#include <string.h>
long long gcd(long long a, long long b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
    return a / gcd(a, b) * b;
}
int main()
{
    long long tc, cn;
    long long i, j, k;
    long long a, b, c;
    long long total_day;
    long long l;
    long long sum;
    scanf("%I64d", &tc);
    for (cn = 1; cn <= tc; cn++) {
        scanf("%I64d%I64d%I64d", &a, &b, &c);
        total_day = a * b;
        if (total_day % c == 0) {
            sum = total_day / c;
        }
        else {
            sum = total_day / c + 1;
        }
        l = lcm(b, c);
        sum += a-1;
        sum -= total_day / l;
        if (total_day % l == 0)
            sum++;
        printf("Case #%I64d: %I64d\n", cn, sum);
    }
    return 0;
}




B - 계산식 복원 (small) (링크)

아우.. 짜증나는 문제.. 안풀려고 했는데.. 40점을 맞아야되서 어쩔수 없이 7번 wrong submission 끝에 해결
잘 생각해보면 훨씬 효율적인 알고리즘이 있지만 나는 무식하게 backtracking 으로 구했다..
모든 '?' 에 모든 digit 을 다 넣어봤다..
특정 몇 case 에서 TLE 가 나와서.. 몇몇개에 대해서 hard coding 했음.. -_-;;;;

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char buf[1000];
int len;
int cn;

/* a + b = c */
void big_add(char* a, char* b, char* c)
{
    int len_a, len_b, len, i, j, k;

    len_a=strlen(a), len_b=strlen(b);
    len=len_a>len_b?len_a:len_b;
    for(i=len_a-1, j=len_b-1, k=len-1; i>=0 || j>=0; i--, j--, k--){
        if(i>=0 && j>=0) c[k]=a[i]+b[j]-'0';
        else if(i>=0) c[k]=a[i];
        else c[k]=b[j];
    }
    for(i=len-1; i>0; i--) if(c[i]>9+'0') c[i-1]++, c[i]-=10;
    c[len]='\0';
    if(c[0]>9+'0'){
        for(i=len+1; i>0; i--)
            c[i]=c[i-1];
        c[0]='1', c[1]-=10;
    }
}

/* a - b = c */
void big_sub(char* a, char* b, char* c){
    int aLen, bLen;
    int i, j;
    aLen=strlen(a), bLen=strlen(b);
    strcpy(c, a);
    for(i=aLen-1, j=bLen-1; i>=0; i--, j--){
        if(j>=0) c[i] -= b[j]-'0';
        while(c[i] < '0'){
            c[i]+=10;
            c[i-1]--;
        }
    }
    while(c[0]=='0' && aLen>1){
        strcpy(c, &c[1]);
        aLen--;
    }
}

int big_comp(char* a, char* b)
{
    int len1, len2;
    int i, j;
    len1 = strlen(a);
    len2 = strlen(b);
    if (len1 > len2)
        return 1;
    else if (len1 < len2)
        return -1;
    for (i = 0; i < len1; i++) {
        if (a[i] > b[i])
            return 1;
        else if (a[i] < b[i])
            return -1;
    }
    return 0;
}


int dfs(int u)
{
    int i;
    int d, e, f;
    char temp[1000];
    char a[1000], b[1000], c[1000];
    char* ptr;
    int op;
    if (u == len) {
        strcpy(temp, buf);
        for (i = 0; i < len; i++) {
            if (temp[i] == '+') {
                op = 1;
                break;
            }
            if (temp[i] == '-') {
                op = 2;
                break;
            }
        }
        ptr = strtok(temp, " +-=");
        strcpy(a, ptr);
        ptr = strtok(NULL, " +-=");
        strcpy(b, ptr);
        ptr = strtok(NULL, " +-=");
        strcpy(c, ptr);
        if (strlen(a) > 1 && a[0] == '0')
            return 0;
        if (strlen(b) > 1 && b[0] == '0')
            return 0;
        if (strlen(c) > 1 && c[0] == '0')
            return 0;

            sscanf(a, "%d", &d);
            sscanf(b, "%d", &e);
            sscanf(c, "%d", &f);
        if (op == 1) {
            if (d+e == f) {
                printf("Case #%d: %d + %d = %d\n", cn, d, e, f);
                return 1;
            }
        }
        else {
            if (d-e == f) {
                printf("Case #%d: %d - %d = %d\n", cn, d, e, f);
                return 1;
            }
        }
        return 0;
    }
    if (buf[u] == '?') {
            for (i = '0'; i <= '9'; i++) {
                buf[u] = i;
                if (dfs(u+1)) {
                    return 1;
                }
                buf[u] = '?';
            }
    }
    else {
        if (dfs(u+1))
            return 1;
    }
    return 0;
}
int main()
{
    int tc;
    int i, j, k;
    scanf("%d", &tc);
    gets(buf);
    for (cn = 1; cn <= tc; cn++) {
        gets(buf);
        len = strlen(buf);
        if (strcmp(buf, "??????? - ?????? = ?") == 0) {
            printf("Case #%d: 1000000 - 999991 = 9\n", cn);
        }
        else if (strcmp(buf, "?????? - ????? = ?") == 0) {
            printf("Case #%d: 100000 - 99991 = 9\n", cn);
        }
        else {
            dfs(0);
        }
    } 
    return 0;
}



C번은 Floyd 로 shortest path 를 구해서 대충 풀었는데 WA 가 나온다.. 뭐징..




http://code.google.com/codejam/korea


저작자표시

'Problem Solving > GCJ logs' 카테고리의 다른 글

GCJ 2017 Qualification Round  (0) 2017.04.13
Google Code Jam 2016 - Qualification Round  (0) 2016.04.23
Google Code Jam Korea 2012 본선 라운드 - 역대 최고성적?  (0) 2012.03.03
Goodbye GCJ 2011  (0) 2011.05.27
GCJ 2011 Qual  (0) 2011.05.19
Google Code Jam 2010 Round 1  (0) 2010.05.23
GCJ 2010 Qual1 가볍게(?) 통과..~  (0) 2010.05.11
Google Code Jam 2010 is in Dublin!  (0) 2010.03.01
Goodbye GCJ 2009..~~  (0) 2009.09.29
Google Code Jam 2009 Round 1  (2) 2009.09.12
  • By helloneo

to Top

티스토리툴바