開始後、Aを理解するのに時間がかかります。何度か読み間違えたのですが、0:24にPretest Passed。
BとCはただコードを打つだけの問題でした。Bは0:39、Cは0:57にPretest Passed.
Eも解くことができました。1:33にPretest Passedです。ただし、この解答自体はオーバーフローを起こしてしまいました。下のソースは、64bit整数を使ったものです。
Eのアルゴリズムは次のようになります。
ベクトルA,B,Cを複素数とみなします。この時、与えられた操作によって出来るベクトルは
i(i(i(i…(i(A+n1C)+n2C)+n3C)+…)+nkC
となります。これを展開して、i^2=-1に注意すると
(i^m)A+NC+iN'C
となります。(m=0,1,2,3)
これがBと等しいので、
B-(i^m)A=CN+iCN'
となります。これを解いて、N,N'を求め、それが整数ならばYES、そうでなければNOです。
結果：2404,216/1015でした。少し易し目のラウンドだったようです。
[A]
#include<stdio.h>
#include<string.h>
#define NUM 100
int main(void){
int m,n;
int price[NUM];
int i,j,k,l;
int min=-1;
short match[NUM][NUM];
memset(match,-1,sizeof(match));
scanf("%d %d",&n,&m);
for(i=0;i<n;i++) scanf("%d",&price[i]);
for(i=0;i<m;i++){
scanf("%d %d",&j,&k);
match[j-1][k-1]=1;
match[k-1][j-1]=1;
}
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
if(match[i-1][j-1]<0) continue;
for(k=j+1;k<=n;k++){
if(match[j-1][k-1]<0) continue;
if(match[i-1][k-1]<0) continue;
if(min<0 || min>price[i-1]+price[j-1]+price[k-1]) min=price[i-1]+price[j-1]+price[k-1];
}
}
}
printf("%d\n",min);
return 0;
}
[B]
#include<stdio.h>
#include<string.h>
#define LENGTH 100001
int main(void){
int count[10];
char num[LENGTH];
int i,j,k,l,times=0,sum;
scanf("%s",num);
for(i=0;i<10;i++) count[i]=0;
l=strlen(num);
if(l==1){
puts("0");
return 0;
}
for(i=0;i<l;i++) count[num[i]-'0']++;
times=1;
while(1){
for(i=0,k=0;i<10;i++) k+=count[i];
if(k<=1) break;
for(i=0,sum=0;i<10;i++) sum+=i*count[i];
sprintf(num,"%d\0",sum);
l=strlen(num);
for(i=0;i<10;i++) count[i]=0;
for(i=0;i<l;i++) count[num[i]-'0']++;
times++;
}
printf("%d\n",times-1);
return 0;
}
[C]
#include<stdio.h>
#include<string.h>
#define LEN 100001
int main(void){
char str[LEN],out[LEN];
int m,n,i,j,k,l,min,minch;
int count[26],c=0;
memset(count,0,sizeof(count));
scanf("%s%*c",str);
scanf("%d",&k);
l=strlen(str);
for(i=0;i<l;i++) count[str[i]-'a']++;
while(1){
min=LEN;
for(i=0;i<26;i++){
if(count[i]==0) continue;
if(min>count[i]){
min=count[i];
minch=i;
}
}
if(k<min || min==LEN) break;
k-=min;
count[minch]=0;
}
for(i=0;i<26;i++) c+=(count[i]!=0);
for(i=0,j=0;i<l;i++){
if(count[str[i]-'a']==0) continue;
out[j++]=str[i];
}
out[j]='\0';
printf("%d\n",c);
puts(out);
return 0;
}
[E]
#include<stdio.h>
int answer(long long int bx,long long int by,long long int cx,long long int cy);
int main(void){
struct vector{
long long int x;
long long int y;
}a,b,c,d;
int flg,j,k;
scanf("%I64d %I64d",&a.x,&a.y);
scanf("%I64d %I64d",&b.x,&b.y);
scanf("%I64d %I64d",&c.x,&c.y);
flg=0;
flg+=answer(b.x-a.x,b.y-a.y,c.x,c.y);
flg+=answer(b.x+a.y,b.y-a.x,c.x,c.y);
flg+=answer(b.x+a.x,b.y+a.y,c.x,c.y);
flg+=answer(b.x-a.y,b.y+a.x,c.x,c.y);
if(flg==0) puts("NO");
else puts("YES");
return 0;
}
int answer(long long int bx,long long int by,long long int cx,long long int cy){
long long int tmp;
if(cx==0 && cy==0){
if(bx==0 && by==0) return 1;
return 0;
}
if(cx==0){
if(bx%cy==0 && by%cy==0) return 1;
return 0;
}else if(cy==0){
if(bx%cx==0 && by%cx==0) return 1;
return 0;
}else{
tmp=cx*cx+cy*cy;
if((bx*cx+by*cy)%tmp==0 && (by*cx-bx*cy)%tmp==0) return 1;
return 0;
}
return 0;
}
0 件のコメント:
コメントを投稿