#P13590. [NWRRC 2023] Jumping Frogs
[NWRRC 2023] Jumping Frogs
Description
Julia 是一位野生自然摄影爱好者。昨天,她拍摄了两张美丽河流的照片,河面上有睡莲和一些青蛙坐在上面。
河流上有许多睡莲,从左到右依次编号为连续的正整数,从 开始。两张照片都是从完全相同的位置拍摄的,并且两张照片上都有相同的 只青蛙坐在睡莲上。每片睡莲最多只能有一只青蛙。
经过对比,Julia 发现所有青蛙在两张照片之间都移动了,因为没有任何一片睡莲在两张照片中都同时有青蛙坐在上面。然而,Julia 无法分辨第一张照片中的哪只青蛙跳到了第二张照片中的哪片睡莲,因为所有青蛙看起来都一模一样!
可以确定的是:每只青蛙都跳到了不同的睡莲上。有些青蛙向左跳,跳到了编号更小的睡莲上,另一些青蛙向右跳,跳到了编号更大的睡莲上。
为了研究青蛙的移动情况,Julia 想要回答这样一个问题:在两张照片之间,有多少只青蛙向左跳了?由于这个问题可能没有唯一答案,你需要帮助 Julia 找出所有可能的答案。
Input Format
第一行包含一个整数 ,表示青蛙的数量()。
第二行包含 个整数 ,表示第一张照片中有青蛙坐着的睡莲编号,按递增顺序排列()。
第三行包含 个整数 ,表示第二张照片中有青蛙坐着的睡莲编号,按递增顺序排列()。
给定的 个整数互不相同:没有任何一片睡莲在两张照片中都同时有青蛙坐在上面。
Output Format
第一行输出一个整数 ,表示 Julia 的问题可能的答案个数。
第二行输出 个整数 ,表示所有可能的答案,按递增顺序排列()。
4
10 20 30 40
1 2 51 52
1
2
4
10 20 30 40
5 15 25 35
4
1 2 3 4
1
100
200
1
0
Hint
在第一个样例中,最终停在睡莲 和 上的青蛙一定是向左跳的,而最终停在睡莲 和 上的青蛙一定是向右跳的。因此,我们可以确定恰好有 只青蛙在两张照片之间向左跳了。
由 ChatGPT 4.1 翻译
京公网安备 11011102002149号