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 |