#UVa:10409-Die Game

將骰子的各面狀態記住(上面1,北面2,西面3,每面與其對面和為7),接著照著指示去轉動即可得解。

C++(0.000)

/*******************************************************/
/* UVa 10409 Die Game                                  */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

struct Dice{
  int top, bottom;
  int north, south;
  int east, west;

  Dice(){
    top = 1;
    north = 2;
    west = 3;
    bottom = 6;
    south = 5;
    east = 4;
  }

  void rotate(string command){
    if( command == "north" ){
      swap(top, north);
      swap(south, top);
      swap(bottom, south);
    }
    else if( command == "south" ){
      swap(top, south);
      swap(north, top);
      swap(bottom, north);
    }
    else if( command == "west" ){
      swap(top, west);
      swap(east, top);
      swap(bottom, east);
    }
    else if( command == "east" ){
      swap(top, east);
      swap(west, top);
      swap(bottom, west);
    }
  }

};



int main(){
  int commandNumber;
  while( scanf("%d", &commandNumber) != EOF && commandNumber != 0 ){
    Dice dice;
    for( int i = 0 ; i < commandNumber ; ++i ){
      string command;
      cin >> command;
      dice.rotate(command);
    }

    printf("%d\n", dice.top);
  }

  return 0;
}

#UVa:729-The Hamming Distance Problem

利用C++中的next_permutation()去列舉所有排列即可。

C++(0.000)

/*******************************************************/
/* UVa 729 The Hamming Distance Problem                */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/27                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int numberOfDataset;
  while( scanf("%d", &numberOfDataset) != EOF ){
    for( int testNumber = 0 ; testNumber < numberOfDataset ; ++testNumber ){
      if( testNumber > 0 ){
        printf("\n");
      }

      int N, H;
      scanf("%d%d", &N, &H);

      string s;
      for( int i = 0 ; i < N-H ; ++i ){
        s += '0';
      }

      for( int i = 0 ; i < H ; ++i ){
        s += '1';
      }

      do{
        printf("%s\n", s.c_str());
      } while( next_permutation(s.begin(), s.end()) );
    }
  }

  return 0;
}

#UVa:793-Network Connections

將每台電腦個別當作一組,接著將有相連的電腦將他們兩組整合成一組。要判斷是否相連只要判斷是否同組即可得解。

C++(0.210)

/*******************************************************/
/* UVa 793 Network Connections                         */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/23                                 */
/*******************************************************/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  int testcase;
  while( scanf("%d", &testcase) != EOF ){

    for( int caseNumber = 0 ; caseNumber < testcase ; ++caseNumber ){
      if( caseNumber >= 1 ){
        printf("\n");
      }

      int numberOfComputers;
      scanf("%d", &numberOfComputers);

      vector<int> connected(numberOfComputers+1);
      for( int i = 1 ; i <= numberOfComputers ; ++i ){
        connected[i] = i;
      }


      int rightAnswer = 0, wrongAnswer = 0;
      string input;
      cin.ignore();
      while( getline(cin, input) && input != "" ){

        stringstream ss(input);
        char type;
        int computerI, computerJ;
        ss >> type >> computerI >> computerJ;

        if( type == 'c' ){ 
          int groupI = connected[computerI], groupJ = connected[computerJ];
          for( int i = 1 ; i <= numberOfComputers ; ++i ){
            if( connected[i] == groupI || connected[i] == groupJ ){
              connected[i] = min(groupI, groupJ);
            }
          }
        }
        else if( type == 'q' ){
          if( connected[computerI] != connected[computerJ] ){
            ++wrongAnswer;
          }
          else{
            ++rightAnswer;
          }
        }
      }

      printf("%d,%d\n", rightAnswer, wrongAnswer);
    }
  }

  return 0;
}

#UVa:567-Risk

利用Floyd-Warshall演算法找出每個節點到每個節點之間的最短路徑即可。

C++(0.040)

/*******************************************************/
/* UVa 567 Risk                                        */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  const int INFINITY = 30;

  int X;
  int caseNumber = 0;
  while( scanf("%d", &X) != EOF ){
    vector< vector<int> > map(21, vector<int>(21, INFINITY));
    for( int i = 1 ; i <= 19 ; ++i ){
      int J;
      for( int j = 0 ; j < X ; ++j ){
        scanf("%d", &J);
        map[i][J] = map[J][i] = 1;
      }

      if( i < 19 ){
        scanf("%d", &X);
      }
    }

    for( int k = 1 ; k <= 20 ; ++k ){
      for( int i = 1 ; i <= 20 ; ++i ){
        for( int j = 1 ; j <= 20 ; ++j ){
          if( map[i][k] + map[k][j] < map[i][j] ){
            map[i][j] = map[i][k] + map[k][j];
          }
        }
      }
    }

    printf("Test Set #%d\n", ++caseNumber);

    int N;
    scanf("%d", &N);
    for( int i = 0 ; i < N ; ++i ){
      int A, B;
      scanf("%d%d", &A, &B);
      printf("%2d to %2d: %d\n", A, B, map[A][B]);
    }
    printf("\n");

  }
  return 0;
}

#UVa:10450-World Cup Noise

剛開始如果長度是2的話有0和1的可能,接著對於下一次的可能性,如果尾巴是0則可增加0或1(…00, …01),而如果尾巴是1則只能增加0(…10),可以得到其成長為一個費氏數列的形式。

C++(0.000)

/*******************************************************/
/* UVa 10450 World Cup Noise                           */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  long long fib[60] = {1, 2};
  for( int i = 2 ; i <= 51 ; ++i ){
    fib[i] = fib[i-1] + fib[i-2];
  }

  int caseCount;
  while( scanf("%d", &caseCount) != EOF ){
    for( int caseNumber = 1 ; caseNumber <= caseCount ; ++caseNumber ){
      int n;
      scanf("%d", &n);
      printf("Scenario #%d:\n", caseNumber);
      printf("%lld\n\n", fib[n]);
    }
  }
  return 0;
}

#UVa:536-Tree Recovery

由於前序是(中,左,右),而中序是(左,中,右),故利用前序前頭遇到的字可以知道在中序中這個字會將以它為root的子樹左右兩側分割開來,藉以知道以此字為root的左右子樹的區段為何,利用這樣的切割即可輸出成後序的格式。

C++(0.000)

/*******************************************************/
/* UVa 536 Tree Recovery                               */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/28                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int postOrder(const string& preord, const string &inord, int preI, int inLow, int inHigh){
  if( inLow >= inHigh ){
    return preI;
  }

  for( int i = inLow ; i < inHigh ; ++i ){
    if( inord[i] == preord[preI] ){
      // left, right, mid
      preI = postOrder(preord, inord, preI+1, inLow, i);
      preI = postOrder(preord, inord, preI, i+1, inHigh);
      printf("%c", inord[i]);
      break;
    }
  }

  return preI;
}

int main(){
  string preord, inord;
  while( cin >> preord >> inord ){
    postOrder(preord, inord, 0, 0, inord.length());
    printf("\n");
  }
  return 0;
}

#UVa:11388-GCD LCM

基本上符合的答案就會是\(a = G, b = L\),原因如下:

先證明什麼時候會有解,由於\(G | a, b\)且\(a, b | L\),故至少\(G | a, b | L\),亦指在有解的情況下至少G要能整除L。

那在有解的情況下a如果要最小該會是多少呢?由於\(G | a\),故a為G的某個倍數,而其中最小的就為G。那在\(a = G\)的情況下一定會有解嗎?由於\(G \times L = a \times b\),而\(a = G\),所以\(G \times L = G \times b\),整理一下可得\(b = L\),所以在有解的情況下最符合的答案即是\((a, b) = (G, L)\)。

C++(0.000)

/*******************************************************/
/* UVa 11388 GCD LCM                                   */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/28                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int caseCount;
  while( scanf("%d", &caseCount) != EOF ){
    for( int caseNumber = 0 ; caseNumber < caseCount ; ++caseNumber ){
      int G, L;
      scanf("%d%d", &G, &L);

      if( L % G == 0 ){
        printf("%d %d\n", G, L);
      }
      else{
        printf("-1\n");
      }
    }
  }
  return 0;
}

#UVa:10000-Longest Paths

使用任一種單一起點的最短路徑演算法,將更新的部分改為比較長才更新即可得解。

P.S. 程式碼部分使用的是SPFA演算法。

C++(0.010)

/*******************************************************/
/* UVa 10000 Longest Paths                             */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/28                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int findLongestPath( bool map[105][105], vector<int> &distance, int s, int n ){
  distance[s] = 0;
  queue<int> next;
  vector<bool> inQueue(n+1, false);
  next.push(s);

  while( !next.empty() ){
    int current = next.front();
    next.pop();
    inQueue[current] = false;

    for( int i = 1 ; i <= n ; ++i ){
      if( map[current][i] && distance[current]+1 > distance[i] ){
        distance[i] = distance[current] + 1;
        if( !inQueue[i] ){
          next.push(i);
          inQueue[i] = true;
        }
      }
    }
  }

  int maxIndex = 1;
  for( int i = 2 ; i <= n ; ++i ){
    if( distance[i] > distance[maxIndex] ){
      maxIndex = i;
    }
  }

  return maxIndex;
}

int main(){
  int n;
  int caseNumber = 0;
  while( scanf("%d", &n) != EOF && n != 0 ){
    int s;
    scanf("%d", &s);

    bool map[105][105] = {false};
    int p, q;
    while( scanf("%d%d", &p, &q) != EOF && p != 0 && q != 0 ){
      map[p][q] = true;
    }

    vector<int> distance(n+1, 0);
    int final = findLongestPath(map, distance, s, n);
    printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n", ++caseNumber, s, distance[final], final);
  }

  return 0;
}

#UVa:465-Overflow

用比較高精度的數值型態儲存去做即可。

P.S. 如果用double型態去做,為了輸出正常,可能還是必須先用字串儲存。

C++(0.000)

/*******************************************************/
/* UVa 465 Overflow                                    */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/28                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <climits>
#include <string>
#include <sstream>
using namespace std;

int main(){
  double a, b;
  string aString, bString, op;
  while( cin >> aString >> op >> bString ){
    stringstream ss(aString);
    ss >> a;
    ss.clear();
    ss.str(bString);
    ss >> b;

    printf("%s %s %s\n", aString.c_str(), op.c_str(), bString.c_str() );
    if( a > INT_MAX ){
      printf("first number too big\n");
    }

    if( b > INT_MAX ){
      printf("second number too big\n");
    }

    if( (op == "+" && a + b > INT_MAX) ||
        (op == "*" && a * b > INT_MAX) ){
      printf("result too big\n");
    }
  }
  return 0;
}

#UVa:661-Blowing Fuses

照著題目要求去紀錄每次開關所用的電流量以及裝置開關狀態即可得解。

C++(0.000)

/*******************************************************/
/* UVa 661 Blowing Fuses                               */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/28                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int n, m, c;
  int caseNumber = 0;
  while( scanf("%d%d%d", &n, &m, &c) != EOF &&
         ( n != 0 || m != 0 || c != 0 ) ){
    int consumption[25] = {0};
    for( int i = 1 ; i <= n ; ++i ){
      scanf("%d", &consumption[i]);
    }         

    bool isTurnOn[25] = {false};
    int nowUsed = 0, maxUsed = 0;
    int operation;
    for( int i = 0 ; i < m ; ++i ){
      scanf("%d", &operation);

      if( isTurnOn[operation] ){
        nowUsed -= consumption[operation];
      }
      else{
        nowUsed += consumption[operation];
        maxUsed = max(maxUsed, nowUsed);
      }

      isTurnOn[operation] = !isTurnOn[operation];
    }

    printf("Sequence %d\n", ++caseNumber);
    if( maxUsed > c ){
      printf("Fuse was blown.\n");
    }
    else{
      printf("Fuse was not blown.\n");
      printf("Maximal power consumption was %d amperes.\n", maxUsed);
    }
    printf("\n");
  }
  return 0;
}
共 38 頁 1 2 3 4 38