厦理机考平台题目(未附答案).doc

哥德巴赫猜想Description1742年，哥德巴赫在给好友欧拉的一封信里陈述了他著名的猜想哥德巴赫猜想：任何一个大于4的偶数都是两个素数之和。例如：8=3+5，3和5都是素数。20=3+17=7+1342=5+37=11+31=13+29=19+23你的任务是写出10000以内的哥德巴赫猜想。Input输入包含一组或多组测试数据。测试数据每一行是一个偶数N（0 N = 10000）输入数据以0为结束符，0不需要处理。Output对于每行测试数据，对应一行形式为N=a+b输出(a b)，a和b必须是素数。如果有多种结果，请输出b-a最大的一组。Sample Input820420Sample Output8=3+520=3+1742=5+37升降序列Description给定N个整数Di(1 = Di = 3，1 = i = N)组成的序列，现在要求改变序列中的一些整数，使得改变后的序列是一个递增序列或者是一个递减序列。例如，序列“13211”可以通过改变一个整数转换成为序列“33211”； 序列“1132”可以通过改变一个整数转换成为序列“1133”。 由于改变一个整数都需要一些费用，简单起见，改变每一个整数都需要1个单位的费用。给定N个整数组成的序列，请你计算出最少需要改变序列中多少个整数，使得改变后的序列是一个递增的序列或者是一个递减的序列。Input输入数据的第一行为一个整数N(1 = N = 100),表示序列中整数的个数。接着一行有N个整数Di(1 = Di = 3，1 = i = N)，分别表示序列中每一个整数的值。Output输出一行一个整数D，表示最少需要改变序列中整数的数量，使得改变后的序列是一个递增序列或者是一个递减序列，如果不需要改变请输出0。Sample Input51 3 2 1 1Sample Output1平分Description玛莎和比尔共同收藏了一批石头。现在他们想以相同的价值均分这批收藏的石头。如果这些石头的价值是相同的那就好办了，但是非常的遗憾的是，这些石头大小不一，美观程度也不一样，因此玛莎和比尔用1到6之间的自然数对每块石头赋予价值。现在他们以相同的价值对这些收藏的石头进行平分。不幸的是，他们意识到即使这些石头的总价值是偶数的情况下，这方法有些时候也不能帮他们实现平分。例如，价值为1的石头有1块；价值为3的石头有1块；价值为4的石头有2块；就不能实现平分。现在他们要求你写一程序帮助他们核查他们的这些石头是否能够平分。Input输入数据第一行是一个正整数N(1 = N = 20)，表示有N组数据需要判断。接下来的N行表示N组数据。每行输入描述了一组待平分的收藏石头。每行数据有6个非负整数构成，其中第i个表示价值为i的石头数量。因此，上述例子表示为“1 0 1 2 0 0”，石头总数不能超过200。Output对于每组收藏，如果可以平分输出YES，否则输出NO，每组测试结果用空行分割。Sample Input21 0 1 2 0 01 0 0 0 1 1Sample OutputNOYESDescription设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti共有 s处可以提供此项服务。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。Input第一行有 2 个正整数n 和 s （0 s = n = 100），表示有n 个顾客且有 s处可以提供顾客需要的服务。 接下来的1 行中，有n个正整数， 表示n个顾客需要的服务时间。Output输出最小平均等待时间，保留两位小数。Sample Input10 256 12 1 99 1000 234 33 55 99 812Sample Output336.00素数环Description问题描述：将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。Input第一行是测试数据的n（0 = t = 12）。输入数据一定存在解。Output输出以1打头所有的素数环，每个解对应一行，每个解元素之间的用空格间隔。如果存在满足题意叙述的素数环，从小到大输出。Sample Input6Sample Output1 4 3 2 5 61 6 5 2 3 4勇者斗恶龙Description有一头有着N个头的恶龙，有M名骑士，每名骑士有一把魔剑。每一把魔剑有两个参数ci和di。如果当前恶龙的头不小于ci个，则骑士可以使用魔剑砍掉恶龙的恰好ci个头；如果当前恶龙的头小于ci个，则骑士无法使用这把魔剑；如果恶龙还没有死亡(即恶龙的头的个数大于0)，则恶龙会立即长出di个头；如果恶龙的头的个数超过L个，则多余的头会脱落，并保持在L个；只有砍掉恶龙所有的头才算是杀死恶龙。你的任务就是判断这M个骑士能否杀死恶龙，如果可以，请输出最少需要使用魔剑的次数，否则输出“-1”。Input输入数据的第一行是三个整数N，M，L(1N500，1M10，NLN+500)，表示恶龙有N个头，骑士数目为M，恶龙的头的数量限制为L。紧接着M行，第i行有两个整数ci，di(0ci，di1,000，1iM)，表示第i把魔剑的参数。如果能够杀死恶龙，则输出最少需要使用魔剑的次数，否则输出“-1”。每把魔剑的使用次数是无限的。Output输出一行一个整数B，表示能够杀死恶龙时最少需要使用魔剑的次数，如果不能杀死恶龙，输出-1Sample Input20 2 5007 18 5Sample Output3最小m段和Description理工学院的学生每个学年结束以后都要搬宿舍，搬宿舍的烦恼还只是暂时的，搬宿舍以后发现插座不够用是永远的伤痛。同学们发现新宿舍只有一个插座，但他们有很多台电脑需要同时使用，于是他们买来了好几个排插，每个排插可支持的插头不一样多，你的任务是帮他们计算一下他们的排插能支持多少台电脑同时使用。（ 注意：排插本身也需要电源接入 ）Input输入数据由一个整数N打头（ 1 = N = 10 ），表示接下来测试案例的个数。接下来是N行，每行描述了一个测试案例。每个测试案例以一个整数K打头（ 1 = K = 10 ），表示这个测试案例中排插的数量。然后同一行中紧跟着K个整数，中间用空格隔开，O1O2OK（ 2 = Oi = 10 ）表示每个插座可支持的插头数。Output每个测试案例对应一行整数输出，这个整数表示最多能支持的电脑数量。Sample Input23 2 3 44 10 10 10 10Sample Output737Description中国人做事情喜欢走捷径，一方面走捷径做事效率高，但另一方面也产生了不遵守规则等问题。小明在玩一个数字游戏，请你帮他找到一条捷径。该数字游戏是一个N行的三角形如下图所示。请你设计一个算法，计算从三角形的底端到顶端的一条捷径，使这条的捷径经过的数字总和最小。（下层的每个数字节点只能跳转到它相邻的两个上层数字节点，如：底层第一个5只能跳转到上层的2或7；底层的4只能跳转到上层2）73 88 1 02 7 4 44 5 2 6 5Input输入数据由一个整数N打头（ 1 = N = 10 ），表示三角形的行数为N，接下来N行是数字三角形各行中的数字Oi（ 1 = Oi = 100 ）。第N行有N个数字。Output输出一行正整数，表示数字总和的最小值。Sample Input573 88 1 02 7 4 44 5 2 6 5Sample Output17牲口棚的安全Description农夫为他的牲口棚安装了一套新的安全系统。现在需要为牛群中的每头母牛设定一个有效的秘密。一个有效的密码由L（3 = L = 15）个不同的小写字母组成（即为传统的拉丁字符az），其中至少包含一个元音字母（a, e, i, o, 或u）和至少两个辅音字母（非元音字母），而且字母必须按字母表顺序排列（如：abc 是有效密码； bac 是无效密码）。Input第一行是两个整型数L和C（ 3 = L = 15 ）（ L = C = 20 ），以空格间隔。第二行是构成密码字符串的C个小写字母，以空格间隔。Output输出是一个长度为L的密码字符串（密码字符串中没有空格）。同时要求密码字符串必须按字母表的顺序依次输出。密码字符串之间以换行间隔。Sample Input4 6a t c i s wSample OutputacisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistwHint四位密码从给定的六个字母中选出雾霾大作战Description京津冀地区常发生雾霾，厦门人普遍感受不深。如今厦门有时也会发生雾霾，厦门市政府决定推行公共自行车来解决雾霾问题。政府决定在厦禾路上设置了N 个自行车出租站1，2，N。市民可在这些自行车出租站租用自行车，并在下面的任何一个自行车出租站归还自行车。自行车出租站i 到自行车出租站j 之间的租金为ri,j，表示第i个站点到第j个站点的租金。试设计一个算法，计算出从自行车出租站1 到自行车出租站N 所需的最少租金。Input测试数据的第一行是一个整数N（ 1 = N = 50 ）表示该测试数据共有N个自行车出租站。接下来的N-1 行是ri,j （ 1 = i j = N ），（ 1 = ri,j = 1000 ），第N行有N-1个数字。Output所需的最少租金。Sample Input35 157Sample Output12Hint输入3（3个自行车出租站）5（出租站1到出租站2的租金) 15(出租站1到出租站3的租金）7（出租站2到出租站3的租金）输出：12（最少租金5+7=12）高智商的游戏Description小明和小红从小到大上的是重点托儿所、重点幼儿园、重点小学、重点初学、重点高中、重点大学，他们俩的智商都是180+，今天他们俩决定玩一个高智商小孩之间的游戏。游戏规则如下：一开始在桌面上放了N堆扑克牌，每次每个人能从任意一堆扑克牌中取走任意张扑克，直到某个人无法取走扑克为止，此时游戏结束，不能再取扑克的人就算输。小明总是先开始取扑克。现在给定扑克的初始状态，让你来判定最终获胜的是小明还是小红。Input测试数据的第一行是一个整数N（ 1 = N = 10 ）表示该测试数据共有N堆扑克。接下来一行由N个数构成，中间用空格隔开，O1O2ON（ 1 = Oi = 100 ）表示每堆有多少张扑克。Output如果小明能获胜则输出NO，否则输出YESSample Input33 6 9Sample OutputYES鬼群Imp swarmDescription伊吹萃香最近迷上了一个游戏，首先利用自己操作疏密程度的能力发动spell card 鬼群Imp swarm，变出n个分身，并让分身组成一个类似循环链表的圈并从1开始编号，之后第一次让第m个分身消失，以后每次继续往后数k个分身，并让这个分身消失，开始玩之前，萃香自己先猜一个数x，看看最后剩下的那个分身是不是第x个分身Input输入包含多组数据，每组数据包含四个正整数n,k,m,x(1=m,x=n,k=1000000)。输入结束标志为n=k=m=x=0。Output对于每个数据，如果猜对输出YES，猜错输出NO，每个数据的输出占一行。Sample Input8 5 3 14 2 1 34 2 1 40 0 0 0Sample OutputYESNOYES魔理沙借走了重要的东西帕秋莉擅长元素魔法，能够使用金、木、水、火、土、日、月七系魔法以及复合魔法。一般使用的是单元素或者双元素的复合魔法，所以这次研究的是三种元素复合的魔法。帕秋莉可以在七种元素中选择任意三种不同元素，并在每种不同的元素分配自己任意的灵力（至少为1），但是如果其中一种元素分配的灵力大于其余所有元素分配的灵力总和，就会元素失衡，则不能这样分配。而且如果所有元素都分配相同的灵力，会造成灵力制约，也不能这样分配。现在帕秋莉想知道在给每种元素分配消耗不超过n灵力的范围内，一共有多少种三元素的复合魔法。Input输入包含多组数据，每组数据包含一个正整数n(2=n=1000000)。输入结束标志为n=0。Output对于每个数据，输出计算结果除以1000000007的余数，每个数据的输出占一行。Sample Input230Sample Output210735M子才不是抖M呢她召唤出了N块岩石，但是每块岩石都不大，天子想把这N块岩石合并成一块巨大的岩石，由于弄塌博丽神社后还有一系列要