【题目描述】

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。

下图 显示了一个迷阵的样例及李逍遥找到仙药的路线。

【输入描述】

第1行输入两个非零整数 M 和 N ，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。

接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:

1) ‘@’：少年李逍遥所在的位置；

2) ‘.’：可以安全通行的方格；

3) ‘#’：有怪物的方格；

4) ‘*’：仙药所在位置。

【输出描述】

求李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。

【样例输入】

8 8  .@##...#  #....#.#  #.#.##..  ..#.###.  #.#...#.  ..###.#.  ...#.*..  .#...###

【样例输出】

10

【题目描述】

小X喜欢玩游戏。 

 这天，小X觉得传统的游戏都玩腻了，自己随手在草稿纸上画了一行N个格子作为棋盘， 制定了如下规则：格子从左到右依次编号为1到N，玩家初始位于格子1，初始前进方向为向右，游戏共进行M轮，第i轮玩家前进Ai格，若玩家到达格子N则改变前进方向为向左，若玩家到达格子1则改变前进方向为向右。 

小X想知道玩家最后会停在哪个格子，但这个游戏太漫长了，他已经玩得快睡着了，希望你帮帮他。

【输入描述】

第一行包含用一个空格隔开的两个整数N,M。 

接下来M行，第i行包含一个整数Ai。

【输出描述】

第一行包含一个整数，表示玩家最后停留的格子编号。

【样例输入】

3 2  2  3

【样例输出】

2

【提示】

样例说明

   玩家的路线为 1->2->3->2->1->2。

【数据范围】

  对于30%的数据，N=2，M≤10，Ai=1。

   对于60%的数据，N≤1000，M≤1000，Ai≤1000。

   对于 100%的数据，2≤N≤100000，1≤M≤100000，1≤Ai≤1000000000。

【题目描述】

平面上有n个点（n≤100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。

若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

【输入描述】

共n+m+3行，其中:

第一行为整数n。

第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。

第n+2行为一个整数m，表示图中连线的个数。

此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。

最后一行：两个整数s和t，分别表示源点和目标点。

【输出描述】

一行，一个实数（保留两位小数），表示从s到t的最短路径长度。

【样例输入】

5   0 0  2 0  2 2  0 2  3 1  5   1 2  1 3  1 4  2 5  3 5  1 5

【样例输出】

3.41

【题目描述】

小T和小K都是OIER，入选省队后有幸去苏州参加JSOI集训，训练之余，他们相约一起去苏州乐园玩。

苏州乐园里有一个非常热门的游乐项目叫双人滑翔翼。小T想和小K一起乘双人滑翔翼，但是排在他们前面的一大群人却为了搭配问题而争执不休，小T和小K便自告奋勇上前为他(她)们排扰解难。

排在小T和小K前面的一大群人中有N个男人和N个女人。本着“男女搭配，干活不累”的原则，他(她)们希望一男一女结成对子飞上天去。由于双人滑翔翼飞行的稳定性很大程度上决定于两侧是否平衡，所以两个人体重相差越小则组成的搭档也越好。

现在已知每个人的体重，你的任务就是将所有人结成N对并使各对的体重差的总和最小。一对的体重差定义为重的减轻的的值，此值一定大于等于0，譬如有一对人，男的体重为50，女的体重为55，则他(她)们的体重差为5，反过来如果男的体重为55，女的体重为50，则他(她)们的体重差仍然是5。

【输入描述】

第一行包含一个自然数N（1≤N≤1000），表示有N对人；

第2～N+1行：每行包含一个自然数，表示N个男人的体重；

第N+2～2N+1行：每行包含一个自然数，表示N个女人的体重。

【输出描述】

仅有一行包含一个整数，表示配对后N对男女的体重差的总和的最小值。

【样例输入】

4  2  8  5  5  1  4  10  7

【样例输出】

6