'ACM'에 해당되는 글 20건
- 2009.06.08 :: [Accept] 10018 Reverse and Add
- 2009.06.03 :: [10018] Reverse and Add
- 2009.06.02 :: [Time Limit] Carmichael Numbers
- 2009.06.02 :: [Accept] 10006 Carmichael Numbers
- 2009.06.02 :: [Accept] 10110 Light, more light
- 2009.06.02 :: [Accept] 850 Crypt Kicker II
- 2009.06.02 :: [Accept] 10132 File Fragmentation
- 2009.06.02 :: [Accept] 10099 - The Tourist Guide
- 2009.06.02 :: [Accept] 10099 - The Tourist Guide
- 2009.06.02 :: [Time Limit] 10099 - The Tourist Guide
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX_SIZE 20 #define MAX_CNT 1000 int isPalindrome(unsigned long long palindrome); int palindromeFunc(unsigned long long palindrome); unsigned long long g_palindromeNum; int g_repeatCnt; int main(void) { int testCase, returnVal; unsigned long long num; scanf("%d", &testCase); while(testCase) { scanf("%llu", &num); returnVal = palindromeFunc(num); printf("%d %llu\n", g_repeatCnt, g_palindromeNum); testCase--; } return 0; } int palindromeFunc(unsigned long long palindrome) { char numStr[MAX_SIZE], reverseNumStr[MAX_SIZE]; int palindromeLen, i, j=0, returnVal, count=1; unsigned long long reversePalindrome; while(count++) { if(count==MAX_CNT) return 0; returnVal = isPalindrome(palindrome); if(returnVal) { g_repeatCnt = count-2; g_palindromeNum = palindrome; return 1; } sprintf(numStr, "%llu", palindrome); palindromeLen = strlen(numStr); // Reverse for(i=palindromeLen-1, j=0; i>=0; i--){ reverseNumStr[j++] = numStr[i]; } reverseNumStr[j] = '\0'; // Add reversePalindrome = (unsigned long long)(atoll(reverseNumStr)); palindrome += reversePalindrome; } return 0; } int isPalindrome(unsigned long long palindrome) { char numStr[MAX_SIZE]; int palindromeLen, i, j; snprintf(numStr, MAX_SIZE, "%llu", palindrome); palindromeLen = strlen(numStr); // Check as if Reverse for(i=0, j=palindromeLen-1; i!=palindromeLen/2; i++, j--) { if(numStr[i]!=numStr[j]) return 0; } return 1; } |
'ACM' 카테고리의 다른 글
[10018] Reverse and Add (0) | 2009.06.03 |
---|---|
[Time Limit] Carmichael Numbers (0) | 2009.06.02 |
[Accept] 10006 Carmichael Numbers (0) | 2009.06.02 |
[Accept] 10110 Light, more light (0) | 2009.06.02 |
[Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
Reverse and Add |
The Problem
The "reverse and add" method is simple: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure.For example:
195 Initial number
591
-----
786
687
-----
1473
3741
-----
5214
4125
-----
9339 Resulting palindrome
In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.
Task :
You must write a program that give the resulting palindrome and the number of iterations (additions) to compute the palindrome.
You might assume that all tests data on this problem:
- will have an answer ,
- will be computable with less than 1000 iterations (additions),
- will yield a palindrome that is not greater than 4,294,967,295.
The Input
The first line will have a number N with the number of test cases, the next N lines will have a number P to compute its palindrome.The Output
For each of the N tests you will have to write a line with the following data : minimum number of iterations (additions) to get to the palindrome and the resulting palindrome itself separated by one space.Sample Input
3 195 265 750
Sample Output
4 93395 45254
3 6666
'ACM' 카테고리의 다른 글
[Accept] 10018 Reverse and Add (0) | 2009.06.08 |
---|---|
[Time Limit] Carmichael Numbers (0) | 2009.06.02 |
[Accept] 10006 Carmichael Numbers (0) | 2009.06.02 |
[Accept] 10110 Light, more light (0) | 2009.06.02 |
[Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
There are two kinds of ways that I solve.
But both are not accepted from Judge Server because of Time Limit.
----------------------------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_NUM 65001
#define MIN_NUM 2
int carmichaelTable[MAX_NUM];
void precalculate(void);
int isCarMichaelFuc(int number);
unsigned long long myPow(int first, int second);
int main(void)
{
int i, inputNumber, isCarmichael;
long long result;
memset(carmichaelTable, 0, sizeof(carmichaelTable));
precalculate();
while(scanf("%d", &inputNumber) && inputNumber!=0)
{
if( !carmichaelTable[inputNumber] )
{
printf("%d is normal.\n", inputNumber);
}
else
{
printf("The number %d is a Carmichael number.\n", inputNumber);
}
}
return 0;
}
void precalculate(void)
{
int i, isCarmichael;
for(i=MIN_NUM; i<MAX_NUM; i++)
{
isCarmichael = 1;
isCarmichael = isCarMichaelFuc(i);
//printf("%d isCarmichael = %d\n", j, isCarmichael);
if( isCarmichael ) {
carmichaelTable[i] = 1;
//printf("%d is %d\n", i, carmichaelTable[i]);
}
}
}
int isCarMichaelFuc(int number)
{
int i, isCarmichael=1;
unsigned long long result;
for(i=MIN_NUM; i<number; i++)
{
result = myPow(i, number);
//printf("%d %d = %d\n", i, number, result);
if( result != i) {
isCarmichael = 0;
break;
}
}
return isCarmichael;
}
unsigned long long myPow(int first, int second)
{
int i;
unsigned long long result = first;
for(i=1; i<second; i++)
{
result *= first;
result %= second;
}
//printf("result = %llu\n", result);
return result;
}
----------------------------------------------------------------------------------------------
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_NUM 65001
#define MIN_NUM 2
int isCarMichaelFuc(int number);
unsigned long long myPow(int first, int second);
int main(void)
{
int i, inputNumber, isPrime, isCarmichael;
long long result;
while(scanf("%d", &inputNumber) && inputNumber!=0)
{
isPrime = 1;
for(i=MIN_NUM; i<inputNumber; i++)
{
if( inputNumber%i == 0 )
{
isPrime = 0;
break;
}
}
if( !isPrime )
{
isCarmichael = isCarMichaelFuc(inputNumber);
if( !isCarmichael )
{
printf("%d is normal.\n", inputNumber);
}
else
{
printf("The number %d is a Carmichael number.\n", inputNumber);
}
}
else
printf("%d is normal.\n", inputNumber);
}
return 0;
}
int isCarMichaelFuc(int number)
{
int i, isCarmichael=1;
unsigned long long result;
for(i=MIN_NUM; i<number; i++)
{
result = myPow(i, number);
if( result != i) {
isCarmichael = 0;
break;
}
}
return isCarmichael;
}
unsigned long long myPow(int first, int second)
{
int i;
unsigned long long result = first;
for(i=1; i<second; i++)
{
result *= first;
result %= second;
}
return result;
}
'ACM' 카테고리의 다른 글
[Accept] 10018 Reverse and Add (0) | 2009.06.08 |
---|---|
[10018] Reverse and Add (0) | 2009.06.03 |
[Accept] 10006 Carmichael Numbers (0) | 2009.06.02 |
[Accept] 10110 Light, more light (0) | 2009.06.02 |
[Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
But I don't like my code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <stdio.h> #include <string.h> int main(void) { int i, inputNumber, isCarmichael; long long result; int table[15]={561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973}; while(scanf("%d", &inputNumber) && inputNumber!=0) { isCarmichael = 0; for(i=0; i<15; i++) { if( table[i] == inputNumber ) { isCarmichael = 1; } } if( isCarmichael ) printf("The number %d is a Carmichael number.\n", inputNumber); else printf("%d is normal.\n", inputNumber); } return 0; } |
'ACM' 카테고리의 다른 글
[10018] Reverse and Add (0) | 2009.06.03 |
---|---|
[Time Limit] Carmichael Numbers (0) | 2009.06.02 |
[Accept] 10110 Light, more light (0) | 2009.06.02 |
[Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
[Accept] 10132 File Fragmentation (0) | 2009.06.02 |
----------------------------------------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <stdio.h> #include <math.h> int main(void) { unsigned long number, i, light=OFF; unsigned long maxNum = (unsigned long)(pow((double)2,(double)32)-1); while( scanf("%u", &number) && number ) { if( number > maxNum ){ //printf("!!! %u\n", number); return 0; } light = (unsigned long)sqrt(number); if( light*light == number ) printf("yes\n"); else printf("no\n"); light = OFF; } return 0; } |
'ACM' 카테고리의 다른 글
[Time Limit] Carmichael Numbers (0) | 2009.06.02 |
---|---|
[Accept] 10006 Carmichael Numbers (0) | 2009.06.02 |
[Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
[Accept] 10132 File Fragmentation (0) | 2009.06.02 |
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
I got accept from Judge Server.
----------------------------------------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
#include <stdio.h> #include <string.h> #define MAX_CHAR 85 #define MAX_LINE 101 #define PLAIN_TEXT 44 #define ALPHABET 26 char replaceTable[ALPHABET]; char plainText[PLAIN_TEXT] = "the quick brown fox jumps over the lazy dog"; int makeReplaceTable(char inputText[PLAIN_TEXT]); void changeInputLine(char inputText[]); void initTable(void); int main(void) { int caseNum, lineNum=0, i=0, success=0, size=0; char inputLine[MAX_LINE][MAX_CHAR]; scanf("%d\n", &caseNum); do { lineNum=0; success=0; caseNum--; while( gets(inputLine[lineNum]) && strlen(inputLine[lineNum]) ) { lineNum++; } if( lineNum >= MAX_LINE ) { lineNum = MAX_LINE-1; } for(i=0; i<lineNum; i++) { if( strlen(inputLine[i]) == strlen(plainText) ) { if( makeReplaceTable(inputLine[i]) ) { success = 1; break; } } } if( !success ) { printf("%s\n", "No solution."); } else { for(i=0; i<lineNum; i++) { changeInputLine(inputLine[i]); printf("%s\n", inputLine[i]); } } if( caseNum != 0 ) printf("\n"); } while(caseNum>0); return 0; } int makeReplaceTable(char inputText[PLAIN_TEXT]) { int i, c; initTable(); for(i=0; i<PLAIN_TEXT; i++) { if( inputText[i] >= 'a' && inputText[i] <= 'z' ) { c = inputText[i]-'a'; if( replaceTable[c] == '\0' ) { replaceTable[c] = plainText[i]; } else { if ( replaceTable[c] != plainText[i] ) { return 0; } } } } for(i=0; i<ALPHABET; i++) { if( replaceTable[i] < 'a' || replaceTable[i] > 'z' ) { return 0; } } return 1; } void changeInputLine(char inputText[]) { int index, i; int size = strlen(inputText); for(i=0; i<size; i++) { if( inputText[i] != ' ' ) { if( inputText[i] >= 'a' && inputText[i] <= 'z' ) { index = inputText[i]-'a'; inputText[i] = replaceTable[index]; } } } } void initTable(void) { int i; for(i=0; i<ALPHABET; i++) { replaceTable[i] = '\0'; } } |
'ACM' 카테고리의 다른 글
[Accept] 10006 Carmichael Numbers (0) | 2009.06.02 |
---|---|
[Accept] 10110 Light, more light (0) | 2009.06.02 |
[Accept] 10132 File Fragmentation (0) | 2009.06.02 |
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
----------------------------------------------------------------------------------------------
#include <stdio.h> #include <string.h> #define FILENUM 144 #define FILEFRAGMENT 2 #define FILESIZE 256 #define FALSE 0 #define TRUE 1 char* getOriginalFile(int inputNum, int originalFileLen, int originalFileOneNum, int fileIndex[4]); void findPair(int inputNum, int originalFileLen, int originalFileOneNum, int fileIndex[4]); char fileInfo[FILENUM*FILEFRAGMENT][FILESIZE]; int fragmentLen[FILENUM*FILEFRAGMENT], fragmentOneNum[FILENUM*FILEFRAGMENT]; int main(void) { char* originalFile; int caseNum, inputNum, i, j, originalFileLen, originalFileOneNum, count; int firstLen, secondLen, fileIndex[4]; scanf("%d", &caseNum); if(caseNum>FILENUM-1) return 0; getchar(); getchar(); do{ // initialize originalFileLen=0; originalFileOneNum=0; memset(fileInfo, 0x00, sizeof(fileInfo)); memset(fragmentLen, 0x00, sizeof(fragmentLen)); memset(fragmentOneNum, 0x00, sizeof(fragmentOneNum)); memset(fileIndex, 0x00, sizeof(fileIndex)); for(i=0; i<FILENUM*FILEFRAGMENT; i++) { fgets(fileInfo[i], 255, stdin); // size check fragmentLen[i]=strlen(fileInfo[i])-1; fileInfo[i][fragmentLen[i]] = '\0'; if(fragmentLen[i]>=FILESIZE-1){ printf("Your input size is more than 256\n"); return 0; } if(!fragmentLen[i]) break; // 1의 개수를 구함 count=0; for(j=0; j<fragmentLen[i]; j++){ if(fileInfo[i][j]=='1') count++; } fragmentOneNum[i] = count; } inputNum = i; // 원래 파일 사이즈(originalFileLen)와 1의 개수(originalFileOneNum)을 구함) for(i=0; i<inputNum; i++) { originalFileLen += fragmentLen[i]; originalFileOneNum += fragmentOneNum[i]; } originalFileLen = originalFileLen * 2 / inputNum; originalFileOneNum = originalFileOneNum * 2 / inputNum; if(originalFileLen >= FILESIZE-1) return 0; // file size check findPair(inputNum, originalFileLen, originalFileOneNum, fileIndex); originalFile = getOriginalFile(inputNum, originalFileLen, originalFileOneNum, fileIndex); if(!originalFile) break; // file null check // result caseNum--; if(!caseNum) printf("%s\n", originalFile); // 마지막 case일때 else printf("%s\n\n", originalFile); // 마지막 case가 아니면 한 줄 더 띄기 } while(caseNum>0); return 0; } // find get the original File char* getOriginalFile(int inputNum, int originalFileLen, int originalFileOneNum, int fileIndex[4]) { static char resultFile[4][FILESIZE]; int i, j; // index를 조합해서 original file이 될 수 있는 후보를 찾음 sprintf(resultFile[0], "%s%s", fileInfo[fileIndex[0]], fileInfo[fileIndex[1]]); sprintf(resultFile[1], "%s%s", fileInfo[fileIndex[1]], fileInfo[fileIndex[0]]); sprintf(resultFile[2], "%s%s", fileInfo[fileIndex[2]], fileInfo[fileIndex[3]]); sprintf(resultFile[3], "%s%s", fileInfo[fileIndex[3]], fileInfo[fileIndex[2]]); // 후보 중에 같은 것이 있으면, 그것이 original file if(!strncmp(resultFile[0], resultFile[2], originalFileLen) || !strncmp(resultFile[0], resultFile[3], originalFileLen)) return resultFile[0]; else if(!strncmp(resultFile[1], resultFile[2], originalFileLen) || !strncmp(resultFile[1], resultFile[3], originalFileLen)) return resultFile[1]; else return NULL; } // Fine 2 pair of file and save indexes; void findPair(int inputNum, int originalFileLen, int originalFileOneNum, int fileIndex[4]) { int i, j; int findFlag=FALSE, count=0; for(i=0; i<inputNum; i++) { for(j=0; j<inputNum; j++) { if(i==j) continue; // 자신의 쌍을 찾았을 경우 if(fragmentLen[i]+fragmentLen[j]==originalFileLen && fragmentOneNum[i]+fragmentOneNum[j]==originalFileOneNum) { // 자신의 쌍의 후보가 2개 이상일 경우(break) if(findFlag){ // pair is more than 2 fileIndex[count]=0; fileIndex[count+1]=0; findFlag = FALSE; break; } // 자신의 쌍을 찾았을 경우 index를 저장 else{ fileIndex[count]=i; fileIndex[count+1]=j; findFlag = TRUE; } } } if(findFlag) { count+=2; if(count>=4) break; } findFlag = FALSE; } return; }
'ACM' 카테고리의 다른 글
[Accept] 10110 Light, more light (0) | 2009.06.02 |
---|---|
[Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Time Limit] 10099 - The Tourist Guide (0) | 2009.06.02 |
This code is also another co-worker's source.
He makes it even if he didn't use any algorithm.
He made his own way that he delete the edge which is not the answer
----------------------------------------------------------------------------------------------
#include
#define MAXV 100
#define MAXDEGREE 100
typedef struct {
unsigned int edges[MAXV+1][MAXV+1];
unsigned int nverticies;
unsigned int nedges;
} graph;
graph g;
typedef struct {
unsigned int x;
unsigned int y;
unsigned int value;
} minSt;
minSt minList[10000];
unsigned int minCnt;
int map[100];
int cnt;
void init_graph()
{
memset(&g, 0, sizeof(graph));
}
void set_edges(int i)
{
g.nedges = i;
}
void set_verticies(int i)
{
g.nverticies = i;
}
void set_edge(int x, int y,int weight)
{
g.edges[x][y] = weight;
g.edges[y][x] = weight;
minList[minCnt].x = x;
minList[minCnt].y = y;
minList[minCnt++].value = weight;
}
void sort_min()
{
minSt tmp;
int i,j;
for ( i = 0 ; i < minCnt ; i++ ) {
for ( j = i ; j < minCnt ; j++ ) {
if ( minList[i].value > minList[j].value ) {
tmp = minList[i];
minList[i] = minList[j];
minList[j] = tmp;
}
}
}
#if 0
for ( i = 0 ; i < minCnt ; i++ ) {
printf("x(%d) y(%d) weight(%d)\n",minList[i].x, minList[i].y, minList[i].value);
}
#endif
}
void print_graph()
{
int i,j;
printf("==========================\n");
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
printf("%3d ",g.edges[i][j]);
}
printf("\n");
}
}
unsigned int ConnMap[101][101];
int isConnected2()
{
int i,j,k;
memcpy(ConnMap, g.edges, sizeof(ConnMap));
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
if ( i == j )
continue;
for ( k = 1 ; k <= g.nverticies ; k++ ) {
if ( j == k )
continue;
if ( i == k )
continue;
if ( ConnMap[i][j] > 0 && ConnMap[j][k] > 0 ) {
ConnMap[i][j] = 1;
ConnMap[j][i] = 1;
ConnMap[j][k] = 1;
ConnMap[k][j] = 1;
ConnMap[i][k] = 1;
ConnMap[k][i] = 1;
}
}
}
}
#if 0
printf("==========================\n");
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
printf("%3d ",ConnMap[i][j]);
}
printf("\n");
}
exit(0);
#endif
}
int isConnected(int start,int end)
{
register unsigned int i,j;
register unsigned int check=0;
if ( start == end )
return 1;
#if 1
if ( g.edges[start][end] > 0 ) {
return 1;
}
#endif
for ( i = 1 ; i <= g.nverticies ; i++ ) {
if ( i == start )
continue;
check = 0;
for ( j = 0 ; j < cnt ; j++ ) {
if ( map[j] == i ) {
check=1;
break;
}
}
if ( check == 1 )
continue;
if ( g.edges[start][i] > 0) {
map[cnt]=start;
cnt++;
if (isConnected(i,end) == 1 ) {
return 1;
}
}
}
return 0;
}
void del_edge(int x,int y)
{
g.edges[x][y] = 0;
g.edges[y][x] = 0;
}
int main()
{
int edge;
int vert;
int x,y;
int i,weight;
int start, end, people;
int min;
int scenario=1;
while(1) {
init_graph();
scanf("%d %d",&vert,&edge);
if ( vert == 0 )
break;
if ( vert < 1 || vert > 100 )
continue;
set_verticies(vert);
set_edges(edge);
for ( i = 0 ; i < edge ; i++ ) {
scanf("%d %d %d",&x,&y,&weight);
set_edge(x,y,weight);
}
scanf("%d %d %d",&start,&end,&people);
sort_min();
cnt = 0;
i = 0;
while ( isConnected(start,end)) {
#if 0
while ( 1 ) {
isConnected2();
if ( ConnMap[start][end] == 0 )
break;
#endif
cnt = 0;
min = minList[i].value;
del_edge(minList[i].x,minList[i].y);
i++;
}
if ( people % (min-1 ) == 0 )
min = people/(min-1);
else
min = people/(min-1) + 1;
printf("Scenario #%d\n",scenario++);
printf("Minimum Number of Trips = %d\n\n",min);
minCnt = 0;
fflush(stdin);
}
return 0;
}
#if 0
int find_min(int *x, int *y)
{
int i,j;
int min=99999;
int a;
for ( i = 1 ; i <= g.nverticies ; i++ ) {
for ( j = 1 ; j <= g.nverticies ; j++ ) {
if ( g.edges[i][j] > 0 && g.edges[i][j] < min ){
min = g.edges[i][j];
*x = i;
*y = j;
}
}
}
return min;
}
#endif
'ACM' 카테고리의 다른 글
[Accept] 850 Crypt Kicker II (0) | 2009.06.02 |
---|---|
[Accept] 10132 File Fragmentation (0) | 2009.06.02 |
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Time Limit] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Accept] 10004 - Bicoloring problem (0) | 2009.06.02 |
Unfortunately, I didn't get accept from Judge Server.
This code is one of my co-worker's source.
He used Dynamic Programming.
I should study that algorithm.
----------------------------------------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <stdio.h> int g_cities[101][101]; #define MIN(a,b) (a>b?b:a) int search_min_trips(int start, int end, int num_cities) { int i, j, k; int max = 0, min; for (i = 1; i <= num_cities; i++) { for (j = 1; j <= num_cities; j++) { for (k = 1; k <= num_cities; k++) { min = MIN(g_cities[i][k], g_cities[k][j]); if (g_cities[i][j] < min) g_cities[i][j] = g_cities[j][i] = min; }}} return g_cities[start][end]; } int main() { int i, cnt = 0; int num_cities; int num_roads; int num_passengers; int start, end; int city1, city2, cap; int max_cap; while (scanf("%d %d", &num_cities, &num_roads) != 1 && num_cities != 0 && num_roads != 0) { memset(g_cities, 0x00, sizeof(g_cities)); for (i = 0; i < num_roads; i++) { scanf("%d %d %d", &city1, &city2, &cap); g_cities[city1][city2] = g_cities[city2][city1] = cap; } scanf("%d %d %d", &start, &end, &num_passengers); max_cap = search_min_trips(start, end, num_cities) - 1; printf("Scenario #%d\n", ++cnt); printf("Minimum Number of Trips = %d\n\n", num_passengers / max_cap + (num_passengers % max_cap == 0 ? 0 : 1)); } return 0; } |
'ACM' 카테고리의 다른 글
[Accept] 10132 File Fragmentation (0) | 2009.06.02 |
---|---|
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Time Limit] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Accept] 10004 - Bicoloring problem (0) | 2009.06.02 |
[Accept] 100 - The 3n+1 problem (0) | 2009.06.02 |
#include <stdio.h> #define MAX_CITY 101 #define DISCONNECTED 0 #define PASSED 1 #define NOTPASSED 0 typedef struct TourInfo{ int roadNum; // road Number (input) int cityNum; // city Number (input) int roadInfo[MAX_CITY][MAX_CITY]; // road info (max passenger info) int cityIsPassed[MAX_CITY]; // passed or not passed int cityMinNum[MAX_CITY]; // min Passenger Number int startCity; // start (input) int destCity; // destination (input) int totalPassengerNum; // total passenger Number (input) int minPassengerNum; // result }TourInfo; void initTourInfo(); int findMinNumberOfTrips(int left); TourInfo tour; int main(void) { int firstCity, secondCity, maxPassengerNum; int scenarioCount=0, result, i; while(1){ scanf("%d %d", &tour.cityNum, &tour.roadNum); if(tour.cityNum==0 && tour.roadNum==0) break; result = 0; initTourInfo(); for(i=0; i<tour.roadNum; i++){ scanf("%d %d %d", &firstCity, &secondCity, &maxPassengerNum); tour.roadInfo[firstCity][secondCity] = maxPassengerNum; tour.roadInfo[secondCity][firstCity] = maxPassengerNum; } scanf("%d %d %d", &tour.startCity, &tour.destCity, &tour.totalPassengerNum); if(tour.totalPassengerNum < 1) break; findMinNumberOfTrips(tour.startCity); scenarioCount++; result = tour.totalPassengerNum / (tour.minPassengerNum-1); if(tour.totalPassengerNum % (tour.minPassengerNum-1)) result++; printf("Scenario #%d\n", scenarioCount); printf("Minimum Number of Trips = %d\n\n", result); } return 0; } int findMinNumberOfTrips(int left) { int i, right, minPass; tour.cityIsPassed[left]=PASSED; // Last City if(left==tour.destCity){ if(!tour.minPassengerNum) { tour.minPassengerNum = tour.cityMinNum[left]; } else { if(tour.minPassengerNum < tour.cityMinNum[left]) { tour.minPassengerNum = tour.cityMinNum[left]; } } tour.cityMinNum[left]=NOTPASSED; tour.cityIsPassed[left]=NOTPASSED; return 1; } for(right=1; right<=tour.cityNum; right++) { if(tour.cityIsPassed[right]==PASSED) continue; // already passed city if(tour.roadInfo[left][right]!=0) // CONNECTED { if(!tour.cityMinNum[left]){ // first path tour.cityMinNum[right] = tour.roadInfo[left][right]; } else{ if(tour.cityMinNum[left] > tour.roadInfo[left][right]){ tour.cityMinNum[right] = tour.roadInfo[left][right]; } else{ tour.cityMinNum[right] = tour.cityMinNum[left]; } } if(tour.minPassengerNum >= tour.cityMinNum[right]) continue; findMinNumberOfTrips(right); } } // init and return tour.cityMinNum[left]=NOTPASSED; tour.cityIsPassed[left]=NOTPASSED; return 1; } void initTourInfo() { int i,j; for(i=0; i<MAX_CITY; i++) { for(j=0; j<MAX_CITY; j++) { tour.roadInfo[i][j] = DISCONNECTED; } tour.cityIsPassed[i] = NOTPASSED; tour.cityMinNum[i] = NOTPASSED; } tour.minPassengerNum = 0; }
'ACM' 카테고리의 다른 글
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
---|---|
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Accept] 10004 - Bicoloring problem (0) | 2009.06.02 |
[Accept] 100 - The 3n+1 problem (0) | 2009.06.02 |
10006 - Carmichael Numbers (0) | 2009.06.02 |