noip2013 模拟试题

CCF 全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day11．转圈游戏(circle.cpp/c/pas)【问题描述】n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。

按照顺时针方向给 n 个位置编号，从 0 到 n-1。

最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。

游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n −m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在，一共进行了10k 轮，请问x 号小伙伴最后走到了第几号位置。

【输入】输入文件名为circle.in。

输入共 1 行，包含 4 个整数n、m、k、x，每两个整数之间用一个空格隔开。

【输出】输出文件名为c ircle.out。

输出共1行，包含1个整数，表示10k 轮后x号小伙伴所在的位置编号。

【输入输出样例】circle.in circle.out10 3 4 5 5【数据说明】对于30%的数据，0 < k < 7；对于80%的数据，0 < k < 107；对于100%的数据，1 < n< 1,000,000，0 <m <n ，0 ≤ x ≤ n，0 < k< 109。

2．火柴排队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中 ai表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

学军中学NOIP2013提高组原创模拟题day2测试时间：3.5小时注意事项：1.评测时采用的机器配置为：CPU T83002.40GHz，内存4G。

2.某些题目数据量大，请C++选手谨慎使用cin读入数据。

1.完全平方数（number.cpp/c/pas）【问题描述】一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数（Pefect Sqaure），也称平方数。

小A认为所有的平方数都是很perfect的~于是他给了小B一个任务：用任意个不大于n的不同的正整数相乘得到完全平方数，并且小A 希望这个平方数越大越好。

请你帮助小B告诉小A满足题意的最大的完全平方数。

【输入】输入文件名为number.in输入仅1行，一个数n。

【输出】输出文件名为number.out输出仅1行，一个数表示答案。

由于答案可以很大，所以请输出答案对100000007取模后的结果。

【输入输出样例1】number.in7number.out144【输入输出样例解释1】144=2×3×4×6，是12的完全平方。

【输入输出样例2】number.in9number.out5184【输入输出样例解释2】5184=3×4×6×8×9，是72的完全平方。

【数据范围】对于20%的数据，0<n≤100；对于50%的数据，0<n≤5,000；对于70%的数据，0<n≤100,000；对于100%的数据，0<n≤5,000,000。

2.卡片游戏（game.cpp/c/pas）【问题描述】小D举办了元旦联欢活动，其中有一个卡片游戏。

游戏的规则是这样的：有n张卡片，每张卡片上正面写着一个小于等于100的正整数a i，反面都是一样的花色。

这n张卡片正面朝下叠成一堆，玩这个游戏的人从中可以抽出连续的k（1≤k≤n）张卡片。

如果对于这k张卡片上的数字的平均值a，满足l<=a<=r，那他就可以获得小礼物一件。

全国信息学奥林匹克联赛（NOIP2013）复赛模拟提高组第二试2013年10月20日8:30-12:00(要求每道题建立子文件夹并把程序放入子文件夹中)一、题目概况中文题目名称剑与魔法矩形数列的GCD 英文题目名称dragons rect gcd 可执行文件名dragons rect gcd 输入文件名dragons.in rect.in gcd.in 输出文件名dragons.out rect.out gcd.out每个测试点时限1秒1秒1秒测试点数目102010每个测试点分值10510附加样例文件有有有题目类型传统传统传统二、提交源程序文件名对于pascal语言dragons.pas rect.pas gcd.pas 对于C语言dragons.c rect.c gcd.c 对于C++语言dragons.cpp rect.cpp gcd.cpp三、编译命令（不包含任何优化开关）对于pascal语言fpc dragons.pas fpc rect.pas fpc gcd.pas对于C语言gcc–o dragonsdragons.c-lmgcc–o rectrect.c-lmgcc–o gcdgcd.c-lm对于C++语言g++-o dragonsdragons.cpp-lmg++-o rectrect.cpp-lmg++-o gcdgcd.cpp-lm四、运行内存限制内存上限128M128M128M五、注意事项1、文件名（程序名和输入输出文件名）必须使用小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU1.9GHz，内存1G，上述时限以此配置为准。

各省在自测时可根据具体配置调整时限。

1.剑与魔法(dragons.pas/c/cpp)【问题描述】万老师听说某大国很流行穿越，于是他就想写一个关于穿越的剧本。

闲话休提。

学军中学NOIP2013提高组原创模拟题解（每试3.5小时）DAY11.装果子关键词：二分二分V，然后每次O(n)判断一遍。

如果可以装进全部的果子就二分左区间，如果不行就二分右区间。

开long long是必然的。

时间复杂度：O(nlog21014)2.零件加工关键词：贪心按照t/s升序排序然后计算，比较大小的时候注意交叉相乘。

对于最后20%的数据相乘时可以使用二进制乘法以避免高精度：long long mul(long long a,long b){long long ret=0;while(a){if(a&1)ret=(ret+b)%MOD;a>>=1;b=(b<<1)%MOD;}return ret;}时间复杂度：O(nlog2n)3.种树关键词：差分约束系统开一个s数组记录前缀和。

根据题意我们可以得到3个约束条件：s[r]-s[l-1]≥c，①s[i]≥s[i-1]，②s[i]-s[i-1]≤k，③根据①得s[l]-s[r]≤-c，在r和l-1之间连一条权值为-c的边。

根据②得s[i-1]-s[i]≤0，在i和i-1之间连一条权值为0的边。

根据③在i-1和i之间连一条权值为k的边。

50分算法：Bellman-Ford。

时间复杂度：O(nm)70分算法：SPFA。

时间复杂度：O(km)100分算法：观察到最大可能需要连150w条边，因此我们要考虑有些边是否需要连。

我们可以只根据条件①计算，每次更新后O(n)检查是否满足条件②和③，如果不满足就修改，这样只用连50w条边，可以过全部数据。

全国信息学奥林匹克联赛（NOIP2013）复赛模拟普及组一.题目概览中文题目名称lignment 消息传递Cow Crossings算周长英文题目名称lignment relay crossings perimeter可执行文件名lignment relay crossings perimeter 输入文件名lignment.in relay.in crossings.in perimeter.in 输出文件名lignmentout relay.out crossings.out perimeter.out 每个测试点时限1秒1秒1秒1秒测试点数目10 10 10 10每个测试点分值10 10 10 10 比较方式全文比较全文比较全文比较全文比较题目类型传统传统传统传统二.提交源程序文件名对于pascal语言alignment pas relay.pas crossings.pas perimeter.pas 对于C语言alignment.c relay.c crossings.c perimeter.c 对于C++语言alignment.cpp relay.cpp crossings.cpp perimeter.cpp三.编译命令（不包含任何优化开关）对于pascal语言fpc queue.pas fpc windows.pas fpc s4.pas fpc book.pas对于C语言gcc –o queuequeue.c gcc –o windowswindows.cgcc –o s4s4.cgcc –o bookbook.c对于C++语言g++ –o queuequeue.cpp g++ –o windowswindows.cppg++ –o s4s4.cppg++ –obookbook.cpp四.运行内存限制运行内存上限50M 50M 50M 50M注意事项：1、文件名（程序名和输入输出文件名）必须使用小写。

NOIP2013提高组复赛试题CCF 全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day11．转圈游戏(circle.cpp/c/pas)【问题描述】n 个小伙伴（编号从0 到n-1）围坐一圈玩游戏。

按照顺时针方向给 n 个位置编号，从 0 到 n-1。

最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。

游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第1 号位置小伙伴走到第m+1 号位置，……，依此类推，第n ?m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在，一共进行了10^k 轮，请问x 号小伙伴最后走到了第几号位置。

【输入】输入文件名为circle.in。

输入共1 行，包含4 个整数n、m、k、x，每两个整数之间用一个空格隔开。

【输出】输出文件名为c ircle.out。

输出共1行，包含1个整数，表示10k 轮后x号小伙伴所在的位置编号。

【数据说明】对于30%的数据，0 < k < 7；对于80%的数据，0 < k < 107；对于100%的数据，1 < n< 1,000,000，0 <="" <="" <="" n，0="" p="" x="" ≤="" ，0="">2．火柴排队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中 ai 表示第一列火柴中第i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

NOIP模拟题bronze刘启鹏竞赛时间：2010年11月13日 8:30-11:30注意：最终测试时，所有编译命令均不打开任何优化开关。

Linear T riple【问题描述】一个线性三元组是指一个满足如下关系有序三元组(s1,s2,s3):s3-s2=s2-s1.如(1,2,3),(2,4,6),(14,21,28)都是满足条件的线性三元组.对于给定的一个S个元素的集合(元素值在1..100间),请输出可以组成的线性三元组的数目。

【输入格式】第一行:一个整数,S (3 <= S <= 30)。

第二行:S个用空格隔开的整数.【输出格式】仅一行,包含一个整数,可以组成的线性三元组的数量,保证在长整形范围内。

【样例输入1】71 2 3 4 6 8 9【样例输出1】5【数据说明】这些三元组是:1 2 32 3 42 4 63 6 94 6 8。

NOIP模拟题bronze 刘启鹏P vs NPP vs NP【问题描述】P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。

P/NP问题中包含了复杂度类P与NP的关系。

1971年Stephen A. Cook 和Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。

这个问题似乎难了点，放在NOIP第一题不太人道。

放心，你需要解决的只是一个简化版的问题：P=N*P?【输入格式】输入的第一行包含两个数，分别为N和P。

【输出格式】如果P=N*P，输出True。

否则输出False。

【样例输入1】1 123789325797235098234798235709235092357092357092347092370924234 【样例输出1】True【样例输入2】-3.14159265358979323846264338327950288419716939937510 0【样例输出2】True【数据说明】保证读入不会超过0.1s。

noip2013 模拟试题[title]: NOIP2013 模拟试题[introduction]:NOIP（全国青少年信息学奥林匹克竞赛）是中国信息学竞赛中最具影响力的比赛之一。

NOIP2013 模拟试题是该年度参赛选手备战竞赛的重要资料。

本篇文章将重点分析并解答该模拟试题中的关键问题，旨在帮助读者更好地理解和应对类似题型。

[body]:一、题目一题目描述：在一个长度为 n（n<=1000）的字符串中，求出最长的回文子串。

解析与思路：1. 回文子串：指正序和倒序读都是一样的字符串，例如"aba"；2. 暴力法：遍历所有子串，判断是否为回文子串，记录最长长度；3. 动态规划法：利用之前判断好的回文子串信息，通过状态转移方程进行计算；4. Manacher 算法：利用回文串的对称性，减少重复计算的次数。

二、题目二题目描述：给定两个字符串 s 和 t，找出它们的最长公共子序列。

如果不存在公共子序列，则返回 0。

解析与思路：1. 公共子序列：指两个字符串中都存在的一个子序列；2. 动态规划法：利用之前计算好的最长公共子序列信息，通过状态转移方程进行计算；3. 二维数组法：使用二维数组记录两个字符串的最长公共子序列信息；4. 降维优化：使用一维数组记录最长公共子序列信息，减少空间复杂度。

三、题目三题目描述：给定一个非负整数数组，选择两个元素使它们的和最大，且两个元素不能相邻。

解析与思路：1. 最大和问题：求解元素之和的最大值；2. 动态规划法：通过状态转移方程求得最优解；3. 状态压缩：使用两个变量保存之前两个状态，减少存储空间；4. 考虑边界条件：数组为空、数组长度为1等情况需要特殊处理。

四、题目四题目描述：给定一个二维矩阵，找出矩阵中的最大连续子矩阵的和。

解析与思路：1. 最大子矩阵和问题：求解满足条件的最大连续子矩阵的和；2. 动态规划法：通过状态转移方程逐步计算最大子矩阵和；3. 二维前缀和优化：通过计算二维前缀和矩阵，避免重复计算；4. 记录子矩阵位置：通过记录起始位置和终止位置，可以输出最大连续子矩阵。

CCF全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day1（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+，2.71GHz，内存2G，上述时限以此配置为准。

4、只提供Linux格式附加样例文件。

5、特别提醒：评测在NOI Linux下进行。

1．转圈游戏(circle.cpp/c/pas)【问题描述】 n 个小伙伴（编号从0到n-1）围坐一圈玩游戏。

按照顺时针方向给n 个位置编号，从0到n-1。

最初，第0号小伙伴在第0号位置，第1号小伙伴在第1号位置，……，依此类推。

游戏规则如下：每一轮第0号位置上的小伙伴顺时针走到第m 号位置，第1号位置小伙伴走到第m+1号位置，……，依此类推，第n −m 号位置上的小伙伴走到第0号位置，第n-m+1号位置上的小伙伴走到第1号位置，……，第n-1号位置上的小伙伴顺时针走到第m-1号位置。

现在，一共进行了10k 轮，请问x 号小伙伴最后走到了第几号位置。

【输入】输入文件名为circle.in 。

输入共1行，包含4个整数n 、m 、k 、x ，每两个整数之间用一个空格隔开。

【输出】输出文件名为circle.out 。

输出共1行，包含1个整数，表示10k 轮后x 号小伙伴所在的位置编号。

【输入输出样例】【数据说明】对于30%的数据，0<k <7； 对于80%的数据，0<k <107；对于100%的数据，1<n <1,000,000，0<m <n ，0≤x <n ，0<k <109。

2．火柴排队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有n 根火柴，每根火柴都有一个高度。

NOIP复赛模拟试题2预览说明:预览图片所展示的格式为文档的源格式展示,下载源文件没有水印,内容可编辑和复制2013开明中学NOIP模拟试题2题目1、NBA总冠军（nba.pas/c/cpp）【问题描述】又要考试了，Ljw决定放松一下，就打开电视，看见了篮球赛，他立即想到了每年的NBA 总冠军队伍。

由于复习紧张，他只记起了一部分，记忆的内容是正确的，可能不是按时间顺序排列的，记忆的内容可能有重复。

现在请求学过编程的你帮助Ljw，按时间依次输出总冠军的球队（不能重复）。

（NBA 从1947A.D到2009A.D）【输入】输入文件nba.in的第一行是一个整数n（0<n<50）。

< bdsfid="75" p=""></n<50）。

<>接下来的n行，每行先是城市名（由大到小写字母、空格组成），后是时间（由数字组成）二者之间用空格隔开。

【输出】输出文件nba.out共n行，即排序后的NBA总冠军队伍。

每行先是时间，后是城市名。

【输入输出样例】2.买票（tickets.pas/c/cpp）【问题描述】周末Ztc想去剧场看演出，但他没有票。

这时，救世主Wzj出现了，他慷慨地愿意卖给Ztc 一些票。

Wzj手上共有n张票，但每张票的费用都不一样，贪心的ztc想要得到尽可能多的票，但又想花费最少，慷慨的wzj原意给连续的m张票。

Ztc 希望你能帮助他在花钱范围内取得最大的票数。

【输入】输入文件tickets.in的第一行是2个整数n,，f。

其中（2≤N≤1000000），表示票的数目，（10≤f≤10000），表示ztc身上的钱。

接下来的1行，有n个整数a（1≤a≤30），表示每一张票的票价。

【输出】输出文件tickets.out仅一行整数m，表示Ztc能得连续的最大票数。

【输入输出样例】【限制】50%的数据满足：2≤n≤10000100%的数据满足：2≤n≤10000003.逛街（shop.pas/c/cpp）【问题描述】某天，ZCL 在街上闲逛。

NOIP 2013初赛模拟题一一、选择题：（本题共20题，每题1.5分，共计30分）1、在计算机内部用来传送、存贮、加工处理的数据或指令都是以（）形式进行的。

A、二进制码B、八进制码C、十进制码D、智能拼音码2、计算机的软件系统通常分为（）A、硬件系统和软件系统B、高级软件和一般软件C、系统软件和应用软件D、军用软件和民用软件3、关于软盘读写孔，正确的说法是（）。

A．从该孔读信息B．从该孔写信息C．当该孔处于开状态时，不能删除盘中文件。

D．该孔没有作用4、一棵二叉树的中序遍历为DGBAECHF，后序遍历为GDBEHFCA，则前序遍历是（）A、ABCDFGHEB、ABDGCEFHC、ACBGDHEFD、ACEFHBGD5、下列叙述中错误的是（）。

A、微机应避免置于强磁场之中B、微机使用时间不宜过长，而应隔几个小时关机一次C、微机应避免频繁关开，以延长其使用寿命D、微机应经常使用，不宜长期闲置不用6、计算机网络最主要的优点是（）。

A、运算速度快B、共享资源C、精度高D、存储容量大7、下列4个不同进制表示的数中，最大的一个数是（）A、(220.1)10B、(11011011.1)2C、(334.1)8D、(DC.1) 168、为了区分汉字与ASCII码，计算机中汉字编码的最高位为（）A、1B、0C、-1D、29、下列不正确的文件名是（）。

A. command。

ComB. command_comC. command,comD. command:com10、一般来说，TCP/IP的IP提供的服务是( )A.运输层服务B.会话层服务C.表示层服务D.网络层服务11、通信时，模拟信号也可以用数字信道来传输，能实现模拟信号与数字信号之间转换功能的是（）A、D/AB、A/DC、ModemD、Codec12、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列是（）。

A、54312B、24135C、21543D、1253413、不属于Internet的功能是（）A、聊天B、远程教育C、查询资料D、传送能量14、下列描述计算机病毒的特性中，（）不是正确的。

机器翻译(translate.pas/c/cpp)【问题描述】小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。

对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有M个单元，每单元能存放一个单词和译义。

每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为N 个单词。

给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

【输入】输入文件名为translate.in，输入文件共2 行。

每行中两个数之间用一个空格隔开。

第一行为两个正整数M 和N，代表内存容量和文章的长度。

第二行为N 个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。

文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

【输出】输出文件translate.out 共1 行，包含一个整数，为软件需要查词典的次数。

【输入输出样例1】translate.in3 71 2 1 5 4 4 1translate.out5【输入输出样例 1 说明】整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：空：内存初始状态为空。

1． 1：查找单词1 并调入内存。

2． 1 2：查找单词2 并调入内存。

3． 1 2：在内存中找到单词1。

4． 1 2 5：查找单词5 并调入内存。

5． 2 5 4：查找单词4 并调入内存替代单词1。

6． 2 5 4：在内存中找到单词4。

CCF 全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day11．转圈游戏(circle.cpp/c/pas)【问题描述】n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。

按照顺时针方向给 n 个位置编号，从 0 到 n-1。

最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。

游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n −m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在，一共进行了10^k 轮，请问x 号小伙伴最后走到了第几号位置。

【输入】输入文件名为circle.in。

输入共1 行，包含4 个整数n、m、k、x，每两个整数之间用一个空格隔开。

【输出】输出文件名为c ircle.out。

输出共1行，包含1个整数，表示10k 轮后x号小伙伴所在的位置编号。

【数据说明】对于30%的数据，0 < k < 7；对于80%的数据，0 < k < 107；对于100%的数据，1 < n< 1,000,000，0 <m <n ，0 ≤ x ≤ n，0 < k< 109。

2．火柴排队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

全国信息学奥林匹克联赛（2013）复赛提高组11．转圈游戏()【问题描述】n 个小伙伴（编号从0 到1）围坐一圈玩游戏。

按照顺时针方向给n 个位置编号，从0 到1。

最初，第0 号小伙伴在第0 号位置，第1 号小伙伴在第1 号位置，……，依此类推。

游戏规则如下：每一轮第0 号位置上的小伙伴顺时针走到第m 号位置，第1 号位置小伙伴走到第1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第0 号位置，第1 号位置上的小伙伴走到第1 号位置，……，第1 号位置上的小伙伴顺时针走到第1 号位置。

现在，一共进行了10k 轮，请问x 号小伙伴最后走到了第几号位置。

【输入】输入文件名为。

输入共1 行，包含4 个整数n、m、k、x，每两个整数之间用一个空格隔开。

【输出】输出文件名为。

输出共1 行，包含1 个整数，表示10k 轮后x 号小伙伴所在的位置编号。

【输入输出样例】10 3 4 55【数据说明】对于30%的数据，0 < k < 7；对于80%的数据，0 < k < 107；对于100%的数据，1 < n< 1,000,000，0 <m <n ，0 ≤ x ≤ n，0 < k< 109。

2．火柴排队()【问题描述】涵涵有两盒火柴，每盒装有n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中表示第一列火柴中第i 个火柴的高度，表示第二列火柴中第i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对99,999,997 取模的结果。

【输入】输入文件为。

共三行，第一行包含一个整数n，表示每盒中火柴的数目。

第二行有n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。