UVa 12844 - Outwitting the Weighing Machine

Source

Second UVa regional warmup（20141101）
UVa 12844

問題概要

$5$ 人の女性に対して，$2$ 人選んで測定した $2$ の体重の和が全ての組み合わせに対して与えられる．
その $10$ 通りの和は $W_1,W_2,\ldots,W_{10}$．
それぞれの女性の体重を求める問題．

テストケースの数 $T$ は $T \leq 3000$ を満たす
$100 \leq W_1 \leq W_2 \leq \cdots \leq W_{10} \leq 400$
それぞれの女性の体重で整数になる解がちょうど $1$ つ存在することが保証されていると思われる

解法

最も体重の軽い人の体重を全部試す．
そうすれば，体重の軽い人から順番に芋づる式に求まる．
具体的には，すでに体重が求まった人たちからできるペアの体重の和を $W_k$ から取り除いておいて，残っている $W_k$ の中で一番小さいものから $1$ 人目の体重を引いたものが残りの人の内最も軽い人の体重．
途中で矛盾があれば打ち切って $1$ 人目の体重を変更する．

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

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

Current time: 2024年04月25日02時27分30秒
Last modified: 2014年11月08日19時30分38秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20141101_1
トップページに戻る

Logged in as: unknown user (not login)