/*
ID: ****
LANG: C
TASK: dualpal
*/

/*#define __DEBUG__*/
#define TRUE 1
#define FALSE 0
#define MAX 100

#include 

int isDualPalindrome(int num);
int checkPalindrome(int num[], int pos);

int main()
{
	int N;
	int S;
	int i;
	int count = 0;

#ifndef __DEBUG__
	FILE *fin;
	FILE *fout;

	fin = fopen("dualpal.in","r");
	fout = fopen("dualpal.out","w");
	fscanf(fin, "%d", &N);
	fscanf(fin, "%d", &S);
#else
	printf("how many do you want to get palindromes : ");
	scanf("%d", &N);
	printf("what number do you want to palindromes that greater than? : ");
	scanf("%d", &S);
#endif

	for (i = S + 1 ; ; i++)
	{
		if (isDualPalindrome(i) == TRUE)
		{
#ifndef __DEBUG__
			fprintf(fout, "%dn", i);
#else
			printf("%dn", i);
#endif
			count++;
		}
		if (count == N) break;
	}

#ifndef __DEBUG__
	fclose(fin);
	fclose(fout);
#endif

	return 0;
}

int isDualPalindrome(int num)
{
	int i;
	int changedNum[MAX];
	int pos;
	int temp;
	int palCount = 0;
	
	for (i = 2 ; i < = 10 ; i++)
	{
		pos = 0;
		temp = num;

		do
		{
			changedNum[pos++] = temp % i;
		} while(temp = temp / i);

		if (checkPalindrome(changedNum, pos) == TRUE)
		{
			palCount++;
			if (palCount >= 2)
			{
				return TRUE;
			}
		}
	}
	
	return FALSE;
}

int checkPalindrome(int num[], int pos)
{
	int i;

	for (i = 0 ; i < = pos / 2 ; i++)
	{
		if (num[i] != num[pos-i-1])
		{
			return FALSE;
		}
	}

	return TRUE;
}

주어진 수보다 큰 수 중에서 2~10진수로 표현했을때 두번 이상 palindrome(회문) 이 되는 수를 구하는 문제였다. 상당히 어렵게 생각하고 있었는데 실제로 해보니 의외로 쉽게 풀린 문제다.

'Developing' 카테고리의 다른 글

PHP에서 MySQL 다중 연결시 조심할 것  (0) 2008.12.30
USACO Training - Dual Plindromes  (0) 2007.12.15
USACO Training - Milking Cows  (0) 2007.11.24
파이썬 문자열 뒤집기  (0) 2007.11.17
/*
ID: ****
LANG: C
TASK: milk2
*/

/*#define __DEBUG__*/
#define MAX 1000000

#include 

int main()
{
	int N;
	int start, end;
	int **time;
	int count = 0;
	int modified = 0;
	int i,j;
	int milkTime = 0;
	int restTime = 0;
	int temp;

#ifndef __DEBUG__
	FILE *fin;
	FILE *fout;

	fin = fopen("milk2.in","r");
	fout = fopen("milk2.out","w");
	fscanf(fin, "%d", &N);
#else
	printf("input the number of farmers : ");
	scanf("%d", &N);
#endif

	time = (int**)malloc(sizeof(int*)*N);

	for(i=0 ; i < N ; i++)
	{
		time[i] = (int*)malloc(sizeof(int)*2);
#ifndef __DEBUG__
		fscanf(fin, "%d %d", &start, &end);
#else
		printf("input start time and end time.n[start time] [end time]n");
		scanf("%d %d", &start, &end);
#endif
		for (j=0 ; j < count ; j++)
		{
			if (start <= time[j][1] && end >= time[j][1])
			{
				time[j][1] = end;
				modified = 1;
			}
			if (end >= time[j][0] && start < = time[j][0])
			{
				time[j][0] = start;
				modified = 1;
			}
		}

		if (modified == 0)
		{
			time[j][0] = start;
			time[j][1] = end;
			count ++;
		}
		modified = 0;
	}

	for (i=0 ; i < count ; i++)
	{
		for (j=0 ; j < count ; j++)
		{
			if (time[i][0] <= time[j][1] && time[i][1] >= time[j][1])
			{
				time[j][1] = time[i][1];
			}
			if (time[i][1] >= time[j][0] && time[i][0] < = time[j][0])
			{
				time[j][0] = time[i][0];
			}
		}
	}

	for (i=0 ; i < count ; i++)
	{
		temp = time[i][1] - time[i][0];
		if (temp > milkTime)
		{
			milkTime = temp;
		}
	}

	for (i=0 ; i < count ; i++)
	{
		temp = MAX;
		for (j=0 ; j < count ; j++)
		{
			if (time[j][0] > time[i][1] && temp > time[j][0])
			{
				temp = time[j][0];
			}
		}

		if (temp == MAX)
		{
			continue;
		}

		temp = temp - time[i][1];

		if (temp > restTime)
		{
			restTime = temp;
		}
	}

#ifndef __DEBUG__
	fprintf(fout, "%d %dn", milkTime, restTime);
	fclose(fin);
	fclose(fout);
#else
	printf("the longest continuous time of milking : %dnthe longest idle time : %dn", milkTime, restTime);
#endif
	return 0;
}

매번 뻔한 코딩만하다보니 문제해결능력이 많이 떨어졌다는 것을 느낀다. 이번 문제는 여러 젖소가 우유를 짜는 시각이 주어지고, 최소한 한 젖소에서 우유를 짜는 가장 긴 시간과 전혀 우유를 짜지 않는 가장 긴 시간을 구하는 문제였다.

최소한 한 젖소에서 우유를 짜는 가장 긴 시간은 금새 구할 수 있었지만, 우유를 짜지 않는 가장 긴 시간을 구하는 것은 쉽게 나오지 않았다.

'Developing' 카테고리의 다른 글

USACO Training - Dual Plindromes  (0) 2007.12.15
USACO Training - Milking Cows  (0) 2007.11.24
파이썬 문자열 뒤집기  (0) 2007.11.17
이클립스에서 EUC-KR 문서 이용  (0) 2007.11.08

/*
ID: ****
LANG: C
TASK: friday
*/

/*#define __DEBUG__*/

#include <stdio.h>

int main()
{
    int period, last, year, leap, i;
    int day=0; // 0=Mon ... 6=Sun
    int count[7];
    for(i=0 ; i<7 ; i++)
        count[i] = 0;
#ifndef __DEBUG__
    FILE *fin;
    FILE *fout;
   
    fin = fopen("friday.in","r");
    fout = fopen("friday.out","w");
    fscanf(fin,"%d",&period);
#else
    do{
        printf("Enter period(N years) : ");
        scanf("%d",&period);
    }while(period<=0 || period>400);
#endif

    last = 1900+period;

    for(year=1900 ; year<last ; year++)
    {
        if(year%100 == 0)
        {
            if(year%400 == 0)
                leap = 1;
            else
                leap = 0;
        }
        else if(year%4 == 0)
            leap = 1;
        else
            leap = 0;

        count[day]++;
        day = (day+3)%7;
        count[day]++;
        day = (day+leap)%7;
        count[day]++;
        day = (day+3)%7;
        count[day]++;
        day = (day+2)%7;
        count[day]++;
        day = (day+3)%7;
        count[day]++;
        day = (day+2)%7;
        count[day]++;
        day = (day+3)%7;
        count[day]++;
        day = (day+3)%7;
        count[day]++;
        day = (day+2)%7;
        count[day]++;
        day = (day+3)%7;
        count[day]++;
        day = (day+2)%7;
        count[day]++;
        day = (day+3)%7;
    }

#ifndef __DEBUG__
    for(i=0 ; i<6 ; i++)
        fprintf(fout,"%d ",count[i]);
    fprintf(fout,"%dn",count[6]);
    fclose(fin);
    fclose(fout);
#else
    for(i=0 ; i<7 ; i++)
        printf("%d ",count[i]);
#endif
    return 0;
}

1900년부터 시작해서 주어진 몇년의 기간동안 날짜가 13일이 되는 요일의 수를 구하는 프로그램인데, 조금 생각하고 코딩을 했더니 결과가 너무 지저분해졌다. 게다가 1월부터 12월까지 달마다 요일을 구하는 부분에서 날짜를 미리 계산해서 넣는 만행을...;

저부분을 제대로 하자면, 각 달의 날짜수를 배열같은 곳에 저장해둔 다음, 윤년을 판단해서 윤년일 경우 2월 계산부분에 하루를 더해주고, 반복문으로 해결을 볼수 있을 듯한데, 일단 이걸로 이번문제는 통과..;;; 더 고치기가 귀찮다.

'Developing' 카테고리의 다른 글

The Java Programming Language - 1일차  (0) 2007.02.03
USACO Training - Friday the Thirteenth  (0) 2006.09.12
PERL에서의 웹 프로그래밍  (0) 2006.06.03
USACO Training - What Time Is It?  (0) 2006.05.15

/*
ID: ****
LANG: C
TASK: clock
*/

#define __DEBUG__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* itoc(int num);

int main()
{
    char* temp;
    char time[6];
    int hour;
    int min;
    char out[100];
#ifndef __DEBUG__
    FILE *fin;
    FILE *fout;
   
    fin = fopen("clock.in","r");
    fout = fopen("clock.out","w");
    fscanf(fin,"%s",time);
#else
    printf("Input time : ");
    scanf("%s",time);
#endif
   
    temp = strtok(time,":");
    hour = atoi(temp);
    temp = strtok(NULL,":");
    min = atoi(temp);
   
    switch(min)
    {
    case 0:
        sprintf(out,"%s o'clock",itoc(hour));
        break;
    case 15:
        sprintf(out,"Quarter past %s",itoc(hour));
        break;
    case 45:
        sprintf(out,"Quarter to %s",itoc(hour%12+1));
        break;
    default:
        if(min>45)
            sprintf(out,"%s to %s",itoc(60-min),itoc(hour%12+1));
        else
            sprintf(out,"%s %s",itoc(hour),itoc(min));
    }
    out[0]=toupper(out[0]);
#ifndef __DEBUG__
    fprintf(fout,"%sn",out);
    fclose(fin);
    fclose(fout);
#else
    printf("%sn",out);
#endif
    return 0;
}

char* itoc(int num)
{
    char* retval;
    retval = (char*)malloc(sizeof(char)*20);
   
    if(num<20)
    {
        switch(num)
        {
        case 1:    return "one";
        case 2:    return "two";
        case 3:    return "three";
        case 4:    return "four";
        case 5:    return "five";
        case 6:    return "six";
        case 7:    return "seven";
        case 8:    return "eight";
        case 9:    return "nine";
        case 10: return "ten";
        case 11: return "eleven";
        case 12: return "twelve";
        case 13: return "thirteen";
        case 14: return "fourteen";
        case 15: return "fifteen";
        case 16: return "sixteen";
        case 17: return "seventeen";
        case 18: return "eighteen";
        case 19: return "nineteen";
        default: return "";
        }
    }
    else
    {
        switch(num/10)
        {
        case 2:
            sprintf(retval,"twenty");
            break;
        case 3:
            sprintf(retval,"thirty");
            break;
        case 4:
            sprintf(retval,"forty");
            break;
        case 5:
            sprintf(retval,"fifty");
            break;
        }

        switch(num%10)
        {
        case 0:
            break;
        case 1:
            strcat(retval,"-one");
            break;
        case 2:
            strcat(retval,"-two");
            break;
        case 3:
            strcat(retval,"-three");
            break;
        case 4:
            strcat(retval,"-four");
            break;
        case 5:
            strcat(retval,"-five");
            break;
        case 6:
            strcat(retval,"-six");
            break;
        case 7:
            strcat(retval,"-seven");
            break;
        case 8:
            strcat(retval,"-eight");
            break;
        case 9:
            strcat(retval,"-nine");
            break;
        }
    }
    return retval;
}

상당히 간단한 문제였다.

'Developing' 카테고리의 다른 글

PERL에서의 웹 프로그래밍  (0) 2006.06.03
USACO Training - What Time Is It?  (0) 2006.05.15
USACO Training - Barn Repair  (0) 2006.05.09
USACO Training - Mixing Milk  (0) 2006.05.03

/*
ID: ****
LANG: C
TASK: barn1
*/

/*#define __DEBUG__*/
#define MAXSTALL1 200+1

#include <stdio.h>

int main()
{
    int max, stal, cow;
    int i, temp;
    int before = 0;
    int total = 0;
    int ival[MAXSTALL1];
    int status[MAXSTALL1];
   
    for(i=0 ; i<MAXSTALL1 ; i++)
    {
        ival[i] = 0;
        status[i] = 0;
    }
   
#ifndef __DEBUG__
    FILE *fin;
    FILE *fout;
   
    fin = fopen("barn1.in","r");
    fout = fopen("barn1.out","w");
    fscanf(fin,"%d %d %d",&max,&stal,&cow);
#else
    printf("Input max & stall & cow : ");
    scanf("%d %d %d",&max,&stal,&cow);
#endif
   
    for(i=0 ; i<cow ; i++)
    {
#ifndef __DEBUG__
        fscanf(fin,"%d",&temp);
#else
        scanf("%d",&temp);
#endif
        status[temp] = 1;
    }
   
    for(i=0 ; i<=stal ; i++)
    {
        if(status[i] == 1)
        {
            if(before != 0)
                ival[i-before-1]++;
            before = i;
        }
    }
   
    max--;
    for(i=stal ; i>0 ; i--)
    {
        if(max > 0)
        {
            if(ival[i] >= max)
            {
                total += (ival[i] - max)*i;
                max = 0;
            }
            else
                max -= ival[i];
        }
        else
            total += ival[i]*i;
    }
#ifndef __DEBUG__
    fprintf(fout,"%dn",total+cow);
    fclose(fin);
    fclose(fout);
#else
    printf("%dn",total+cow);
#endif
    return 0;
}

저번 문제와 비슷한 접근 방법으로 문제를 해결했다.

주어진 갯수의 널판지로 최소한의 길이의 널판지를 이용해서 헛간을 고치겠다는 것이 문제였다. 비어있는 칸은 반드시 고칠 필요가 없고, 소가 있는 칸만 고치면 되므로, 소가 있는 칸 사이의 넓이가 가장 넓은 곳 부터 비우는 방식으로 널판지 갯수를 맞췄다.

소가 있는 칸 번호가 반드시 순서대로 들어오는 것은 아니므로 연산이 더 필요했다.

'Developing' 카테고리의 다른 글

PERL에서의 웹 프로그래밍  (0) 2006.06.03
USACO Training - What Time Is It?  (0) 2006.05.15
USACO Training - Barn Repair  (0) 2006.05.09
USACO Training - Mixing Milk  (0) 2006.05.03

구입할 우유의 양과 구입할 수 있는 목장의 수를 입력 받은 뒤에, 각 목장에서 판매할 수 있는 우유의 양과 가격을 입력받는다.

단위당 우유의 가격이 0~1000으로 한정되어 있는 것에 착안하여 1001짜리 배열을 생성한 뒤에 0으로 초기화 하고, 각 가격별로 구입할 수 있는 양을 더해서 0부터 시작해서 1000까지 구입할 양만큼만 값을 계산하도록 했다.

'Developing' 카테고리의 다른 글

PERL에서의 웹 프로그래밍  (0) 2006.06.03
USACO Training - What Time Is It?  (0) 2006.05.15
USACO Training - Barn Repair  (0) 2006.05.09
USACO Training - Mixing Milk  (0) 2006.05.03

+ Recent posts