b*******y
发帖数: 232 | 1 是样题，然后还是45分钟倒计时的
可以用各种语言编写
感觉这种题目，用C或者java写是不是编程时间上比不过python？
单单看题目本身也很难啊，像是hannoi，但比它难多了，不知道有什么思路？
There are K pegs. Each peg can hold discs in decreasing order of radius when
looked from bottom to top of the peg. There are N discs who have radius 1
to N; Given the initial configuration of the pegs and the final
configuration of the pegs, output the moves required to transform from the
initial to final configuration. You are required to do the transformations
in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and
placing it on top of anyother peg. At anypoint of time, the decreasing
radius property of all the pegs must be maintained.
Constraints:
1<= N<=8
3<= K<=5
Input Format:
NK
2nd line contains N integers, each in the range 1 to K, the i-th integer
denotes, the peg to which disc of radius i is present in the initial
configuration.
3rd line denotes the final configuration in a format similar to the initial
configuration.
Output Format:
The first line contains M - The minimal number of moves required to complete
the transformation.
The following M lines describe a move, by a peg number to pick from and a
peg number to place on.
If there are more than one solutions, it's sufficient to output any one of
them. You can assume, there is always a solution with less than 7 moves and
the initial confirguration will not be same as the final one.
Sample Input #00:
2 3
1 1
2 2
Sample Output #00:
3
1 3
1 2
3 2
Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1 | l******n
发帖数: 492 | 2 dp
没看懂
23
11
22
when
【在 b*******y 的大作中提到】
: 是样题，然后还是45分钟倒计时的
: 可以用各种语言编写
: 感觉这种题目，用C或者java写是不是编程时间上比不过python？
: 单单看题目本身也很难啊，像是hannoi，但比它难多了，不知道有什么思路？
: There are K pegs. Each peg can hold discs in decreasing order of radius when
: looked from bottom to top of the peg. There are N discs who have radius 1
: to N; Given the initial configuration of the pegs and the final
: configuration of the pegs, output the moves required to transform from the
: initial to final configuration. You are required to do the transformations
: in minimal number of moves.
| b*******y
发帖数: 232 | 3 sorry，粘贴的时候没空格了，已经在正文中改了，数字之间都有空格
【在 l******n 的大作中提到】
: dp
: 没看懂
: 23
: 11
: 22
:
: when
| l***i
发帖数: 1309 | 4 You can use BFS, each node is a configuration, each edge is a valid move.
Each configuration is an array of length at most 8, a[i]=peg that disc[i] is
at. So you have at most 5^8=10^6 configurations, which fits in memory. And
from each configuration you can make a move to next configuration using
those moves. Since you have only 5 pegs, you can have at most 4*5=20 valid
moves. Your total running time is then at most 10^6 states times at most 20
moves from each state, which is at most 10^8 and it should be pretty fast. | b*******y
发帖数: 232 | 5 Dynamic Programming做的话，configuration的indexing好像就不是那么清晰了。
例如我不知道下一个要算的configuration是什么...
也许，你说的Dynamic Programming是用了BFS的，这样，可以知道接下来要算的一组元
素。
不过要给每个configuration标记是否已经被访问过
好像这题也可以用DFS来做，就是遍历各种情况，因为题目告诉我们可以assume最短布
数在7步之内，而且很多move可以直接看出违反“小在上，大在下”的规律的。
is
And
20
【在 l***i 的大作中提到】
: You can use BFS, each node is a configuration, each edge is a valid move.
: Each configuration is an array of length at most 8, a[i]=peg that disc[i] is
: at. So you have at most 5^8=10^6 configurations, which fits in memory. And
: from each configuration you can make a move to next configuration using
: those moves. Since you have only 5 pegs, you can have at most 4*5=20 valid
: moves. Your total running time is then at most 10^6 states times at most 20
: moves from each state, which is at most 10^8 and it should be pretty fast.
| g**********y
发帖数: 14569 | 6 这个题不好写的是状态保存和转换。
最多5个peg, 8个disc, 所以可以用long(64-bit)来保存状态，转换需要位操作。
这是我的写法，欢迎改进：
public class KPeg {
public void move(int N, int K, int[] begin, int[] end) {
long s0 = stateToLong(begin);
long sn = stateToLong(end);
ArrayList visited = new ArrayList();
visited.add(new Node(s0, 0, 0, -1));
Deque dq = new ArrayDeque();
dq.add(0);
while (!dq.isEmpty()) {
int current = dq.remove();
for (int i=0; i
for (int j=0; j
long next = move(visited.get(current).state, i, j);
if (next == sn) {
visited.add(new Node(next, i+1, j+1, current));
printSolution(visited, current);
return;
}
if (next > 0 && !seen(visited, next)) {
visited.add(new Node(next, i+1, j+1, current));
dq.add(visited.size() - 1);
}
}
}
}
}
private boolean seen(ArrayList visited, long state) {
for (Node node : visited) if (node.state == state) return true;
return false;
}
private long stateToLong(int[] state) {
long s = 0;
for (int i=0; i
s |= (1 << i) << (8*state[i] - 8);
}
return s;
}
private long move(long state, int from, int to) {
if (from == to) return -1;
int pegFrom = (int) ((state >> 8*from) & 0xff);
int pegTo = (int) ((state >> 8*to) & 0xff);
for (int i=0; i<8; i++) {
if ((pegFrom >> i & 1) > 0) {
state &= ~((1L << i) << 8*from);
state |= (1L << i) << 8*to;
return state;
}
if ((pegTo >> i & 1) > 0) return -1;
}
return -1;
}
private void printSolution(ArrayList visited, int current) {
Stack stack = new Stack();
stack.push(visited.size()-1);
while (current > 0) {
stack.push(current);
current = visited.get(current).parent;
}
System.out.println(stack.size());
while (!stack.isEmpty()) {
int t = stack.pop();
System.out.println(visited.get(t).from + " " + visited.get(t).to
);
}
}
private class Node {
long state;
int from;
int to;
int parent;
public Node(long state, int from, int to , int parent) {
this.state = state;
this.from = from;
this.to = to;
this.parent = parent;
}
}
public static void main(String[] args) {
KPeg k = new KPeg();
// k.move(2, 3, new int[]{1, 1}, new int[]{2, 2});
k.move(6, 4, new int[]{4, 2, 4, 3, 1, 1}, new int[]{1, 1, 1, 1, 1, 1
});
}
} | l*********y
发帖数: 142 | 7 顺手写了一个，46min整。也没用状态压缩，待会看一下gloomyturkey的code。
#include
#include
#include
#include
#include
#include
#include
| C*******l
发帖数: 1198 | | d*******l
发帖数: 338 | 9 这学期试着在学习python，用python也写了一个。力求简练，效率应该不怎么高。
def getpath(now, visited, steps):
if now == visited[h(now)]:
print steps;
return ;
prev = visited[h(now)];
p = [i for i in xrange(0, len(now)) if now[i] != prev[i]][0];
getpath(prev, visited, steps + 1);
print prev[p], now[p];
def h(node):
return ''.join([str(n) for n in node]);
def solve(N, K, init, target):
q = [init];
visited = {h(init):init};
while q != []:
now = q.pop(0);
if now == target:
getpath(now, visited, 0);
for i in [j for j in xrange(0, N) if [k for k in xrange(j) if now[k]
== now[j]] == []]:
for j in [k for k in xrange(1, K + 1) if [l for l in xrange(i)
if now[l] == k] == []]:
next = now[:];
next[i] = j;
if not visited.has_key(h(next)):
visited[h(next)] = now;
q.append(next);
if __name__ == '__main__':
(N, K) = map(int, raw_input().split(' '));
init = map(int, raw_input().split(' '));
target = map(int, raw_input().split(' '));
solve(N, K, init, target); | d*******l
发帖数: 338 | 10 主要要解决的问题就像上面说的是状态的表示和move。我得思路是，其实输入的那种格
式就可以很好的表示状态，即从小到大N个disc的位置构成的向量。每次move的时候，
从小到大试着移动disc，如果某个disc之前有和它位置相同的，那就说明它无法移动。
确定可以移动之后，枚举所有可能位置，如果它之前有在这个位置上的，就不能移动到
这个位置。这里说的“之前”就是在向量中下标比它小的那些元素。 | b*******y
发帖数: 232 | 11 学习了，
python编写严格限时完成的题目的时候，比c++有很大优势
【在 d*******l 的大作中提到】
: 这学期试着在学习python，用python也写了一个。力求简练，效率应该不怎么高。
: def getpath(now, visited, steps):
: if now == visited[h(now)]:
: print steps;
: return ;
: prev = visited[h(now)];
: p = [i for i in xrange(0, len(now)) if now[i] != prev[i]][0];
: getpath(prev, visited, steps + 1);
: print prev[p], now[p];
: def h(node):
|
|
