noi2009A.doc

立即下载 作者: 真不错
上传时间: 2024-12-10
关键词: 输出 文件 10 输入 之间 Ti 整数 poet 包含 数据
大小 85 KB
描述
第二十六届全国信息学奥林匹克竞赛
NOI 2009
第一试
竞赛时间：2009年7月27日上午8:00-13:00
题目名称 变换序列 诗人小G 二叉查找树
目录 transform poet treapmod
可执行文件名 transform poet treapmod
输入文件名 transform.in poet.in treapmod.in
输出文件名 transform.out poet.out treapmod.out
每个测试点时限 1秒 30 秒 1 秒
测试点数目 10 10 10
每个测试点分值 10 10 10
是否有部分分 无 有 无
题目类型 传统 传统 传统
提交源程序须加后缀
对于Pascal语言 transform.pas poet.pas treapmod.pas
对于C 语言 transform.c poet.c treapmod.c
对于C++ 语言 transform.cpp poet.cpp treapmod.cpp
注意：最终测试时，所有编译命令均不打开任何优化开关
变换序列
【问题描述】
对于N个整数0, 1, ……, N-1，一个变换序列T可以将i变成Ti，其中且。，定义x和y之间的距离。给定每个i和Ti之间的距离D(i,Ti)，你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序最小的一个。
说明：对于两个变换序列S和T，如果存在p【输入文件】
输入文件transform.in的第一行包含一个整数N，表示序列的长度。接下来的一行包含N个整数Di，其中Di表示i和Ti之间的距离。
【输出文件】
输出文件为transform.out。
如果至少存在一个满足要求的变换序列T，则输出文件中包含一行N个整数，表示你计算得到的字典序最小的T；否则输出”No Answer”（不含引号）。注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。
【输入样例】
5
1 1 2 2 1
【输出样例】
1 2 4 0 3
【数据规模和约定】
20%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。
诗人
目录
输出/文件/10/输入/之间/Ti/整数/poet/包含/数据/ 输出/文件/10/输入/之间/Ti/整数/poet/包含/数据/