CF109D.Lucky Sorting

普及+/提高

通过率:0%

时间限制:3.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya got an array consisting of n numbers, it is the gift for his birthday. Now he wants to sort it in the non-decreasing order. However, a usual sorting is boring to perform, that's why Petya invented the following limitation: one can swap any two numbers but only if at least one of them is lucky. Your task is to sort the array according to the specified limitation. Find any possible sequence of the swaps (the number of operations in the sequence should not exceed 2_n_).

佩佳喜欢幸运数字。众所周知,幸运数字是指十进制表示中仅包含幸运数字 4 和 7 的正整数。例如,47、744、4 是幸运数字,而 5、17、467 则不是。

佩佳收到了一个由 $ n $ 个数组成的数组,作为他的生日礼物。现在他希望将该数组按非递减顺序排序。然而,常规的排序方式过于乏味,因此佩佳提出了如下限制:仅当两个待交换的数中至少有一个是幸运数字时,才允许交换它们。你的任务是依据该限制对数组进行排序。请找出任意一种满足要求的交换序列(该序列中的操作次数不应超过 $ 2n $)。

输入格式

The first line contains an integer n (1 ≤ n ≤ 105) — the number of elements in the array. The second line contains n positive integers, not exceeding 109 — the array that needs to be sorted in the non-decreasing order.

第一行包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5)—— 数组中元素的个数。
第二行包含 nn 个正整数,每个数不超过 10910^9 —— 需要按非递减顺序排序的数组。

输出格式

On the first line print number k (0 ≤ k ≤ 2_n_) — the number of the swaps in the sorting. On the following k lines print one pair of distinct numbers (a pair per line) — the indexes of elements to swap. The numbers in the array are numbered starting from 1. If it is impossible to sort the given sequence, print the single number -1.

If there are several solutions, output any. Note that you don't have to minimize k. Any sorting with no more than 2_n_ swaps is accepted.

第一行输出数字 kk(0 ≤ k ≤ 2n0 \leq k \leq 2n)—— 排序过程中执行的交换次数。接下来的 kk 行中,每行输出一对互异的数字(即待交换元素的下标)。数组中的元素编号从 1 开始。若无法将给定序列排序,则仅输出单个数字 -1。

若存在多种解法,输出任意一种即可。注意:你无需最小化 kk。任何交换次数不超过 2n2n 的排序方案均可接受。

输入输出样例

  • 输入#1

    2
    4 7

    输出#1

    0
  • 输入#2

    3
    4 2 1

    输出#2

    1
    1 3
  • 输入#3

    7
    77 66 55 44 33 22 11

    输出#3

    7
    1 7
    7 2
    2 6
    6 7
    3 4
    5 3
    4 5

输入解题思路,AI测评打分。不知道怎么写?

首页