QOJ.ac

QOJ

时间限制: 2.0 s 内存限制: 256 MB 总分: 100

#12919. Vier

统计

你在问题 “Oha” 中构建的在线游戏涉及 $n$ 种怪物。怪物类型编号从 $1$ 到 $n$,第 $i$ 种类型的怪物具有力量 $i$ 和魔法能力 $\pi_i$。所有魔法能力都是 $1$ 到 $n$ 之间的不同整数,换句话说,$\pi$ 是一个排列。为简单起见,你生成的这个排列是均匀随机的。

现在你需要为游戏的双方选择起始怪物队伍。每一方必须在起始队伍中恰好拥有两只怪物(它们可以是相同类型的),并且双方的起始队伍必须不同。然而,为了使游戏平衡,起始队伍必须具有相同的总力量模 $n$ 和相同的总魔法能力模 $n$。

更正式地说,你需要找到四个 $1$ 到 $n$ 之间的整数 $a, b, c$ 和 $d$,使得:

  1. $a + b \equiv c + d \pmod n$,且
  2. $\pi_a + \pi_b \equiv \pi_c + \pi_d \pmod n$。

注意,当 $a = c$ 且 $b = d$,或者当 $a = d$ 且 $b = c$ 时,上述陈述是平凡成立的。你需要找到任何其他的解,或者报告不存在这样的解。注意,这四个整数中的某些可以相同——唯一的限制是它们不能以本段第一句话中描述的两种方式重合。

输入格式

输入文件的第一行包含一个整数 $n, 2 \le n \le 10^6$。输入文件的第二行包含 $n$ 个不同的整数,每个整数都在 $1$ 到 $n$ 之间。其中第 $i$ 个整数给出了 $\pi_i$ 的值。

保证该排列是从 $n$ 个整数的所有排列中均匀随机选取的。

输出格式

如果存在非平凡解,在输出文件的第一行打印 Ja,否则打印 Nein。如果你打印了 Ja,则在第二行打印四个 $1$ 到 $n$ 之间的整数:$a, b, c$ 和 $d$。

样例

输入 1

5
2 4 3 5 1

输出 1

Ja
5 5 1 4

说明

本题共有 50 个非样例测试用例。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.