Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1447
Identity Decode

Time Limit: 2 Seconds      Memory Limit: 65536 KB

WishingBone met a ppmm in school today. He is really enthusiastic to know her name. The only information he's got is her school identity which is on her school bag. At night, WishingBone broke into the office of the principal, and found a long long list of all the students' names. It reads:

1: WishingBone ID: green_bone blue_bone red_bone
2: WishingMM ID: blue_bone green_bone red_bone
3: WishingFish ID: green_bone red_bone blue_bone
4: WashingBone ID: red_bone green_bone blue_bone

And he remembers the ppmm's ID is white_bone blue_bone greed_bone. Of course, he did not want to read the list through to find this ID. Well, fortunately, he found a piece of code in the recycled bin that the principle used to generate those ID's. This program reads in m and n, where m is the number of color of bones and n is the length of the ID. Then it reads in a list of colors and generates the list of possible ID's. Since WishingBone is quite poor at programming, he resorts to your help.


Input consists of multiple tests. Each test starts with a line of m and n (0 < n <= m <= 12), and a list of m distinct names of colors on the next line, separated by a single space. Names are made up of up to 30 upper, lower Latin characters and the '_' character. The third line of a test contains a sequence of n names of colors, which is the school identity of the ppmm.

Process to the end of file. There will be no more than 10000 tests.


For each test in the input, output a single integer - the line on which to find her name.

Sample Input

4 3
red_bone blue_bone green_bone white_bone
red_bone green_bone blue_bone
4 3
red_bone blue_bone green_bone white_bone
white_bone blue_bone green_bone

Sample Output



The Program WishingBone found in the pricipal's office:

#include <iostream.h>
#define MAXN 12

void FAINT(int m,int n,int l,int a[MAXN][3],int t,char name[MAXN][50],int& c){
  int i;
  if (!t--)
    for (cout<<++c<<": ",i=0;i<n;i++)
      cout<<name[a[i][1]]<<(i<n-1?' ':'\n');
    for (i=0;i<n;i++)
      if (!a[i][2])

void faint(int m,int n,int l,int a[MAXN][3],int t,char name[MAXN][50],int& c){
  int i;
  if (t==n)
    for (i=l;i<m;i++)

int main(){
  char name[MAXN][50];
  int a[MAXN][3],m,n,i,c=0;
  for (i=0;i<m;i++)
  return 0;

const maxn=12;
type words=string[50];
var n,m,i:integer;
    name:array [1..maxn] of words;
    a,p:array [1..maxn] of integer;
    yes:array [1..maxn] of boolean;
procedure getwords(var s:words);
var ch:char;
function rec:boolean;
  rec:=(ch='_') or ('A'<=ch) and (ch<='Z') or ('a'<=ch) and (ch<='z');
  s:='';repeat read(ch);until rec;
  repeat s:=s+ch;read(ch);
  until not rec;
procedure print(l:integer);
var i:integer;
  if l=0 then
      for i:=1 to m do write(' ',name[p[a[i]]]);
    end else
  for i:=1 to m do if yes[i] then
    begin yes[i]:=false;a[l]:=i;print(l-1);yes[i]:=true;end;
procedure faint(nn,mm:integer);
  if mm=0 then print(m) else
      if nn>mm then faint(nn-1,mm);
  for i:=1 to n do getwords(name[i]);

Source: WishingBone's Contest #1
Submit    Status