TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3085
  • Problem
  • P3085【基础算法】冒泡排序
    Limits : Time Limit : 30000 MS   Memory Limit : 565536 KB
    Description

    给出一个1到n的排列a1,a2,...,an,对它进行冒泡排序。 本题中规定冒泡排序一定是按照下面这段代码这样实现的:

    for(i=1;i<=n;i++) 
    for(j=1;j<n;j++)
    if(a[j]>a[j+1])
    swap(a[j],a[j+1]);
    

    现在问题来了!

    1.求调用K次swap之后的序列,保证冒泡排序至少需要进行K次swap。

    2.给出另一个1到n的排列b1,b2,...,bn,保证它是由原序列调用了若干次swap之后得到的,求次数。

    3.学挖掘机技术,到底哪加强。

    Input Format

    第一行一个正整数n。 第二行n和正整数a1,a2,...,an。 第三行一个正整数K。 第四行n个正整数b1,b2,...,bn。


    Output Format

    第一行n和正整数,表示第一问的答案。 第二行一个正整数,表示第二问的答案。 第三行一个字符串,表示第三问的答案。


    Sample Input

    4
    4 3 2 1 
    3
    1 2 3 4

    Sample Output

    3 2 1 4 
    6
    Zhong guo  shan dong zhuo 1an xiang!

    Hint

    n<=1000000 其他保证满足题目描述中的要求



    Source  感谢nodgd造坑爹题并提供坑爹数据