TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3826
  • 题目
  • P3826排序
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1000ms
    问题描述

    shell排序是众多排序算法中的一种。给定N个互不相同的整数,存放在数组A中,排成升序。Shell排序的 代码段在附加的shell.cpp中。 此处的i, N, X, gap, temp, ok 均是整数。数组A的元素互不相同,取值范围在1 N之间。如果第11行被遗漏 了,这个有bug的shell排序程序在X取某些值时,仍然有可能得到正确的排序结果。 请你找出所有能得到正确排序结果的X。
     

    输入格式

    第1行:1个整数N,表示要排序的元素个数
    第2行:N个整数,表示要排序的数组A
     

    输出格式

    第1行:1个整数C,表示X有多少种不同的取值方案,能得到正确排序结果
    第2行:C个整数,表示能得到正确排序结果的X的取值
     

    样例输入


    4 2 6 1 5 3

    样例输出

    2
    1 3

    提示

    样例解释
    有6个元素,分别是4, 2, 6, 1, 5, 3。能得到正确的排序结果的X有2种取值方案:
    ∙ X = 1, 我们交换以下这些位置的元素 (1,2), (3,4), (4,5), (5,6), (2,3), (4,5), (1,2), (3,4); ∙ X = 3, 我们交换以下这些位置的元素 (1,4), (3,6).

    数据范围和约定
    对于20%的数据,n ≤ 1000
    对于100%的数据,n ≤ 500000
     


    来源  八中