#include #include #include #include #include //#ifdef UNIX typedef unsigned long long DDWORD; #define FMT1 "%llu\n" #define FMT2 "%llu/%llu\n" #define FMT3 "%llu %llu/%llu\n" //#else //typedef unsigned __int64 DDWORD; //#define FMT1 "%I64u\n" //#define FMT2 "%I64u/%I64u\n" //#define FMT3 "%I64u %I64u/%I64u\n" //#endif typedef unsigned long DWORD; #define MAX_DIGITS 200000 #define TOPVAL (MAX_DIGITS +1) #define LEFTVAL (-1) typedef struct _relstack { int loc; int val; } RELSTACK; typedef struct _LR_ { int left; int right; } LR; RELSTACK relst[32]; LR lefrt[TOPVAL]; int chcnt; int invals[TOPVAL]; int ScanString() { int curind, curval, sttop; int scanval, scanind, nxtind; sttop = 0; relst[0].loc = LEFTVAL; relst[0].val = 20; for(curind = 0; curind < chcnt ; curind++) { curval = invals[curind]; lefrt[curind].right = TOPVAL; while(curval > relst[sttop].val) { lefrt[relst[sttop].loc].right = curind; scanval = relst[sttop].val; scanind = relst[sttop].loc; nxtind = lefrt[scanind].left; while((nxtind >= 0) && (invals[nxtind] == scanval) && (lefrt[nxtind].right == TOPVAL)) { lefrt[nxtind].right = curind; scanind = nxtind; nxtind = lefrt[scanind].left; } sttop--; } lefrt[curind].left = relst[sttop].loc; if(curval < relst[sttop].val) { sttop++; } relst[sttop].loc = curind; relst[sttop].val = curval; } return 0; } DDWORD GCD(DDWORD a, DDWORD b) { DDWORD c; if(a == 0) return b; if(b == 0) return a; if(a < b) { c = a; a = b; b = c; } c = a % b; while (c > 0) { a = b; b = c; c = a % b; } return b; } DDWORD CompDenom (void) { DDWORD T, ret; T = chcnt; if(chcnt & 1) { ret = (T+1)/2; ret = ret *T; } else { ret = T/2; ret = ret*(T+1); } return ret; } // leftdist is length of longest substring to left with // rt end at curind and left end first entry or just after next larger entry // rtdist is length of longest substring to rt with left end at curind and // rt end lest entry or just before next larger entry DDWORD CountSubstr(int leftdist, int rtdist) { DDWORD T, D1, D2, ret; ret = 0; D1 = leftdist; D2 = rtdist; if(D1 > D2) { // make D1 no larger than D2 T = D1; D1 = D2; D2 = T; } // starting with a substring of len 1 at curind get 2 len2 ...D1 len D1 when you hit an end T = (D1*(D1+1))/2; ret += T; // now do lens d1+1 .. D2 to hit second end (D1 of each) T = D1*(D2 - D1); ret += T; // now do d1 - 1 len D2+1 ... 1 len D1 + D2 -1 T = ((D1 - 1)*D1)/2; ret += T; return ret; } DDWORD CompNum(void) { int curind, left, rt; DDWORD ret, ddval, count; ret = 0; for(curind = 0; curind < chcnt ; curind++) { ddval = invals[curind]; left = lefrt[curind].left; rt = lefrt[curind].right; if((left == LEFTVAL) && (rt == TOPVAL)) { count = CountSubstr(curind+1, chcnt - curind); ret = ret + ddval*count; } else if(left == LEFTVAL) { count = CountSubstr(curind + 1, rt - curind); ret = ret + ddval*count; } else if(rt == TOPVAL) { count = CountSubstr(curind - left, chcnt - curind); ret = ret + ddval*count; } else { count = CountSubstr(curind - left, rt - curind); ret = ret + ddval*count; } } return ret; } int ParseInput(void) { char c; chcnt = 0; while((c = getc(stdin)) != EOF) { if((c < '0') || (c > '9')) { return 0; } invals[chcnt] = c - '0'; chcnt++; if(chcnt > MAX_DIGITS) { fprintf(stderr, "Too many digits\n"); return -11; } } return 0; } int main() { int ret; DDWORD num, denom, ndgcd, units; if((ret = ParseInput()) != 0) { return ret; } ScanString(); denom = CompDenom(); num = CompNum(); ndgcd = GCD(denom,num); denom = denom/ndgcd; num = num/ndgcd; if(denom == 1) { printf(FMT1, num); } else if(num > denom) { units = num/denom; num = num - units*denom; printf(FMT3, units, num, denom); } else { printf(FMT2, num, denom); } return 0; }