ACM 2009. 6. 8. 15:04

[Accept] 10018 Reverse and Add

반응형
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
posted by ssuk1010
:
ACM 2009. 6. 3. 20:25

[10018] Reverse and Add

반응형

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 9339
5 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
posted by ssuk1010
:
ACM 2009. 6. 2. 21:11

[Time Limit] Carmichael Numbers

반응형

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
posted by ssuk1010
:
ACM 2009. 6. 2. 21:08

[Accept] 10006 Carmichael Numbers

반응형
I got accept from Judge Server.
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
posted by ssuk1010
:
ACM 2009. 6. 2. 21:05

[Accept] 10110 Light, more light

반응형
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

#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
posted by ssuk1010
:
ACM 2009. 6. 2. 21:04

[Accept] 850 Crypt Kicker II

반응형

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
posted by ssuk1010
:
ACM 2009. 6. 2. 21:03

[Accept] 10132 File Fragmentation

반응형
I got accept form Judge Server

----------------------------------------------------------------------------------------------
#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
posted by ssuk1010
:
ACM 2009. 6. 2. 21:02

[Accept] 10099 - The Tourist Guide

반응형

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
posted by ssuk1010
:
ACM 2009. 6. 2. 20:56

[Accept] 10099 - The Tourist Guide

반응형

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
posted by ssuk1010
:
ACM 2009. 6. 2. 20:51

[Time Limit] 10099 - The Tourist Guide

반응형
I got time limite from Judge Server. T.T

#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
posted by ssuk1010
:

티스토리툴바