长郡NOIp模拟试题六
题目名称 老鼠找食物 商店购物 地图问题 魔板
程序文件 food.exe shop.exe map.exe magic.exe
输入文件 food.in shop.in;offer.txt map.in magic.in
输出文件 food.out shop.out map.out magic.out
时间限制 1s 1s 2s 1s
空间限制 16MB 16MB 16MB 16MB
题目分值 100 100 100 100
老鼠找食物
题意描述：
迷宫里饥肠辘辘的老鼠得到一张地图，上面记载了迷宫地图、目前所在位置、及所有食物所在位置。老鼠在迷宫里只能上下左右移动，一次移动一格，并且不能超过边界。请依照距离由近到远，列出牠从目前位置到每一个可以到得了的食物所在点，所需移动的最小步数。
输入描述：
输入档案第一行的两个整数代表地图的大小(M, N) (0<M, N<100, M不一定等于N)。第二行以后有M行（每行N个）字母记载地图的组态。字母B代表不能穿越的障碍物；字母C代表可自由移动的空间；字母R代表老鼠现在所在位置；字母F代表食物所在位置（可以穿越）。
输出描述：
在每行印出食物所在坐标（左下角原点的坐标为(0,0)，横向为X，纵向为Y）及老鼠走到此坐标所需步数。依步数由小到大印出。若步数相同，则按X优先Y次优先的顺序输出。
范例一：
输入：
5 5
BCBBC
CFCCB
BCBBC
RCCBF
BCCCC
输出：
(1,3) 3
(4,1) 6
范例二:
输入：
10 10
BCBBBCBCBB
BFCCCCBCCB
BCBBCCBCCB
BCCBFCCCCC
BCBBBBBBCB
CCBCRCCBCB
BCBBCBCCCC
BCFBCBBBCB
BCCCCCCBCC
BCBBCBBBBB
输出：
(2,2) 6
(4,6) 12
(1,8) 13
商店购物
题意描述：
某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。
特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。
编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:
1朵花加2个花瓶: 优惠价:10 ICU
2朵花 正常价: 4 ICU
输入描述：
用两个文件表示输入数据。第一个文件shop.in描述顾客所购物品（放在购物筐中）；第二个文件描述商店提供的优惠商品及价格（文件名为offer.txt）。两个文件中都只用整数。
第一个文件shop.in的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。
第二个文件offer.txt的格式为:第一行是一个数字S（0≤S≤99），表示共有S种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然，优惠价要低于该组合中商品正常价之总和。
输出描述：
在输出文件shop.out中写 一个数字（占一行）， 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
输入/输出数据举例
┌────────┐ ┌────────────┐┌────────┐
│ shop.in │ │ OFFER．TXT ││ shop.out │
├────────┤ ├────────────┤├────────┤
│ 2 │ │ 2 ││ 14 │
│ ７ ３ ２ │ │ 1 7 3 5 ││ │
│ ８ ２ ５ │ │ 2 7 1 8 2 10││ │
└────────┘ └────────────┘└────────┘
地图问题
题意描述：
在Byteland新的行政划分以后，制图工作室需要制作国家新的统计地图。因为技术上的原因，仅有很少的颜色能够被使用。地图上有着相同或者相似的人口（居民数）的地区被着为相同的颜色。对于给定的颜色K，让A（k）为数字，意思为：
1．至少有一半颜色为k的地区人口不大于A（k）。
2．至少有一半颜色为k的地区人口不少于A（k）。
地区的着色误差是指A（k）与地区人口之间的差额的绝对值，累积误差是指所有地区的着色误差之和。我们寻找一种地图的最佳着色方案（即最小的累积误差）。我们要求您写一个程序：
1．从输入文件map.in读取Byteland地区的人口，
2．计算最小的累积误差，
3．把结果写到文本文件map.out中。
输入描述：
在输入文件map.in的首行有一个整数n（30<=n<=300），它是Byteland的地区数。第二行有数字m（2<=m<=30），表示用于着色的颜色数。在接下来的n行中的每一行里有一个非负的整数- Byteland一个地区的人口数。注：人口数不超过2^30。
输出描述：
你的程序应该在输出文件map.out单独的一行里写下一个整数—等于能够完成地图最佳着色的最小累积误差。
样例输入：
11
3
21
14
6
18
10
2
15
12
3
2
2
样例输出：
15
魔板
题意描述：
在魔方风靡全球之后，Rubik先生发明了它的简化版－－魔板，如图1所示，魔板由8个同样大小的方块组成，每个方块的颜色均不相同，本题中以数字1－8分别表示，可能出现在魔板的任一位置，任一时刻魔板的状态可以用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，得到的数字序列即可表示此时魔板的状态。例如，序列（1,2,3,4,5,6,7,8）表示图1所示魔板的状态，这也就是题中魔板的初始状态。
1 2 3 4
8 7 6 5
图1：初始状态
对于魔板，可以施加三种不同的操作，分别以A，B，C标识。具体操作方法如下：
A：上下行互换；
B：上下两行同时循环右移一格；
C：中间4个方块顺时针旋转一格；
应用这三种基本操作，可以由任一状态达到任意另一状态。
图2描述了上述3种操作的具体含义，图中方格外面的数字标识魔板的8个方块位置，方格内的数字表示此次操作前该小方块所在位置。即：如果位置P中有数字I，则表示此次操作前该方块在位置I。
1 2 3 4 1 2 3 4 1 2 3 4
A 8 7 6 5 B 4 1 2 3 C 1 7 2 4
1 2 3 4 5 8 7 6 8 6 3 5
8 7 6 5 8 7 6 5 8 7 6 5
图2：三个基本操作
请编一程序，对于输入的一个目标状态，寻找一种操作的序列，使得从初始状态开始，经过此操作序无后使该魔板变为目标状态。并且这个操作序列应该尽量短。
输入描述：
文件名magic.in，第一行包含8个数字表示目标状态。
输出描述：
输出文件名为magic.out，在第一行输出你的程序寻找到的操作序列的步数L，随后L行是相应的操作序列，每行的行首写一个字符，代表相应的操作。
