作者smartboy (小光光)
看板ACMCLUB
標題Re: world final 賽記
時間Tue Apr 6 15:26:37 2004
※ 引述《smartboy (小光光)》之銘言：
: : 我猜應該是終止條件的英文解讀問題.
: 事實上我沒明講, 是希望有人會去看看題目之類的 ;)
: 在比賽時我就把題目讀了三四遍, 深怕漏掉什麼條件沒看到
: 比完賽我繼續拿 source code 反覆閱讀想看出問題在哪,
: 也解釋給隊友聽.
: 比完賽隔天睡前再讀一次, 覺得有句的英文意思我不太肯定.
: Input for the last test case is followed by a line consisting of
: letter X.
: 比賽當時我覺得要一行剛好是 "X" 才結束.
: 重看幾遍, 那 "AAAXAAA" 呢, "XXX" 呢
: 若問題真出在這裡, 真是太可惜了.
所以我還是希望在其他地方有 bug 只是我沒看出來 :P
以下附當時我寫的 code, 大家幫忙看看吧(印出來再 keyin 的, 大致上保持原樣)
(第一次 time limit execeeded, 所以我加上一些 cut, 順便用 macro 降常數)
順帶一題, 這次大會有說, 不公布各題時限, 只知是合理的時間,
judge solution 的執行時間乘上一個 constant factor 云云.
gcc compile 參數只有 -lm, 沒加 optimize flags
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int m;
#define PLUS(x) x++; if(x==m) x=0;
#define SKIPSPACE(s,str) while(str[s]==0) { PLUS(s) }
int skipspace(int s,char str[])
{
while(str[s]==0)
s=(s+1)%m;
return s;
}
int next(int now,int k,char str[])
{
SKIPSPACE(now,str);
while(k--) {
PLUS(now);
//now=(now+1)%m;
SKIPSPACE(now,str);
}
return now;
}
int getstr(int start,int k,int len,char str[],char output[])
{
int i;
int now=start;
for(i=0;i<len;i++) {
if(i==0)
now=next(now,0,str);
else
now=next(now,k,str);
output[i]=str[now];
str[now]=0;
}
output[i]=0;
return 0;
}
int matstr(int start,int k,int len,char str[],char tomatch[])
{
int i;
int now=start;
for(i=0;i<len;i++) {
if(i==0)
now=next(now,0,str);
else
now=next(now,k,str);
if(tomatch[i]!=str[now])
return 0;
str[now]=0;
}
return 1;
}
int main(void)
{
int z;
char line[45];
char str[45];
char stra[45];
int casen=0;
freopen("insecure.in","r",stdin);
while(scanf("%s",line)==1 && strcmp(line,"X")) {
int bestlen=0,bestans=0;
char beststr[45]="";
char bak2[45];
int len;
int s,i,t,j;
char linecpy[45];
int count[256]={0};
strcpy(linecpy,line);
m=strlen(line);
for(z=0;z<m;z++)
count[line[z]]++;
for(len=m/2;len>0;len--) {
int ans=0;
for(s=0;s<m;s++)
for(i=0;i<m;i++) {
memset(str,0,sizeof(str));
strcpy(line,linecpy);
getstr(s,i,len,line,stra);
int bad=0;
for(z=0;z<len;z++) {
count[stra[z]]-=2;
if(count[stra[z]]<0)
bad=1;
}
for(z=0;z<len;z++) {
count[stra[z]]+=2;
}
if(bad) continue;
memcpy(bak2,line,sizeof(line));
int found=0;
for(t=0;t<m;t++) {
for(j=m;j>i;j--) {
memcpy(line,bak2,sizeof(line));
if(matstr(t,j,len,line,stra)) {
found=1;
ans++;
if(bestlen==len) {
if(strcmp(beststr,stra)!=0)
bestans++;
} else {
bestlen=len;
bestans=1;
strcpy(beststr,stra);
}
}
if(found) break;
}
if(found) break;
}
}
if(bestans) break;
}
casen++;
if(bestans>1)
printf("Code %d: Codeword not unique\n",casen);
else
printf("Code %d: %s\n",casen,beststr);
}
return 0;
}
--
"靈感 = 經驗 + 嘗試 + 快速的計算能力"
--- Ledia
"靈感, 是實力的累積"
--- untitled
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.82
※ 編輯: smartboy 來自: 140.112.30.82 (04/06 15:27)