UVa 13039 - Fibonacci Triangle

Source

A Bangladeshi Contest at SUST(20151212)
UVa 13039

問題概要

この問題においてフィボナッチ数は $2,3,5,8,13,\ldots$ とする.
$N$ 種類の棒があり $i$ 番目の棒の長さは $i$ 番目のフィボナッチ数と等しく,その棒が $A_i$ 個ある.
$3$ つの棒を使って,面積が正の三角形を作れるだけ作りたい.
最大で何個の三角形を作ることができるかを求める問題.

解法

貪欲法.
最も長い棒として $F_k$ の長さの棒を使うならば,次の $3$ パターンが考えられる.

  1. $F_k$ の棒を $1$ 個,$F_{k-1}$ の棒を $2$ 個使う
  2. $F_k$ の棒を $2$ 個,$F_k$ より短い棒を何でも良いから $1$ 個使う
  3. $F_k$ の棒を $3$ 個使う

なぜなら,$F_k, F_{k-1}, F_{k-2}$ の棒を使うと,フィボナッチ数の漸化式から面積が $0$ になるからである.
よって,短い棒が処理に困るので,$k=1,2,3,\ldots$ と処理していって,できるだけ上の $3$ 条件のうち,上の方から優先的に採用して三角形を作っていけば良い.
$F_{k-2}$ 以下の長さの棒が何個残っているかというのを計算しておけば,時間計算量は $O(N)$ となる.
ちなみに,$A_i \geq 3 \times 10^8 + 3$ なら,それで正三角形を $10^8 + 1$ 個作れるから,$A_i \leq 10^8+2$ であるので,$32$ ビット整数型で十分扱える.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月21日04時14分56秒
Last modified: 2015年12月16日01時52分30秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: