#UVa:725-Division

羅列所有可能的分母出來,與N相乘找到分子,再檢查分母和分子是否剛好用完0~9的數字,即可得解。

C++(0.040)

/*******************************************************/
/* UVa 725 Division                                    */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/10/19                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

bool iterateAllPossibleAnswer(int N, bool digitsUsed[], int digit, int denominator){
  if( digit == 5 ){
    int numerator = denominator * N;
    if( numerator >= 100000 ) return false;

    bool checkAllDigitUsed[10];
    memcpy( checkAllDigitUsed, digitsUsed, sizeof(checkAllDigitUsed) );

    for( int checkDigit = 10; checkDigit <= 100000 ; checkDigit *= 10 ){
      int numeratorDigit = numerator % checkDigit / (checkDigit / 10);
      if( checkAllDigitUsed[numeratorDigit] ) return false;
      checkAllDigitUsed[numeratorDigit] = true;
    }

    printf("%05d / %05d = %d\n", numerator, denominator, N);

    return true;
  }

  bool haveAnswer = false;
  for( int i = 0 ; i < 10 ; ++i ){
    if( digitsUsed[i] ) continue;

    digitsUsed[i] = true;
    denominator = denominator * 10 + i;
    haveAnswer |= iterateAllPossibleAnswer(N, digitsUsed, digit + 1, denominator);
    denominator /= 10;
    digitsUsed[i] = false;
  }

  return haveAnswer;
}


int main(){
  int N;
  bool separationLine = false;
  while( scanf("%d", &N) != EOF && N != 0 ){
    if( separationLine ){
      printf("\n");
    }
    separationLine = true;

    bool digitsUsed[10] = {false};
    bool haveAnswer = iterateAllPossibleAnswer(N, digitsUsed, 0, 0);

    if( !haveAnswer ){
      printf("There are no solutions for %d.\n", N );
    }
  }


  return 0;
}

#UVa:10986-Sending email

求一點到另外一點的最短距離,用SPFA即可得解。

P.S. 記得紀錄每個邊可以對點去分群,這樣在更新最短路徑的速度會比較快,如果沒做很容易TLE。

C++(0.100)

/*******************************************************/
/* UVa 10986 Sending email                             */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/10/16                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int UNREACHABLE = -1;

struct Edge{
  int from;
  int to;
  int w;

  Edge(){}

  Edge(int _from, int _to, int _w){
    from = _from;
    to = _to;
    w = _w;
  }
};

int main(){
  int N;
  while( scanf("%d", &N) != EOF ){
    int n, m, S, T;
    for( int testcase = 1 ; testcase <= N ; ++testcase ){
      scanf("%d%d%d%d", &n, &m, &S, &T);

      vector<int> shortestPath(n, UNREACHABLE);
      shortestPath[S] = 0;
      vector< vector<Edge> > nodeEdges = vector< vector<Edge> >(n, vector<Edge>());

      int a, b, w;
      for( int i = 0 ; i < m ; ++i ){
        scanf("%d%d%d", &a, &b, &w);
        nodeEdges[a].push_back( Edge(a, b, w) );
        nodeEdges[b].push_back( Edge(b, a, w) );
      }


      queue<int> next;
      vector<bool> inQueue(n, false);
      next.push(S);

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

        for( int i = 0 ; i < nodeEdges[current].size() ; ++i ){
          int toNode = nodeEdges[current][i].to;
          if( shortestPath[toNode] == UNREACHABLE || 
              shortestPath[current] + nodeEdges[current][i].w < shortestPath[toNode] ){
            shortestPath[toNode] = shortestPath[current] + nodeEdges[current][i].w;
            if( !inQueue[toNode] ){
              next.push(toNode);
              inQueue[toNode] = true;
            }
          }
        }
      }

      printf("Case #%d: ", testcase);
      if( shortestPath[T] == UNREACHABLE ){
        printf("unreachable\n");
      }
      else{
        printf("%d\n", shortestPath[T]);
      }
    }
  }

  return 0;
}

#UVa:11455-Behold my quadrangle

根據所給的邊長去判斷是哪種四邊形,唯一比較難的應該是quadrangle的判斷,其判斷為:\(最長的邊長 \leq 其餘三邊長之和\)。

C++(0.000)

/*******************************************************/
/* UVa 11455 Behold my quadrangle                      */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/08/03                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
  int numTestcase;
  while( scanf("%d", &numTestcase) != EOF ){
    for( int testcase = 0 ; testcase < numTestcase ; ++testcase ){
      int sides[4];
      for( int i = 0 ; i < 4 ; ++i ){
        scanf("%d", &sides[i]);
      }
      sort(sides, sides+4);

      if( sides[0] == sides[3] ){ // Four sides are the same.
        printf("square\n");
      }
      else if( sides[0] == sides[1] && sides[2] == sides[3] ){
        printf("rectangle\n");
      }
      else if( sides[0] + sides[1] + sides[2] >= sides[3] ){
        printf("quadrangle\n");
      }
      else{
        printf("banana\n");
      }
    }
  }

  return 0;
}

#UVa:392-Polynomial Showdown

依照題目的規則去寫判斷式決定輸出的格式長相即可。

C++(0.050)

/*******************************************************/
/* UVa 392 Polynomial Showdown                         */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/08/03                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int coefficients[9];
  while( scanf("%d", &coefficients[0]) != EOF ){
    for( int i = 1 ; i < 9 ; ++i ){
      scanf("%d", &coefficients[i]);
    }

    bool firstTerm = false;
    for( int i = 0 ; i < 9 ; ++i ){
      if( coefficients[i] != 0 ){
        int coefficientTemp = coefficients[i];
        if( firstTerm ){
          coefficientTemp = abs(coefficientTemp);
          if( coefficients[i] > 0 ){
            printf(" + ");
          }
          else{
            printf(" - ");
          }
        }

        if( 8 - i == 0 ){
          printf("%d", coefficientTemp);
        }
        else{
          if( abs( coefficientTemp ) != 1 ){
            printf("%d", coefficientTemp);
          }
          else if( coefficientTemp == -1 ){
            printf("-");
          }
          printf("x");
          if( 8 - i > 1 ){
            printf("^%d", 8-i);
          }
        }

        firstTerm = true;
      }
    }

    if( !firstTerm ){
      printf("0");
    }
    printf("\n");
  }

  return 0;
}

#UVa:10487-Closest Sums

將數字兩兩相加看看哪對離所求之數字最近即是解。

P.S. 其實最後搜尋部分可用二分搜尋加速,不過這題的數量小可以不用。

C++(0.010)

/*******************************************************/
/* UVa 10487 Closest Sums                              */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/08/02                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int main(){
  int n;
  int testcase = 1;
  while( scanf("%d", &n) != EOF && n != 0 ){
    int num[1005];
    for( int i = 0 ; i < n ; ++i ){
      scanf("%d", &num[i]);
    }
    sort(num, num+n);

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

    printf("Case %d:\n", testcase++);
    int query;
    for( int i = 0 ; i < m ; ++i ){
      scanf("%d", &query);

      int closetSum = num[0] + num[1];
      for( int j = 0 ; j < n ; ++j ){
        for( int k = j+1 ; k < n ; ++k ){
          int sum = num[j] + num[k];
          if( abs( sum - query ) < abs( closetSum - query ) ){
            closetSum = sum;
          }
          else if( sum - query > abs(closetSum - query) ){
            break;
          }
        }
      }

      printf("Closest sum to %d is %d.\n", query, closetSum);
    }


  }

  return 0;
}

#UVa:10611-The Playboy Chimp

找出Query所要的數字在不遞減數列中的前後位置找出即可。

C++(0.010)

/*******************************************************/
/* UVa 10611 The Playboy Chimp                         */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/30                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
  int N, Q;
  while( scanf("%d", &N) != EOF ){
    int chimps[50005] = {0};
    for( int i = 0 ; i < N ; ++i ){
      scanf("%d", &chimps[i]);
    }

    scanf("%d", &Q);
    int height;
    for( int i = 0 ; i < Q ; ++i ){
      scanf("%d", &height);

      int *lower = lower_bound(chimps, chimps+N, height);
      int *upper = upper_bound(chimps, chimps+N, height);
      if( (lower == chimps+N) || *lower >= height ){
        --lower;
      }
      if( (lower - chimps) < 0 ){
        printf("X ");
      }
      else{
        printf("%d ", *lower);
      }


      if( (upper - chimps) >= N ){
        printf("X\n");
      }
      else{
        printf("%d\n", *upper);
      }
    }
  }
  return 0;
}

#UVa:10226-Hardwood Species

將所有物種的數量記下來算比例即可。

C++(0.680)

/*******************************************************/
/* UVa 10226 Hardwood Species                          */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/30                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

int main(){
  int numTestcase;
  while( scanf("%d", &numTestcase) != EOF ){
    getchar(); // for '\n'

    string input;
    getline(cin, input); // for blank line

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

      map<string, int> numSpecies;
      int total = 0;
      while( getline(cin, input) && input != "" ){
        ++numSpecies[input];
        ++total;
      }

      for( map<string, int>::iterator it = numSpecies.begin();
           it != numSpecies.end() ; ++it ){
        printf("%s %.4f\n", it->first.c_str(), (double)it->second / total * 100);
      }

    }

  }
  return 0;
}

#UVa:537-Artificial Intelligence?

照著文法從題目敘述中將資訊剖析出來即可得解。

C++(0.000)

/*******************************************************/
/* UVa 537 Artificial Intelligence                     */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/29                                 */
/*******************************************************/
#include <iostream>
#include <string>
#include <cstdio>
#include <cctype>
using namespace std;

const int P = 0, U = 1, I = 2;

double dataField( const string &statement, int index ){
  if( statement[++index] != '=' ){
    return -1;
  }

  double value = 0;
  while( isdigit( statement[++index] ) ){
    value = value * 10 + (statement[index] - '0');
  }

  if( statement[index] == '.' ){
    double position = 0.1;
    while( isdigit( statement[++index] ) ){
      value += (statement[index] - '0') * position;
      position *= 0.1;
    }
  }

  // Prefix Check
  if( statement[index] == 'm' ){
    value *= 1e-3;
    ++index;
  }
  else if( statement[index] == 'k' ){
    value *= 1e3;
    ++index;
  }
  else if( statement[index] == 'M' ){
    value *= 1e6;
    ++index;
  }

  // Unit
  if( statement[index] == 'W' || statement[index] == 'V' || statement[index] == 'A' ){
    return value;
  }
  else{
    return -1;
  }
}

int main(){
  int numTestcase;
  while( scanf("%d", &numTestcase) != EOF ){
    getchar(); // for '\n'
    for( int testcase = 1 ; testcase <= numTestcase ; ++testcase ){
      string statement;
      getline(cin, statement);

      double value[3] = {-1, -1, -1};
      for( int i = 0 ; i < statement.length() ; ++i ){
        if( statement[i] == 'P' ){
          value[P] = dataField(statement, i);
        }
        else if( statement[i] == 'U' ){
          value[U] = dataField(statement, i);
        }
        else if( statement[i] == 'I' ){
          value[I] = dataField(statement, i);
        }
      }

      printf("Problem #%d\n", testcase);
      if( value[P] == -1 ){
        printf("P=%.2fW\n", value[U] * value[I]);
      }
      else if( value[U] == -1 ){
        printf("U=%.2fV\n", value[P] / value[I]);
      }
      else if( value[I] == -1 ){
        printf("I=%.2fA\n", value[P] / value[U]);
      }
      printf("\n");
    }
  }

  return 0;
}

#UVa:400-Unix ls

將最大檔名長度找出,算出最大行列各為多少,利用printf(“%-*s”,…)這個方便技法排版印出即可。

P.S. 當檔名長度+2是有可能會超過60個字的,在算最大行列時要小心,超過的話就是一行一個即可。

C++(0.010)

/*******************************************************/
/* UVa 400 Unix ls                                     */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  int N;
  while( scanf("%d", &N) != EOF ){
    vector<string> filename(N);

    int maxLength = 0;
    for( int i = 0 ; i < N ; ++i ){
      cin >> filename[i];
      maxLength = max((int)filename[i].length(), maxLength);
    }

    sort(filename.begin(), filename.end());

    int column = 60 / (maxLength + 2);
    if( column == 0 ){
      column = 1;
    }
    int maxRow = N / column + ((N % column != 0)? 1 : 0);

    for( int i = 0 ; i < 60 ; ++i ){
      printf("-");
    }
    printf("\n");

    for( int i = 0 ; i < maxRow ; ++i ){
      for( int j = 0 ; j < column ; ++j ){
        if( i + j * maxRow >= N ){
          break;
        }
        printf("%-*s", maxLength+2, filename[i + j * maxRow].c_str());
      }
      printf("\n");
    }


  }
  return 0;
}

#UVa:106-Fermat vs. Pythagoras

利用維基百科中的Pythagorean triple可知要求出每一組primitive triple可用下列公式:\(x = a \times a – b \times b,y = 2 \times a \times b,z = a \times a + b \times b\)。而且a與b之間為互質,且必為一奇一偶。

因此可以利用兩層的巢狀迴圈將a與b列舉出來並求出所有的primitive triple有哪些,求出primitive triple後為了要能確定有哪些數字是不會出現在所有的Pythagorean triple中,故必須要將其triple的所有倍數都找過,例如透過a與b可以求出(3,4,5)這個primitive triple,但若要算有哪些數字不會出現在所有的Pythagorean triple中,則要記得檢查它的倍數(6,8,10)、(9,12,15)……等等。

C++(0.090)

/*******************************************************/
/* UVa 106 Fermat vs. Pythagoras                       */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/07/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const double ERROR = 1e-9;

int gcd(int a, int b){
  while( (a %= b) && (b %= a) );
  return a+b;
}

int main(){
  int N;
  while( scanf("%d", &N) != EOF ){
    vector<bool> used(N+5, false);
    int numTriples = 0;

    for( int i = 1 ; i <= (int)(sqrt(N)+ERROR) ; ++i ){
      for( int j = i+1 ; ; j += 2 ){
        if( gcd(i, j) != 1 ){
          continue;
        }

        int x, y, z;
        x = j*j - i*i;
        y = 2*j*i;
        z = j*j + i*i;

        if( x > N || y > N || z > N ){
          break;
        }

        ++numTriples;
        for( int otherX = x, otherY = y, otherZ = z ; 
            otherX <= N && otherY <= N && otherZ <= N ; 
            otherX += x, otherY += y, otherZ += z ){
          used[otherX] = used[otherY] = used[otherZ] = true;
        }
      }
    }

    int numNotUsed = 0;
    for( int i = 1 ; i <= N ; ++i ){
      if( !used[i] ){
        ++numNotUsed;
      }
    }

    printf("%d %d\n", numTriples, numNotUsed);

  }
  return 0;
}
共 38 頁1 2 3 38