ACM 2009. 6. 2. 21:03
반응형
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
: