入门必做的题（再接上）

61. 一个餐厅在相继的Ｎ天里，第 i 天需要 Ri 块餐巾(i=1，2，...，N)。餐厅
 可以从三种途径得到餐巾:
   (1) 购买新的餐巾，每块需Ｐ分；
   (2) 把用过的餐巾送到快洗部，洗一块需Ｍ天，费用需Ｆ分(Ｆ＜Ｐ)；
   (3) 把餐巾送到慢洗部，洗一块需Ｎ天(Ｎ＞Ｍ)，费用需Ｓ分(Ｓ＜Ｆ)。
 在每天结束时，餐厅必须决定将多少块用过的餐巾送到快洗部，多少块送慢洗部，
 多少块保存起来延期送洗。在每天开始时，餐厅必须决定是否购买新餐巾及购买多
 少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使Ｎ天总的费用最小。请
 编程输入总天数，每天所需的餐巾块数以及每块餐巾的新购费用Ｐ，快，慢洗费用
 Ｆ，Ｓ，和所需天数Ｍ，Ｎ，输出每天开始时需购新餐巾数，结束时送快，慢洗部
 和延期送洗的餐巾数。

 62. ( 旅行商 ) 一个推销员计划做一次旅行，他必须访问如图所示每个城市。每
 两个城市的路径旁标有路径。要求从城市Ａ出发，访问每个城市一次，且只访问一
 次，最后返回城市Ａ，求一条距离最短的路线。

 63. (tic__tac__toe 游戏) tic__tac__toe 游戏的规则是：从一个空的 (N*N) 的
 棋盘（例如Ｎ＝３）开始，甲乙二人轮流将棋子放置在棋盘上未被占据的方格中，
 例如甲第一个放，他把棋子放在中央的方格里， 然后轮到乙放，他把棋子放在第
 一行中间的方格里。于是又轮到甲放，......如此进行下去。判定胜负的方法是：
 若某一游戏者有Ｎ枚棋子占据了一横行，或一竖列，或一对角线，则此人获胜；若
 直至整个棋盘被占满还没有一方获胜，则为平局。
     ┏━┯━┯━┓         ┏━┯━┯━┓         ┏━┯━┯━┓
     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │Ｏ│  ┃
     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨
     ┃  │  │  ┃         ┃  │Ｘ│  ┃         ┃  │Ｘ│  ┃
     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨
     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │  │  ┃
     ┗━┷━┷━┛         ┗━┷━┷━┛         ┗━┷━┷━┛

 
作者：GCC
专家分：14380
 会员信息
 发短消息  
 所属BLOG
    
发表时间：2006-4-14 12:05:00    [回复]  [引用]
13 楼  
64.  以字符串形式由键盘输入两个高精度的８进制正整数，串长小于２５５，以
 第一个数为被除数，第二个数为除数，进行高精度除法运算，并显示按 8 进制表
 示的商和余数。
 ( 参看程序 8 )

 65. ( NOI'94.1_1 ) 键盘输入一个仅由小写字母组成的字符串，输出以该串中任
 取Ｍ个字母的所有排列及排列总数。

 66. ( NOI'94.1_2 ) 编程实现两个高精度实数减法，两数分别由键盘输入，均不
  超过２４０位。
 ( 参看程序 5 )

 67. ( NOI'94.1_3 ) 一个实数数列共有Ｎ项，已知a(i)=(a(i-1)-a(i+1))/2+d，
（１〈i〈Ｎ）(N<60) , 键盘输入Ｎ，d，a(1)，a(n)，m，输出 a(m)。

 68. ( NOI'94.1_4 ) 键盘输入一个高精度的正整数Ｎ，去掉其中任意Ｓ个数字后
 剩下的数字按原左右次序将组成一个新的正整数。编程对给定的Ｎ和Ｓ，寻找一种
 方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新
 的正整数。（Ｎ不超过２４０位）

 69. 在两个文本文件中各存有一个以西文制表符制成的未填入任何表项的表结构，
 分别称之为表１和表２，要求编程将表１和表２下述规则合并成表３：
     规则：表１在表２之上，表１和表２的左边框对齐，将表１的最低行与表２的
 最顶行合并。例：在你的Ｃ盘根目录下有两个文件 t0.1 和 t0.2，分别存放上述
 的表１和表２，经上述规则合并后得到表３，放在文件中。三张表见下图：
  ┎─┰─┰─┰─┒                                ┎─┰─┰─┰─┒
  ┃  ┃  ┃  ┃  ┃        ┎┰─┰─┒            ┃  ┃  ┃  ┃  ┃
  ┠─╂─╂─╂─┨        ┃┃  ┃  ┃            ┠─╂─╂─╂─┨
  ┃  ┃  ┃  ┃  ┃        ┖┸─┸─┚            ┃  ┃  ┃  ┃  ┃
  ┖─┸─┸─┸─┚                                ┠┰┸┰┸┰┸─┚
                                                    ┃┃  ┃  ┃
                                                    ┖┸─┸─┚
        表１                    表２                     表３
    编程要求：
   (1) 程序应能自给定的文件中读入两个源表并显示。
   (2) 若源表有错，应能指出其错。
   (3) 将表１和表２规则合并成表３，并显示之。
   (4) 所有制表符的ＡＳＣＩＩ码应由选手自己从给出的示例文件中截取。

 70. (圆盘问题) 从左向右依次安放 4 根细柱 A,B,C,D. 在 A 上套有 N (N≤20)
 个直径相同的圆盘, 从下到上依次用连续的小写字母 a,b,c,...编号, 将这些圆盘
 经过 B, C 单向地移入 D (即不允许从右向左移动). 圆盘可在 B,C 中暂存. 从键
 盘输入 N, 及前 N 个小写字母的一个排列, 它表示最后在 D 盘上形成的一个从下
 到上的圆盘序列. 请用文本文件 ANS2.TXT 输出形成这一排列的操作过程.
   该文件的每一行为一个形如 "k M L" 的字母序列, 其中 k 为圆盘编号, M 为 k
 盘原先的柱号, L 为新柱号. 或者直接在屏幕上输出"No",表示不能生成这种排列.
     例:                                ┃      ┃      ┃      ┃
     键盘输入:                          ┃      ┃      ┃      ┃
         3                        d   ━╋━    ┃      ┃      ┃
         acb                      c   ━╋━    ┃      ┃      ┃
     则一个正确的输出文件         b   ━╋━    ┃      ┃      ┃
  可以是:                         a   ━╋━    ┃      ┃      ┃
      c  A  B                       ━━┻━━━┻━━━┻━━━┻━??
      b  A  C                           A       B       C       D
      a  A  D
      b  C  D
      c  B  D

 
作者：GCC
专家分：14380
 会员信息
 发短消息  
 所属BLOG
    
发表时间：2006-4-14 12:06:00    [回复]  [引用]
14 楼  
71. (最长连线) 设有一个 N×N 的方格图形，且 N 为 3 的倍数。要求在图形中
 存放 0 或 1，相邻的 1 可以连成一条连线，连接的方法可以是行，也可以是列；
 同时约定一条连线只能有一个起点和一个终点，图形上的点最多只能访问一次。
 编程求最长连线. 例如 N＝6 时，有下图：
                 １  ２  ３  ４  ５  ６
               ┌─┬─┬─┬─┬─┬─┐
           １  │１│１│１│０│０│１│
               ├─┼─┼─┼─┼─┼─┤
           ２  │１│１│０│１│１│１│
               ├─┼─┼─┼─┼─┼─┤
           ３  │０│０│０│１│０│１│
               ├─┼─┼─┼─┼─┼─┤
           ４  │１│１│０│１│１│１│
               ├─┼─┼─┼─┼─┼─┤
           ５  │０│１│０│０│０│０│
               ├─┼─┼─┼─┼─┼─┤
           ６  │１│１│１│１│０│０│
               └─┴─┴─┴─┴─┴─┘
   在该图中，包含有如下的一些连线：
     １←１←１        １←１                     １
     ↓                ↓                         ↓
     １→１            １                 １→１  １
                       ↓                 ↑      ↓
                       １→１→１         １      １
                                          ↑      ↓
                                          １←１←１
    在以上的连线中，最长的连线为：    表示方法：
             １                       最长连线长度：LMAX=9
             ↓                       连线：(1,6)→(2,6)→
     １→１  １                             (3,6)→(4,6)→
     ↑      ↓                             (4,5)→(4,4)→
     １      １                             (3,4)→(2,4)→
     ↑      ↓                             (2,5)
     １←１←１                  连线的表示不是唯一的，仅给出一种即可。


 72. (NOI'95.1_2)　在一个园形操场的四周摆放 N 堆石子(N≤100)， 现要将石子
有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆
的石子数，记为该次合并的得分。
　　编一程序，由文件读入堆数 N 及每堆的石子数(≤20)，
　　① 选择一种合并石子的方案, 使得做N-1次合并, 得分的总和最小;
    ② 选择一种合并石子的方案, 使得做N-1次合并, 得分的总和最大.
    例如, 图 2-1 所示的4堆石子,每堆的石子数(从最上面的一堆数起, 顺时针数)
依次为4  5  9  4. 则 3 次合并得分总和最小的方案为图2-2,得分总和最大的方案
为图 2-3.
    (加图)
　　输入数据:
    文件名由键盘输入，该文件内容为;
    第一行为石子堆数 N;
    第二行为每堆的石子数, 每两个数之间用一个空格符分隔
    输出数据:
    输出文件名为 OUTPUT.TXT
　　第 1 至 N-1 行为得分最小的合并过程. 每行包含两个数, 表示应该合并的两
 堆石子的数目, 小数在前, 大数在后, 第 N 行为合并成一堆后的最小得分总和;
 第 N+1 行为空行, 第 N+2 至 2N+1 行为得分最大合并过程(格式同前). 第 2N+2
 行为最大得分总和.

 
作者：GCC
专家分：14380
 会员信息
 发短消息  
 所属BLOG
    
发表时间：2006-4-14 12:07:00    [回复]  [引用]
15 楼  
73. (NOI'95.1_4) N 位由 0 和 1 组成的字符串 A、B 可分别表示为
　　A＝ａNａN-1…ａi…ａ2ａ1
　　B＝ｂNｂN-1…ｂi…ｂ2ｂ1
 其中, ａi＝0或1, ｂi＝0或1,   1≤i≤N, N≤15.
    如果存在某一位j(j∈1…N), 在该位上两串不同, 即ａj≠ｂj, 而其余N-1位
 上的两串相同, 即ａi＝ｂi(i∈1…N，i≠j), 则称 A、B 两串“互邻”。
　　比如，在N＝4时, A＝1100, B＝1000, A、B 两串“互邻”, 而 C＝1100, D＝
 1010, C、D 两串不“互邻”。
 编程要求：
    寻找一个含有 2N 个上述01串的序列, 该序列满足以下要求:
    ① 组成该序列的每一个01串都与其它串不同;
    ② 第k个串与第k-1个串有“互邻”关系，2≤k≤2N;
    ③ 该序列首项由输入指定.
    例如 N=2, 指定首项为01, 则一个满足上述要求的序列为
    01  11  10  00
　　输入数据                         ┏━━━━━━┓  ┏━━━━━┓
    文件名由键盘输入                 ┃EXAMPLE4.TXT┃  ┃MODEL4.TXT┃
    该文件共有两行                   ┠──────┨  ┠─────┨
    第一行为  N                      ┃2           ┃  ┃2         ┃
    第二行为指定的序列首项           ┃01          ┃  ┃01        ┃
                                     ┃            ┃  ┃11        ┃
　　输出数据                         ┗━━━━━━┛  ┃10        ┃
    输出文件为 OUTPUT.TXT                              ┃00        ┃
    第一行为  N                                        ┃          ┃
    第二行至第2N+1行依次输出序列的每一个串.            ┗━━━━━┛
　　输入输出举例
    参考输入文件: EXAMPLE4.TXT
    参考输出文件: MODEL4.TXT

 74. (NOI'95.1_5) m、n为整数，且满足下列两个条件：
　　① m、n∈｛1, 2, …, k｝, (1≤k≤109)
    ② (n^2－m*n－m^2)^2＝1
    编一程序, 由键盘输入k, 求一组满足上述两个条件的 m、n, 并且使m^2＋n^2
 的值最大.
    例如, 若 k＝1995, 则 m＝987, n＝1597 时, 则 m、n 满足条件, 且可使
 m^2＋n^2的值最大.

 75. (钱币系统问题) 某钱币系统由 k (k≤20) 种硬币组成, 币值依次为 a[1],
 a[2],...,a[k], 其中 a[i] (i=1,2,...,k) 为互不相同的正整数, 且依降序排列,
 a[1]≤200. 给定某整数币值 n(n≤3000), 要求用最少枚数的硬币表示这个币值.
    输入: 用文件输入已知数据, 格式为:
      第 1 行: k (硬币种数)
      第 2 行: a[1] a[2] ... a[k] (各币值用空格隔开,已按降序排列好)
      第 3 行: n (给定的币值)
    输出: 直接在屏幕上输出结果. 如果该钱币系统无法表示币值 n,应输出'No',
 否则按以下格式输出:
      第 1 行: 最少钱币枚数 r.
      第 2 行: 输出若干形如 m*n 的表达式, m 为币值, n为使用该币值的枚数.
 各式第 2 个因子之和应等于 r, 各式乘积之和应等于 n.
    例: 设 (a[1],a[2],a[3])=(5,2,1),  n=12,  则应输出
       3
       5*2  2*1.

 
作者：GCC
专家分：14380
 会员信息
 发短消息  
 所属BLO
    
发表时间：2006-4-14 12:07:00    [回复]  [引用]
16 楼  
76. (省刻度尺问题)给定长度为 L 的直尺, L 为整数, 且L≤40. 为了能一次直接
 量出  1,2,...,L 的各种长度, 该尺内部至少要有多少条刻度 ?  请输出最少刻度
 数( 不含两端点)及每个刻度的位置. 测量长度时可利用两端点, 其位置分别为 0,
 L.
    输入: 由键盘输入 L.
    输出: 用文本文件按以下格式输出结果(文件名: ANS2.TXT):
      第 1 行: S ( 最少刻度数 )
      第 2 行: 尺内 S 个刻度的位置
      第 3 行至第 L+2 行: 每行输出 3 个用空格隔开的整数 t m n, 其中
 1≤t≤L 为要测量的各长度, m,n 依次为该长度的起止刻度 (m    例: 如果 L=6, 则一个正确的输出是:
       2
       1 4                    提示:  (1) 最少刻度数 S 应满足:
       1 0 1                     C[S+2,2]=(S+2)*(S+1)/2≥L.
       2 4 6                         (2) 除两端点外, 第一个刻度可取为
       3 1 4                     A[1]=1, 第二个刻度可在 1, L-2, L-1 这
       4 0 4                     三个数中选取.
       5 1 6
       6 0 6