問題一覧 > 通常問題

No.2594 Mix shake!!

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 5
作問者 : 👑 hitonanode / テスター : Sumitacchan
お気に入りにしたユーザー ProblemId : 10399 / 自分の提出
問題文最終更新日: 2023-12-20 12:19:09
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. Back to the original
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

This problem is an homage to Problem I, Liquid Distribution, of the ICPC 2023 Asia Yokohama Regional ( problem summary and editorial (PDF, from around p.67), official problem statement (PDF), online judge (Codeforces Gym) ).

There are $n$ glasses containing drinks. The drink in glass $i$ ($i = 1, \ldots, n$) is a uniform mixture of $a_i~\mathrm{ml}$ of apple juice and $b_i~\mathrm{ml}$ of banana juice.

You may perform the following operation up to $10^{100}$ times: choose $2$ glasses $i$, $j$ ($i \neq j$) and transfer any amount of the drink in glass $i$ to glass $j$. The contents of the glass receiving the drink are immediately mixed uniformly.

Determine whether, by a series of operations alone, it is possible to reach a final state in which each glass $i$ contains a drink consisting of $c_i~\mathrm{ml}$ of apple juice and $d_i~\mathrm{ml}$ of banana juice.

Input

$n$
$a_1$ $\cdots$ $a_n$
$b_1$ $\cdots$ $b_n$
$c_1$ $\cdots$ $c_n$
$d_1$ $\cdots$ $d_n$

  • $2 \leq n \leq 50$
  • $1 \leq a_i \leq 10^{17}$ $(i = 1, \ldots, n)$
  • $1 \leq b_i \leq 10^{17}$ $(i = 1, \ldots, n)$
  • $1 \leq c_i \leq 10^{17}$ $(i = 1, \ldots, n)$
  • $1 \leq d_i \leq 10^{17}$ $(i = 1, \ldots, n)$
  • $\sum_{i=1}^n a_i = \sum_{i=1}^n c_i$
  • $\sum_{i=1}^n b_i = \sum_{i=1}^n d_i$
  • All input values are integers.

Output

Print Yes if it is possible to reach the target state described in the problem statement, and No otherwise.

Sample

Sample 1
Input
2
1 4
4 1
2 3
3 2
Output
Yes

It can be verified that the target state is achieved by performing the following operations in order.

  1. First, transfer $2.5~\mathrm{ml}$ of the contents of glass $1$ to glass $2$.
  2. Next, transfer $2.5~\mathrm{ml}$ of the contents of glass $2$ to glass $1$.
Therefore, print Yes.

Sample 2
Input
3
1 3 5
3 1 5
3 1 5
1 3 5
Output
No

It is impossible to swap the mixing ratios of glass $1$ and glass $2$ by the operations.

Sample 3
Input
5
1 9 5 9 3
2 1 4 6 3
1 9 5 9 3
2 1 4 6 3
Output
Yes

The target state may already be reached without performing any operations.

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