블로그는 귀차니즘

First Sensation
  • 공지
  • 지역로그
  • 태그
  • 방명록

TopCoder - Tournament - Inv 2001 R1

TopCoder 2008/04/05 22:27 귀차니스트
Problem Statement
   
***Note:  Please keep programs under 7000 characters in length.  Thank you

Class Name: SquareDigits
Method Name: smallestResult
Parameters: int
Returns: int
Define the function S(x) as the sum of the squares of the digits of x.  
For example: S(3)=3*3=9 and S(230)=2*2+3*3+0*0=13.
Define the set T(x) to be the set of unique numbers that are produced by
repeatedly applying S to x.  That is: S(x), S(S(x)), S(S(S(x))), etc...
For example, repeatedly applying S to 37:
S(37)=3*3+7*7=58. 
S(58)=5*5+8*8=89.
S(89)=145.
S(145)=42.
S(42)=20.
S(20)=4.
S(4)=16.
S(16)=37.
Note this sequence will repeat so we can stop calculating now and:
T(37)={58,89,145,42,20,4,16,37}.
However, note T(x) may not necessarily contain x. 
Implement a class SquareDigits, which contains a method smallestResult.  The
method takes an int, n, as a parameter and returns the smallest int, x, such
that T(x) contains n.
The method signature is (be sure your method is public):
int smallestResult(int n);
TopCoder will ensure n is non-negative and is between 0 and 199 inclusive.
Examples:
If n=0: S(0) = 0, so T(0)={0}, so the method should return 0.
If n=2: T(0) through T(10) do not contain the value 2.  If x=11, however:
S(11)=1*1+1*1=2, so T(11) contains 2, and the method should return 11.
If n=10: T(0) through T(6) do not contain 10.  If x=7:
S(7)=49.
S(49)=97.
S(97)=130.
S(130)=10.
S(10)=1.
and it starts to repeat...
so T(7) is {49,97,130,10,1}, which contains 10, and the method should return 7.
n=1 -> x=1
n=19 -> x=133
n=85 -> x=5
n=112 -> x=2666
Definition
   
Class:
SquareDigits
Method:
smallestResult
Parameters:
int
Returns:
int
Method signature:
int smallestResult(int param0)
(be sure your method is public)
   
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.

  대충 얘기를 하자면 X(11)= 1*1 + 1*1 = 2 라는 X 함수가 존재합니다. 그런데 이 함수는 중첩적으로 계속 하여 호출 될 수 있습니다. 대충 예를 들면 X(11) = 2, X(2) = 4, X(4) = 16 ... 등등으로 계속 호출 될 수 있겠죠.
  그러다가 이 함수 호출에 있어서 X(A)=Y 형태 중 A가 이미 호출되었을 때는 해당 N 숫자에 대한 집합에 들어가 있으므로 결국 T(11) = { 2, 4, 16 .. } 형태의 집합으로 나타낼 수 있습니다.
  중요한 것은 T(11)로 표현되는 집합에 11이라는 숫자가 들어가 있는가 하는 점입니다. 들어가 있다면 11을 리턴하게 되고, 포함되어있지 않으면 T(12)를 작업해보고, 그 결과에 따라 13, 14로 늘어날 수 있습니다. 그리고 제일 작은 숫자를 리턴하면 됩니다.

SquareDigits.h (Language : cpp)
  1. #pragma once
  2.  
  3. #include <map>
  4. #include <set>
  5. #include <cmath>
  6.  
  7. class SquareDigits
  8. {
  9. public:
  10.     SquareDigits(void);
  11.     ~SquareDigits(void);
  12.  
  13.     int smallestResult( int param0 );
  14.     int nextInt( int param0 );
  15.  
  16. private:
  17.     std::map< int, int > LinkIndex;
  18. };
  19.  

SquareDigits.cpp (Language : cpp)
  1. #include "SquareDigits.h"
  2.  
  3. SquareDigits::SquareDigits(void)
  4. {
  5. }
  6.  
  7. SquareDigits::~SquareDigits(void)
  8. {
  9. }
  10.  
  11. int SquareDigits::smallestResult( int param0 )
  12. {
  13.     std::set< int > ContainsSet;
  14.     for( int i = 0; i < INT_MAX; ++i )  {
  15.  
  16.         int CurrentNumber = i;
  17.         ContainsSet.clear();
  18.         while( ContainsSet.find( CurrentNumber ) == ContainsSet.end() ) {
  19.  
  20.             ContainsSet.insert( CurrentNumber );
  21.             std::map< int, int >::const_iterator Iter = LinkIndex.find( CurrentNumber );
  22.             if( Iter == LinkIndex.end() )   {
  23.  
  24.                 int Temp = nextInt( CurrentNumber );
  25.                 LinkIndex.insert( std::make_pair( CurrentNumber, Temp ));
  26.                 CurrentNumber = Temp;
  27.             }
  28.             else    {
  29.  
  30.                 CurrentNumber = Iter->second;
  31.             }
  32.  
  33.             if( CurrentNumber == param0 )   {
  34.  
  35.                 return i;
  36.             }
  37.         }
  38.     }
  39.  
  40.     return 0;
  41. }
  42.  
  43. int SquareDigits::nextInt( int param0 )
  44. {
  45.     int RetValue = 0;
  46.     while( param0 > 0 ) {
  47.  
  48.         RetValue += static_cast< int >( std::pow( param0 % 10, 2.00) );
  49.         param0 /= 10;
  50.     }
  51.  
  52.     return RetValue;
  53. }

  이 번엔 제대로 검사를 하긴 했습니다. 그런데 INT_MAX 라는 범위가 있다보니 199까지 최대 숫자를 측정하여 배열을 이용한 O(1)시간의 검색이 되어야 하나, 손해를 약간 보더라도 set에 대한 find 검색작업을 수행하도록 구성하였습니다.
  포인트가 안 좋은건 속도 때문일까요?^^. 그냥 풀어본 것에 의미를 가지도록 하겠습니다.

http://www.topcoder.com
크리에이티브 커먼즈 라이센스
Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"TopCoder" 분류의 다른 글

TopCoder - Tournament - Inv 2001 R1 (4)2008/03/05
TopCoder - 전 세계 프로그래머들과 경쟁하기 (0)2008/02/18
2008/04/05 22:27 2008/04/05 22:27
TAG C++, TopCoder
받은 트랙백이 없고, 댓글이 없습니다.

트랙백 주소 :: http://www.filewiki.net/tc/trackback/45

댓글을 달아 주세요

TopCoder - Tournament - Inv 2001 R1

TopCoder 2008/03/05 23:45 귀차니스트

Problem Statement

     
***Note:  Please keep programs under 7000 characters in length.  Thank you


Class Name: HowEasy
Method Name: pointVal
Parameters: String
Returns: int
 
TopCoder has decided to automate the process of assigning problem difficulty
levels to problems.  TopCoder developers have concluded that problem difficulty
is related only to the Average Word Length of Words in the problem statement:

If the Average Word Length is less than or equal to 3,  the problem is a 250
point problem.
If the Average Word Length is equal to 4 or 5, the problem is a 500 point
problem.
If the Average Word Length is greater than or equal to 6, the problem is a 1000
point problem.
 
Definitions:
Token - a set of characters bound on either side by spaces, the beginning of
the input String parameter or the end of the input String parameter.
Word - a Token that contains only letters (a-z or A-Z) and may end with a
single period. A Word must have at least one letter.
Word Length - the number of letters in a Word. (NOTE: a period is NOT a letter)

The following are Words :
"ab",  "ab."

The following are not Words :
"ab..", "a.b", ".ab", "a.b.", "a2b.", "."

Average Word Length - the sum of the Word Lengths of every Word in the problem
statement divided by the number of Words in the problem statement.  The
division is integer division. If the number of Words is 0, the Average Word
Length is 0.
 
Implement a class HowEasy, which contains a method pointVal.  The method takes
a String as a parameter that is the problem statement and returns an int that
is the point value of the problem (250, 500, or 1000). The problem statement
should be processed from left to right.
 
Here is the method signature (be sure your method is public):
int pointVal(String problemStatement);
 
problemStatement is a String containing between 1 and 50 letters, numbers,
spaces, or periods.  TopCoder will ensure the input is valid.
 
Examples:
 
If problemStatement="This is a problem statement", the Average Word Length is
23/5=4, so the method should return 500.
If problemStatement="523hi.", there are no Words, so the Average Word Length is
0, and the method should return 250.
If problemStatement="Implement a class H5 which contains some method." the
Average Word Length is 38/7=5 and the method should return 500.
If problemStatement=" no9 . wor7ds he8re. hj.." the Average Word Length is 0,
and the method should return 250.

Definition

    
Class: HowEasy
Method: pointVal
Parameters: string
Returns: int
Method signature: int pointVal(string param0)
(be sure your method is public)
    

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.


  간단한 문제 였습니다. String 에 관련된 문제라 std::string 인 C++ 이 아니라 C# 쪽의 split 메소드를 사용해보았습니다. 간단하게 구현되는 문제라. 어려움은 없었습니다.

Inv 2001 R1.cs (Language : csharp)
  1. class HowEasy {
  2.  public int pointVal( string param0)
  3.  {
  4.   string [] SplitData = param0.Split( " .".ToCharArray() );
  5.   if( SplitData.Length == 0 )
  6.    return 0;
  8.   int AverageCount = 0;
  9.   for( int i = 0; i < SplitData.Length; ++i ) {
  10.    AverageCount += SplitData[ i ].Length;
  11.   }
  12.  
  13.   int Point =  ( int )System.Math.Floor( ( double )( AverageCount / SplitData.Length ) );
  14.   if( Point == 3 )
  15.     return 250;
  16.   if( Point == 4 || Point == 5 )
  17.     return 500;
  18.    
  19.   if( Point >= 6 )
  20.     return 1000;
  21.   return 0;
  22.  }
  23. }
  24.  

ㅡ,.ㅡ 알고보니 잘못된 코드였군요.. 급하게 수정하여 올립니다.
수정버젼.cs (Language : cpp)
  1. class HowEasy
  2. {
  3.     public int pointVal(string param0)
  4.     {
  5.         int WordTotalCount = 0;
  6.         int WordCount = 0;
  7.  
  8.         string[] WordArray = param0.Split(" ".ToCharArray());
  9.  
  10.         for (int i = 0; i < WordArray.Length; ++i, ++WordCount)
  11.         {
  12.             string Word = WordArray[i];
  13.  
  14.             int FirstIndex = Word.IndexOf('.');
  15.             int LastIndex = Word.LastIndexOf('.');
  16.  
  17.             if (FirstIndex != -1 && FirstIndex != LastIndex)
  18.                 continue;
  19.  
  20.             Word = Word.Replace(".", "");
  21.  
  22.             bool Flag = true;
  23.             foreach (char TempChar in Word)
  24.             {
  25.                 if (!char.IsLetter(TempChar))
  26.                     Flag = false;
  27.             }
  28.  
  29.             if (!Flag)
  30.                 continue;
  31.  
  32.             WordTotalCount += Word.Length;
  33.         }
  34.  
  35.         int Average = (WordTotalCount / (WordCount == 0 ? 1 : WordCount));
  36.         if (Average <= 3)
  37.             return 250;
  38.         else if (Average == 4)
  39.             return 500;
  40.         else if (Average >= 5)
  41.             return 1000;
  42.  
  43.         return 0;
  44.     }
  45. }


P.S 승훈이횽 HDTV 카드 지르세용 +ㅅ+ ㅋㅋ 아래는 스크린샷


http://www.topcoder.com/
크리에이티브 커먼즈 라이센스
Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"TopCoder" 분류의 다른 글

TopCoder - Tournament - Inv 2001 R1 (0)2008/04/05
TopCoder - 전 세계 프로그래머들과 경쟁하기 (0)2008/02/18
2008/03/05 23:45 2008/03/05 23:45
TAG TopCoder, 탑코더
받은 트랙백이 없고, 댓글 4개가 달렸습니다.

트랙백 주소 :: http://www.filewiki.net/tc/trackback/25

댓글을 달아 주세요

  1. 준호씨 2008/03/06 00:49  댓글주소  수정/삭제  댓글쓰기

    우와...
    마지막 스크린샷.. 참 깨끗하군 +_+

    • 귀차니스트 2008/03/06 10:18  댓글주소  수정/삭제

      ㅋㅋ 준호님도 이 참에 지르는건 어떠함??
      지름신 with you!~

  2. kkamagui 2008/03/12 20:08  댓글주소  수정/삭제  댓글쓰기

    횽은 TV도 안보는데 왠 TV 카드냐 ㅋㅋ 천지 이래서 안대 ㅋㅋ

    • 귀차니스트 2008/03/12 23:25  댓글주소  수정/삭제

      Infinity loop of 지름 이에용 ㅋㅋ

TopCoder - 전 세계 프로그래머들과 경쟁하기

TopCoder 2008/02/18 09:00 귀차니스트

  컴퓨터 프로그래밍 쪽으로 관심이 좀 깊거나, 전공자라면 한 번쯤은 ACM-ICPC라는 대회에 대해서 들어보신 적이 있으실 겁니다. 간단하게 설명을 하자면 대학생들이 3인 1조 팀을 이루어 제한된 시간 내에 문제를 효율적인 시간으로 풀이를 해야 하는 대회이죠. 그런 알고리즘 문제들을 풀 수 있는 여러 가지 사이트들이 준비되어 있기도 합니다. 간단히 검색엔진에서 찾는다면 문제를 풀어볼 수 있습니다.
  그런데 그와 비슷하게 전 세계 프로그래머들과 문제풀이 경쟁을 할 수 있는 사이트가 하나 있습니다. 그 사이트의 이름은 "TopCoder"입니다. 이름에서 뭔가 느껴지지 않나요^^? 최고의 코더를 가리는 사이트 입니다(?).
  한 번 가입을 해보도록 할까요?


  1. http://www.topcoder.com/reg/ 다음 주소로 들어가 사이트에 가입합시다. 프로그래밍으로 경쟁을 하려면 "Competition Registration"에 체크를 하고 Submit 하면 됩니다.

  2. 아래의 속성에 맞게 가입정보를 입력합니다.
    1. Given Name - 성
    2. Surname - 이름
    3. Address1 - 주소
    4. Address2
    5. Address3
    6. City - 도시
    7. State (US Only)
    8. Postal Code
    9. Province
    10. Country - South Korea를 선택합니다.
    11. Country to represent - South Korea를 선택합니다.
    12. Timezone - Asia/Seoul을 선택합니다.
    13. Phone Number
    14. Email Address - 이메일을 입력합니다.
    15. Confirm Email Address - 14번에 입력한 이메일을 재입력합니다.
    16. Email Notifications - 이메일로 통지받고 싶은지 선택합니다.
      1. Algorithm Competitions
      2.  Software Development Opportunities
      3.  Employment Opportunities
      4.  TopCoder News & Events
    17. Enable Member Contact - 잘 모르겠습니다. 그냥 기본 값인 No 하면 될듯하네요.
      1.  Yes
      2.  No
    18. User Name - 로그인시 사용할 아이디입니다.
    19. Password - 로그인시 사용할 비밀번호입니다.
    20. Confirm Password - 19번에 입력한 비밀번호를 재입력합니다.
    21. Secret Question - 비밀번호 같은 것을 알려고 할 때 필요한 질문입니다.
    22. Secret Question Response - 21번 질문에 대한 답이죠.
    23. Quote
    24. Student/Professional - Student로 하면 되지 않을까요^^?

  3. 위 정보를 입력하고 나서 Submit 버튼을 누르면 또 입력 창이 뜨는군요. 또 각각에 맞게 넣어봅시다.
    1. Age - 나이겠죠^^?
    2. Gender - 성입니다. 프라이버시 때문에 안 밝히고 싶은 경우도 선택할 수 있습니다.
    3. Ethnic Background - 민족을 선택합니다. Asian or Pacific Islander를 선택합니다.
    4. Primary Interest In TopCoder - TopCoder 사이트에서 제일 관심있는 분야를 선택합니다.
    5. Shirt Size - T셔츠의 크기를 선택합니다. 그냥 단순합니다. Small, Medium, Large, Etc.
    6. College Major - 대학에서의 전공을 선택합니다. 전 컴퓨터 공학과가 없어서 컴퓨터 사이언스를 택했죠.
    7. College Major Description - 전공에 대해서 설명을 적으면 될 것같습니다.
    8. Degree Program - 이수학위를 선택하면 됩니다
        Bachelors는 학사, Masters는 석사, Doctorate는 박사입니다.
    9. Graduation Year - 졸업년도를 입력합니다.
    10. Graduation Month - 말 안해도 아시겠죠^^?
    11. Clubs / Organizations - 다른 클럽에 가입한 적이 있는지 선택하는 부분입니다. 이를테면 ACM 같은..
    12. Other Clubs / Organizations - 11번에 없으면 이 곳에 적으면 됩니다.
    13. School - 학교를 입력해 봅시다. 제가 다니는 대학교는 없었습니다. ㅠ_ㅠ 그래서 제가 입력!!
    14. Show / Hide my school
    15. GPA
    16. GPA Scale
    17. Resume - 입사지원서를 적으면 됩니다. 사이트에서 성적이 좋으면 취업으로 연결될 수 있습니다^^

  4. 입력을 마치시고 Submit 버튼을 누르시면 입력한 정보가 정확한지 전체적으로 보여주고 등록할 것인지 물어봅니다. 여기서 Confirm 버튼을 누르면 처음 등록한 이메일로 계정확인 메일이 발송됩니다. 이메일로 들어가서 계정을 활성화 시킵시다^^. 자 그럼 대망의 TopCoder 가입이 완료되었네요.

  5. 경쟁은 http://www.topcoder.com/ 에 들어가시면 Compete 라는 분류가 있을 겁니다. 그것을 선택하시면 왼쪽 Competition 메뉴에서 원하는 경쟁 메뉴를 선택합니다. Algorithm을 예로 들면 Launch Arena를 선택하면 JDK 1.42 버젼이 깔리게 되며, Java Web Start로 자바 어플리케이션이 실행되게 됩니다.


    짜잔!~
    TopCoder


  6. Username과 Password에 입력했던 내용을 입력하고 "Go" 버튼을 눌러 로그인합시다!! 그리고 창이 바뀌면 Practice Rooms 를 선택합니다.
    Practice

  7. 그럼 문제를 선택해야 하겠죠^^? Active Contest는 컨테스트가 벌어지고 있을 때, 참여하면 되는 것으로 알고 있습니다. 아직 저는 해본 적이 없어서 잘 모르겠네요. 문제를 선택해 봅시다.
    PracticeSelect

  8. 문제를 선택하면 레벨을 선택합니다. 전 250을 선택했습니다. 쉬운 것일까요? 어려운 것일까요?
    Level


  9. Summary 버튼을 클릭하면 드디어 문제 창이 뜹니다. 이제 코딩만 남았군요!! 문제를 읽고 코딩합시다!! 다른 대회들과 같게 코딩을 다 한 뒤에는 Submit 버튼으로 소스를 서브밋하면 됩니다. 언어도 선택할 수 있고, 코드를 저장할 수도 있나 보네요. 아주 많이 편리합니다^^ 그럼 이제 경쟁의 세계로 빠져봅시다~
    Problem
크리에이티브 커먼즈 라이센스
Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"TopCoder" 분류의 다른 글

TopCoder - Tournament - Inv 2001 R1 (0)2008/04/05
TopCoder - Tournament - Inv 2001 R1 (4)2008/03/05
2008/02/18 09:00 2008/02/18 09:00
TAG Contest, TopCoder
받은 트랙백이 없고, 댓글이 없습니다.

트랙백 주소 :: http://www.filewiki.net/tc/trackback/11

댓글을 달아 주세요

◀ 이전페이지 1 다음페이지 ▶
블로그 이미지
First Sensation 귀차니스트
rss
  • 관리자
  • 글쓰기

카테고리

  • 전체 (110)
    • Computer (3)
    • Language (14)
    • Reverse Engineering (1)
    • Algorithm (9)
    • TopCoder (3)
    • Library (2)
    • Programming (19)
    • Programming Tip (9)
    • PSP-Programming (10)
    • Program (5)
    • Small Talk (31)
    • Document (4)

최근에 올라온 글

  • Gradient 작성중에 있습.... (3)
  • 게임&인터랙티브 애플리....
  • 한게임 자동테트리스 Ve.... (24)
  • Intel 64 And IA32 Arch.... (2)
  • 한게임 자동테트리스 Ve.... (24)

최근에 달린 댓글

  • 다운어덯게 받아요. difl 2008
  • 멋있네요 ㅎㅎ. 준호씨 2008
  • ^^; 그러셨군요.. 사실 동영.... 귀차니스트 2008
  • ㅋㅋ 속도 튜닝의 무서움 ㅜ.... 귀차니스트 2008
  • 관리자만 볼 수 있는 댓글입.... 비밀방문자 2008

달력

«   2009/01   »
일 월 화 수 목 금 토
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

링크

  • kkamagui 프로그래밍 세상.
  • 류광의 번역 이야기.
  • 서광열의 프로그래밍 언....
  • 준호씨의 블로그.
  • 최익필의 이름없는 블로그.
  • 위키는 귀차니즘.

최근에 받은 트랙백

  • 궁극의 예외처리. 이름없는 블로그 2008
  • Maximum sum. 티스토리 지점 2008

글 보관함

  • 2008/12 (1)
  • 2008/11 (4)
  • 2008/10 (2)
  • 2008/09 (3)
  • 2008/08 (5)

태그목록

  • Xtream Toolkit Pro
  • Call By Value
  • 수학
  • .Net
  • boost::shared_ptr
  • multimap
  • 분양
  • 부트로더
  • boost::array
  • LGT
  • 후위연산
  • Inheritance
  • 파티션
  • Chaos
  • Image Processing
  • SSD
  • Component
  • Mouse Message
  • interface design guide
  • 계발
  • Call By Reference
  • Newline
  • High Precision Event Timer
  • Freetype2
  • C#
  • 폰트
  • Assassin's Creed
  • Ribbon UI
  • ostream_iterator
  • Borland
지역로그 : 태그 : 방명록 : 관리자 : 글쓰기
귀차니스트’s Blog is powered by Textcube 1.7.5 : Risoluto / Designed by DesignNia.net