B - Sun and Moon - 秘密結社太陽と月の団
Editorial
/ 
西暦20XX年、人類は未曾有の危機に瀕していた。 皆既日蝕により太陽と月のパワーバランスが崩れ、 終末が訪れたのである。
終わりの迫った世界を救うため、 秘密結社『太陽と月の団』は、 日蝕の
x
日後に『太陽と月の儀式』と呼ばれる 太陽と月のパワーバランスを整える儀式を執り行うことにした。
太陽と月の儀式は『太陽の儀式』と『月の儀式』から構成される。
儀式において各社員は初期状態としていくつかの供物といくらかの魔力を持っている。 また、各社員は太陽の加護を授かった『太陽の使者』と、
月の加護を授かった『月の使者』に分けられている。
儀式では初めに太陽の儀式を執り行う。 太陽の儀式において、各社員は所持する供物を一つ生贄に捧げる。
ここで供物を所持していない社員は以降の儀式から除外される。 儀式の後、各社員の魔力は初めに彼らが持っていた供物の数だけ倍増する。
(i番目の社員が初期状態で生贄Oi個、魔力Piを持っていた場合、魔力がOi×Piに変化する。)
全ての社員はこの儀式を丁度一回ずつ行う。
続いて、月の儀式を執り行う。 この儀式で各社員は、所持する供物全てを生贄に捧げる。 儀式のあと、各社員の魔力は
x^{p}
倍に増加する。 ここで
x
は日蝕からの経過日数、
p
は各社員がその時点(月の儀式が行われる直前)で所持している供物の数である。 太陽の儀式で残った全ての社員は丁度一回ずつ儀式を行う。
これらの儀式の後、太陽の使者と月の使者は 全ての魔力を『魔力リアクター』に注ぎ込む。
このとき太陽の使者の魔力の総和と月の使者の魔力の総和が等しければ、 儀式は成功し世界は救われる。
さて、太陽の儀式には大量の資金がいるのだが、 秘密結社は不景気のため予算を捻出することができない可能性がある。
あなたの仕事は太陽と月の儀式のうち、 太陽の儀式を行った場合／行わなかった場合の どちらの場合においても儀式全体が成功するような、
日蝕からの経過日数
x
を求めるプログラムを書くことである。 日蝕の起こった日(0日目)に儀式を行うことはできない。
入力形式は以下の通りである。
問題文の条件を満たすような日蝕からの経過日数がある場合は
/ 
Time Limit: 2 sec / Memory Limit: 128 MB
問題文
入力
N
O_{1} P_{1}
...
O_{N} P_{N}
初めの行は一つの整数
N (0 ≤ N ≤ 1,000)
からなり、 これは秘密結社の社員数を表す。 続く
N
行には二つの整数
O_{i} (0 ≤ O_{i} ≤ 10^{9})
と
P_{i} (1 ≤ |P_{i}| ≤ 10^{15})
が与えられる。
O_{i}
は
i
番目の社員が持つ生贄の数を表し、
P_{i}
は
i
番目の社員が持つ魔力を表す。
P_{i}
が正の数の場合は
i
番目の社員は太陽の使者に属し、
P_{i}
が負の数の場合は
i
番目の社員は月の使者に属する。
出力
Yes
と、 その経過日数を出力せよ。 それ以外の場合は
No
を出力せよ。 当然のことながら、経過日数は正の数でなければならない。
部分点
- 1 ≤ |P_{i}| ≤ 10^{3} を満たす入力にのみ正解した場合、部分点として 175 点が与えられます
- 1 ≤ |P_{i}| ≤ 10^{9} を満たす入力にのみ正解した場合、部分点として 25 点が与えられます
入力例 1
9 2 1 1 -1 1 -1 1 -1 1 -1 0 1 0 1 0 1 0 1
出力例 1
Yes 2
入力例 2
2 1 1 0 -1
出力例 2
No