/*
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

+ Recent posts