問題一覧 > 通常問題

No.904 サメトロ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 155
作問者 : pekempeypekempey / テスター : cielciel
15 ProblemId : 2699 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-11 23:37:56

問題文

yuki 国には駅が $N$ 駅あり $1$ から $N$ の通し番号がついています。この $N$ 駅同士は改札を出ずに行き来できる電車があり、この $N$ 駅とそれ以外の駅を行き来できる電車はありません。この国の駅には改札を入ったら入った駅とは異なる駅の改札を出なければならないという規則があります。さらにこの国では夜に駅が閉まるため、改札を入ったらその日中に改札を出なければなりません。

これらの駅では改札を入った人数と改札を出た人数を毎日記録しているのですが、yuki 国のとあるお祭りの日に起きたとある事件の影響でこの日だけ駅 $1$ に関する記録が残っていません。お祭りの日に駅 $i$ に入った人数を $A_i$、出た人数を $B_i$ とするとき $(A_1, B_1)$ が何通りあり得るのか求めてください。

入力

$N$
$A_2\;B_2$
$A_3\;B_3$
$\vdots$
$A_N\;B_N$

$2 \le N \le 37$
$0 \le A_i, B_i \le 10000\quad(2 \le i \le N)$

出力

答えを出力してください。答えは有限の値であることが示せます。

サンプル

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

ありえる組は $(A_1,B_1)=(0,4),(1,5),(2,6),(3,7)$ です。たとえば $(A_1,B_1)=(0,4)$ は以下の状況が考えられます。

  • 人 $1$ が駅 $2$ で入って駅 $1$ で出た。
  • 人 $2$ が駅 $2$ で入って駅 $1$ で出た。
  • 人 $3$ が駅 $2$ で入って駅 $3$ で出た。
  • 人 $4$ が駅 $3$ で入って駅 $1$ で出た。
  • 人 $5$ が駅 $3$ で入って駅 $1$ で出た。
  • 人 $6$ が駅 $3$ で入って駅 $2$ で出た。
  • 人 $7$ が駅 $3$ で入って駅 $2$ で出た。
サンプル2
入力
4
3 3
3 3
2 2
出力
9

サンプル3
入力
3
10000 10000
10000 10000
出力
20001

$A_1$, $B_1$ は $10000$ を超えても構いません。

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