블로그는 귀차니즘

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

3n+1 Problem

Algorithm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36 
  2.  의   경   : 처음으로 나오는 쉬운 기초적인 문제입니다. 하지만 체크해야될 조건이 있습니다. 바로 입력 숫자의 크기가 서로 바뀔 수 있다는 점이죠.
    입력 방식이 10 20과 같이 입력될 때에는 괜찮으나 20 10과 같이 입력될 때에는 체크를 꼭 해주어야 합니다.
  3. 소스
    100.c (Language : c)
    1. #include <stdio.h>
    2.  
    3. int Calculation( int number );
    4.  
    5. int main( int argc, char **argv )
    6. {
    7.     int StInput, EnInput;
    8.     int StartNum, EndNum, RetValue;
    9.  
    10.     int i, MaxCycle;
    11.     while( scanf( "%d %d", &StInput, &EnInput ) == 2 ) {
    12.         if( StInput > EnInput ) {
    13.             StartNum = EnInput;
    14.             EndNum = StInput;
    15.         }
    16.         else {
    17.             StartNum = StInput;
    18.             EndNum = EnInput;
    19.         }
    20.         MaxCycle = 0;
    21.         for( i = StartNum; i <= EndNum; i++ ) {
    22.             RetValue = Calculation( i );
    23.             if( RetValue > MaxCycle )
    24.                 MaxCycle = RetValue;
    25.         }
    26.         printf( "%d %d %d\n", StInput, EnInput, MaxCycle );
    27.     }
    28.     return 0;
    29. }
    30.  
    31. int Calculation( int number )
    32. {
    33.     int CycleLength;
    34.     for( CycleLength = 1; number != 1; CycleLength++ ) {
    35.         if( number == 1 )
    36.             break;
    37.         if( number % 2 == 1 ) {
    38.             number = number * 3 + 1;
    39.         }
    40.         else {
    41.             number = number >> 1;
    42.         }
    43.     }
    44.     return CycleLength;
    45. }


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

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)2008/06/09
The Blocks Problem (0)2008/02/17
Maximum Sum (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG ACM, ACM-ICPC, C, ICPC
받은 트랙백이 없고, 댓글이 없습니다.

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

댓글을 달아 주세요

The Blocks Problem

Algorithm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37
  2.  의   견   : 명령어 파싱에 대한 연습을 하는 문제라고 생각합니다. 한 가지 언어 특성상 Pointer를 이용한 List 형식으로 코드를 작성할 때 구현에 있어 난이도가 조금 있을 것입니다. 그리하여 STL을 부분적으로 사용했었고
    , 아마 지금 재작성 한다면 table을 비롯하여 모든 부분을 STL으로 작성할 것 같습니다.
  3. 소스
    101.cpp (Language : cpp)
    1. #include <iostream>
    2. #include <deque>
    3. #include <string>
    4.  
    5. using namespace std;
    6.  
    7. deque< int > *table;
    8. int *link;
    9. int BlockNum;
    10.  
    11. void returning( int index );
    12. void moving( int index1, int index2 );
    13. void piling( int index1, int index2 );
    14. void print();
    15.  
    16. int main( int argc, char **argv )
    17. {
    18.     cin >> BlockNum;
    19.     if( 0 < BlockNum && BlockNum < 25 ) {
    20.         table = new deque< int >[ BlockNum ];
    21.         link = new int[ BlockNum ];
    22.         for( int i = 0; i < BlockNum; i++ ) {
    23.             link[ i ] = i;
    24.             table[ i ].push_back( i );
    25.         }
    26.         string cmd1;
    27.         int a;
    28.         string cmd2;
    29.         int b;
    30.         while( true ) {
    31.             cin >> cmd1;
    32.             if( cmd1 == "quit" ) {
    33.                 print();
    34.                 break;
    35.             }
    36.             cin >> a >> cmd2 >> b;
    37.             if( a != b && link[ a ] != link[ b ] && 0 <= a && a < BlockNum && 0 <= b && b < BlockNum ) {
    38.                 if( cmd1 == "move" ) {
    39.                     if( cmd2 == "onto" ) {
    40.                         // move A onto B
    41.  
    42.                         returning( a );
    43.                         returning( b );
    44.                         moving( a, b );
    45.                     }
    46.                     else if( cmd2 == "over" ) {
    47.                         // move A over B
    48.                         returning( a );
    49.                         moving( a, b );
    50.                     }
    51.                 }
    52.                 else if( cmd1 == "pile" ) {
    53.                     if( cmd2 == "onto" ) {
    54.                         // pile A onto B
    55.  
    56.                         returning( b );
    57.                         piling( a, b );
    58.  
    59.                     }
    60.                     else if( cmd2 == "over" ) {
    61.                         // pile A over B
    62.                         piling( a, b );
    63.                     }
    64.                 }
    65.             }
    66.         }
    67.         delete [] table;
    68.         delete [] link;
    69.     }
    70.     return 0;
    71. }
    72.  
    73. void returning( int index )
    74. {
    75.     int BlockIndex = link[ index ];
    76.     while( table[ BlockIndex ].back() != index ) {
    77.  
    78.         int Block = table[ BlockIndex ].back();
    79.         table[ Block ].push_back( Block );
    80.         table[ BlockIndex ].pop_back();
    81.         link[ Block ] = Block;
    82.     }
    83. }
    84.  
    85. void moving( int index1, int index2 )
    86. {
    87.     int a = link[ index1 ];
    88.     int b = link[ index2 ];
    89.     table[ b ].push_back( table[ a ].back() );
    90.     table[ a ].pop_back();
    91.     link[ index1 ] = link[ index2 ];
    92. }
    93.  
    94. void piling( int index1, int index2 )
    95. {
    96.     deque< int > temp;
    97.     int BlockIndex1 = link[ index1 ];
    98.     while( table[ BlockIndex1 ].back() != index1 ) {
    99.         temp.push_back( table[ BlockIndex1 ].back() );
    100.         table[ BlockIndex1 ].pop_back();
    101.     }
    102.     temp.push_back( table[ BlockIndex1 ].back() );
    103.     table[ BlockIndex1 ].pop_back();
    104.     int BlockIndex2 = link[ index2 ];
    105.     while( !temp.empty() ) {
    106.         int linkTemp = temp.back();
    107.         temp.pop_back();
    108.         table[ BlockIndex2 ].push_back( linkTemp );
    109.         link[ linkTemp ] = link[ index2 ];
    110.     }
    111. }
    112.  
    113. void print()
    114. {
    115.     deque< int >::iterator prt;
    116.     for( int i = 0; i < BlockNum; i++ ) {
    117.         cout << i << ":";
    118.         prt = table[ i ].begin();
    119.         while( prt != table[ i ].end() ) {
    120.             cout << " " << *prt;
    121.             prt++;
    122.         }
    123.         cout << endl;
    124.     }
    125. }
크리에이티브 커먼즈 라이센스
Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)2008/06/09
3n+1 Problem (0)2008/02/17
Maximum Sum (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG ACM, ACM-ICPC, C++, ICPC, STL
받은 트랙백이 없고, 댓글이 없습니다.

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

댓글을 달아 주세요

Maximum Sum

Algorithm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
  2.  의   견   : Dynamic Programming을 배웠고, 사용한다면 쉬운 문제, 하지만 단순히 for 루프를 이용하여 6중 for 루프를 사용한다면 time exceed를 면할 수 없을 것입니다.
    DP 방법은 배열을 사용할 때 [ 시작 x 인덱스 ][ 시작 y 인덱스 ][ 끝 x 인덱스 ][ 끝 y 인덱스 ]로 의미를 부여하여 대상 값들을 계산 후 업데이트하고 재사용합니다.
  3. 소스
    108.cpp (Language : cpp)
    1. #include <iostream>
    2.  
    3. using namespace std;
    4.  
    5. short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };
    6.  
    7. int main( int argc, char **argv )
    8. {
    9.     int MaxSum = -999999;
    10.     int size;
    11.  
    12.     cin >> size;
    13.  
    14.     for( int i = 1; i <= size; i++ ) {
    15.         for( int j = 1; j <= size; j++ ) {
    16.             cin >> Matrix[ i ][ j ][ i ][ j ];
    17.         }
    18.     }
    19.  
    20.     for( int StartI = 1; StartI <= size; StartI++ ) {
    21.         for( int StartJ = 1; StartJ <= size; StartJ++ ) {
    22.  
    23.             for( int EndI = StartI; EndI <= size; EndI++ ) {
    24.                 for( int EndJ = StartJ; EndJ <= size; EndJ++ ) {
    25.  
    26.                     short RectangleSum = Matrix[ StartI ][ StartJ ][ EndI ][ EndJ - 1 ];
    27.                     short LineSum = Matrix[ StartI ][ EndJ ][ EndI - 1 ][ EndJ ];
    28.  
    29.                     short NewLineSum = LineSum + Matrix[ EndI ][ EndJ ][ EndI ][ EndJ ];
    30.                     Matrix[ StartI ][ EndJ ][ EndI ][ EndJ ] = NewLineSum;
    31.  
    32.                     short NewRectangleSum = RectangleSum + NewLineSum;
    33.                     Matrix[ StartI ][ StartJ ][ EndI ][ EndJ ] = NewRectangleSum;
    34.  
    35.                     if( MaxSum < NewRectangleSum )
    36.                         MaxSum = NewRectangleSum;
    37.                 }
    38.             } 
    39.  
    40.         }
    41.     }
    42.  
    43.     cout << MaxSum;
    44.  
    45.     return 0;
    46. }
    47.  

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

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)2008/06/09
3n+1 Problem (0)2008/02/17
The Blocks Problem (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG ACM, ACM-ICPC, C++, DP, Dynamic Programming
트랙백은 하나, 댓글이 없습니다.

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

  1. Subject: Maximum sum

    Tracked from 티스토리 지점 2008/04/09 14:22  삭제

    문제 페이지 귀차니스트 님이 푸신 답을 조금 개선해 봤다. 자동채점 기준으로 수행 시간이 0.4초 정도 줄었다. #include <stdio.h> short m[101][101][101][101]={}; int main(void) { int rsum, lsum, nrsm, nlsm; int si, sj, ei, ej, size,i,j; int maxsum = -2000000; scanf("%d", &size); for (i=1; i<=size; i+..

댓글을 달아 주세요

The Skyline Problem

Algorithm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41
  2.  의   견   : 일일이 하나의 경우에 대해서 앞의 모든 경우를 검사하는 것이 아님을 가르쳐주는 문제. 방법은 배열을 선언, 입력이 들어올 때마다 배열을 범위로 선택 값을 갱신합니다. 출력시에는 다른 지점의 인덱스만 출력하면 됩니다.
  3. 소스
    105.cpp (Language : cpp)
    1. #include <iostream>
    2.  
    3. short Skyline[ 10001 ] = { 0, };
    4.  
    5. void InsertHeight( int Left, int Right, int Height )
    6. {
    7.     for( int i = Left; i < Right; ++i ) {
    8.         if( Skyline[ i ] < Height )
    9.             Skyline[ i ] = Height;
    10.     }
    11. }
    12.  
    13. void PrintHeight()
    14. {
    15.     int LastHeight = 0;
    16.     int CurrentHeight;
    17.     bool IsFirst = true;
    18.  
    19.     for( int i = 0; i < 10001; ++i ) {
    20.  
    21.         CurrentHeight = Skyline[ i ];
    22.  
    23.         if( CurrentHeight != LastHeight ) {
    24.  
    25.             if( IsFirst )
    26.                 IsFirst = false;
    27.             else {
    28.                 std::cout << " ";
    29.             }
    30.  
    31.             std::cout << i << " " << CurrentHeight;
    32.  
    33.             LastHeight = CurrentHeight;
    34.         }
    35.     }
    36.  
    37.     std::cout << std::endl;
    38. }
    39.  
    40. int main( int argc, char **argv )
    41. {
    42.     int Left, Height, Right;
    43.  
    44.     while( std::cin >> Left >> Height >> Right ) {
    45.         InsertHeight( Left, Right, Height );
    46.     }
    47.  
    48.     PrintHeight();
    49.  
    50.     return 0;
    51. }
    52.  



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

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)2008/06/09
3n+1 Problem (0)2008/02/17
The Blocks Problem (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG ACM, ACM-ICPC, Array, C++, ICPC
받은 트랙백이 없고, 댓글 2개가 달렸습니다.

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

댓글을 달아 주세요

  1. alex 2008/08/19 23:39  댓글주소  수정/삭제  댓글쓰기

    그냥 using namespace std 쓰시지 ...
    큰 작업도 아니고 uva 문제 푸는 정도면
    유도리 있게 코딩하시는거도 좋다고 생각합니다.

    • 귀차니스트 2008/09/21 21:21  댓글주소  수정/삭제

      아 ㅋㅋ 물론 진짜 ACM 대회를 나가게 된다면 시간이 중요하니 그럴수 있겠지만.. 평상시 일 때는 원칙을 되도록 지키고 싶어서 그렇습니다^^.

Ecological Bin Packing

Algorithm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38
  2.  의   견   : 나올 수 있는 경우의 수는 3! 개 입니다. 즉, 경우의 수가 적으므로 6가지 경우에 대한 측정값들을 수동으로 계산하여 출력할 수 있습니다. 하지만, 일반적으로 계산을 해보고자 하는 마음으로 priority_queue와 string을 짝으로 조합하여 구현을 했습니다.
  3. 소스
    103.cpp (Language : cpp)
    1. #include <iostream>
    2. #include <queue>
    3. #include <string>
    4.  
    5. struct SortNode {
    6.     int Total;
    7.     std::string OutputStr;
    8. };
    9.  
    10. bool operator < ( const SortNode &Left, const SortNode &Right )
    11. {
    12.     size_t LeftLength = Left.OutputStr.length();
    13.     size_t RightLength = Right.OutputStr.length();
    14.  
    15.     if( ( Left.Total == Right.Total ) && ( LeftLength == RightLength ) )    {
    16.         for( int i = 0; i < 3; i++ )    {
    17.  
    18.             char LeftChar = Left.OutputStr[ i ];
    19.             char RightChar = Right.OutputStr[ i ];
    20.  
    21.             if( LeftChar == RightChar )
    22.                 continue;
    23.             else if( LeftChar > RightChar )
    24.                 return true;
    25.             else
    26.                 return false;
    27.         }
    28.     }
    29.  
    30.     return ( Left.Total > Right.Total );
    31. }
    32.  
    33. int main( int argc, char **argv )
    34. {
    35.     unsigned int Bottle[ 9 ] = { 0, };
    36.  
    37.     while( std::cin >> Bottle[ 0 ] >> Bottle[ 1 ] >> Bottle[ 2 ] >> Bottle[ 3 ] >> Bottle[ 4 ] >> Bottle[ 5 ] >> Bottle[ 6 ] >> Bottle[ 7 ] >> Bottle[ 8 ] )    {
    38.         std::priority_queue< SortNode > BackTracking;
    39.  
    40.         SortNode Temp;
    41.         Temp.Total = 0;
    42.         BackTracking.push( Temp );
    43.  
    44.         while( true )   {
    45.  
    46.             SortNode ProcessNode = BackTracking.top();
    47.             BackTracking.pop();
    48.  
    49.             size_t ProcessStrLength = ProcessNode.OutputStr.length();
    50.  
    51.             if( ProcessStrLength == 3 ) {
    52.                 std::cout << ProcessNode.OutputStr << " " << ProcessNode.Total << std::endl;
    53.                 break;
    54.             }
    55.  
    56.             ProcessStrLength *= 3;
    57.  
    58.             if( ProcessNode.OutputStr.find( "C" ) == UINT_MAX ) {
    59.                 SortNode CNode( ProcessNode );
    60.  
    61.                 CNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 1 ] );
    62.                 CNode.OutputStr += "C";
    63.  
    64.                 BackTracking.push( CNode );
    65.             }
    66.  
    67.             if( ProcessNode.OutputStr.find( "G" ) == UINT_MAX ) {
    68.                 SortNode GNode( ProcessNode );
    69.  
    70.                 GNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 2 ] );
    71.                 GNode.OutputStr += "G";
    72.  
    73.                 BackTracking.push( GNode );
    74.             }
    75.  
    76.             if( ProcessNode.OutputStr.find( "B" ) == UINT_MAX ) {
    77.                 SortNode BNode( ProcessNode );
    78.  
    79.                 BNode.Total += ( Bottle[ ProcessStrLength + 1 ] + Bottle[ ProcessStrLength + 2 ] );
    80.                 BNode.OutputStr += "B";
    81.  
    82.                 BackTracking.push( BNode );
    83.             }
    84.         }
    85.     }
    86.  
    87.     return 0;
    88. }



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

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)2008/06/09
3n+1 Problem (0)2008/02/17
The Blocks Problem (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG ACM, ACM-ICPC, C++, ICPC, priority_queue
받은 트랙백이 없고, 댓글이 없습니다.

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

댓글을 달아 주세요

◀ 이전페이지 1 2 다음페이지 ▶
블로그 이미지
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)

태그목록

  • boost
  • OpenMP
  • 보안
  • istreambuf_iterator
  • iterator_traits
  • 파일입출력
  • Codegear
  • 한글표현
  • 쉘
  • TopCoder
  • ATL
  • ASM
  • RLE8
  • tr1
  • Mine Sweeper
  • Mouse Message
  • Dialog
  • 표준
  • 라이브러리
  • 6GB
  • Codejock
  • HTML Parser
  • Try
  • RLE
  • 갑
  • 분양
  • 1.35
  • Ribbon UI
  • ostream_iterator
  • Generics
지역로그 : 태그 : 방명록 : 관리자 : 글쓰기
귀차니스트’s Blog is powered by Textcube 1.7.5 : Risoluto / Designed by DesignNia.net