#B4138. [信息与未来 2016] 洗牌

[信息与未来 2016] 洗牌

题目描述

小明把 nnnn 为偶数)张牌按编号顺序 1,2,3,,n1,2,3,\dots ,n 排成一堆,然后开始洗牌。一次洗牌的过程如下:

  1. 对于一堆编号为 a1,a2,,ana_1,a_2,\dots,a_n,首先将牌分成均匀的两堆:a1,a2,,ama_1,a_2,\dots,a_mam+1,am+2,,ana_{m+1},a_{m+2},\dots,a_n(其中 m=n2m=\frac{n}{2})。

  2. 然后按顺序交叉插入:a1,am+1,a2,am+2,,am,ana_1,a_{m+1},a_2,a_ {m+2},\dots,a_m,a_n

洗牌过程总共重复了 kk 次,请你编程帮助小明模拟洗牌的过程。

例如 n=6n=6,初始时,牌堆中牌的编号为 1,2,3,4,5,61,2,3,4,5,6

首次洗牌时,会将牌分成 1,2,31,2,34,5,64,5,6 两堆,交叉插入后的结果为 1,4,2,5,3,61,4,2,5,3,6

再次洗牌,会将牌分成 1,4,21,4,25,3,65,3,6 两堆,交叉插入后,得到 1,5,4,3,2,61,5,4,3,2,6

输入格式

一行,正整数 n,k,in,k,i,分别代表牌的数量、洗牌的次数、和牌的位置。

输出格式

nn 张牌洗牌 kk 次后,牌堆中第 ii 张牌的编号。

6 2 5
2
400 300 200
368

提示

对于 100%100\% 的数据,1n,k1000,1in1\leq n,k\leq 1000,1\leq i\leq n

保证 nn 是偶数。

本题原始满分为 20pts20\text{pts}