問題一覧 > 通常問題

No.343 手抜き工事のプロ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : FF256grhyFF256grhy
2 ProblemId : 707 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-02-13 00:09:08

問題文

建設業を営むあなたは、喜間市の市政 $N$ 周年を記念したモニュメントの、設計の確認と施工を依頼されました。
そのモニュメントは、縦100cm、横 $L$ cm、高さ1cmの直方体の鋼材を、水平な土台の上に、各鋼材の横方向を南北に向けて、鉛直方向に $N$ 枚重ねたタワー状の構造をしており、さらに、下から $i$ 番目 $(2 \leq i \leq N)$ の鋼材は、1番下の鋼材の位置を基準として、北に $X_i$ cmだけずれた位置に配置されます($X_i$ が負のときは南へ $|X_i|$ cmだけずれる)。

倒壊を防ぐため、各鋼材間を溶接しないといけないのですが、技術的な都合により、各鋼材間の接触面積が100cm$^2$以上でないとうまく溶接することができません。
この要請を満たしていなかった場合は、依頼者に設計が破綻していることを伝えてください。
設計に問題がなければ、あなたは各鋼材間 $N-1$ 箇所の溶接を行うことになっています(なお、一番下の鋼材だけは既に土台にしっかりと固定されているので、土台との間を溶接する必要はありません)。

ところで、あなたは手抜き工事のプロフェッショナルでもあります。
あなたは、各 $i \ (1 \leq i \leq N-1)$ について、下から $i$ 番目の鋼材よりも上にある鋼材全体の重心点を通る鉛直線が、下から $i$ 番目の鋼材と $i+1$ 番目の鋼材の両方(の内部)を貫く場合は、下から $i$ 番目の鋼材と $i+1$ 番目の鋼材の間を溶接しなくても、直ちには倒壊しないことに気付きました。
ただし、鉛直線が(少なくともどちらか一方の)鋼材のちょうど表面を通る場合は、溶接しておかないと不安定になり、直ぐにでも倒壊してしまいそうになるので、溶接が必要です。

モニュメントを直ちには倒壊しないようにするために、あなたは最低でも何箇所を溶接する必要があるでしょうか?

ただし、鋼材は密度の一様な剛体(変形しない物体)とみなせるものとし、溶接することによる形状や質量、密度分布の変化も無視できるものとします。
また、溶接した鋼材同士は、1つの剛体とみなせる(大きな力がかかっても分離しない)ものとします。

入力

$N$
$L$
$X_2$
$X_3$
$\vdots$
$X_N$

$N$, $L$, $X_i \ (2 \leq i \leq N)$ は整数で、
$1 \leq N \leq 10^5$
$1 \leq L \leq 10^4$
$|X_i| \leq 5 \times 10^3$
を満たす。

出力

溶接が必要な箇所数(設計が破綻していたら-1)を出力して改行する。

サンプル

サンプル1
入力
1
6
出力
0

(右側が北、■が鋼材、□は空間)
■■■■■■
そもそも溶接を依頼されていませんね……。

サンプル2
入力
4
2
-1
0
1
出力
3

□□■■
□■■□
■■□□
□■■□
3箇所全てに溶接が必要です。

サンプル3
入力
2
4
4
出力
-1

□□□□■■■■
■■■■□□□□
設計が破綻しています。

サンプル4
入力
3
5
-3
-1
出力
0

□□■■■■■□
■■■■■□□□
□□□■■■■■
手抜き工事チャンス!

サンプル5
入力
5
100
13
29
54
103
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。