题目名称 905. 威斯康星州的牧场
输入输出 wissqu.in/out
难度等级
时间限制 5000 ms (5 s)
内存限制 128 MiB
测试数据 1
题目来源 Gravatarsywgz 于2012-07-12加入
开放分组 全部用户
提交状态
分类标签
USACO 搜索法
分享题解
通过:1, 提交:12, 通过率:8.33%
Gravatarcstdio 100 0.933 s 0.31 MiB C++
Gravatarmildark 0 0.000 s 0.31 MiB C++
Gravatarmildark 0 0.000 s 0.31 MiB C++
Gravatarmildark 0 0.000 s 0.31 MiB C++
Gravatarmildark 0 0.001 s 0.31 MiB C++
Gravatarmildark 0 0.001 s 0.31 MiB C++
Gravatarmildark 0 0.001 s 0.31 MiB C++
Gravatarmildark 0 0.001 s 0.31 MiB C++
Gravatarcstdio 0 1.000 s 0.31 MiB C++
Gravatarcstdio 0 1.000 s 0.31 MiB C++
关于 威斯康星州的牧场 的近10条评论(全部评论)
这道题重点是看懂题啊喂……
这道题的意思是用三个A,三个B,三个C,四个D,三个E替换题中所述的那个表格,要求不替换相同的字母且始终满足相同字母不8-相邻,输出的意义是按那个序列(比如说第一次用D替换(4,1)的B)替换后恰好形成一个合法的由三个A,三个B,三个C,四个D,三个E构成的表格
linux下读一行字符的问题不可战胜
裸搜,考虑到USACO的评测机巨快所以时限放宽至5s
Gravatarcstdio
2013-11-15 17:26 1楼

905. 威斯康星州的牧场

★   输入文件:wissqu.in   输出文件:wissqu.out   简单对比
时间限制:5 s   内存限制:128 MiB
USACO/wissqu(译 by Felicia Crazy)

描述

威斯康星州的春天来了,是该把小奶牛们赶到小牧场上并把大奶牛们赶到北纬 40 度的大牧场上的时候了。

农夫约翰的牧场上有五种奶牛(括号内的是缩写):格恩西奶牛(A),泽西奶牛(B),赫里福奶牛(C),黑安格斯奶牛(D),朗赫恩奶牛(E)。这些奶牛群放养在一片 16 英亩的牧场上,每英亩上都有一小群奶牛,像下面这样排列成 4 x 4 的格子(用行和列标号):

  1 2 3 4
 +-------
1|A B A C
2|D C D E
3|B E B C
4|C A D E

  

最初,牧场上的奶牛群总共有 3 群 A,3 群 B,4 群 C,3 群 D,3 群 E。今年的 D 种小奶牛比去年多一群 ,C 种少一群,共有 3 群 A,3 群 B,3 群 C,4 群 D,3 群 E。

农夫约翰对于他牧场上的奶牛群的布局非常小心。这是因为如果同一种类型的奶牛群靠得太近,她们就乱来:她们聚集在栅栏边上抽烟,喝牛奶。如果她们在相同的格子上或者在临近的 8 个格子上,就是靠得太近了。

农夫约翰得用他的棕色旧福特皮卡把他的大奶牛群运出牧场,并把他的小奶牛群运进牧场,皮卡一次只能运一群奶牛。他装上一群小奶牛,开车到小牧场的一个方格中,卸下这群小奶牛,再装上这个格子上的那群大奶牛,开到北纬 40 度的大牧场卸下来。他重复这样的操作 16 次,然后开车去杰克商店办理低脂酸奶的交易和家居装修。

帮助农夫约翰。他必须选择正确的顺序来替换他的奶牛群,使得他从不把一群小奶牛放入当前被同样类型奶牛占有的方格或者当前被同样类型奶牛占据的方格的临近方格。当然,一旦大奶牛走了,小奶牛来了,他必须小心以后的情况,要根据新的排列把奶牛群分开。

非常重要的提示:农夫约翰从过去的经验知道,他必须先移动 D 种奶牛群。

找出农夫约翰将他的小奶牛搬迁到她们的新牧场上的办法。输出 16 个连续的 奶牛群类型/行/列 的信息,使得这样的安排能够符合安全经验。

计算 4 x 4 牧场的最终排列总数(这应该是原题作者的笔误,输出样例中并没有说明要输出最终排列总数,此题只有一个测试数据,也没有体现这个问题——译者注),和产生那些排列的方式的总数。

 

PROGRAM NAME: wissqu

INPUT FORMAT (file wissqu.in)

四行,每行四个用空格分开的字母,表示奶牛群(又是原题作者的笔误了,字母之间没有空格——译者注)。


 

OUTPUT FORMAT(file wissqu.out)

16 行,每行分别由 奶牛群类型/行/列 组成。如果有多解(一定有),那么你应该输出奶牛群类型按照字典序排列在最前面的那个解。如果不只一个解满足条件,那么你应该输出行信息按照字典需排列在最前面的那个解。如果仍然不只一个解满足条件,那么你应该输出列信息按照字典序排列在最前面的那个解。

最后多输出一行,包含能够由这个排列方式产生的排列的总数。


 

SAMPLE INPUT (file wissqu.in)

ABAC
DCDE
BEBC
CADE


 

SAMPLE OUTPUT (file wissqu.out)

D 4 1
C 4 2
A 3 1
A 3 3
B 2 4
B 3 2
B 4 4
E 2 1
E 2 3
D 1 4
D 2 2
C 1 1
C 1 3
A 1 2
E 4 3
D 3 4
14925