UVa/VolumeC2

VolumeC2

• 10200:Prime Time
  • Mathematics? - Prime?
  • Euler Prime Number Definition?、n^2+n+41の精度を調べる問題.
    aからbの範囲で素数が全体の何%あるかを、Euler Prime Number Definition?を用いて調べる.
    入力のMAXが10000なので普通に解けばいいけど、
    プログラムの最初にnに0から10000までを与えた場合の、
    素数かどうかの結果をboolの配列に入れておく.
    入力に対しては添え字アクセスのみで求める.じゃないとたぶんTLE.

• 10202:Pairsumonious Numbers
  • Mathematics?
  • N個の数の各ペアの和が与えられて、それから元のN個の数を求める問題.
    答えの一番小さい数(data[0])は、( (data[0] + data[1]) + (data[0] + data[2]) - (data[1] + data[2]) ) / 2と等しい.
    data[i] + data[j]は、与えられるデータと等しいので既に分かっている.
    また、data[0] + data[1]と data[0] + data[2]は、与えられたデータを昇順にしたときの、それぞれ1番目と2番目のデータに等しい.
    よって、data[1] + data[2]となるような数を与えられたデータから選びながら探していけば良い.

• 10220:I Love Big Numbers !
  • Mathematics? - Big Integer?
  • タイトルが何かむかつく多倍長問題.

• 10222:Decode the Mad man
  • String?
  • 面倒くさいだけ.

• 10227:Forests
  • AdHoc?
  • 問題の意味が良く分からないけど、とりあえず関係のある木が違う人の人数を求める.vectorに木のインデックスを突っ込んでく.uniqueを使わないとwa.

• 10229:Modular Fibonacci
  • Mathematics? - Fibonacci Number?
  • O(log n)で動作するフィボナッチ数列生成関数を使う.
    データ型はunsigned long longでないとwa.

• 10235:Simply Emirp
  • Mathematics? - Prime Number?
  • Eratosthenes' Sieve?で一発.emirpの定義に注意.

• 10252:Common Permutation
  • Dynamic Programming? - Longest Common Subsequence?
  • ソートしてLCSを求める.

• 10258:Contest Scoreboard
  • AdHoc?
  • データは時間通りに入ってくるので、timeが同じだったとしても、先に現れるデータの方が時間的に早いという事になる.
    また、出力と関係あるのはCとIのみ.
    それ以外は定義通りに.

• 10276:Hanoi Tower Troubles Again!
  • Backtracking? - Tower of Hanoi?
  • 平方数を作れるように、1から順番にボールを入れていく.

• 10281:Average Speed
  • Mathematics?
  • 単純に移動距離を出力.
    出力するタイミングは、速度が変化した時だけであることに注意.

• 10282:Babelfish
  • Sorting? + Searching?
  • 安定なソートをした後、Binary Search?.普通に調べたらたぶんTLE.

• 10293:Word Length and Frequency
  • String?
  • タイトル通り、単語の長さとその頻度を出力.

• 10295:Hay Points
  • String?
  • 単語に点数が与えられる.
    文章から点数を求める.

• 10298:Power Strings
  • String?
  • 与えられる文字列は全て、a^nの形になっているので、
    各文字の個数を数えるだけで良い.ababとaabbが違う答えになることに注意.
    また、全ての文字が同じだった場合も例外処理.