2021“MINIEYE杯”中国大学生算法设计超级联赛（9）-题解1
需积分: 0 175 浏览量
2022-08-03
21:11:53
上传
评论
收藏 204KB PDF 举报
2021 HDU Multi-University Training Contest 9
Nanjing U Contest, Tuesday, August 17, 2021
Problem A. NJU Emulator
First, we consider the idea of doubling, for any N ≥ 2, we can obtain N using (×2) or (×2 + 1) from
1 in blog
2
Nc steps. Then we may come up with an algorithm to construct any N within O(log N) s86
instructions as follows:
Use 3 instructions "p1, dup, add 1"to push 1 and 2 into stack, then use "p1"and (×2) or (×2 + 1) for
blog
2
Nc times to get N.
It takes at most 2blog
2
Nc+ 5 instructions to construct N, which is too large. To improve our algorithm,
we can consider applying the method of four Russians, i.e., try to use a larger base k instead of the base
2.
For any k ≥ 2 and N ≥ 2, we can obtain N using (×k + p)(0 ≤ p < k) from some x(1 ≤ x < k) by
blog
k
Nc steps. Thus we can use 2k −1 instructions "p1, dup, add 1, dup, add 1, ..."to push 1, 2, ..., k into
the stack, then use "p1, add (x-1)"and blog
k
Nc times of (×k + p)(0 ≤ q < k) operation to get N.
It takes at most 2blog
k
Nc+ 2k + 2 instructions to construct N. Take k = 7(or 8, 9, 10, 11, 12), we obtain
an algorithm to construct any N < 2
64
within 60 s86 instructions, which is close to our goal.
For further improvements, note that for a base k, if we have obtained 1, 2, ..., bk/2c and k in the stack,
then for any x ≤ k, we can get x in 2 steps as following:
• "p1, add x − 1"when x ≤ bk/2c.
• "dup, sub k − x"when x > bk/2c.
Then for N > k, we can obtain N using (×k + p)(0 ≤ p ≤ bk/2c) or (×k − p)(1 ≤ p ≤ bk/2c) from
some x(1 ≤ x ≤ k) in blog
k
Nc steps. Thus we can use k + 1 instructions to push 1, 2, ..., bk/2c and k
into the stack, then construct x in 2 steps, finally applying blog
k
Nc times of (×k + p)(0 ≤ p ≤ bk/2c) or
(×k − p)(1 ≤ p ≤ bk/2c) to get N .
It takes at most 2blog
k
Nc+ k + 4 instructions to construct N. Take k = 16(or 12, 14), we can obtain an
algorithm to construct any N < 2
64
within 50 s86 instructions.
Problem B. Just another board game
Consider what is the optimal strategy if the "instant-ending"operation is not allowed. We can reinterpret
the operations of the two players as follows:
We start with r = 1 and c = 1. In each turn, if it’s Roundgod’s turn to move, he can set c to
some arbitrary value satisfying 1 ≤ c ≤ m. If it’s kimoyami’s turn to move, he can set r to
some arbitrary value satisfying 1 ≤ r ≤ n. After k rounds, the game ends, and the value of
the game is a
r,c
.
We consider the process backward. If it’s Roundgod to move in the last turn, he should obviously choose c
to be the position of the maximum element in the current row, and thus kimoyami, who is second-to-last
to move, should choose r to be the row with the minimal maximum. Similarly, if it’s kimoyami to move in
the last turn, he should choose r to be the position of the minimum element in the current column, and
thus Roundgod, who is second-to-last to move, should choose c to be the row with the maximal minimum.
There still exists a special case where k = 1, i.e., the game only lasts for at most one turn, then clearly
it’s optimal for Roundgod to choose the maximum in the first row.
So, let’s now consider the case where the "instant-ending"operation is allowed. I claim that this operation
wouldn’t make much difference to the strategy for both players, except for the first move of Roundgod.
Why is this the case? Because if you choose the second operation after your opponent has moved, it is
never better than doing nothing(keeping the chess unmoved), as in the optimal strategy of your opponent,
he would also do nothing(or if he chooses the second operation, it’s still the same), otherwise, if he chooses
Page 1 of 6
评论0
最新资源