2015
09-17

# Pirate’s Chest

Explorer yy feels lucky that he has got N rather valuable chests by chance. But he had problem opening them. After doing some research for days, he has a clue. Let us number the chests from 1 to N, the chest with number i can be open in three ways:

1. Open it with the key with number Ai.
2. Open it with the crowbar with number Bi.
3. Just open it by force, doing that will decrease yy’s HP by Di. yy will die if his HP is less or equal to zero.

Initially, yy has no keys and no crowbars, the tools are stored in a tower which is in the control of monsters. The tower has M floors, every floor can be considered as a 20×20 grids and contains at most two tools, and in case that it contains two tools, those two tools must be the same kind (i.e. both keys or crowbars). Each cell contains either a monster or a tool. If yy stands on a cell with tool, he can pick it up. But if the cell contains a monster, a fight will take place and cost his HP. After the battle this cell will turn into an empty one. On each floor there exist exactly one special "entry" cell, this cell is empty, when yy get to the floor, he will be teleported to that cell immediately. Note that yy can move upstairs or downstairs at any cell.
Once a tool get picked, it can be used arbitary times. It is guaranteed that every tool mentioned will appear at most once.
yy simply hates moving upstairs, as his friend, you’re asked to calculate the minimum number of floors yy should go so that he can open all the N chests and still alive, and the minimum total HP cost in above case.

The input contains several test cases, terminated by EOF. Most of test cases are rather small.

In each case first line contains three integer N, M, H (1 <= N <= 30000, 0 <= M <= 1000, 1 <= H <= 109), denotes number of chests, number of floors, and yy’s initial health points (HP). Next n lines each contains three integers Ai, Bi and Di (1 <= Ai,Bi <= m, 1 <= Di <= 1000). Next m blocks describing the tower, each block has a 20×20 map describing the floor, the values denotes (suppose the value is x):

(1) 0 <= x <= 1000 : a monster, defeating it will decrease yy’s HP by x.
(2) 100000 < x <= 101000 : a key with number x – 100000.
(3) 200000 < x <= 201000 : a crowbar with number x – 200000.
(4) -1 : "entry" cell as we mentioned above.

The input contains several test cases, terminated by EOF. Most of test cases are rather small.

In each case first line contains three integer N, M, H (1 <= N <= 30000, 0 <= M <= 1000, 1 <= H <= 109), denotes number of chests, number of floors, and yy’s initial health points (HP). Next n lines each contains three integers Ai, Bi and Di (1 <= Ai,Bi <= m, 1 <= Di <= 1000). Next m blocks describing the tower, each block has a 20×20 map describing the floor, the values denotes (suppose the value is x):

(1) 0 <= x <= 1000 : a monster, defeating it will decrease yy’s HP by x.
(2) 100000 < x <= 101000 : a key with number x – 100000.
(3) 200000 < x <= 201000 : a crowbar with number x – 200000.
(4) -1 : "entry" cell as we mentioned above.

3 2 10
2 2 11
1 2 11
2 1 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 200002 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 100001 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 100002 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 9

kmp  next数组应用。

 #include<cstdio>
#include<cstring>
const int maxn=1000000+5;
char s[maxn];
int next[maxn];
int snext[maxn];
void get_next(char *T,int len,int *next)
{
next[0]=-1;
for(int i=1;i<=len;i++)
{
int j=next[i-1];
while(T[i]!=T[j+1]&& j>=0)
j=next[j];
if(T[i]==T[j+1])next[i]=j+1;
else next[i]=0;
}
}
bool find(char *a,int n,char *b,int m,int *next)
{
get_next(b,m,next);
int j=0;
for(int i=0;i<n;i++)
{
while(j&&b[j]!=a[i]) j=next[j];
if(b[j]==a[i]) j++;
if(j==m) return true;
}
return false;
}
bool compare(char *a,char *b,int len)
{
for(int i=0;i<len;i++)
if(a[i]!=b[i]) return false;
return true;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
getchar();
scanf("%s",s);
int len=strlen(s);
get_next(s,len,snext);
char *rear=s+len;
int cur=snext[len-1];
while(cur>len/3)
cur=snext[cur];
int flag=0;
for(int i=cur;i>=0;i=snext[i])
{
int le=i+1;
if(!compare(s,rear-le,le)) continue;
if(find(s+le,len-2*le,rear-le,le,next)) {flag=1;printf("%d\n",le);break;}
}
if(!flag) printf("0\n");
}
}
return 0;
}