Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-07-01

[][] Google Code Jam Round3 Problem D small 01:36 はてなブックマーク -  Google Code Jam Round3 Problem D small  - 練習帳

問題文

 問題文

概要

  • 文字列sが与えられている.長さnで次の条件を満たす文字列が存在するような数nのうち,最小のものを答えよ.
  • 条件:文字列が,文字列sの「2-gram」及び「2-gramの一部分をleet変換して出来るすべての候補」を全て含む.
    • 文字列のN-グラムとは,長さNの部分列の事.例えば「abca」なら「ab」「bc」「ca」
    • leet変換とは特定のアルファベットを形の似ている数字や記号に変換する事.例えば「google」→「g00gle」など.この問題では,"o" → "0", "i" → "1", "e" → "3", "a" → "4", "s" → "5", "t" → "7", "b" → "8" "g" → "9"のleet変換のみ考える.
  • 制限:sの長さは1000以下

コード

 Practiceでの提出コード(gist):https://gist.github.com/2952584

考えた過程

方針1:時間のかかる解き方 → 失敗

最初に思いついた方法は,巡回セールスマン問題に帰着させる方法でした.sの2-gram及び2-gramのleet変換すべてを列挙し,それらをグラフの頂点とします.頂点aから頂点bへのコストは,aの後ろにいくつか文字を加えて,bが接尾辞となる為に必要な最小の文字数とします.すると,全ての頂点を1回ずつ訪問するコストは,解候補となる文字列の長さとなります.従ってそのような訪問コストのうち,最小のものをとれば答えが得られます.

しかし,sの長さが1000なので,部分文字列の個数は1000個,leet変換を施すと候補数は最悪2*2=4倍に増えるので,頂点数が4000の巡回セールスマン問題を解かなければならず,とても時間に間に合いません.

方針2 (その1):簡単な場合の問題に帰着させる

問題を簡単化する事を考えます.leet変換できるような文字がsの中に存在しないとします.例えばs="pqrp"などです.leet変換がない場合に,文字列を2-gramに分解してからごにょごにょするようなアルゴリズムで問題が解けるとします.すると,一般にleet変換がある場合は,同じように2-gramに分解した後,leet変換で拡張してから同じアルゴリズムを適用すれば問題が解けるはずです.まずはleet変換がない場合について考えてみようと思います.

(2-gramに分解せずに解くようなアルゴリズムを用いた場合,そのアルゴリズムをleet変換が含まれるケースに拡張できるかは分かりません.例えばppoの場合,含めるべき2-gramはpp, po, p0だけですが,もとの文字列ppoにp0を追加してしまうと,ppop0となり,含める必要のないopが入ってしまいます.)

方針2 (その2):leet変換がない場合を考える → 失敗

leet変換がない場合,答えはsの長さと同じになるかというと,そうとは限りません.例えば,s="pqppqp"は2-gramの種類としてpq, qp, ppしか持ちません.この3種類の部分列をすべて含む最短の文字列は,sよりも短い"pqpp"などの4文字です.もっと極端なのは,s="ppppppppppppppppppp"などは,"pp"が条件を満たします.

少し気になるのは,全2-gramをunique操作を残った2-gramから,元の文字列を復元する問題は,今解こうとしている問題と同程度に難しい事です.例えば,pqppqrから2-gramをとってunique操作をすると,pq, qp, pp, qrが取り出せます.これらを組み合わせて、もとの文字列のpqppqrを復元する問題は,今解きたい問題から最小性の条件を取り除いたものです.

条件を満たす文字列は可能性としては短くなる事しかあり得ません.そこで,どのような時に短くなるかを考えてみましたが,法則みたいなものは見つかりませんでした.

方針3:2-gramの別の表現方法を考える → うまくいく...らしい

この辺りで手詰まり感が出てきたので,別な方針を考える事にしました.これまではずっと,個々の2-gramを一つの頂点だと思ってきましたが,別の表現方法もありました.つまり,それぞれのアルファベットを頂点だと思って,xyという2-gramがあったら,xからyへ枝を貼るとしてグラフを作っても,2-gramを表現できます.このグラフの場合,最短の文字列を作るのは,すべての枝を通る,最短の一筆書き(重複を許す)を見つける問題に帰着されます.

もし一筆書きが出来るのならば,答えは単純に1+(枝の数)です.しかし,一般の場合には枝の本数より長くならなければなりません.早く提出している人の回答を見てみると,その答えは,1+(枝の数)+max( (Σ_{v} max(out_edge-in_edge, 0) )-1 , 0)となるようです.証明は,例えば節の数についての帰納法等で行えると思うのですが,もう少し直感的な説明が欲しいところです.

2011-06-05

[][] Google Code Jam Round 2 18:14 はてなブックマーク -  Google Code Jam Round 2 - 練習帳

 問題一覧:http://code.google.com/codejam/contest/dashboard?c=1150486

=A.B.C.D.
-SLSLSLSL
47.3443:0143:34------
.1 Wrong Try---1 Wrong Try---

全体 1703位.

普段の成績から考えれば妥当な線とはいえ,やっぱり悔しいです.

A. Airport Walkways

要約

 スタートからゴールまでのxメートルの一本道に動く歩道がいくつか設置されており,その上を歩く走る繰り返しながら移動して,出来るだけ最速ゴールタイムを求めたい.それぞれの動く歩道の速度秒速w[i]メートル,また動く歩道同士はオーバーラップしていない,動く歩道に乗っている乗っていないに関わらず,自分の歩く速度は秒速sメートルで,合計t秒間だけは秒速rメートルで走れる(従って,秒速wメートルの動く歩道の上で歩いたら秒速s + wメートル,走ったら秒速 r + wメートルで移動する).スタートしてからゴールまでのに要する時間の最小値を求めよ.

 テストケースの数は40個以下,歩行,走行速度s. rは1 <= s < r <=100の正数,動く歩道のスピードは1 <= w[i] <= 100, 移動距離xはsmallで1以上100以下,largeで1以上10**6以下.動く歩道の数nはsmallで1以上20以下,largeで1以上1000以下.

分析

 移動距離を歩道の動く距離と自分で走った距離で分ければ,後者により稼げる距離r * tでどこでも同じだから,どの歩道の上で走ったとしても,結果は同じになるのではないかと最初思った.しかしその直感は正しくなく,その稼いだ距離を全行程xのうちどの部分に割り当てるかが問題になる.速く動く歩道よりも遅く動く方で,この稼いだ距離を割り当てた方が,短い時間でゴールに到達できる.つまり,より遅い歩道の上で走れば良い.

引数が多すぎて覚えられません...

コード例
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <numeric>
#include <iomanip>

using namespace std;

typedef long long ll;

vector<int> b, e, w;

bool comp(int i, int j){
  return w[i] < w[j];
}

double  solve(int x, int s, int r, int T,vector<int> & _b, vector<int> & _e,  vector<int> & _w){
  b = _b;e = _e;w = _w;
  double ans = 0;
  int n = w.size();

  vector<int> ind(n + 1);
  for(int i = 0;i <n + 1;i++){
    ind[i] = i;
  }

  vector<int > len(n);
  for(int i = 0;i < n ;i++){
    len[i] = e[i] - b[i];
  }

  int sum = accumulate(len.begin(), len.end(), 0);

  // the total length of the parts which railways arex not installed.
  b.push_back(0);
  e.push_back(x - sum);
  w.push_back(0);
  n++;

  sort(ind.begin(), ind.end(), comp);

  for(int i = 0;i < n; i++){
    if(ans < T){
      double buf = (e[ind[i]] - b[ind[i]]) / (double)(r + w[ind[i]]);
      if(buf + ans <= T){
	ans += buf;
      }else{
	ans = T + (e[ind[i]] - b[ind[i]] - (T - ans) * (r + w[ind[i]])) /(double) (s + w[ind[i]]);
      }
    }else{
      ans += (e[ind[i]] - b[ind[i]]) / (double)(s + w[ind[i]]);
    }
  }
 
  return ans;
}


int main(){
  int t;cin >> t;
  for(int j = 1;j<=t;j++){
    int x, s, r, T, n;
    cin >> x >> s >> r >> T >> n;
    vector<int> _b(n);
    vector<int> _e(n);
    vector<int >  _w(n);
    for(int i= 0;i < n;i++){
      cin >> _b[i] >> _e[i] >> _w[i];
    }
    double ans = solve(x, s, r, T, _b, _e,_w);
		       
    cout << "Case #" << j << ": " << setprecision(10) <<  ans <<endl;
  }
  return 0;

}

C. Expensive Dinner

方針

 少し実験すると(実験するまでもない?),i番目までの人が来た後の合計金額は,i番目までの人のindexの最小公倍数となる.という事は最後の人まで来店した時の合計金額は来店する順番にはよらない.例えば,N = 12ならば

1から12までの最大公約数を求めて,それを素因数分解すると

 2:□□□
 3:□□
 5:□
 7:□
11:□

となる(□はその素因数の個数を表している).waiterが呼ばれる回数が最小となるのは

(8番の人が来店)
 2:■■■
 3:□□
 5:□
 7:□
11:□
(9番の人が来店)
 2:■■■
 3:■■
 5:□
 7:□
11:□
(5番の人が来店)
 2:■■■
 3:■■
 5:■
 7:□
11:□
・
・
・

のように,それぞれの素因数の最も大きなベキを持つ数の人達が最初に来店した場合である.これらの人はどのタイミングで来ても初めは必ずunhappyでwaiterを呼ばないとならず,逆にそれ以降の人は来た時点happyになのでwaiterを呼ぶ必要はない.

問題は複数の柱(例えば2と3)を同時に埋めるような数があると,その数を用いてwaiterを呼ぶ回数を減らせるが,実際にはそのような数は存在しない.例えば2**3 * 3**2 = 72だが,2**4 < 72なので,最小公倍数のが持つ素因数2の数は5個以上である.

waiterを呼ぶ回数が最大になるのは,最初に番号1の人が入店した後,下図のように,□を1つずつ埋めるように来客が狂う場合である

(2番の人が来店)
 2:■□□
 3:□□
 5:□
 7:□
11:□
(4番の人が来店)
 2:■■□
 3:□□
 5:□
 7:□
11:□
(8番の人が来店)
 2:■■■
 3:□□
 5:□
 7:□
11:□

以上より,それぞれの素数pに対し,p ** i (i = 2, 3, ・・・)の形で書けるN以下の数が何個あるかを数え上げれば良いと分かる.Nが10 ** 12なので,pは10 ** 6以下の素数を調べればよいので,素数判定を前計算しておけば,O(√N)で計算できる.

コード例

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cmath>
#include <cstring>

using namespace std;

typedef long long ll;


bool prime[1000000] = {};

const int N = 1000000;

void sieve(){
  prime[0] = prime[1] = false;
  for(ll i = 2;i < N;i++){
    if(!prime[i]) continue;
    for(ll j = i + i ;j < N;j+=i){
      prime[j] = false;
    }
  }

}

bool isprime(ll i){
  if(i == 0  || i == 1) return false;
  for(ll j = 2;j * j <= i ;j++){
    if(i % j == 0) return false;
  }
  return true;
}

ll solve(ll n){
  if (n == 1) return 0;
  ll ans = 0;
  
  for(ll i = 2;i * i <= n ;i++){
    if(!prime[i]) continue;
    ll mul = i * i;
    while(mul <=n){
      ans++;
      mul *= i;
    }
  }

  return ans + 1;
}


int main(){
  memset(prime, 1, sizeof(prime));
  sieve();

  int t;cin >> t;
  for(int j = 1;j<=t;j++){
    ll n;cin >> n;
    ll ans = solve(n);
		       
    cout << "Case #" << j << ": " << setprecision(10) <<  ans <<endl;
  }
  return 0;

}



2011-05-28

[][] Google Code Jam Round 1A Problem C 18:20 はてなブックマーク -  Google Code Jam Round 1A Problem C - 練習帳

要約

 カードを用いたゲームを行う.それぞれのカードには3つの数字が書かれており,それぞれs(score), c(card), t(turn)と表す.手札に何枚かカードを持ち,残りは山札としてゲームを始める.残りターン数1から初めて,1ターンに次の行動を行う.

  • 手札から好きなカードを1枚切る
  • 捨てたカードに書かれた
    • sの数だけ得点を獲得する
    • cの数だけ山札の上からカードを引く
    • tの数だけターン数を増やす
  • 残りターン数を1消費する
  • 最初に戻る

 手札が0になるか,残りターン数が0になったらゲームは終了する.最初の手札と山札にあるカードが予めすべて分かっているとき,得られる点数の最大値を求めよ.テストケースは100個以下.最初の手札の枚数は1枚以上,山札の枚数は0枚以上で,手札と山札の合計は80枚未満.カードに書かれている数は

small:0 <= c <= 1, 0 <= s <= 20, 0 <= t <= 20

large:0 <= c <= 2, 0 <= s <= 50, 0 <= t <= 50

分析

 まず,手札の中でターン数を増やすもの(つまり t > 0)があればそれを切っても損はしないので,無条件に選ぶ.問題は手札が全てt = 0の時何を切るか.sあるいはcの多いカードから貪欲に切る方法は,例えば次のような反例がある(|の左3枚が手札,右2枚が山札で(s, c) = (9, 0)の方が上).

(残りターン数:2)
s 2 1 0 | 9 0
c 0 1 2 | 0 0

この時は(1, 1), (9, 0)と切ると最高得点10点が得られる.また,同じ手札でも,

(残りターン数:2)
s 2 1 0 | 0 9
c 0 1 2 | 0 0

ならば,(0, 2), (9, 0)と切らないと最高得点とならない.つまり,何を切るかはいまある手札だけではわからない.

という事は,「cの値で手札を分類した時,それぞれのグループで得点が最大のものが次に切るカードの候補である,それらのどれを切るかで動的計画法を行う」のか等と考える.しかし山札の中では後にくるカードを先に切る可能性があるので,それぞれのカードを切った/切っていないで状態を持たなければならず,従って組み合わせ爆発を起こしてしまう.

 この辺りで何をすればよいかが分からなくなったので,解説を読む.自分が気づかなかったのはobservationの2つ目.これがあれば,cの値が同じ2枚のカードがあり,両方とも最終的に切る事になる場合,2枚のうち山札の中で上にある方を先に切ったと仮定してよい.すると,山札を上から順番に走査して切る/切らないを決めていけば良く,後戻りする必要はない.c = 0, 1, 2で分類したとき,どのカードまで切る/切らないかが決まっているかを動的計画法で用いる状態で持てばよい.

コード例

下のコードはkrijgertjeさんのコードを写経したものです.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

vector<int> cs, ss, ts;
int n;

int best[81][81];
int memo[81][81][81][81];

// c1 : the position of cards whose bonus of turn is 1 and which is not determined if it is discarded or trumped.
// c2 : bonus of turn is 2. 
// drawn : the largest index of the card drawn. 
// turn : residual turn
// todraw : the number of cards to draw in next turn whose bonus of turn are zero.

int solve(int c1, int c2, int drawn, int turn, int todraw){
  if(turn == 0) return 0;

  // Trump cards at hand whose bonus of turn are more than 0.
  int extra = 0;
  while(todraw > 0 && drawn < n){
    if(ts[drawn] > 0){
      todraw += cs[drawn];
      extra += ss[drawn];
      turn += ts[drawn] - 1;
    }
    todraw--;
    drawn++;
  }
  turn = min(turn, n);
  
  // search for next cards to be considered.
  while(c1 < drawn && (ts[c1] > 0 || cs[c1] != 1)) c1++;
  while(c2 < drawn && (ts[c2] > 0 || cs[c2] != 2)) c2++;

  int ret = memo[c1][c2][drawn][turn];
  if(ret == -1){
    // Points from cards from C0-cards
    ret = best[drawn][min(drawn,turn)];

    if(c1 < drawn){
      // trump C1-card
      ret = max(ret, ss[c1] + solve(c1 + 1, c2, drawn, turn + ts[c1] - 1, cs[c1]));
      // discard C1-card
      ret = max(ret, solve(c1 + 1, c2, drawn, turn, 0));
    }
    if(c2 < drawn){
      // trump C2-card
      ret = max(ret, ss[c2] + solve(c1, c2 + 1, drawn, turn + ts[c2] - 1, cs[c2]));
      // discard C2-card
      ret = max(ret, solve(c1, c2 + 1, drawn, turn, 0));
    }
  }
  
  memo[c1][c2][drawn][turn] = ret ;
  return ret + extra;
}


int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    int N;cin >> N;
    cs.clear();cs.resize(N);
    ss.clear();ss.resize(N);
    ts.clear();ts.resize(N);

    for(int j = 0;j <N;j++){
      cin >> cs[j] >> ss[j] >> ts[j];
    }
    int M;cin >> M;
    for(int j = 0;j < M;j++){
      int c,s,t;
      cin >> c >> s >> t;
      cs.push_back(c);
      ss.push_back(s);
      ts.push_back(t);
    }

    n = N + M;

    for(int j = 0 ;j <= n;j++) {
      vector<int> have;
      for(int k = 0; k < j ;k++){
	if(ts[k] == 0 && cs[k]==0)
	  have.push_back(ss[k]);
      }
      sort(have.rbegin(),have.rend());
      best[j][0]=0;
      for(int k =1; k <= j; k++){
	best[j][k] = best[j][k-1] + (k-1 < have.size() ? have[k-1] : 0);
      }
    }

    memset(memo, -1, sizeof(memo));
    int ans = solve(0,0,0,1,N);
    
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;

}

}

||<

2011-05-23

[][] Google Code Jam Round 1A 02:14 はてなブックマーク -  Google Code Jam Round 1A - 練習帳

 問題一覧:http://code.google.com/codejam/contest/dashboard?c=1145485

 結果:http://code.google.com/codejam/contest/scoreboard?c=1145485#vf=1

 解説:http://code.google.com/codejam/contest/dashboard?c=1145485#s=a

=A.B.C.
-SmallLargeSmallLargeSmallLarge
26.3925.3026.39----
.--1 Wrong Try-1 Wrong Try-

全体 729位.

 3回あるRound 1の1回目,各回で上位1000人までが次のラウンドに進出できます.運良く1回目で条件を満たせました.ボーダーはProblem Aをsmall, large両方を42分程度で解答するものでした.

A. FreeCell Statistics

要約

 引き分けのない一人用のゲームこれまでに何回か行っており,勝率は今日行ったゲームだけで集計するとPD%, 全体でPG%である(PD, PG整数).また,今日行ったゲームの回数はN回以下と分かっている.このような条件を満たすゲームのプレイ回数と勝ち負けの回数が存在するか,あるいは,これらは矛盾する情報かを判定せよ(存在する場合でも,条件を満たす数の具体例を挙げる必要はない).

 テストケースの数はsmallで100以下,largeで2000以下.PD, PGは0以上100以下,Nはsmallで1以上10以下,largeで1以上10^{15}以下.

方針

 今日(resp. これまで)の行ったゲームの回数をD(resp. G)とすると,求める条件は

  • D * PD <= G * PG
  • D * (100 - PD) <= G * (100 - PG)
  • D * PD / 100, G * PG / 100は整数
  • D <= N

 ポイントはGはいくらでも大きくしても良いということ,Gを大きくする事で,PGが0でない限り1番目の条件は満たされ,100でない限り2番目の条件は満たされる.また,Gを100の倍数にすればG * PG /100は整数になる.よってD * PD / 100を整数にするような整数Dのうち最小のものを求め,それがN以下かを調べれば良い.例えば,PD = 12の場合,12/100 = 3/25と既約分数にすれば,D = 25が条件を満たす最小の数とわかる,つまり,PDと100の最大公約数を求めれば良い.

コード例
#include <iostream>
#include <vector>
#include <utility>
#include <string>

using namespace std;

typedef long long ll;

ll gcd (ll a, ll b){
  if(a < b) swap(a, b);
  if(a % b == 0) return b;
  return gcd(a %b, b);
}

string  solve(ll N, int pd, int pg){
  if(pg == 0){
    if(pd == 0) return "YES";
    else return "NO";		  
  }
  if(pg == 100){
    if(pd == 100) return "YES";
    else return "NO";		  
  }
 
  ll g = gcd(100, pd);
  ll n = 100 / g;
  if( n <= N) return "YES";
  else return "NO";

}


int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    ll n;
    int pd, pg;
    cin >> n >> pd >> pg ;

    string ans = solve(n, pd, pg);
    if(ans == "YES") ans = "Possible";
    else ans = "Broken";
		       
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;

}

B. The Killer Word

要約

 ハングマン(http://en.wikipedia.org/wiki/Hangman_(game))を2人で行う.但し,通常のハングマンとは異なり,解答者の誤答回数に制限はない.出題者と解答者は共通するワードリストを持っており,次の要領でゲームは進む.

  • 出題者が単語を一つ選び,単語の文字数分だけ空白マスを黒板に書く,出題者は解答者の提示に応じて答えを埋めていく.
  • 解答者は26文字のアルファベットのを並べ替えたリストを作る
  • 解答者はリストから順にアルファベットを選ぶ
  • 正解の候補の中に選んだアルファベットがあるならばそれを提示する,そうでなければ提示しない
    • 正解の候補とは,リスト中の単語のうち,解答者が知っている情報と矛盾しないものの事を言う
    • 解答者の知っている情報は答えの文字数と,答えのうち既にアルファベットが書かれているマスと答えとなる単語の文字数
  • 解答者が提示した場合で,
    • もしそのアルファベットが答えの中にあれば,その単語のなかの同じアルファベットをマスに書き込む.
    • なければ,解答者は1点得点を失う
  • 3番目に戻る
  • 以上をマスがすべて埋まるまで繰り返す

 出題者と解答者が共有する単語のリスト,及び解答者のアルファベットを提示する順序が与えられている.リストの中で解答者が失う点数が最も大きくなる単語を答えよ.

 テストケースの数は1以上10以下.共有リストの数はsmallで100以下,largeは10000以下.リストに現れる単語の文字数は10文字以下.1つのテストケースで与えられるリストの数はsmallで10以下,largeで100以下.

方針

 愚直に実装しても,リストの個数の2乗に比例するアルゴリズムが得られる.リストの数が10000なので,枝刈りを十分行えばlargeでも制限時間の8分以内に解答が得られる(ですが,largeは1発勝負なので,時間内に計算が終了するかの確認は事前に行うのが安全だと思います).

コード例

このコードはpracticeのlargeデータを48秒程度で計算できました.

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <cmath>

using namespace std;

int INF = 100000000;

int solveone(int n, string & s, vector<string> & d, string c){
  vector<int> kouho(n, 1);
  int lpoint = 0;
  for(int i = 0; i < n; i++){
    if(s.size() != d[i].size()){
      kouho[i] = 0;
    }
  }
  
  string suggest;
  for(int i = 0; i < s.size(); i++){
    suggest += "_";
  }
  
  for(int i = 0; i < c.size(); i++){
    bool flag = false;

    //check if c[i] should be claimed.
    for(int j = 0; j < n; j++){
      if(kouho[j] == 0) continue;
      for(int k = 0; k < d[j].size(); k++){
	if(d[j][k] == c[i]){
	  flag = true;
	}
      }
      if(flag){
	break;
      }
    }

    if(flag){
      bool islost = false;
      //completion of suggest
      for(int j = 0; j < s.size(); j++){
	if(s[j] == c[i]){
	  suggest[j] = c[i];
	  islost = true;
	}
      }
      if(!islost){
	lpoint++;
	for(int j = 0; j < n; j++){
	  if(kouho[j] == 0) continue;
	  if(d[j].find(c[i]) != string::npos){
	    kouho[j] = 0 ;
	  }
	}

      }
    }
    // narrow down of kouho 
    if(flag){
      for(int j = 0; j< n; j++){
	if(kouho[j] == 0) continue;
	for(int k = 0; k < d[j].size(); k++){
	  if(suggest[k] != '_' && d[j][k] != suggest[k]){
	    kouho[j] = 0;
	  }
	}
      }
    }
  }
  return lpoint;
}


string solve(int n, vector<string> & d, string c){
  int mn = -1;
  int pos = -1 ;
  for(int i = 0; i < n; i++){
    int s = solveone(n, d[i], d, c);
    if(s > mn){
      mn = s;
      pos = i;
    }
  }

  return d[pos];
}


int main(){
  int t;cin >> t;
  for(int i = 1; i <= t; i++){
    int n, m;cin >> n >> m;
    vector<string> d(n);
    vector<string> c(m);
    for(int j = 0; j < n; j++){
      cin >> d[j];
    }
    for(int j = 0; j < m; j++){
      cin >> c[j];
    }
    string ans;
    for(int j = 0; j < m; j++){
      ans +=solve(n, d, c[j]);
      if(j != m-1)
	ans += " ";
    }
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;

}