UVa 324, PKU 1454. Factorial Frequencies. [판정:AC]

저도 처음에는 Dlbo군의 판정과 같은( 아마 같을 ) In the queue였습니다

그래서

일단 pku에 먼저 질러보자

하는 마음으로 질렀습니다

..

두번의 CE를 받으면서 채점 기준이 좀 까다롭다는 생각을 했습니다

채점을 위해서는 형식을 통일해야한다는건 잘 알지만, 그냥 짜증나더라고요 ㅋㅋㅋㅋ

pku에서 AC받고 uva로 넘어갔더니, 거기에서도 CE가 떠있길래

( uva에 처음 제출한 소스와 pku에 처음 제출한 소스가 동일 )

pku에 마지막으로 제출한 소스를 그대로 uva에 제출했더니 AC가 나오더군요, 다행히 ㄷㄷ

소스를 올릴까 말까 했는데, 일단 올려봅니다

알고리즘은 매우 간단합니다

1~366의 범위를 갖는 자연수 k에 대해 k!의 값을 구해서,

그것의 각 자리수가 무엇으로 이루어져있는가를 보면 됩니다

쉽게 확인할 수 있는 방법중 하나는

k!을 10으로 나눈 나머지를 구해서 세고, k!을 저장하고 있던 변수에는 k!을 10으로 나눈 몫을 구해서 저장하고…

이 짓을 반복하면 k!의 뒤에서부터 확인이 가능합니다

단지 매우 큰 양수를 저장할 자료형이 마땅치 않다는 점이 가장 큰 문제가 되겠습니다만

제게는 UBINT가 있잖아요?

갖다 썼습니다

이 문제에서 필요하지 않은 멤버함수는 싹다 지우고, 멤버변수의 속성을 protected에서 public으로 바꾸고,

그 외에 CE판정을 받은 부분은 살짝 고쳐서 해결했습니다

제 UBINT의 경우, 숫자를 나타내는 부분이 string이므로 앞에서부터 하나씩 세었습니다 -_-;

( 소스는 다소 스압이 있을것 =_= )

#include <iostream> using std::cout; using std::ostream; using std::istream; #include <string> using std::string; // ubint: Unsigned Big INTeger class ubint { public: string num; ubint(); ubint( const ubint& ub ); ubint operator =( const ubint& ub2 ); ubint( int number ); ubint operator =( int n2 ); friend ostream& operator <<( ostream& os, ubint ub ); string add( string n2 ); // main heritage 1 ubint operator +( ubint ub2 ); string multiply( string n2 ); // main heritage 2 ubint operator *( ubint ub2 ); ubint operator +=( ubint ub2 ); ubint operator *=( ubint ub2 ); ubint operator ++(); bool operator >( ubint ub2 ); bool operator <=( ubint ub2 ); }; //============================================================================// // default constructor ubint::ubint() { num = '0'; } // copy constructor ubint::ubint( const ubint& ub ) { num = ub.num; } // overloading: ubint = ubint ubint ubint::operator =( const ubint& ub2 ) { num = ub2.num; return ub2; } //============================================================================// // constructor: int ubint::ubint( int number ) { string temp = string(12, '0'); int i, s = 11; if( number < 0 ) number = -number; while( number > 0 ) { temp[s] = number % 10 + '0'; number /= 10; s--; } s = temp.size(); for( i = 0; i < s; i++ ) { if( temp[i] != '0' ) break; } if( i < s ) num = temp.substr(i, s-i); else num = '0'; } // overloading: ubint = int ubint ubint::operator =( int n2 ) { ubint temp(n2); num = temp.num; return temp; } //============================================================================// // overloading: ostream ostream& operator <<( ostream& os, ubint ub ) { os << ub.num; return os; } //============================================================================// // addition of two strings; main heritage 1 string ubint::add( string n2 ) { string t1, t2; int s1, s2; t1 = num; t2 = n2; s1 = t1.size(); s2 = t2.size(); if( s1 > s2 ) t2 = string(s1-s2, '0') + n2; else if( s1 < s2 ) t1 = string(s2-s1, '0') + num; int i, s = t1.size(), carry = 0; string res = string(s, '0'); for( i = s-1; i >= 0; i-- ) { res[i] = t1[i] + t2[i] - '0' + carry; if( res[i] > '9' ) { carry = 1; res[i] -= 10; } else carry = 0; } if( carry ) res = '1' + res; return res; } // overloading: ubint + ubint ubint ubint::operator +( ubint ub2 ) { ubint res; res.num = this->add(ub2.num); return res; } //============================================================================// // multiplication of two strings; main heritage 2 string ubint::multiply( string n2 ) { int s1, s2; string res; s1 = num.size(); s2 = n2.size(); res = string(s1+s2, 0); int i, j, s, carry = 0; for( i = s2-1; i >= 0; i-- ) { for( j = s1-1; j >= 0; j-- ) { res[i+j+1] += (num[j] - '0') * (n2[i] - '0') + carry; if( res[i+j+1] > 9 ) { carry = res[i+j+1] / 10; res[i+j+1] %= 10; } else carry = 0; } res[i+j+1] = carry; carry = 0; } s = res.size(); for( i = 0; i < s; i++ ) { res[i] += '0'; } for( i = 0; i < s; i++ ) { if( res[i] != '0' ) break; } if( i < s ) res = res.substr(i, s-i); else res = '0'; return res; } // overloading: ubint * ubint ubint ubint::operator *( ubint ub2 ) { ubint res; res.num = this->multiply(ub2.num); return res; } //============================================================================// // overloading: ubint += ubint ubint ubint::operator +=( ubint ub2 ) { *this = *this + ub2; return *this; } // overloading: ubint *= ubint ubint ubint::operator *=( ubint ub2 ) { *this = *this * ub2; return *this; } //============================================================================// // overloading: prefix increment ubint ubint::operator ++() { ubint temp(1); *this += temp; return *this; } //============================================================================// // overloading: ubint > ubint bool ubint::operator >( ubint ub2 ) { int s1, s2; s1 = num.size(); s2 = ub2.num.size(); if( s1 > s2 ) return true; else if( s1 < s2 ) return false; else { int i, s = s1; for( i = 0; i < s; i++ ) { if( num[i] != ub2.num[i] ) break; } if( num[i] > ub2.num[i] ) return true; else return false; } } // overloading: ubint <= ubint bool ubint::operator <=( ubint ub2 ) { return !(*this > ub2); } //============================================================================// int dscanf( int *pnum ) { scanf("%d", pnum); return *pnum; } ubint factorial( int n ) { ubint res = 1; ubint i, max = n; for( i = 1; i <= max; ++i ) { res *= i; } return res; } void print( int n, ubint ub ) { string str = ub.num; int s = str.size(); int i, j, count; cout << n << "! --\n"; j = 0; while( j < 10 ) { count = 0; for( i = 0; i < s; i++ ) { if( str[i] == j + '0' ) count += 1; } printf(" (%d)%5d ", j, count); j++; if( j % 5 == 0 ) printf("\n"); } } int main() { int n; ubint fact; while( dscanf(&n) != 0 ) { fact = factorial(n); print(n, fact); } return 0; }

이 글을 쓸 때까지 한가지 잊어먹고 있던 것이 하나 있는데,

4번째 줄에 있는 using std::istream; 도 지우고 제출했어야 했는데 그냥 했네요 ㅋㅋㅋ