训练2

1

2011年全国青少年信息学奥林匹克联赛

莱芜市第一中学暑期训练2

试题名称 1 火星人 2 盖房子 提交文件 martians.cpp/c/pas house.cpp/c/pas 输入输出文件 martians.in/out house.in/out 本题总分 100 100 试题名称 4最小数字倍数 提交文件 num.cpp/c/pas 输入输出文件 num.in/out 本题总分 100 3 十字绣 ten.cpp/c/pas ten.in/out 100 1 火星人

描述 Description

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3„„。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字： 三进制数 123 132 213 231 312 321 代表的数字 1 2 3 4 5 6

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

LOI Whybert

2

输入格式 Input Format

输入包括三行，第一行有一个正整数N，表示火星人手指的数目(1<=N<=10000)。第二行是一个正整数M，表示要加上去的小整数(1<=M<=100)。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式 Output Format

输出只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。、

样例输入 Sample Input

5 3

1 2 3 4 5

样例输出 Sample Output

1 2 4 5 3

时间限制 Time Limitation 各个测试点1s

2盖房子

描述 Description

永恒の灵魂最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所房子，这个房子必须是正方形的。 但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。 他希望找到一块最大的正方形无瑕疵土地来盖房子。

不过，这并不是什么难题，永恒の灵魂在10分钟内就轻松解决了这个问题。

现在，您也来试试吧。 输入格式 Input Format

输入文件第一行为两个整数n,m（1<=n,m<=1000），接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。

输出格式 Output Format

一个整数，最大正方形的边长。

样例输入 Sample Input

4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1

样例输出 Sample Output

2

LOI Whybert

3

时间限制 Time Limitation

1s

3 十字绣

背景 Background

考古学家发现了一块布，布上做有针线活，叫做“十字绣”，即交替地在布的两面穿线。

描述 Description

布是一个n*m的网格，线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一，而在绣的过程中，一针中连续的两段线必须分处布的两面。给出布两面的图案(实线代表该处有线,虚线代表背面有线)，问最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。

输入格式 Input Format

第1行两个数N和M(1<=N,M<=200)。 接下来N行每行M个数描述正面。 再接下来N行每行M个数描述反面。

每个格子用.（表示空）,/（表示从右上角连到左下角）,\\（表示从左上角连到右下角）和X（表示连两条对角线）表示。

输出格式 Output Format

一个数，最少要用的针数。

样例输入 Sample Input

4 5 ..... .\\... ..\\.. ..... ..... ....\\

LOI Whybert

4

.\\X.. .....

样例输出 Sample Output

4

时间限制 Time Limitation 各个测试点1s

4 最小数字倍数

描述 Description

写一个程序，对于给定的一个自然数N（0≤N≤4999），以及M个不同的十进制数字X1,X2...XM（M≥1 最多10个数字），找出一个由X1,X2..XM组成的整数P，使得P是N的严格的倍数，且要求P最小。

输入格式 Input Format

第一行为一个整数N。第二行为一个整数M。此后的M行分别为M个数字X1,X2..XM。

输出格式 Output Format 输出一个整数P（占一行），保证有解。

样例输入 Sample Input 22

3 7 0 1

样例输出 Sample Output 110

时间限制 Time Limitation 1s