CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组Day1试题

CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day1

(请选手务必仔细阅读本页内容)

一.题目概况

中文题目名称 Vigenère 密码 国王游戏 开车旅行 英文题目与子目录名 vigenere game drive 可执行文件名 vigenere game drive

输入文件名 vigenere.in game.in drive.in 输出文件名 vigenere.out game.out drive.out 每个测试点时限 1秒 1秒 1秒 测试点数目 10 10 20 每个测试点分值 10 10 5 附加样例文件 有 有 有

结果比较方式 全文比较(过滤行末空格及文末回车) 题目类型传统 传统 传统 二.提交源程序文件名

对于 C++语言 vigenere.cpp game.cpp drive.cpp 对于 C 语言 vigenere.c game.c drive.c

对于 pascal 语言 vigenere.pas game.pas drive.pas

三.编译命令(不包含任何优化开关) 对于 C++语言 g++ -o vigenere vigenere.cpp -lm g++ -o game game.cpp -lm g++ -o game drive.cpp -lm 对于 C 语言 gcc-o vigenere vigenere.c -lm gcc-o vigenere game.c -lm gcc-o vigenere drive.c -lm

对于 pascal 语言 fpc vigenere.pas fpc game.pas fpc drive.pas

128M 128M

四.运行内存限制 内存上限

128M 128M 128M 注意事项:

1、文件名(程序名和输入输出文件名)必须使用英文小写。

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

3、全国统一评测时采用的机器配置为:CPU Intel Core2 Quad Q8200 2.33GHz, 内存 2G,上述时限以此配置为准。

4、特别提醒:评测在 NOI Linux 下进行。

1.Vigenère 密码 (vigenere.cpp/c/pas) 【问题描述】

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。Vigenère 密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南军所广泛使用。

在密码学中,我们称需要加密的信息为明文,用 M 表示;称加密后的信息为密文,用C 表示; 而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 k。 在 Vigenère 密码中,密钥 k 是一个字母串, k1k2...kn。 当明文 M=m1m2...mn 时,

得到的密文 C=c1c2...cn,其中 ci=mi?ki,运算?的规则如下表所示:

Vigenère 加密在操作时需要注意:

1. ?运算忽略参与运算的字母的大小写,并保持字母在明文 M 中的大小写形式; 2. 当明文 M 的长度大于密钥 k 的长度时,将密钥 k 重复使用。 例如,明文 M=Helloworld,密钥 k=abc 时,密文 C=Hfnlpyosnd。 明文 H e l l o w o r l d 密钥 a b c a b c a b c a 密文 H f n l p y o s n d 【输入】

输入文件名为 vigenere.in。 输入共 2 行。

第一行为一个字符串,表示密钥 k,长度不超过 100,其中仅包含大小写字母。第二行为一个字符串,表示经加密后的密文,长度不超过 1000,其中仅包含大小写字母。 【输出】

输出文件名为 vigenere.out。

输出共 1 行,一个字符串,表示输入密钥和密文所对应的明文。 【输入输出样例】

vigenere.in

CompleteVictory

Yvqgpxaimmklongnzfwpvxmniytm vigenere.out

Wherethereisawillthereisaway 【数据说明】

对于 100%的数据,输入的密钥的长度不超过 100,输入的密文的长度不超过 1000,且都仅包含英文字母。 2.国王游戏 (game.cpp/c/pas) 【问题描述】

恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。 【输入】

输入文件为 game.in。

第一行包含一个整数 n,表示大臣的人数。 第二行包含两个整数 a 和 b, 之间用一个空格隔开,

分别表示国王左手和右手上的整数。

接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。 【输出】

输出文件名为 game.out。

输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。 【输入输出样例】 game.in 3 1 2 7 4 game.out 2 1