'ACM'에 해당되는 글 6건

  1. 2008/02/17 귀차니스트 The Skyline Problem (2)
  2. 2008/02/17 귀차니스트 Ecological Bin Packing
  3. 2008/02/17 귀차니스트 LCD Display (3)
  4. 2008/02/17 귀차니스트 3n+1 Problem
  5. 2008/02/17 귀차니스트 The Blocks Problem
◀ 이전페이지 1 2 다음페이지 ▶

3n+1 Problem

Algorithm/Acm 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>
    3. int Calculation( int number );
    5. int main( int argc, char **argv )
    6. {
    7.     int StInput, EnInput;
    8.     int StartNum, EndNum, RetValue;
    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. }
    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

"Algorithm / Acm" 분류의 다른 글

The Blocks Problem (0)2008/02/17
Ecological Bin Packing (0)2008/02/17
The Skyline Problem (2)2008/02/17
Maximum Sum (0)2008/02/17
LCD Display (3)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , ,
받은 트랙백이 없고, 댓글이 없습니다.

댓글을 달아 주세요

The Blocks Problem

Algorithm/Acm 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>
    5. using namespace std;
    7. deque< int > *table;
    8. int *link;
    9. int BlockNum;
    11. void returning( int index );
    12. void moving( int index1, int index2 );
    13. void piling( int index1, int index2 );
    14. void print();
    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
    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
    56.                         returning( b );
    57.                         piling( a, b );
    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. }
    73. void returning( int index )
    74. {
    75.     int BlockIndex = link[ index ];
    76.     while( table[ BlockIndex ].back() != index ) {
    78.         int Block = table[ BlockIndex ].back();
    79.         table[ Block ].push_back( Block );
    80.         table[ BlockIndex ].pop_back();
    81.         link[ Block ] = Block;
    82.     }
    83. }
    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. }
    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. }
    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

"Algorithm / Acm" 분류의 다른 글

3n+1 Problem (0)2008/02/17
Ecological Bin Packing (0)2008/02/17
The Skyline Problem (2)2008/02/17
Maximum Sum (0)2008/02/17
LCD Display (3)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , , ,
받은 트랙백이 없고, 댓글이 없습니다.

댓글을 달아 주세요

Maximum Sum

Algorithm/Acm 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>
    3. using namespace std;
    5. short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };
    7. int main( int argc, char **argv )
    8. {
    9.     int MaxSum = -999999;
    10.     int size;
    12.     cin >> size;
    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.     }
    20.     for( int StartI = 1; StartI <= size; StartI++ ) {
    21.         for( int StartJ = 1; StartJ <= size; StartJ++ ) {
    23.             for( int EndI = StartI; EndI <= size; EndI++ ) {
    24.                 for( int EndJ = StartJ; EndJ <= size; EndJ++ ) {
    26.                     short RectangleSum = Matrix[ StartI ][ StartJ ][ EndI ][ EndJ - 1 ];
    27.                     short LineSum = Matrix[ StartI ][ EndJ ][ EndI - 1 ][ EndJ ];
    29.                     short NewLineSum = LineSum + Matrix[ EndI ][ EndJ ][ EndI ][ EndJ ];
    30.                     Matrix[ StartI ][ EndJ ][ EndI ][ EndJ ] = NewLineSum;
    32.                     short NewRectangleSum = RectangleSum + NewLineSum;
    33.                     Matrix[ StartI ][ StartJ ][ EndI ][ EndJ ] = NewRectangleSum;
    35.                     if( MaxSum < NewRectangleSum )
    36.                         MaxSum = NewRectangleSum;
    37.                 }
    38.             }
    40.         }
    41.     }
    43.     cout << MaxSum;
    45.     return 0;
    46. }

크리에이티브 커먼즈 라이센스
Creative Commons License

"Algorithm / Acm" 분류의 다른 글

The Blocks Problem (0)2008/02/17
3n+1 Problem (0)2008/02/17
Ecological Bin Packing (0)2008/02/17
The Skyline Problem (2)2008/02/17
LCD Display (3)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , , ,
트랙백은 하나, 댓글이 없습니다.

댓글을 달아 주세요

The Skyline Problem

Algorithm/Acm 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>
    3. short Skyline[ 10001 ] = { 0, };
    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. }
    13. void PrintHeight()
    14. {
    15.     int LastHeight = 0;
    16.     int CurrentHeight;
    17.     bool IsFirst = true;
    19.     for( int i = 0; i < 10001; ++i ) {
    21.         CurrentHeight = Skyline[ i ];
    23.         if( CurrentHeight != LastHeight ) {
    25.             if( IsFirst )
    26.                 IsFirst = false;
    27.             else {
    28.                 std::cout << " ";
    29.             }
    31.             std::cout << i << " " << CurrentHeight;
    33.             LastHeight = CurrentHeight;
    34.         }
    35.     }
    37.     std::cout << std::endl;
    38. }
    40. int main( int argc, char **argv )
    41. {
    42.     int Left, Height, Right;
    44.     while( std::cin >> Left >> Height >> Right ) {
    45.         InsertHeight( Left, Right, Height );
    46.     }
    48.     PrintHeight();
    50.     return 0;
    51. }



크리에이티브 커먼즈 라이센스
Creative Commons License

"Algorithm / Acm" 분류의 다른 글

The Blocks Problem (0)2008/02/17
3n+1 Problem (0)2008/02/17
Ecological Bin Packing (0)2008/02/17
Maximum Sum (0)2008/02/17
LCD Display (3)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , , ,
받은 트랙백이 없고, 댓글 2개가 달렸습니다.

댓글을 달아 주세요

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

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

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

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

Ecological Bin Packing

Algorithm/Acm 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>
    5. struct SortNode {
    6.     int Total;
    7.     std::string OutputStr;
    8. };
    10. bool operator < ( const SortNode &Left, const SortNode &Right )
    11. {
    12.     size_t LeftLength = Left.OutputStr.length();
    13.     size_t RightLength = Right.OutputStr.length();
    15.     if( ( Left.Total == Right.Total ) && ( LeftLength == RightLength ) )    {
    16.         for( int i = 0; i < 3; i++ )    {
    18.             char LeftChar = Left.OutputStr[ i ];
    19.             char RightChar = Right.OutputStr[ i ];
    21.             if( LeftChar == RightChar )
    22.                 continue;
    23.             else if( LeftChar > RightChar )
    24.                 return true;
    25.             else
    26.                 return false;
    27.         }
    28.     }
    30.     return ( Left.Total > Right.Total );
    31. }
    33. int main( int argc, char **argv )
    34. {
    35.     unsigned int Bottle[ 9 ] = { 0, };
    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;
    40.         SortNode Temp;
    41.         Temp.Total = 0;
    42.         BackTracking.push( Temp );
    44.         while( true )   {
    46.             SortNode ProcessNode = BackTracking.top();
    47.             BackTracking.pop();
    49.             size_t ProcessStrLength = ProcessNode.OutputStr.length();
    51.             if( ProcessStrLength == 3 ) {
    52.                 std::cout << ProcessNode.OutputStr << " " << ProcessNode.Total << std::endl;
    53.                 break;
    54.             }
    56.             ProcessStrLength *= 3;
    58.             if( ProcessNode.OutputStr.find( "C" ) == UINT_MAX ) {
    59.                 SortNode CNode( ProcessNode );
    61.                 CNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 1 ] );
    62.                 CNode.OutputStr += "C";
    64.                 BackTracking.push( CNode );
    65.             }
    67.             if( ProcessNode.OutputStr.find( "G" ) == UINT_MAX ) {
    68.                 SortNode GNode( ProcessNode );
    70.                 GNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 2 ] );
    71.                 GNode.OutputStr += "G";
    73.                 BackTracking.push( GNode );
    74.             }
    76.             if( ProcessNode.OutputStr.find( "B" ) == UINT_MAX ) {
    77.                 SortNode BNode( ProcessNode );
    79.                 BNode.Total += ( Bottle[ ProcessStrLength + 1 ] + Bottle[ ProcessStrLength + 2 ] );
    80.                 BNode.OutputStr += "B";
    82.                 BackTracking.push( BNode );
    83.             }
    84.         }
    85.     }
    87.     return 0;
    88. }



크리에이티브 커먼즈 라이센스
Creative Commons License

"Algorithm / Acm" 분류의 다른 글

The Blocks Problem (0)2008/02/17
3n+1 Problem (0)2008/02/17
The Skyline Problem (2)2008/02/17
Maximum Sum (0)2008/02/17
LCD Display (3)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , , ,
받은 트랙백이 없고, 댓글이 없습니다.

댓글을 달아 주세요

◀ 이전페이지 1 2 다음페이지 ▶