noip1995普复赛试题

noip1995普复赛试题

1 NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛

分区联赛复赛试题（初中组）

（上机编程，完成时间：210分钟）

<1> 设有下列的算式：

8 0 9

-------------

□□) □□□□

□□

-------------

□□□

□□□

-------------

1

求出□中的数字，并打印出完整的算式来。

<2> 方阵填数：在一个N ?N 的方阵中，填入1，2，……N ?N 个数，并要求构成如下的格式：

例：

<3> 若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A 类数，否则就称其为B 类数。

例如：（13）10=（1101）2

其中1的个数为3，0的个数为1，则称此数为A 类数；

（10）10=（1010）2

其中1的个数为2，0的个数也为2，称此数为B 类数；

（24）10=（11000）2

其中1的个数为2，0的个数为3，则称此数为B 类数；

程序要求：求出1～1000之中（包括1与1000），全部A 、B 两类数的个数。

<4> 编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER ；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i ≠j 时）。

例如：N=6时，有： A=（4，3，0，5，1，2）

此时，数组A 的编码定义如下：

A[0]的编码为0；

N=5 13 14 15 16 1 12 23 24 17 2 11 22 25 18 3 10 21 20 19 4 9 8 7 6 5 N=6 16 17 18 19 20 1 15 30 31 32 21 2 14 29 36 33 22 3 13 28 35 34 23 4 12 27 26 25 24 5 11 10 9 8 7 6

noip1995普复赛试题

A[i]的编码为：在A[0]，A[1]，……A[i-1]中比A[i]的值小的个数（i=1，2……N-1）∴上面数组A的编码为：B=（0，0，0，3，1，2）

程序要求解决以下问题：

①给出数组A后，求出其编码；

②给出数组A的编码后，求出A中的原数据。

<5> 灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，

每种灯的个数记为N1，N2，……N k（k表示不同颜色灯的个数）。

放灯时要遵守下列规则：

①同一种颜色的灯不能分开；

②不同颜色的灯之间至少要有一个空位置。

例如：N=8（格子数）

R=2（红灯数）

B=3（蓝灯数）

放置的方法有：

R-B顺序

B-R顺序

放置的总数为12

数据输入的方式为：

N

P1（颜色，为一个字母）N1（灯的数量）

P2 N2

……

Q（结束标记，Q本身不是灯的颜色）

程序要求：求出一种顺序的排列方案及排列总数。

2

本文来源：https://www.bwwdw.com/article/eh31.html