pas联赛是什么-pla联赛是什么意思

2009年信息学奥赛（我是高一的）的四道题目及解法

1．潜伏者

(spy.pas/c/cpp)

问题描述

R 国和S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。

历尽艰险后，潜伏于 S 国的R 国间谍小C 终于摸清了S 国军用密码的编码规则：

1． S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所

得的内容均由大写字母‘A’-‘Z’构成（无空格等其他字符）。

2． S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替

换为其对应的“密字”。

3． 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以

和原字母相同。

例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信

息“ABA”被加密为“ACA”。

现在，小 C 通过内线掌握了S 国网络上发送的一条加密信息及其对应的原信息。小C

希望能通过这条信息，破译S 国的军用密码。小C 的破译过程是这样的：扫描原信息，对

于原信息中的字母x（代表任一大写字母），找到其在加密信息中的对应大写字母y，并认为

在密码里y 是x 的密字。如此进行下去直到停止于如下的某个状态：

1． 所有信息扫描完毕，‘A’-‘Z’ 所有 26 个字母在原信息中均出现过并获得了相应

的“密字”。

2． 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。

3． 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反S 国密码的编码规则）。例

如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。

在小 C 忙得头昏脑涨之际，R 国司令部又发来电报，要求他翻译另外一条从S 国刚刚

截取到的加密信息。现在请你帮助小C：通过内线掌握的信息，尝试破译密码。然后利用破

译的密码，翻译电报中的加密信息。

输入

输入文件名为 spy.in，共3 行，每行为一个长度在1 到100 之间的字符串。

第 1 行为小C 掌握的一条加密信息。

第 2 行为第1 行的加密信息所对应的原信息。

第 3 行为R 国司令部要求小C 翻译的加密信息。

输入数据保证所有字符串仅由大写字母‘A’-‘Z’构成，且第1 行长度与第2 行相等。

输出

输出文件 spy.out 共1 行。

若破译密码停止时出现 2，3 两种情况，请你输出“Failed”（不含引号，注意首字母大

写，其它小写）。

否则请输出利用密码翻译电报中加密信息后得到的原信息。

输入输出样例 1

spy.in spy.out

AA

AB

EOWIE

Failed

全国信息学奥林匹克联赛（NOIP2009）复赛提高组

第 3 页共 7 页

输入输出样例 1 说明

原信息中的字母‘A’和‘B’对应相同的密字，输出“Failed”。

输入输出样例 2

spy.in spy.out

QWERTYUIOPLKJHGFDSAZXCVBN

ABCDEFGHIJKLMNOPQRSTUVWXY

DSLIEWO

Failed

输入输出样例2 说明

字母‘Z’在原信息中没有出现，输出“Failed”。

输入输出样例 3

spy.in spy.out

MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP

YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL

FLSO

NOIP

2．Hankson 的趣味题

(son.pas/c/cpp)

问题描述

Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫Hankson。现

在，刚刚放学回家的Hankson 正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数c1 和c2 的最大公约数和最小公倍数。现

在Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公

倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整

数x 满足：

1． x 和a0 的最大公约数是a1；

2． x 和b0 的最小公倍数是b1。

Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的

x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮

助他编程求解这个问题。

输入

输入文件名为 son.in。第一行为一个正整数n，表示有n 组输入数据。接下来的n 行每

行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入

数据保证a0 能被a1 整除，b1 能被b0 整除。

输出

输出文件 son.out 共n 行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的 x，请输出0；

若存在这样的 x，请输出满足条件的x 的个数；

全国信息学奥林匹克联赛（NOIP2009）复赛提高组

第 4 页共 7 页

输入输出样例

son.in son.out

2

41 1 96 288

95 1 37 1776

6

2

说明

第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。

第二组输入数据，x 可以是48、1776，共有2 个。

数据范围

对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。

对于 100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000 且n≤2000。

3．最优贸易

(trade.pas/c/cpp)

问题描述

C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个

城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路，一部分

为双向通行的道路，双向通行的道路在统计条数时也计为1 条。

C 国幅员辽阔，各地的分布情况各不相同，这就导致了同一种商品在不同城市的价

格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息

之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设C 国n 个城

市的标号从1~ n，阿龙决定从1 号城市出发，并最终在n 号城市结束自己的旅行。在旅游的

过程中，任何城市可以重复经过多次，但不要求经过所有n 个城市。阿龙通过这样的贸易方

式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另

一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来C 国旅游，他决定

这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

设 C 国有5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路

为单向通行，双向箭头表示这条道路为双向通行。

设 1~n 号城市的水晶球价格分别为4，3，5，6，1。

阿龙可以选择如下一条线路：1->2->3->5，并在2 号城市以3 的价格买入水晶球，在3

号城市以5 的价格卖出水晶球，赚取的旅费数为2。

阿龙也可以选择如下一条线路 1->4->5->4->5，并在第1 次到达5 号城市时以1 的价格

买入水晶球，在第2 次到达4 号城市时以6 的价格卖出水晶球，赚取的旅费数为5。

全国信息学奥林匹克联赛（NOIP2009）复赛提高组

第 5 页共 7 页

现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号

以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

输入

输入文件名为 trade.in。

第一行包含 2 个正整数n 和m，中间用一个空格隔开，分别表示城市的数目和道路的

数目。

第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n 个城

市的商品价格。

接下来 m 行，每行有3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，

表示这条道路是城市x 到城市y 之间的单向道路；如果z=2，表示这条道路为城市x 和城市

y 之间的双向道路。

输出

输出文件 trade.out 共1 行，包含1 个整数，表示最多能赚取的旅费。如果没有进行贸易，

则输出0。

输入输出样例

trade.in trade.out

5 5

4 3 5 6 1

1 2 1

1 4 1

2 3 2

3 5 1

4 5 2

5

数据范围

输入数据保证 1 号城市可以到达n 号城市。

对于 10%的数据，1≤n≤6。

对于 30%的数据，1≤n≤100。

对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。

对于 100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市

水晶球价格≤100。

4．靶形数独

(sudoku.pas/c/cpp)

问题描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他

们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z 博士请教，

Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有9 个3 格宽×3 格

高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些

全国信息学奥林匹克联赛（NOIP2009）复赛提高组

第 6 页共 7 页

数字，利用逻辑推理，在其他的空格上填入1 到9 的数字。每个数字在每个小九宫格内不能

重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即

每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

上图具体的分值分布是：最里面一格（**区域）为 10 分，**区域外面的一圈（红

色区域）每个格子为9 分，再外面一圈（蓝色区域）每个格子为8 分，蓝色区域外面一圈（棕

色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 分，如上图所示。比赛的

要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取

更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字

的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游

戏规定，将以总分数的高低决出胜负。

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能

够得到的最高分数。

全国信息学奥林匹克联赛（NOIP2009）复赛提高组

第 7 页共 7 页

输入

输入文件名为 sudoku.in。

一共 9 行。每行9 个整数（每个数都在0—9 的范围内），表示一个尚未填满的数独方

格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。

输出

输出文件 sudoku.out 共1 行。

输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。

输入输出样例 1

sudoku.in sudoku.out

7 0 0 9 0 0 0 0 1

1 0 0 0 0 5 9 0 0

0 0 0 2 0 0 0 8 0

0 0 5 0 2 0 0 0 3

0 0 0 0 0 0 6 4 8

4 1 3 0 0 0 0 0 0

0 0 7 0 0 2 0 9 0

2 0 1 0 6 0 8 0 4

0 8 0 5 0 4 0 1 2

2829

输入输出样例 2

sudoku.in sudoku.out

0 0 0 7 0 2 4 5 3

9 0 0 0 0 8 0 0 0

7 4 0 0 0 5 0 1 0

1 9 5 0 8 0 0 0 0

0 7 0 0 0 0 0 2 5

0 3 0 5 7 9 1 0 8

0 0 0 6 0 1 0 0 0

0 6 0 9 0 0 0 0 1

0 0 0 0 0 0 0 0 6

2852

数据范围

40%的数据，数独中非0 数的个数不少于30。

80%的数据，数独中非0 数的个数不少于26。

100%的数据，数独中非0 数的个数不少于24。

答案：

1、潜伏者

program spy;

var

v: array['A'..'Z'] of boolean;

p, q: array['A'..'Z'] of char;

a, b: string;

j: char;

i: integer;

procedure stop;

begin

writeln('Failed');

close(input);

close(output);

halt;

end;

begin

assign(input, 'spy.in');

reset(input);

assign(output, 'spy.out');

rewrite(output);

readln(a);

readln(b);

fillchar(v, sizeof(v), 0);

for i := 1 to length(a) do

begin

v[a[i]] := true;

p[a[i]] := b[i];

q[b[i]] := a[i];

end;

for j := 'A' to 'Z' do

if not v[j] then stop;

for i := 1 to length(a) do

begin

if p[a[i]] <> b[i] then stop;

if q[b[i]] <> a[i] then stop;

end;

readln(a);

for i := 1 to length(a) do

write(p[a[i]]);

writeln;

close(input);

close(output);

end.

2、Hankson的趣味题

program son;

var

p, x, c: array[1..10000] of longint;

n, m, t, i, j, k, a0, a1, b0, b1: longint;

function gcd(m, n: longint): longint;

var

r: longint;

begin

while n <> 0 do

begin

r := m mod n;

m := n;

n := r;

end;

gcd := m;

end;

procedure dfs(const i: longint; s: longint);

var

j: longint;

begin

if i > m then

begin

inc(k);

p[k] := s;

exit;

end;

dfs(i + 1, s);

for j := 1 to c[i] do

begin

s := s * x[i];

dfs(i + 1, s);

end;

end;

procedure get(b: longint);

var

i: longint;

begin

m := 0;

i := 2;

while i <= sqrt(b) + 1e-6 do

begin

if b mod i = 0 then

begin

inc(m);

x[m] := i;

c[m] := 0;

repeat

inc(c[m]);

b := b div i;

until b mod i <> 0;

end;

inc(i);

end;

if b <> 1 then

begin

inc(m);

x[m] := b;

c[m] := 1;

end;

k := 0;

dfs(1, 1);

end;

begin

assign(input, 'son.in');

reset(input);

assign(output, 'son.out');

rewrite(output);

read(n);

for i := 1 to n do

begin

read(a0, a1, b0, b1);

get(b1);

t := 0;

for j := 1 to k do

if (gcd(p[j], a0) = a1) and (p[j] div gcd(p[j], b0) * b0 = b1) then

inc(t);

writeln(t);

end;

close(input);

close(output);

end.

3、最优贸易

program trade;

const

maxn = 100005;

var

e1, e2: array[1..1000010] of record

t, next: longint;

end;

a, b, g1, g2, q: array[1..maxn] of longint;

v: array[1..maxn] of boolean;

n, i, f, r, k, p, s: longint;

procedure init;

var

m, s, i, j, k, z: longint;

procedure link(const i, j: longint);

begin

inc(s);

with e1[s] do

begin

t := j;

next := g1[i];

end;

g1[i] := s;

with e2[s] do

begin

t := i;

next := g2[j];

end;

g2[j] := s;

end;

begin

read(n, m);

for i := 1 to n do read(b[i]);

fillchar(g1, sizeof(g1), 0);

fillchar(g2, sizeof(g2), 0);

s := 0;

for k := 1 to m do

begin

read(i, j, z);

link(i, j);

if z = 2 then link(j, i);

end;

end;

begin

assign(input, 'trade.in');

reset(input);

assign(output, 'trade.out');

rewrite(output);

init;

fillchar(v, sizeof(v), 0);

a[1] := b[1];

for i := 2 to n do a[i] := 100000;

f := 0;

r := 1;

q[1] := 1;

while f <> r do

begin

if f = maxn then f := 1 else inc(f);

k := q[f];

v[k] := false;

p := g1[k];

while p <> 0 do

begin

with e1[p] do

if a[t] > a[k] then

begin

a[t] := a[k];

if a[t] > b[t] then a[t] := b[t];

if not v[t] then

begin

if r = maxn then r := 1 else inc(r);

q[r] := t;

v[t] := true;

end;

end;

p := e1[p].next;

end;

end;

s := 0;

fillchar(v, sizeof(v), 0);

f := 1;

r := 1;

q[1] := n;

v[n] := true;

if s < b[n] - a[n] then s := b[n] - a[n];

while f <= r do

begin

p := g2[q[f]];

while p <> 0 do

begin

with e2[p] do

if not v[t] then

begin

v[t] := true;

if s < b[t] - a[t] then s := b[t] - a[t];

inc(r);

q[r] := t;

end;

p := e2[p].next;

end;

inc(f);

end;

writeln(s);

close(input);

close(output);

end.

4、靶形数独

program d_1;

var usei,usej,u:array[0..10,0..10] of boolean;

usep:array[0..100] of boolean;

maxi,a:array[0..10,0..10] of longint;

t,s,max,tot,i,j,k,n,m,p:longint;

x,y:array[0..100] of longint;

function solve(i,J:longint):longint;

var s,s1:longint;

begin

if (i<=j) then s:=i else s:=j;

if (10-i<=10-j) then s1:=10-i else s1:=10-j;

if (s=1) or (s1=1) then begin solve:=6; exit;end;

if (s=2) or (s1=2) then begin solve:=7; exit;end;

if (s=3) or (s1=3) then begin solve:=8; exit;end;

if (s=4) or (s1=4) then begin solve:=9; exit;end;

if (s=5) or (s1=5) then begin solve:=10;exit;end;

end;

function pr(i,j:longint):longint;

begin

pr:=(i-1) div 3*3+(j-1) div 3+1;

end;

procedure tryit(pp,now:longint);

var t,min,w,j:longint;

begin

if pp=s+1 then

begin

if now>max then

begin

max:=now;

maxi:=a;

end

end

else

begin

t:=0; min:=999999;

for i:=1 to s do

if (a[x[i],y[i]]=0) and (not(usep[i])) then

begin

w:=0;

for j:=1 to 9 do

if (usei[x[i],j]) and (usej[y[i],j]) and (u[pr(x[i],y[i]),j]) then

begin

inc(w);

if w>=min then break;

end;

if w<min then

begin

min:=w;

t:=i;

end;

end;

if min=0 then exit;

usep[t]:=true;

for j:=1 to 9 do

if (usei[x[t],j]) and (usej[y[t],j]) and (u[pr(x[t],y[t]),j]) then

begin

usei[x[t],j]:=false;

usej[y[t],j]:=false;

u[pr(x[t],y[t]),j]:=false;

a[x[t],y[t]]:=j;

tryit(pp+1,now+solve(x[t],y[t])*j);

a[x[t],y[t]]:=0;

usei[x[t],j]:=true;

usej[y[t],j]:=true;

u[pr(x[t],y[t]),j]:=true;

end;

usep[t]:=false;

end;

end;

begin

assign(input,'sudoku.in');

assign(output,'sudoku.out');

reset(input);

rewrite(output);

fillchar(usei,sizeof(usei),true);

fillchar(usej,sizeof(usej),true);

fillchar(u,sizeof(u),true);

tot:=0; max:=0; s:=0;

for i:=1 to 9 do

begin

for j:=1 to 9 do

begin

read(a[i,j]);

if a[i,j]<>0 then

begin

usei[i,a[i,j]]:=false;

usej[j,a[i,j]]:=false;

u[pr(i,j),a[i,j]]:=false;

t:=solve(i,j);

tot:=tot+t*a[i,j];

end;

if (a[i,j]=0) then

begin

inc(s);

x[s]:=i; y[s]:=j;

end;

end;

readln;

end;

fillchar(usep,sizeof(usep),false);

tryit(1,tot);

if max=0 then writeln('-1') else writeln(max);

close(input);

close(output);

end.

求第十二届全国青少年奥林匹克信息学联赛(普及组PASCAL语言)复赛试题

第十二届全国青少年信息学奥林匹克

联赛复赛试题

（NOIP2006普及组）

竞赛时间：2006年11月18日 下午1:30-4:30

试题名称

random

Hy

count

sequence

目录

random

Hy

count

sequence

输入文件名

random.in

hy.in

count.in

sequence.in

输出文件名

random.out

hy.out

count.out

sequence.out

试题类型

非交互式程序题

非交互式程序题

非交互式程序题

非交互式程序题

附加文件

无

无

无

无

时限

1秒

1秒

1秒

1秒

关于竞赛中不同语言使用限制的说明

一．关于使用Pascal语言与编译结果的说明

1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。

2．允许使用数学库(uses math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。

二．关于C++语言中模板使用的限制说明

1．允许使用的部分：

标准容器中的布尔集合，迭代器，串，流。

相关的头文件：

2．禁止使用的部分：

序列：vector，list，deque

序列适配器：stack, queue, priority_queue

关联容器：map, multimap, set, multiset

拟容器：valarray

散列容器：hash_map, hash_set, hash_multimap, hash_multiset

所有的标准库算法

相关头文件：

1.明明的随机数

（random.pas/c/cpp）

问题描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入文件

输入文件random.in 有2行，第1行为1个正整数，表示所生成的随机数的个数：

N

第2行有N个用空格隔开的正整数，为所产生的随机数。

输出文件

输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入样例

10

20 40 32 67 40 20 89 300 400 15

输出样例

8

15 20 32 40 67 89 300 400

2.开心的金明

(hy.pas/c/cpp)

问题描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入文件

输入文件hy.in 的第1行，为两个正整数，用一个空格隔开：

N m

（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数

v p

（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）

输出文件

输出文件hy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

输入样例

1000 5

800 2

400 5

300 5

400 3

200 2

输出样例

3900

3.Jam的计数法

（count.pas/c/cpp）

问题描述

Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则U，且不存在Jam数字P，使U）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。

输入文件

输入文件counting.in 有2行，第1行为3个正整数，用一个空格隔开：

s t w

（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1≤s≤26, 2≤w≤t-s ）

第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。

所给的数据都是正确的，不必验证。

输出文件

输出文件counting.out 最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。

输入样例

2 10 5

bdfij

输出样例

bdghi

bdghj

bdgij

bdhij

befgh

4.数列

（sequence.pas/c/cpp）

问题描述

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：

1，3，4，9，10，12，13，…

（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）

请你求出这个序列的第N项的值（用10进制数表示）。

例如，对于k=3，N=100，正确答案应该是981。

输入文件

输入文件sequence.in 只有1行，为2个正整数，用一个空格隔开：

k N

（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。

输出文件

输出文件sequence.out 为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。（整数前不要有空格和其他符号）。

输入样例

3 100

输出样例

981

NOIP2010（Pascal提高组）复赛

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 1 页 共 7 页

全国信息学奥林匹克联赛（NOIP2010）复赛

提高组（请选手务必仔细阅读本页内容）

一．题目概况

中文题目名称 机器翻译 乌龟棋 关押罪犯 引水入城

英文题目与子目录名 translate tortoise prison flow

可执行文件名 translate tortoise prison flow

输入文件名 translate.in tortoise.in prison.in flow.in

输出文件名 translate.out tortoise.out prison.out flow.out

每个测试点时限 1秒 1秒 1秒 1秒

测试点数目 10 10 10 10

每个测试点分值 10 10 10 10

附加样例文件 有 有 有 有

结果比较方式 全文比较（过滤行末空格及文末回车）

题目类型 传统 传统 传统 传统

二．提交源程序文件名

对于pascal语言 translate.pas tortoise.pas prison.pas flow.pas

对于C语言 translate.c tortoise.c prison.c flow.c

对于C++语言 translate.cpp tortoise.cpp prison.cpp flow.cpp

三．编译命令（不包含任何优化开关）

对于pascal语言 fpc translate.pasfpc tortoise.pasfpc prison.pas fpc flow.pas

对于C语言

gcc -o translate

translate.c -lm

gcc -o tortoise

tortoise.c -lm

gcc -o prison

prison.c -lm

gcc -o flow

flow.c -lm

对于C++语言 g++ -o translate

translate.cpp -lm

g++ -o tortoise

tortoise.cpp -lm

g++ -o prison

prison.cpp -lm

g++ -o flow

flow.cpp -lm

四．运行内存限制内存上限 128M 128M 128M 128M

注意事项：

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

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

3、全国统一评测时用的机器配置为：CPU P4 3.0GHz，内存1G，上述时限以此配置为准。

各省在自测时可根据具体配置调整时限。

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 2 页 共 7 页

1．机器翻译

(translate.pas/c/cpp)

问题描述

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，

软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中

文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入

内存前，如果当前内存中已存入的单词数不超过M?1，软件会将新单词存入一个未使用的

内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，

存放新单词。

设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多

少次词典？设在翻译开始前，内存中没有任何单词。

输入

输入文件名为translate.in，输入文件共2行。每行中两个数之间用一个空格隔开。

第一行为两个正整数M和N，代表内存容量和文章的长度。

第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文

单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出输出文件translate.out共1行，包含一个整数，为软件需要查词典的次数。

输入输出样例1

translate.in translate.out

3 7

1 2 1 5 4 4 1

5

输入输出样例1说明

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

空：内存初始状态为空。

1． 1：查找单词1并调入内存。

2． 1 2：查找单词2并调入内存。

3． 1 2：在内存中找到单词1。

4． 1 2 5：查找单词5并调入内存。

5． 2 5 4：查找单词4并调入内存替代单词1。

6． 2 5 4：在内存中找到单词4。

7． 5 4 1：查找单词1并调入内存替代单词2。

共计查了5次词典。

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 3 页 共 7 页

输入输出样例2

translate.in translate.out

2 10

8 824 11 78 11 78 11 78 8 264

6

数据范围

对于10%的数据有M=1，N≤5。

对于100%的数据有0≤100，0≤1000。

2．乌龟棋

(tortoise.pas/c/cpp)

问题描述

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一

的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

……

1 2 3 4 5 ……N

乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型

的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡

片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择

一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到

该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的

分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡

片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到

多少分吗？

输入

输入文件名tortoise.in。输入文件的每行中两个数之间用一个空格隔开。

第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。

第2行N个非负整数，a1a2

……aN

，其中ai表示棋盘第i个格子上的分数。第3行M个整数，b1b2

……bM

，表示M张爬行卡片上的数字。

输入数据保证到达终点时刚好用光M张爬行卡片，即N?1=∑

M

ib

1

输出

输出文件名tortoise.out。

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 4 页 共 7 页

输出只有1行，1个整数，表示小明最多能得到的分数。

输入输出样例1

tortoise.in tortoise.out

9 5

6 10 14 2 8 8 18 5 17

1 3 1 2 1

73

输入输出样例1说明

小明使用爬行卡片顺序为1，1，3，1，2，得到的分数为6+10+14+8+18+17=73。注意，

由于起点是1，所以自动获得第1格的分数6。

输入输出样例2

tortoise.in tortoise.out

13 8

4 96 10 64 55 13 94 53 5 24 89 8 30

1 1 1 1 1 2 4 1

455

数据范围

对于30%的数据有1

≤

N

≤

30，1

≤

M

≤

12。

对于50%的数据有1≤N≤120，1

≤

M

≤

50，且4种爬行卡片，每种卡片的张数不会超

过20。

对于100%的数据有1≤N≤350，1≤M≤120，且4种爬行卡片，每种卡片的张数不会

超过40；0≤ai≤100，1≤i≤N；1≤bi≤4，1≤i≤M。输入数据保证N?1=

∑

M

ib

1

3．关押罪犯

(prison.pas/c/cpp)

问题描述

S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极

不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨

气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之

间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并

造成影响力为c的冲突。

每年年末，警察局会将本年内监狱中的所有冲突按影响力从大到小排成一个列表，

然后上报到S城Z那里。公务繁忙的Z只会去看列表中的第一个的影响力，

如果影响很坏，他就会考虑撤换警察局长。

在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在

两座监狱内重新分配，以求产生的冲突影响力都较小，从而保住自己的乌纱帽。设只

要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那

么，应如何分配罪犯，才能使Z看到的那个冲突的影响力最小？这个最小值是多

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 5 页 共 7 页

少？

输入

输入文件名为prison.in。输入文件的每行中两个数之间用一个空格隔开。

第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨

气值为cj。数据保证Nba

jj

≤1，0000000001

0≤

jc

，且每对罪犯组合只出现一

次。

输出

输出文件prison.out共1行，为Z看到的那个冲突的影响力。如果本年内监狱

中未发生任何冲突，请输出0。

输入输出样例

prison.in prison.out

4 6

1 4 2534

2 3 3512

1 2 28351

1 3 6618

2 4 1805

3 4 12884

3512

输入输出样例说明

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，看到的冲突

影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。

数据范围

对于30%的数据有N≤15。

对于70%的数据有N≤2000，M≤50000。

对于100%的数据有N≤20000，M≤100000。

2 1

3 4

1805 6618

2534 3512

12884

28351 2 1

3 4

2534 3512

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 6 页 共 7 页

4.引水入城

(flow.pas/c/cpp)

问题描述

湖泊

沙漠

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政

区划十分特殊，刚好构成一个N行M列的矩形，如上图所示，其中每个格子都代表一座城

市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施

有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的

蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通

过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是

存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。

由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利

设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干

旱区中不可能建有水利设施的城市数目。

输入

输入文件名为flow.in。输入文件的每行中两个数之间用一个空格隔开。

输入的第一行是两个正整数N和M，表示矩形的规模。

接下来N行，每行M个正整数，依次代表每座城市的海拔高度。

输出

输出文件名为flow.out。

输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少

建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有

几座干旱区中的城市不可能建有水利设施。

输入输出样例1

flow.in flow.out

2 5

9 1 5 4 3

8 7 6 1 2

11

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 7 页 共 7 页

样例1说明

只需要在海拔为9的那座城市中建造蓄水厂，即可满足要求。

输入输出样例2

flow.in flow.out

3 6

8 4 5 6 4 4

7 3 4 3 3 3

3 2 2 1 1 2

13

样例2说明

湖泊

8 4 5 6 4 4

7 3 4 3 3 3

3 2 2 1 1 2

沙漠

上图中，在3个粗线框出的城市中建造蓄水厂，可以满足要求。以这3个蓄水厂为源头

在干旱区中建造的输水站分别用3种颜色标出。当然，建造方法可能不唯一。

数据范围

本题共有10个测试数据，每个数据的范围如下表所示：

测试数据编号 能否满足要求 N M

1 不能 ≤ 10 ≤ 10

2 不能 ≤ 100 ≤ 100

3 不能 ≤ 500 ≤ 500

4 能 = 1 ≤ 10

5 能 ≤ 10 ≤ 10

6 能 ≤ 100 ≤ 20

7 能 ≤ 100 ≤ 50

8 能 ≤ 100 ≤ 100

9 能 ≤ 200 ≤ 200

10 能 ≤ 500 ≤ 500

对于所有的10个数据，每座城市的海拔高度都不超过10

6

换页

希腊足球的参赛球队

2015–16年希腊足球参赛队伍共有 16 支。 中文名称 英文名称 所在城市 奥林匹亚科斯 Olympiacos FC 比雷埃夫斯 PAOK塞萨洛尼基 P.A.O.K. FC 塞萨洛尼基 AEK雅典 AEK Athens 雅典 特里波利 Asteras Tripoli FC 特里波利 帕纳辛纳科斯 Panathinaikos FC 雅典 萨丁 Skoda Xanthi FC 克桑西 帕尼奥尼奥斯 Panionios GSS 雅典 卡洛尼 Kalloni FC 米蒂利尼 帕斯基安尼纳Pas Giannina阿尔塔普拉坦亚斯　　Platanias FC干尼亚　　莱瓦贾科斯Levadiakos　　伊拉克里斯Iraklis塞萨洛尼基帕纳多里高斯Panaitolikos Agrinio阿格里尼翁阿特罗米托斯PAE Atromitos佩里斯特里维瑞亚Veria FC韦里亚潘斯拉基科斯Panthrakikos亚历山德鲁波利斯