1247 Magnificent Meatballs

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

問題

poj1247 Magnificent Meatballs [#q1f3e74c]

円の上に時計回りに数字が描かれていて数字には時計回りに1からｎまで番号が付いている。
円の周りを1からスタートするsum氏と番号ｎから反時計回りにスタートするElla氏が互いに出会うまで数字を合計していく。
2人が出会ったとき数字の計を2等分できるならその場所を問題で指定されている法方で表示せよ。

分かりやすく言えば円を1～ｍまでとｍ+1～ｎまでに分割した時sum(1～ｍ)=sum(m+1,n)(m+1==nの可能性もある)となるなら分割点ｍを表示せよ。

無理ならその峰をNo equal partitioning.と表示すること。
n<31、計算はint型に収まると仮定してよい。

入力

最初の数字が円のサイズｎ、その後に続く数字が時計回りに並んでいる数である。
0一つの行が問題の終わりとなる。

出力

分割が可能なら
Sam stops at position m and Ella stops at position m+1.
日本語に訳せばサムのストップ地点ｍとエラのストップ地点ｍ+1を表示。
不可能ならNo equal partitioning.と表示せよ。

入力の例

5 9 4 2 8 3
5 3 9 4 2 8
6 1 2 1 2 1 2
6 1 2 1 2 1 1
0

出力の例

Sam stops at position 2 and Ella stops at position 3.
No equal partitioning.
No equal partitioning.
Sam stops at position 3 and Ella stops at position 4.

ヒント

特になし

出典

POJ