作者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)