問題一覧 > 通常問題

No.3016 Hachimaki Ojisan

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 158
作問者 : のらら / テスター : ゆにたりー卿 👑 binap DeltaStruct Apollo@Kuro Yama.can Rice_tawara459 あじゃじゃ eom2357
お気に入りにしたユーザー ProblemId : 11736 / 自分の提出
問題文最終更新日: 2025-01-24 21:58:58
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
第1回 岩井星人アンソロジープログラミングコンテスト (順位表) の他の問題:

Problem Statement

Hachimaki Ojisan's only friends are AI and yuki(coder). Whenever he finds a hungry child, he shares his hachimaki (headbands) with them.

Hachimaki Ojisan has $N$ hachimaki with lengths $A_1, A_2, ... , A_N$ respectively, and he gives $1$ hachimaki each to $N-1$ children.

Each child has a favorite hachimaki length, and the $j$-th child feels dissatisfied when receiving a hachimaki of any length other than $B_j$.

Specifically, when the $i$-th hachimaki is given to the $j$-th child, a dissatisfaction of $|A_i-B_j|$ occurs.

When the total dissatisfaction is minimized by giving appropriate hachimaki to each child, find the number of distinct possible lengths of the $1$ hachimaki left in Hachimaki Ojisan's hands, and all of those specific lengths in ascending order.

Constraints

  • $2 \leq N \leq 2×10^5$
  • $1 \leq A_i, B_i \leq N$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$A_1\ A_2\ ...\ A_{N-1}\ A_N$
$B_1\ B_2\ ...\ B_{N-1}$

Output

On line $1$, print the number $T$ of distinct lengths of the hachimaki that may be left in Hachimaki Ojisan's hands. On line $2$, print those specific hachimaki lengths $L$ as a sequence of $T$ terms in ascending order, $L_1\ L_2\ ...\ L_T$.

Sample

Sample 1
Input
3
1 2 3 
1 1
Output
1
3

Only a hachimaki of length $3$ can be left in his hands.

If the $1$-st hachimaki is given to the $1$-st child and the $2$-nd hachimaki is given to the $2$-nd child, the total dissatisfaction is the minimum value, $|1-1|+|2-1|=1$.

There is no way of distributing that leaves a hachimaki of any other length in his hands and makes the total dissatisfaction $1$.

Sample 2
Input
5
4 1 5 1 3 
5 2 1 5
Output
2
1 3

Hachimaki of lengths $1$ and $3$ can be left in his hands.

When keeping a hachimaki of length $1$, starting from child $1$ in order, giving the hachimaki numbered $3,5,4,1$ makes the total dissatisfaction the minimum value, $2$.

When keeping a hachimaki of length $3$ as well, starting from child $1$ in order, giving the hachimaki numbered $3,4,2,1$ makes the total dissatisfaction $2$.

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