fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <string>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <algorithm>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <vector>
  13.  
  14. #define REP(I,A,B) for(register int I=A,_END_=B;I<=_END_;I++)
  15. #define REPD(I,A,B) for(register int I=A,_END_=B;I>=_END_;I--)
  16. #define RI(X) X=Readint()
  17. #define RII(X,Y) RI(X),RI(Y)
  18. #define RIII(X,Y,Z) RI(X),RI(Y),RI(Z)
  19. #define RS(X) scanf("%s",X)
  20. #define RD(X) scanf("%lf",&X)
  21. #define GCH getchar()
  22. #define PCH(X) putchar(X)
  23. #define MS(X,Y) memset(X,Y,sizeof(X))
  24. #define MC(X,Y,var,len) memcpy(X,Y,sizeof(var)*(len))
  25. #define debug(...) fprintf(stderr,__VA_ARGS__)
  26. #define pb(X) push_back(X)
  27. #define mp(A,B) make_pair(A,B)
  28. #define ts first
  29. #define sc second
  30. #define lch(p) (p+p)
  31. #define rch(p) (p+p+1)
  32. #define lowbit(X) ((X)&(-(X)))
  33.  
  34. using namespace std;
  35.  
  36. typedef pair<int,int> poi;
  37.  
  38. inline int Readint()
  39. {
  40. 	int ret=0;
  41. 	int f=1;
  42. 	char ch;
  43. 	do
  44. 	{
  45. 		ch=GCH;
  46. 		if (ch=='-') f*=-1;
  47. 	}while(ch>=0 && (ch<'0' || ch>'9'));
  48.  
  49. 	while ('0'<=ch && ch<='9')
  50. 	{
  51. 		ret=ret*10+ch-'0';
  52. 		ch=GCH;
  53. 	}
  54. 	return ret*f;
  55. }
  56.  
  57. void open()
  58. {
  59. 	freopen("gen.in","r",stdin);
  60. 	freopen("gen.out","w",stdout);
  61. }
  62. void close()
  63. {
  64. 	fclose(stdin);
  65. 	fclose(stdout);
  66. }
  67.  
  68. const int MAXN = 105;
  69. const int inf = 1000;
  70.  
  71. int pw[30]={1};
  72.  
  73. int f[27][27]={0};
  74. int g[MAXN][MAXN]={0};
  75.  
  76. int ans[MAXN]={0};
  77.  
  78. char str[MAXN]={0};
  79.  
  80. int n;
  81. int len;
  82.  
  83. void prepare()
  84. {
  85. 	RI(n);
  86. 	char change[10];
  87. 	pw[0]=1;
  88. 	REP(i,1,25) pw[i]=pw[i-1]<<1;
  89.  
  90. 	REP(i,1,n)
  91. 	{
  92. 		RS(change);
  93. 		change[0]-='A';
  94. 		change[1]-='A';
  95. 		change[2]-='A';
  96. 		f[change[1]][change[2]]|=pw[change[0]];
  97. 	}
  98. }
  99.  
  100. void init()
  101. {
  102. 	RS(str+1);
  103. 	MS(g,0);
  104. 	len=strlen(str+1);
  105. 	ans[0]=0;
  106. 	REP(i,1,len) ans[i]=inf,str[i]-='A';
  107. }
  108.  
  109. inline int log2(const int &k)
  110. {
  111. 	if (k==1) return 0;
  112. 	if (k==2) return 1;
  113. 	if (k==4) return 2;
  114. 	if (k==8) return 3;
  115. 	if (k==16) return 4;
  116. 	if (k==32) return 5;
  117. 	if (k==64) return 6;
  118. 	if (k==128) return 7;
  119. 	if (k==256) return 8;
  120. 	if (k==512) return 9;
  121. 	if (k==1024) return 10;
  122. 	if (k==2048) return 11;
  123. 	if (k==4096) return 12;
  124. 	if (k==8192) return 13;
  125. 	if (k==16384) return 14;
  126. 	if (k==32768) return 15;
  127. 	if (k==65536) return 16;
  128. 	if (k==131072) return 17;
  129. 	if (k==262144) return 18;
  130. 	if (k==524288) return 19;
  131. 	if (k==1048576) return 20;
  132. 	if (k==2097152) return 21;
  133. 	if (k==4194304) return 22;
  134. 	if (k==8388608) return 23;
  135. 	if (k==16777216) return 24;
  136. 	if (k==33554432) return 25;
  137. }
  138.  
  139.  
  140. inline int merge(int u,int v)
  141. {
  142. 	register int ch1,ch2,t;
  143. 	register int ret=0;
  144. 	for (;u;u&=u-1)
  145. 	{
  146. 		ch1=(int)log2(lowbit(u));
  147. 		for (t=v;t;t&=t-1)
  148. 		{
  149. 			ch2=(int)log2(lowbit(v));
  150. 			ret|=f[ch1][ch2];
  151. 		}
  152. 	}
  153. 	return ret;
  154. }
  155.  
  156. inline void init_dynamic()
  157. {
  158. 	REP(i,1,len)
  159. 		g[i][i]=pw[str[i]];
  160. 	register int j;
  161. 	REP(l,2,len)
  162. 		REP(i,1,len-l+1)
  163. 		{
  164. 			j=i+l-1;
  165. 			REP(k,i,j-1)
  166. 				g[i][j]|=merge(g[i][k],g[k+1][j]);
  167. 		}
  168. }
  169. const int  S=262144; 
  170. inline void dynamic()
  171. {
  172. 	REP(i,0,len-1)
  173. 		if (ans[i]!=inf)
  174. 			REP(j,i+1,len)
  175. 				if (g[i+1][j]&S)
  176. 					ans[j]=min(ans[j],ans[i]+1);
  177. 	if (ans[len]==inf)
  178. 		printf("NIE\n");
  179. 	else
  180. 		printf("%d\n",ans[len]);
  181. }
  182.  
  183. int main()
  184. {
  185. //	open();
  186. 	int _=0;
  187. 	prepare();
  188. 	RI(_);
  189. 	REP(__,1,_)
  190. 	{
  191. 		init();
  192. 		init_dynamic();
  193. 		dynamic();
  194. 	}
  195. 	close();
  196. 	return 0;
  197. }
Success #stdin #stdout 0s 3500KB
comments (?)
stdin
copy 
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA
stdout
copy 
3
1
NIE
https://ideone.com/FPZCCa
gen poi
language:
C++14 (clang 8.0)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!