ACM q305 作法

Question

http://luckycat.kshs.kh.edu.tw/homework/q305.htm
此題作法為何？
dfs？

可以說得具體一些嗎？能有code?

Answer 1

這題是simulation(模擬)

你就先假設m=1，然後模擬去殺一遍，看看這樣會不會達到目標
如果不行的話，再設m=2，再去做一遍，直到找最一個可以的m
這個m就是最小的答案

你可以先把k=1~13的答案都算好存到陣列裡
要注意的是在模擬時應該不能用陣列，不然會TLE
你只要用一個變數代表殺到誰
再用一個變數代表還剩幾個人就行了

以上是想法
如果還是不懂的話
可以再補充發問或是寄信給我

2007-02-02 02:07:49 補充：
樓下說錯了
而且程式也不對

sample並沒有錯
當k=4時共有8個人
若m=30，被殺的順序為6、8、7、5
符合題目的要求

2007-02-02 15:35:49 補充：
#include
int ans[15];
void create()
{
int i,m;
int test,last,pos,flag;
for(test=1;test<=13;test )
{
m = 1;
while(1)
{
last = 2 * test;
pos = last - 1;
flag = 1;
for(i=1;i<=test;i )
{
pos = (pos m) % last;

2007-02-02 15:36:10 補充：
if(pos {
flag = 0;
break;
}
else
{
last--;
pos--;
}
}
if(flag==1) break;
else m ;
}
ans[test] = m;
}
}
main()
{
int n;
create();
while(scanf("%d",&n)==1)
{
if(n==0) break;
else printf("%d\n",ans[n]);
}
}

2007-02-02 15:38:23 補充：
因字數限制
請複製後自行縮排以方便閱讀

不過我不建議你看別人的code
因為這東西要自己多寫才會進步

Answer 2

標準的殺人模擬題
可以用array來模擬
殺掉其中一個人之後，將後面的人搬上來
然後用 % 餘數算一下就知道下個該殺的人在哪了
寫的好的話，其實1~13都可以在程式裡面跑完填表
還是會過的 :-)
(雖然大家都直接寫在code裡面)

順帶一題
很多的殺人題目都可以用DP來解 (Dynamic Programming)
速度比模擬要快得多
如果模擬過不了，可以換個方向來想 :-)
比如說ACM180
單純模擬的話是過不了的
給你參考

2007-02-02 02:35:13 補充：
ps. Sample沒錯，是二樓的JJ錯了 :p

Answer 3

本程式會印出 "被吃" 的順序 (一半的人)
n = 2k => 留下 k 人
n = 2k+1 => 留下 k 人
以及 最小的 m
Sample 中 n=4 的答案不對 (m=30 剛好相反, 先吃掉 1, 2)

#include
main()
{
int i, j, skip, outp, Ns, Diff, resvr, done;
int ary[15];
do
{
printf("Number ( <14 ) : ");
scanf("%d", &Ns);
if (Ns == 0) return;
resvr = (int) (Ns/2);
Diff = resvr;
done = 0;
do
{
for (i = 1; i <= Ns; i++) /* 預設 全部都還沒數過 */
ary[i] = 0;
Diff++;
outp = 0; /* 都還沒數 */
i = 0; /* 目前指標的位置 */
while (outp < Ns)
{
skip = 0; /* 還沒找到有效的間隔 */
while (skip < Diff)
{
i++;
if (i > Ns) i -= Ns; /* 超過最大數了嗎 */
if (ary[i] == 0) skip++; /* 找到有效的間隔數 */
}
if (i <= resvr) break;
ary[i] = ++outp; /* 標示這一個數過了 */
if (outp == (Ns - resvr)) done = 1;
}
} while (!done);
for (i = 1; i <= outp; i++)
for (j = 1; j <= Ns; j++)
if (ary[j] == i)
{
printf("%d ", j);
break;
}
printf("\n%d\n", Diff);
} while (Ns != 0);
return;
}
如果有問題, 請來函討論. 不然, 我可能會錯失你再補充的疑點.

2007-02-03 05:38:53 補充：
我看錯 Sample 裡的 k 的意思
其他兩位看錯我程式裡 n 的意思
程式裡 n 是自然數 從 1 到 14
(如果要放大, 請把 ary[15] 加大即可)

所以本程式可以處理 奇數和偶數 的情形
請看程式頭的說明