SRM 509 !!

가깟으로 500을 종료 직전에 submit 했는데.. 챌 당해서 마음이 아팠다..
다들 빨리 푼 250을 늦게 풀어서 다시 blue 로 복귀하는줄 알았는데.. 오히려 rating 이 올랐다..
흠.. 그러고보니 한국사람중에 500을 푼 사람이 아무도 없다.. 쉽지 않은 문제였군..
어쨋거나 Yellow 1차 방어전 성공..~

Level1 - LuckyRemainder

Problem Statement
     
Little Arthur loves numbers and 9 is his most favorite. When encountering a number, he always calculates its lucky remainder - the remainder after division by 9.  This time Arthur is given a number X of length N which contains no zeros. He is asked to find the supersum of X: super(X).  super(X) is defined as follows. For a given non-full set S of digit positions in X we erase the digits in these positions to obtain a sub-number. For example, if X = 12345 and S = {2, 4} we erase 2nd and 4th digits and obtain a sub-number 135. Supersum of X is simply the sum of sub-numbers for all valid sets S.  For example, if X is 123, then super(X) = 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177.  Calculating super(X) is very difficult for Arthur. However, before getting to work he is wondering if it is possible to quickly tell what the lucky reminder of the supersum of X is. You have to help him.  Given string X, which contains the decimal representation of the number X, return super(X)'s lucky remainder.
Definition
    
Class:
LuckyRemainder
Method:
getLuckyRemainder
Parameters:
string
Returns:
int
Method signature:
int getLuckyRemainder(string X)
(be sure your method is public)
    
 
Constraints
-
X will contain between 1 and 50 characters, inclusive.
-
Each character of X will be one of the following: '1', '2', '3', '4', '5', '6', '7', '8', '9'.
Examples
0)
 
    
"123"
Returns: 6
Example from the problem statement. super(123) = 177, which gives remainder 6 after division by 9.
1)
 
    
"24816"
Returns: 3
Supersum of 24816 is 43986.
2)
 
    
"8"
Returns: 8
 
3)
 
    
"11235813213455"
Returns: 7
Supersum is 43950094900477.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

super(x) = x에서 임의의 digit 몇개를 빼서 만들수 있는수를 모두 더한 수..
예를 들어 x = 123 이라고 하면
super(123) = 123 + 12 + 23 + 13 + 1 + 2 + 3 = 177 이다.
x 가 주어질때, super(x) % 9 구하기..

1) x % 9 = (x의 각 digit 의 합) % 9    <== 맞나???
2) super(x) 의 모든 set 의 원소를 구하면 각 digit 은 2^(digit개수-1) 개가 나온다.. 이걸 다 더하면 됨..

코드는 짧지만 그닥 빨리 풀 수 있는 문제는 아니었는데.. 249 점 맞은 사람은 뭐임??

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  7 using namespace std;
  8 //#define min(x, y) ((x) > (y) ? (y) : (x))
  9 //#define max(x, y) ((x) > (y) ? (x) : (y))
 10 //#define INF 999999999
 11 //#define EPS 1e-14
 12
 13 class LuckyRemainder {
 14 public:
 15
 16 int getLuckyRemainder(string X)
 17 {
 18     int i;
 19     int len;
 20     int sum;
 21     len = X.size();
 22     sum = 0;
 23     for (i = 0; i < X.size(); i++) {
 24         sum += X[i]-'0';
 25         sum %= 9;
 26     }
 27     for (i = 0; i < len-1; i++) {
 28         sum *= 2;
 29         sum %= 9;
 30     }
 31     return sum % 9;
 32 }
 33
 34 };