問題一覧 > 通常問題

No.904 サメトロ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 163
作問者 : pekempey / テスター : ciel
お気に入りにしたユーザー ProblemId : 2699 / 自分の提出
問題文最終更新日: 2019-10-11 23:37:56
Sametro
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 227 (順位表) の他の問題:

Problem Statement

The country of yuki has $N$ stations, numbered serially from $1$ to $N$. These $N$ stations are connected by trains that allow travel among them without leaving the ticket gates, and no train allows travel between these $N$ stations and any other station. The stations in this country have a rule that anyone who enters through a ticket gate must exit through the ticket gate of a station different from the one they entered. Furthermore, since stations in this country close at night, anyone who enters through a ticket gate must exit through a ticket gate within the same day.

These stations record the number of people who entered and the number of people who exited through the ticket gates every day, but due to a certain incident that occurred on the day of a certain festival in yuki, the records for station $1$ are missing for that day only. Let $A_i$ be the number of people who entered station $i$ on the day of the festival, and $B_i$ the number of people who exited it. Find how many possibilities there are for $(A_1, B_1)$.

Input

$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)$

Output

Output the answer. It can be shown that the answer is finite.

Sample

Sample 1
Input
3
3 2
4 1
Output
4

The possible pairs are $(A_1,B_1)=(0,4),(1,5),(2,6),(3,7)$. For example, $(A_1,B_1)=(0,4)$ can arise from the following situation.

  • Person $1$ entered at station $2$ and exited at station $1$.
  • Person $2$ entered at station $2$ and exited at station $1$.
  • Person $3$ entered at station $2$ and exited at station $3$.
  • Person $4$ entered at station $3$ and exited at station $1$.
  • Person $5$ entered at station $3$ and exited at station $1$.
  • Person $6$ entered at station $3$ and exited at station $2$.
  • Person $7$ entered at station $3$ and exited at station $2$.
Sample 2
Input
4
3 3
3 3
2 2
Output
9

Sample 3
Input
3
10000 10000
10000 10000
Output
20001

$A_1$, $B_1$ may exceed $10000$.

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