スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Rujia Liu's Present 6: Happy 30th Birthday to Myself

Rujia Liu さんの誕生日コンテストらしい。
48 時間で 17 問。
gift.zip というファイルがダウンロードできるようになっていて、追加のテストケースや幾何問題の visualizer が入っているという親切仕様。

Tags : プログラミング UVa 未解決


結果

ABCD-FGHIJK----P-
の 11 問解いて 7 位だった。
F と G が特におもしろかった。

問題

A. A Special "Happy Birthday" Song!!! (UVa 12554)
n 人で
Happy birthday to you Happy birthday to you Happy birthday to Rujia Happy birthday to you
という歌を一単語ずつ回しながら歌う。
全員が一回以上歌い、終わるときは歌の最後でなといけない。
何周歌うか求めよ。

1 ≦ n ≦ 100

B. Baby Me (UVa 12555)
"a斤b两" または "a斤" という入力が文字コード UTF-8 without BOM で与えられる。
kg 単位に変換せよ。
1 斤は 0.5 kg、1 两は 0.05 kg。

C. "Center" of perimeter midpoints (UVa 12556)
三角形 ABC に対して、
CA+AD = DB+BC
となる三角形の辺上の点 ( 一意に定まる ) を D とする。
E, F も同様に定める。
直線 CD、AE、BF が一点で交わるかどうか判定し、一点で交わるときは交点の座標も出力せよ。

D. Detecting Code Snippets (UVa 12557)
長い文字列 s[1..|s|] と短い文字列 t[1..|t|] が与えられる。
どちらもアルファベットのみからなる。

s の長さ |t| の部分文字列 s' について、
{a,b,c,...,z}のある permutation p が存在して、すべての i = 1, 2, ..., |t| で
・t[i] が大文字のとき、s'[i] == t[i]
・t[i] が小文字のとき、s'[i] == p[t[i]]
とできるとき、s' == t であると定める。

s[i..i+|t|] == t となる i はいくつあるか。

1 ≦ |s|, |t| ≦ 10^6

F. Finding Black Circles (UVa 12559)
中心の座標と半径がすべて整数である円が H × W のグリッド上にいくつか描かれている。
グリッドの黒いマスは必ずある円の一部である。
一方、白いマスに円がないことは保証されていない。
黒くなるべきだけど白くなっているマスが高々 2% だけ存在する。
すべての円の中心と半径を求めよ。

30 ≦ H, W ≦ 100
1 ≦ 円の個数 ≦ 5
複数通りの答えがありうるテストケースは存在しない

G. Good Friends (UVa 12560)

集合 S = { 1, 2, ..., n } と S の m 個の部分集合 T_1, ..., T_m が与えられる。
S の部分集合 S' は、S' ⊂ T_i をみたす i が m/5 個以上あるとき good であるという。
S の good な部分集合で包含関係について極大なものをすべて列挙せよ。

2 ≦ n ≦ 30
5 ≦ m ≦ 10^4
テストケースはランダムに生成される。 ( 生成方法は明示されている。)

H. Hadamard Gate (UVa 12561)
量子情報で使われるアダマールゲート ( 説明略 ) に a|0> + b|1> を n 回通したときの |a|^2 を求めよ。

1 ≦ n ≦ 10^6

I. In an effort to Change History (UVa 12562)
過去に起こる x 個の事象 a_1, ..., a_x、
現在に起こる y 個の事象 b_1, ..., b_y、
未来に起こる z 個の事象 c_1, ..., c_z
が与えられる。
各 b_i は a_1, ..., a_x によって決定される。
各 c_i は b_1, ..., b_y によって決定される。

a_1, ..., a_x の起こった・起こらなかったを自由に改変して、c_1, ..., c_z の起こる個数を最大化せよ。
ただし、いくつかの b_i については起こったか起こらなかったかが変化してはいけない。

1 ≦ x, y, z ≦ 15

J. Jin Ge Jin Qu hao (UVa 12563)

カラオケで歌う曲の候補が n 曲ある。
それとは別に Jin Ge Jin Qu という名前の 678 秒の曲も歌える。
どの曲も高々一回しか歌えない。
持ち時間が t 秒ある。
持ち時間が 0 秒になったときに歌っている歌は歌いきっていい。
歌う曲数を最大化し、その上でカラオケにいる時間 ( 最後の歌を歌い終わるまでの時間 ) を最大化せよ。

1 ≦ n ≦ 50
曲 i を歌うのにかかる時間 ≦ 180 秒 ( i = 1, 2, ..., n )
1 ≦ t ≦ 10^9

K. King of Fighters explained (UVa 12564)
軸に平行な長方形がいくつか与えられるので交わったりしているかどうか判定せよ。
( 書くのがめんどうになってきた。 )

P. Planning mobile robot on Tree (EASY Version) (UVa 12569)
木があり、各頂点にはロボットがいるか障害物があるか何もないか。
ロボットと障害物は隣接する空き頂点に移動できる。
ロボットが目的の頂点に移動するための最小手数と具体的なルートを一つ求めよ。

4 ≦ |V| ≦ 15

解答

A
やる。

B.
やる。

C.
D, E, F を二分探索で求める。

D.
全然わからなかった。
正解者がたくさんいることと、gift のケースでは全部 |t| が小さかったので、もしやと思って全探索解を投げたら通った。
通らなかったら KMP で大文字がマッチする位置を列挙して、大文字がマッチしているところだけ全探索するつもりだった。それでも最悪 O(|s||t|) だけど。

F.
円の上下左右のまっすぐになっているところを検出して、それらから考えられる中心と半径の候補を全部求めた。
候補の円が答えかどうかは、黒マスになるべき箇所が本当に黒マスになっているかを適当にサンプリングして調べてみて、90% 以上一致していれば OK とした。
閾値を 95% 以上にすると WA だった。

G.
かしこくやるのは難しいので全探索。
n ≦ 30 なので bit に押し込めて一気に判定することで 30 倍速になる。
それだけだと TLE したので、包含のチェックのときに、調べるまでもなくダメな T_i は後ろに swap して最初から見ないようにしたら通った。

H.
わりと見え見えの行列べき乗。
実は今回の場合、変換行列を二乗すると単位行列になるので、偶奇で判定してもいい。

I.
a_1, ..., a_x の割り当て方を全部試す。
構文解析をがんばる。

J.
t がやたら大きいけど、実際の所要時間は 180n + 678 で抑えられるので、気にせず DP すればいい。

K.
問題文どおりに判定するだけ。

P.
典型的な bit DP。

ソースコード

A.
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const char *song[16]={"Happy","birthday","to","you","Happy","birthday","to","you","Happy","birthday","to","Rujia","Happy","birthday","to","you"};

int main(){
int n; scanf("%d",&n);
char name[100][101];
rep(i,n) scanf("%s",name[i]);

int p=0;
bool end=false;
while(1){
rep(i,16){
printf("%s: %s\n",name[p],song[i]), p=(p+1)%n;
if(p==0) end=true;
}
if(end) break;
}

return 0;
}


B.
#include<cctype>
#include<cstdio>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++){
char s[32]; gets(s);
int n=strlen(s);
rep(i,n) if(!isdigit(s[i])) s[i]=' ';
int a,b; sscanf(s,"%d%d",&a,&b);
double ans=0.5*a+(n<7?0:0.05*b);
if(ans==(int)ans) printf("Case %d: %.0f\n",cas,ans);
else if(n>6&&b%2==1) printf("Case %d: %.2f\n",cas,ans);
else printf("Case %d: %.1f\n",cas,ans);
}
return 0;
}


C.
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const double EPS=1e-7;

struct point{
double x,y;
point operator+(const point &a)const{ return (point){x+a.x,y+a.y}; }
point operator-(const point &a)const{ return (point){x-a.x,y-a.y}; }
};

point operator*(double c,const point &a){ return (point){c*a.x,c*a.y}; }

bool operator==(const point &a,const point &b){ return abs(a.x-b.x)<EPS && abs(a.y-b.y)<EPS; }

double cross(const point &a,const point &b){ return a.x*b.y-a.y*b.x; }

struct line{ point a,b; };

double dist(const point &a,const point &b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

point get_intersect(const line &L1,const line &L2){
double a1=cross(L1.b-L1.a,L2.b-L2.a);
double a2=cross(L1.b-L1.a,L1.b-L2.a);
if(a1==0) return L1.a; // L1 == L2
return L2.a+a2/a1*(L2.b-L2.a);
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++){
point a,b,c;
scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);

point d,e,f;
double lo=0,hi=1;
rep(_,50){
double mi=(lo+hi)/2,t=mi;
d=(1-t)*a+t*b;
if(dist(c,a)+dist(a,d)<dist(d,b)+dist(b,c)) lo=mi; else hi=mi;
}
lo=0; hi=1;
rep(_,50){
double mi=(lo+hi)/2,t=mi;
e=(1-t)*b+t*c;
if(dist(a,b)+dist(b,e)<dist(e,c)+dist(c,a)) lo=mi; else hi=mi;
}
lo=0; hi=1;
rep(_,50){
double mi=(lo+hi)/2,t=mi;
f=(1-t)*c+t*a;
if(dist(b,c)+dist(c,f)<dist(f,a)+dist(a,b)) lo=mi; else hi=mi;
}

line L={c,d},M={a,e},N={b,f};
point g1=get_intersect(L,M);
point g2=get_intersect(M,N);
point g3=get_intersect(N,L);

printf("Case %d: ",cas);
if(g1==g2 && g1==g3) printf("%.6f %.6f\n",g1.x,g1.y);
else puts("ERROR");
}

return 0;
}


D.
#include<cstdio>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int solve(){
static char s[1000001],t[1000001];
gets(s);
gets(t);
int m=strlen(s),n=strlen(t);

int last1[128],last2[128];
char f[128];
rep(c,128) last1[c]=last2[c]=-1;

int ans=0;
rep(i,m-n+1){
bool ok=true;
rep(j,n){
if('A'<=s[i+j] && s[i+j]<='Z'){
if(t[j]!=s[i+j]){
ok=false;
break;
}
}
else{
if('A'<=t[j] && t[j]<='Z'){
ok=false;
break;
}
else if(last1[t[j]]!=i){
if(last2[s[i+j]]==i){
ok=false;
break;
}
else{
f[t[j]]=s[i+j];
last1[t[j]]=i;
last2[s[i+j]]=i;
}
}
else if(f[t[j]]!=s[i+j]){
ok=false;
break;
}
}
}
if(ok) ans++;
}
return ans;
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++) printf("Case %d: %d\n",cas,solve());
return 0;
}


F.
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const double PI=acos(-1);

struct point{ int x,y; };

struct circle{
point c;
int r;
bool operator<(const circle &C)const{ return make_pair(make_pair(r,c.x),c.y)<make_pair(make_pair(C.r,C.c.x),C.c.y); }
bool operator==(const circle &C)const{ return r==C.r && c.x==C.c.x && c.y==C.c.y; }
};

int h,w;
char B[100][101];

bool check(const circle &C){
int cnt=0;
rep(t,1000){
double theta=2*PI*t/1000;
int x=(int)(C.c.x+C.r*cos(theta)+0.5);
int y=(int)(C.c.y+C.r*sin(theta)+0.5);
if(0<=y && y<h && 0<=x && x<w && B[y][x]=='1') cnt++;
}
return cnt>900; // 90% くらい正しい色だったら OK とする ( 95% にしたら WA だった )
}

void solve(){
scanf("%d%d",&w,&h);
rep(i,h) scanf("%s",B[i]);

vector<point> H,V;
rep(i,h) rep(j,w) if(B[i][j]=='1') {
int x=j;
while(j<w && B[i][j]=='1' || j+1<w && B[i][j+1]=='1') j++; // ピクセルの欠損を考慮して, 一マスは白でもいいことにする
if(j-x>=5){
H.push_back((point){x,i});
}
}
rep(j,w) rep(i,h) if(B[i][j]=='1') {
int y=i;
while(i<h && B[i][j]=='1' || i+1<h && B[i+1][j]=='1') i++;
if(i-y>=5){
V.push_back((point){j,y});
}
}

vector<circle> C; // 答えとなる円の候補
rep(j,H.size()) rep(i,j) {
int d1=abs(H[j].y-H[i].y);
if(d1%2!=0 || d1<10) continue;
int r1=d1/2;

rep(l,V.size()) rep(k,l) {
int d2=abs(V[l].x-V[k].x);
if(d2%2!=0 || d2<10) continue;
int r2=d2/2;

if(r1==r2){
int y=min(H[i].y,H[j].y)+r1;
int x=min(V[k].x,V[l].x)+r2;
C.push_back((circle){(point){x,y},r1});
}
}
}

sort(C.begin(),C.end());
C.erase(unique(C.begin(),C.end()),C.end());
rep(i,C.size()) if(!check(C[i])) C.erase(C.begin()+i), i--;

printf("%d",C.size());
rep(i,C.size()) printf(" (%d,%d,%d)",C[i].r,C[i].c.x,C[i].c.y);
puts("");
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++) printf("Case %d: ",cas), solve();
return 0;
}


G.
#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int n,m,group[10000];

vector<int> ans;

bool check(int k,int S,int &k2){
k2=k;
int cnt=0;
rep(i,k){
if((S&group[i])==S) cnt++;
else{
swap(group[i],group[k-1]);
i--;
k--;
k2--;
}
if(5*cnt>=m) return true;
if(5*(cnt+(k-i-1))<m) return false;
}
return false;
}

void dfs(int i,int k,int S){
if(i==n){ ans.push_back(S); return; }
int k2;
if(check(k,S|1<<i,k2)) dfs(i+1,k2,S|1<<i);
dfs(i+1,k,S);
}

void solve(){
scanf("%d%d",&n,&m);
rep(i,m){
group[i]=0;
int k; scanf("%d",&k);
rep(j,k){
int a; scanf("%d",&a); a--;
group[i]|=1<<a;
}
}

ans.clear();
dfs(0,m,0);

rep(i,ans.size()){
bool covered=false;
rep(j,ans.size()) if(i!=j && (ans[i]&ans[j])==ans[i]) { covered=true; break; }
if(covered) ans.erase(ans.begin()+i), i--;
}

vector< vector<int> > ans2;
rep(i,ans.size()){
vector<int> A;
rep(j,n) if(ans[i]>>j&1) A.push_back(j);
ans2.push_back(A);
}
sort(ans2.begin(),ans2.end());

printf("%d\n",ans2.size());
rep(i,ans2.size()) rep(j,ans2[i].size()) printf("%d%c",ans2[i][j]+1,j+1<ans2[i].size()?' ':'\n');
puts("");
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++) printf("Case %d: ",cas), solve();
return 0;
}


H.
#include<cmath>
#include<cstdio>
#include<complex>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int N_MAX=2;

template<class T>
void mul(int n,const T A[N_MAX][N_MAX],const T x[N_MAX],T y[N_MAX]){
static T z[N_MAX];
rep(i,n){
z[i]=0;
rep(j,n) z[i]+=A[i][j]*x[j];
}
rep(i,n) y[i]=z[i];
}

template<class T>
void mul(int n,const T A[N_MAX][N_MAX],const T B[N_MAX][N_MAX],T C[N_MAX][N_MAX]){
static T tmp[N_MAX][N_MAX];
rep(i,n) rep(j,n) {
tmp[i][j]=0;
rep(k,n) tmp[i][j]+=A[i][k]*B[k][j];
}
rep(i,n) rep(j,n) C[i][j]=tmp[i][j];
}

template<class T>
void pow(int n,const T A[N_MAX][N_MAX],int m,T B[N_MAX][N_MAX]){
static T tmp[N_MAX][N_MAX];
rep(i,n) rep(j,n) {
tmp[i][j]=A[i][j];
B[i][j]=(i==j?1:0);
}
for(int t=0;m>0;t++){
if(m&(1LL<<t)){
mul(n,B,tmp,B);
m-=1LL<<t;
}
mul(n,tmp,tmp,tmp);
}
}

double solve(){
double a0,a1,b0,b1;
int n; scanf("%lf%lf%lf%lf%d",&a0,&a1,&b0,&b1,&n);
complex<double> a(a0,a1),b(b0,b1);
complex<double> A[2][2]={{1/sqrt(2),1/sqrt(2)},{1/sqrt(2),-1/sqrt(2)}},v[2]={a,b};
pow(2,A,n,A);
mul(2,A,v,v);
return norm(v[0]);
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++) printf("Case %d: %.6f\n",cas,solve());
return 0;
}


I.
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

inline int popcount(int x){
x=((x>>1)&0x55555555)+(x&0x55555555);
x=((x>>2)&0x33333333)+(x&0x33333333);
x=((x>>4)+x)&0x0f0f0f0f;
x+=(x>>8);
x+=(x>>16);
return x&0x3f;
}

int expr(const char *,int &,int);

int number(const char *s,int &idx){
int n=0;
while('0'<=s[idx] && s[idx]<='9') n=n*10+(s[idx++]-'0');
return n;
}

int primary(const char *s,int &idx,int S){
if(s[idx]=='('){
idx++;
int a=expr(s,idx,S);
idx++;
return a;
}
else{
idx++;
int n=number(s,idx);
return S>>(n-1)&1;
}
}

int factor(const char *s,int &idx,int S){
if(s[idx]=='!'){
idx++;
return !primary(s,idx,S);
}
else{
return primary(s,idx,S);
}
}

int term(const char *s,int &idx,int S){
int a=factor(s,idx,S);
while(s[idx]=='&'){
idx+=2;
a&=factor(s,idx,S);
}
return a;
}

int expr(const char *s,int &idx,int S){
int a=term(s,idx,S);
while(s[idx]=='|'){
idx+=2;
a|=term(s,idx,S);
}
return a;
}

int equation(const char *s,int S){
int idx;
for(idx=0;s[idx]!='=';idx++);
idx++;
return expr(s,idx,S);
}

int x,y,z;
char b[15][512],c[15][512];

int b_ini[15];

int parse(int a_S){
int b_res[15];
rep(i,y) b_res[i]=equation(b[i],a_S);
rep(i,y) if(b[i][0]=='*' && b_res[i]!=b_ini[i]) return 0;

int b_S=0;
rep(i,y) b_S|=b_res[i]<<i;

int c_res[15];
rep(i,z) c_res[i]=equation(c[i],b_S);

int c_S=0;
rep(i,z) c_S|=c_res[i]<<i;
return c_S;
}

void solve(){
scanf("%d%d%d",&x,&y,&z);
int a[15];
rep(i,x) scanf("%d",a+i);
rep(i,y) scanf("%s",b[i]);
rep(i,z) scanf("%s",c[i]);

int S_ini=0;
rep(i,x) S_ini|=a[i]<<i;
rep(i,y) b_ini[i]=equation(b[i],S_ini);

int ini=parse(S_ini);

int ans=ini,S_ans;
rep(S,1<<x){
int tmp=parse(S_ini^S);
if(popcount(tmp)>popcount(ans) || popcount(tmp)==popcount(ans) && popcount(S)<popcount(S_ans)) ans=tmp, S_ans=S;
}

if(ans==ini) puts("Unable to improve future.\n");
else{
printf("Increased from %d to %d.\n",popcount(ini),popcount(ans));
int sz=popcount(S_ans);
rep(i,x) if(S_ans>>i&1) printf("a%d%c",i+1,sz>1?' ':'\n'), sz--;
puts("");
}
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++) printf("Case %d: ",cas), solve();
return 0;
}


J.
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

void solve(){
int n,T; scanf("%d%d",&n,&T);
int a[51];
rep(i,n) scanf("%d",a+i);
a[n++]=678;
sort(a,a+n);
int last=a[--n];

static int dp[51][10000];
rep(i,n+1) rep(j,T+1) dp[i][j]=(i==0&&j==0?0:-INF);
rep(i,n) for(int j=T;j>=0;j--) {
if(j+a[i]<=T){
dp[i+1][j+a[i]]=max(dp[i+1][j+a[i]],dp[i][j]+1);
}
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
}

int ans1=0;
rep(i,n+1) rep(j,T) ans1=max(ans1,dp[i][j]);
int ans2=0;
rep(i,n+1) rep(j,T) if(dp[i][j]==ans1) ans2=max(ans2,j);
ans1++;
ans2+=last;
printf("%d %d\n",ans1,ans2);
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++) printf("Case %d: ",cas), solve();
return 0;
}


K.
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

bool overlap(int t1,int l1,int b1,int r1,int t2,int l2,int b2,int r2){ return t1<b2 && t2<b1 && l1<r2 && l2<r1; }

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++){
int n[4];
int t[4][5],l[4][5],b[4][5],r[4][5];
scanf("%d%d",n+0,n+1);
rep(i,n[0]) scanf("%d%d%d%d",l[0]+i,t[0]+i,r[0]+i,b[0]+i);
rep(i,n[1]) scanf("%d%d%d%d",l[1]+i,t[1]+i,r[1]+i,b[1]+i);
scanf("%d%d",n+2,n+3);
rep(i,n[2]) scanf("%d%d%d%d",l[2]+i,t[2]+i,r[2]+i,b[2]+i);
rep(i,n[3]) scanf("%d%d%d%d",l[3]+i,t[3]+i,r[3]+i,b[3]+i);

bool ans1=false,ans2=false;
rep(i,n[0]) rep(j,n[3]) if(overlap(t[0][i],l[0][i],b[0][i],r[0][i],t[3][j],l[3][j],b[3][j],r[3][j])) ans1=true;
rep(i,n[2]) rep(j,n[1]) if(overlap(t[2][i],l[2][i],b[2][i],r[2][i],t[1][j],l[1][j],b[1][j],r[1][j])) ans2=true;
printf("Case %d: %s\n",cas,ans1&&ans2?"Both":ans2?"First":ans1?"Second":"Neither");
}

return 0;
}


P.
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int n;

pair<int,int> encode(int u1,int S1,int u2,int S2){ // どのマスからどのマスへ動いたかの情報へ変換
if(u1!=u2) return make_pair(u1,u2);
rep(u,n) if((S1>>u&1) && !(S2>>u&1)) rep(v,n) if(!(S1>>v&1) && (S2>>v&1)) return make_pair(u,v);
}

void solve(){
int m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); s--; t--;
int S0=0; // 障害物
rep(i,m){
int u; scanf("%d",&u); u--;
S0|=1<<u;
}
vector<int> T[15];
rep(i,n-1){
int u,v; scanf("%d%d",&u,&v); u--; v--;
T[u].push_back(v);
T[v].push_back(u);
}

static int dp[15][1<<15];
static pair<int,int> path[15][1<<15];
memset(dp,-1,sizeof dp);
dp[s][S0]=0;

int head=0,tail=0;
static pair<int,int> Q[15*(1<<15)];
Q[tail++]=make_pair(s,S0);

int u_ans=-1,S_ans;
while(head<tail){
int u=Q[head].first,S=Q[head].second; head++;

if(u==t){ u_ans=u; S_ans=S; break; }

// ロボットが動く
rep(i,T[u].size()){
int v=T[u][i];
if((S>>v&1)==0 && dp[v][S]==-1){
Q[tail++]=make_pair(v,S);
dp[v][S]=dp[u][S]+1;
path[v][S]=make_pair(u,S);
}
}
// 障害物が動く
rep(v,n) if(S>>v&1) {
rep(i,T[v].size()){
int w=T[v][i],S2=S&~(1<<v)|(1<<w);
if((S>>w&1)==0 && w!=u && dp[u][S2]==-1){
Q[tail++]=make_pair(u,S2);
dp[u][S2]=dp[u][S]+1;
path[u][S2]=make_pair(u,S);
}
}
}
}

if(u_ans==-1){ puts("-1\n"); return; }

printf("%d\n",dp[u_ans][S_ans]);
int u=u_ans,S=S_ans;
vector< pair<int,int> > p_ans;
while(u!=s || S!=S0){
pair<int,int> a=path[u][S];
p_ans.push_back(encode(a.first,a.second,u,S));
u=a.first;
S=a.second;
}
reverse(p_ans.begin(),p_ans.end());
rep(i,p_ans.size()) printf("%d %d\n",p_ans[i].first+1,p_ans[i].second+1);
puts("");
}

int main(){
int T; scanf("%d ",&T);
for(int cas=1;cas<=T;cas++) printf("Case %d: ",cas), solve();
return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。