#UVa:10530-Guessing Game

在猜數字的過程中一直更新上界與下界,直到猜中時看看是否猜中的數字介在此範圍內即是答案。

C++(0.000)

/*******************************************************/
/* UVa 10530 Guessing Game                             */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/27                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int guessNumber;
  while( scanf("%d ", &guessNumber) != EOF && guessNumber != 0 ){
    int lowBound = 1, highBound = 10;
    string respond;
    while( getline(cin, respond) && respond != "right on" ){
      if( respond == "too high" ){
        highBound = min(highBound, guessNumber - 1 );
      }
      else if( respond == "too low" ){
        lowBound = max(lowBound, guessNumber + 1 );
      }

      scanf("%d ", &guessNumber);
    }

    if( guessNumber >= lowBound && guessNumber <= highBound ){
      printf("Stan may be honest\n");
    }
    else{
      printf("Stan is dishonest\n");
    }
  }
  return 0;
}

#UVa:482-Permutation Arrays

根據第一行的index將第二行的資料放入陣列中。

P.S. 為了保持浮點數型態,可以用字串方式儲存。

C++(0.000)

/*******************************************************/
/* UVa 482 Permutation Arrays                          */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/27                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

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

      string input;
      getline(cin, input);

      stringstream ss(input);
      vector<int> index;
      int x;
      while( ss >> x ){
        index.push_back(x);
      }

      vector<string> data(index.size()+1);
      getline(cin, input);
      ss.clear();
      ss.str(input);
      for( int i = 0 ; i < index.size() ; ++i ){
        ss >> data[index[i]];
      }

      for( int i = 1 ; i < data.size() ; ++i ){
        printf("%s\n", data[i].c_str());
      }
    }

  }
  return 0;
}

#UVa:315-Network

尋找一張圖的critical point有幾個點:利用DFS從第一個開始當作root開始建樹,只要發現連結的點尚未走過就當作自己的child,而如果是有走過的點而且不是自己的parent表示有一條back edge,利用這些自己這個點的back edge和所有自己的children能走到最遠的的祖先去紀錄整體能走到最遠的的祖先到哪裡,則那位祖先只要不是root就是其中一個critical point(因為它的children只要不經過這個點就無法連過去它parent以上的祖先)。而判斷祖先是否為critical point僅要判斷其children是否有兩個以上即可。

參考:演算法筆記-Cut Vertex

C++(0.000)

/*******************************************************/
/* UVa 315 Network                                     */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/27                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <sstream>
using namespace std;

int findCriticalPoint(bool connected[105][105], int travelNumber[], 
                      int connectToParent[], int nowTravel, int i, int parentI, int n){
  int childrenCount = 0;
  bool isCriticalPoint = false;
  int childrenCriticalCount = 0;
  travelNumber[i] = connectToParent[i] = nowTravel;

  for( int j = 1 ; j <= n ; ++j ){
    if( connected[i][j] ){
      if( travelNumber[j] > 0 && parentI != j ){ // back edge
        connectToParent[i] = min( connectToParent[i], travelNumber[j] ); 
      }
      else if( travelNumber[j] == 0 ){
        ++childrenCount;
        childrenCriticalCount += findCriticalPoint(connected, travelNumber, connectToParent, nowTravel+1, j, i, n);
        connectToParent[i] = min( connectToParent[i], connectToParent[j] );

        if( connectToParent[j] >= travelNumber[i] ){
          isCriticalPoint = true;
        }
      }
    }
  }

  if( (parentI == 0 && childrenCount > 1) || ( parentI != 0 && isCriticalPoint ) ){
    return childrenCriticalCount + 1;
  }              
  else {
    return childrenCriticalCount;
  }
}

int main(){
  int N;
  while( scanf("%d ", &N) != EOF && N != 0 ){
    bool connected[105][105] = { false };

    string line;
    while( getline(cin, line) && line != "0" ){
      stringstream ss(line);
      int mainPlace, place;
      ss >> mainPlace;
      while( ss >> place ){
        connected[mainPlace][place] = connected[place][mainPlace] = true;
      }

    }

    int travelNumber[105] = {0};
    int connectToParent[105] = {0};
    printf("%d\n", findCriticalPoint(connected, travelNumber, connectToParent, 1, 1, 0, N));
  }
  return 0;
}

#UVa:231-Testing the CATCHER

利用LIS之演算法修改為遞減版本即可得解。

C++(0.000)

/*******************************************************/
/* UVa 231 Testing the CATCHER                         */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/24                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
  int number;
  vector<int> LIS;
  int caseNumber = 0;
  while( scanf("%d", &number) != EOF ){
    if( number == -1 && LIS.size() == 0 ){
      break;
    }

    if( number == -1 ){
      if( caseNumber > 0 ){
        printf("\n");
      }
      printf("Test #%d:\n", ++caseNumber);
      printf("  maximum possible interceptions: %d\n", LIS.size());
      LIS.clear();
      continue;
    }

    if( LIS.size() == 0 || number <= LIS.back() ){
      LIS.push_back(number);
    }
    else{
      *upper_bound(LIS.begin(), LIS.end(), number, greater<int>()) = number;
    }



  }
  return 0;
}

#UVa:10104-Euclid Problem

利用輾轉相除法的特性即可得解。

如果\(A \mod B = 0\),則\(X = 0, Y = 1\);反之則反。

如果\(A \mod B \neq 0, A \ge B\),則根據遞迴式得知\(\gcd(A,B) = \gcd(A – B * \lfloor\frac{A}{B}\rfloor, B)\),由此式可得\(\gcd(A – B * \lfloor\frac{A}{B}\rfloor, B) = (A – B * \lfloor\frac{A}{B}\rfloor) \times X’ + B \times Y’ = \gcd(A,B) = AX + BY\),整理整理可得:\(AX’ – (B * \lfloor\frac{A}{B}\rfloor)X’ + BY’ = AX’ + B(Y’ – \lfloor\frac{A}{B}\rfloor X’) = AX + BY\),所以兩相對照之下可得\(X = X’, Y = (Y’ – \lfloor\frac{A}{B}\rfloor X’)\);反之則利用相同方式推導。

C++(0.060)

/*******************************************************/
/* UVa 10104 Euclid Problem                            */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/24                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int gcd(int A, int B, int &X, int &Y){
  if( A % B == 0 ){
    X = 0;
    Y = 1;
    return B;
  }

  if( B % A == 0 ){
    X = 1;
    Y = 0;
    return A;
  }

  if( A >= B ){
    int x, y;
    int value = gcd(A + B * (-A/B), B, x, y);
    X = x;
    Y = y + x * (-A/B);
    return value;
  }
  else {
    int x, y;
    int value = gcd(A, B + A * (-B/A), x, y);
    X = x + (-B/A) * y;
    Y = y;
    return value;
  }
}


int main(){
  int A, B;
  while( scanf("%d%d", &A, &B) != EOF ){
    int X, Y;
    int value = gcd(A, B, X, Y);
    printf("%d %d %d\n", X, Y, value);
  }

  return 0;
}

#UVa:11777-Automate the Grades

將成績照著公式算出總和再判斷等第即可得解。

P.S. 最後三科課堂考試成績只取前兩高的分數做平均。

C++(0.000)

/*******************************************************/
/* UVa 11777 Automate the Grades                       */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

struct Grade{
  char name;
  int score;
};

int main(){
  const Grade gradeTable[] = { {'A', 90}, {'B', 80}, {'C', 70}, {'D', 60}, {'F', 0}};
  int gradeTableSize = sizeof(gradeTable) / sizeof(Grade);

  int T;
  while( scanf("%d", &T) != EOF ){
    int term1, term2, final, attendence, classTest1, classTest2, classTest3;
    for( int caseNumber = 1 ; caseNumber <= T ; ++caseNumber ){
      scanf("%d%d%d%d%d%d%d", &term1, &term2, &final, &attendence, &classTest1, &classTest2, &classTest3);
      int score = term1 + term2 + final + attendence +
                  ( max( max(classTest1, classTest2), classTest3 ) +
                    max( min(classTest1, classTest2), min( max(classTest1, classTest2), classTest3 ) ) ) / 2;
      for( int i = 0 ; i < gradeTableSize ; ++i ){
        if( score >= gradeTable[i].score ){
          printf("Case %d: %c\n", caseNumber, gradeTable[i].name);
          break;
        }
      }
    }
  }

  return 0;
}

#UVa:11677-Alarm Clock

直接算出第二個時間與第一個時間的時間差,若為負數表示其實還相隔了一整天,再加上24個小時即可得解。

C++(0.000)

/*******************************************************/
/* UVa 11677 Alarm Clock                               */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int H1, M1, H2, M2;
  while( scanf("%d%d%d%d", &H1, &M1, &H2, &M2) != EOF &&
         (H1 != 0 || M1 != 0 || H2 != 0 || M2 != 0 )){
    int minutes = (H2 - H1) * 60 + (M2 - M1);
    if( minutes < 0 ){
      minutes += 24 * 60;
    }

    printf("%d\n", minutes);
  }
  return 0;
}

#UVa:408-Uniform Generator

利用一個布林陣列記住所有產出的隨機數,在遇到重複的隨機數時判斷是否已經讓所有0~(mod-1)的數字都出現過即可得解。

C++(0.050)

/*******************************************************/
/* UVa 408 Uniform Generator                           */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int step, mod;
  while( scanf("%d%d", &step, &mod) != EOF ){
    bool hasUsed[1000005] = {false};
    int count = 0;
    for( int i = 0; !hasUsed[i] ; i = (i + step) % mod, ++count ){
      hasUsed[i] = true;
    }

    printf("%10d%10d    ", step, mod);
    if( count == mod ){
      printf("Good Choice");
    }
    else{
      printf("Bad Choice");
    }
    printf("\n\n");

  }
  return 0;
}

#UVa:10341-Solve It

首先,由於要計算的函數先拆解每一項來看:

  • \(e^{-x}\):在\(0 \leq x \leq 1\)區間內為遞減函數
  • \(\sin{x}\):在\(0 \leq x \leq 1\)區間內為遞增函數
  • \(\cos{x}\):在\(0 \leq x \leq 1\)區間內為遞減函數
  • \(\tan{x}\):在\(0 \leq x \leq 1\)區間內為遞增函數
  • \(x^{2}\):在\(0 \leq x \leq 1\)區間內為遞增函數

接著配合係數限制:

  • \(p \times e^{-x}\):在\(0 \leq p \leq 20\)區間內為遞減函數
  • \(q \times \sin{x}\):在\(-20 \leq q \leq 0\)區間內,由於係數為負,故倒向為遞減函數。
  • \(r \times \cos{x}\):在\(0 \leq r \leq 20\)區間內為遞減函數
  • \(s \times \tan{x}\):在\(-20 \leq s \leq 0\)區間內,由於係數為負,故倒向為遞減函數。
  • \(t \times x^{2}\):在\(-20 \leq t \leq 0\)區間內,由於係數為負,故倒向為遞減函數。

由於五項皆為遞減函數,和亦為遞減函數。利用遞減函數的性質與二分搜尋法即可找到解。

P.S. 小心兩浮點數之間不能直接做等於運算,會有誤差,必須算兩數相減小於某個可容忍的誤差值去判斷相等。

C++(0.010)

/*******************************************************/
/* UVa 10341 Solve It                                  */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

bool isEqual(double a, double b){
  return (a - b) < 1e-9 && (a - b) > -1e-9;
}

struct Formula{
  double p;
  double q;
  double r;
  double s;
  double t;
  double u;

  double calculate(double x){
    return p * exp(-x) + q * sin(x) + r * cos(x) + s * tan(x) + t * x * x + u;
  }
};

int main(){
  Formula f;
  while( scanf("%lf%lf%lf%lf%lf%lf", &(f.p), &(f.q), &(f.r), &(f.s), &(f.t), &(f.u)) != EOF){
    double lowerBound = 0, upperBound = 1;
    double lowerValue = f.calculate(lowerBound), upperValue = f.calculate(upperBound);
    if( isEqual(lowerValue, 0) ){
      printf("%.4lf\n", lowerBound);
      continue;
    }

    if( isEqual(upperValue, 0) ){
      printf("%.4lf\n", upperBound);
      continue;
    }

    if( lowerValue * upperValue > 0 ){
      printf("No solution\n");
      continue;
    }

    double mid;
    double midValue;
    do{
      mid = (lowerBound + upperBound) / 2;
      midValue = f.calculate(mid);

      if( midValue < 0 ){
        upperBound = mid;
      }
      else {
        lowerBound = mid;
      }
    } while( !isEqual(midValue, 0) );

    printf("%.4lf\n", mid);

  }

  return 0;
}

#UVa:10579-Fibonacci Numbers

大數加法配合DP加速。

C++(0.000)

/*******************************************************/
/* UVa 10579 Fibonacci Numbers                         */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  vector< vector<int> > dp( 3, vector<int>(1, 0) );
  dp[1][0] = 1;
  dp[2][0] = 1;

  int n;
  while( scanf("%d", &n) != EOF ){
    if( n >= dp.size() ){
      for( int i = dp.size() ; i <= n ; ++i ){
        dp.push_back( vector<int>(dp[i-1].size(), 0) );
        for( int j = 0 ; j < dp[i-2].size() ; ++j ){
          dp[i][j] += dp[i-1][j] + dp[i-2][j];
          if( j + 1 >= dp[i].size() && dp[i][j] / 10 > 0){
            dp[i].push_back(dp[i][j] / 10);
          }
          else if( dp[i][j] / 10 ){
            dp[i][j+1] += dp[i][j] / 10;
          }
          dp[i][j] %= 10;
        }
        if( dp[i-1].size() > dp[i-2].size() ){
          for( int j = dp[i-2].size() ; j < dp[i-1].size() ; ++j ){
            dp[i][j] += dp[i-1][j];
            if( j + 1 >= dp[i].size() && dp[i][j] / 10 > 0){
              dp[i].push_back(dp[i][j] / 10);
            }
            else if( dp[i][j] / 10 ){
              dp[i][j+1] += dp[i][j] / 10;
            }
            dp[i][j] %= 10;
          }
        }
      }
    }

    for( int i = dp[n].size() - 1 ; i >= 0 ; --i ){
      printf("%d", dp[n][i]);
    }
    printf("\n");
  }
  return 0;
}
共 35 頁 1 2 3 4 5 35