Banal_Tickets.dpr 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251
  1. program doshide;
  2. const
  3. maxn = 18;
  4. base = 9;
  5. maxm = 50000;
  6. sum : array [ 1..9, 1..4 ] of longint =
  7. ( ( 0, 0, 0, 0 ), ( 1, 0, 0, 0 ), ( 0, 1, 0 ,0 ), ( 2, 0, 0, 0 ), ( 0, 0, 1, 0 ), ( 1, 1, 0, 0 ), ( 0, 0, 0, 1 ), ( 3, 0, 0, 0 ), ( 0, 2, 0, 0 ) );
  8. type
  9. Tnumber = array [ 0..6 ] of longint;
  10. ArrayType = array [ 0..1, 1..maxm ] of TNumber;
  11. NumberType = array [ 1..maxn ] of char;
  12. var
  13. dpa, dpb : ArrayType;
  14. a, b : NumberType;
  15. d : array [ 0..base ] of longint;
  16. queue : array [ 1..maxm, 1..4 ] of longint;
  17. dist : array [ 1..maxm ] of longint;
  18. p : array [ -1..maxn * 3, 0..maxn * 2, 0..maxn, 0..maxn ] of longint;
  19. n, final, node : longint;
  20. ans, m : array [ 0..10 ] of longint;
  21. procedure ReadData;
  22. var
  23. i : longint;
  24. begin
  25. readln( n );
  26. for i := 1 to n do
  27. read( a[ i ] );
  28. for i := 1 to n do
  29. read( b[ i ] );
  30. end;
  31. procedure PreWork;
  32. var
  33. h, t, i : longint;
  34. begin
  35. h := 0;
  36. t := 1;
  37. queue[ 1 ][ 1 ] := 0;
  38. queue[ 1 ][ 2 ] := 0;
  39. queue[ 1 ][ 3 ] := 0;
  40. queue[ 1 ][ 4 ] := 0;
  41. dist[ 1 ] := 0;
  42. p[ 0 ][ 0 ][ 0 ][ 0 ] := 1;
  43. repeat
  44. inc( h );
  45. if ( dist[ h ] = n ) then
  46. continue;
  47. for i := 1 to 9 do
  48. if ( p[ queue[ h ][ 1 ] + sum[ i ][ 1 ] ][ queue[ h ][ 2 ] + sum[ i ][ 2 ] ][ queue[ h ][ 3 ] + sum[ i ][ 3 ] ][ queue[ h ][ 4 ] + sum[ i ][ 4 ] ] = 0 ) then
  49. begin
  50. inc( t );
  51. queue[ t ][ 1 ] := queue[ h ][ 1 ] + sum[ i ][ 1 ];
  52. queue[ t ][ 2 ] := queue[ h ][ 2 ] + sum[ i ][ 2 ];
  53. queue[ t ][ 3 ] := queue[ h ][ 3 ] + sum[ i ][ 3 ];
  54. queue[ t ][ 4 ] := queue[ h ][ 4 ] + sum[ i ][ 4 ];
  55. dist[ t ] := dist[ h ] + 1;
  56. p[ queue[ t ][ 1 ] ][ queue[ t ][ 2 ] ][ queue[ t ][ 3 ] ][ queue[ t ][ 4 ] ] := t;
  57. end;
  58. until ( h >= t );
  59. inc( t );
  60. queue[ t ][ 1 ] := - 1;
  61. queue[ t ][ 2 ] := 0;
  62. queue[ t ][ 3 ] := 0;
  63. queue[ t ][ 4 ] := 0;
  64. node := t;
  65. end;
  66. procedure Plus( var a, b : TNumber );
  67. var
  68. i, k : longint;
  69. begin
  70. if ( a[ 0 ] = 0 ) then
  71. a[ 0 ] := 1;
  72. k := a[ 0 ];
  73. if ( b[ 0 ] > k ) then
  74. k := b[ 0 ];
  75. for i := 1 to k do
  76. inc( a[ i ], b[ i ] );
  77. for i := 1 to k do
  78. if ( a[ i ] >= d[ base ] ) then
  79. begin
  80. inc( a[ i + 1 ] );
  81. dec( a[ i ], d[ base ] );
  82. end;
  83. if ( a[ a[ 0 ] + 1 ] > 0 ) then
  84. inc( a[ 0 ] );
  85. end;
  86. procedure Mul( var a, b : TNumber );
  87. var
  88. i, j : longint;
  89. w : int64;
  90. begin
  91. if ( a[ 0 ] = 0 ) then
  92. a[ 0 ] := 1;
  93. if ( b[ 0 ] = 0 ) then
  94. b[ 0 ] := 1;
  95. for i := 1 to a[ 0 ] do
  96. for j := 1 to b[ 0 ] do
  97. begin
  98. w := int64( a[ i ] ) * b[ j ] + ans[ i + j - 1 ];
  99. ans[ i + j - 1 ] := w mod d[ base ];
  100. inc( ans[ i + j ], w div d[ base ] );
  101. end;
  102. i := a[ 0 ] + b[ 0 ] - 1;
  103. while ( ans[ i + 1 ] >= d[ base ] ) do
  104. begin
  105. inc( i );
  106. inc( ans[ i + 1 ], ans[ i ] div d[ base ] );
  107. ans[ i ] := ans[ i ] mod d[ base ];
  108. end;
  109. while ( ans[ i + 1 ] > 0 ) do
  110. inc( i );
  111. while ( i > 1 ) and ( ans[ i ] = 0 ) do
  112. dec( i );
  113. if ( i > ans[ 0 ] ) then
  114. ans[ 0 ] := i;
  115. end;
  116. procedure Minus( k : longint );
  117. var
  118. i : longint;
  119. begin
  120. m[ 0 ] := 1;
  121. m[ 1 ] := 1;
  122. for i := 1 to k do
  123. if ( int64( m[ m[ 0 ] ] ) * 10 < d[ base ] ) then
  124. m[ m[ 0 ] ] := m[ m[ 0 ] ] * 10
  125. else
  126. begin
  127. m[ m[ 0 ] ] := 0;
  128. inc( m[ 0 ] );
  129. m[ m[ 0 ] ] := 1;
  130. end;
  131. for i := 1 to m[ 0 ] do
  132. begin
  133. ans[ i ] := m[ i ] - ans[ i ];
  134. if ( ans[ i ] < 0 ) then
  135. begin
  136. inc( ans[ i ], d[ base ] );
  137. dec( m[ i + 1 ] );
  138. end;
  139. end;
  140. ans[ 0 ] := m[ 0 ];
  141. while ( ans[ 0 ] > 1 ) and ( ans[ ans[ 0 ] ] = 0 ) do
  142. dec( ans[ 0 ] );
  143. end;
  144. procedure Print;
  145. var
  146. i, j : longint;
  147. begin
  148. write( ans[ ans[ 0 ] ] );
  149. for i := ans[ 0 ] - 1 downto 1 do
  150. for j := base - 1 downto 0 do
  151. write( ans[ i ] div d[ j ] mod 10 );
  152. writeln;
  153. end;
  154. procedure Calculate( var m : NumberType; var dp : ArrayType );
  155. var
  156. now, i, j, num : longint;
  157. begin
  158. dp[ 0 ][ 1 ][ 0 ] := 1;
  159. dp[ 0 ][ 1 ][ 1 ] := 1;
  160. i := 0;
  161. for now := 1 to n do
  162. begin
  163. i := i xor 1;
  164. fillchar( dp[ i ], sizeof( dp[ i ] ), 0 );
  165. for j := 1 to node - 1 do
  166. if not ( ( dp[ i xor 1 ][ j ][ 0 ] = 0 ) or ( ( dp[ i xor 1 ][ j ][ 0 ] = 1 ) and ( dp[ i xor 1 ][ j ][ 1 ] = 0 ) ) ) then
  167. if ( m[ now ] = '?' ) then
  168. begin
  169. Plus( dp[ i ][ node ], dp[ i xor 1 ][ j ] );
  170. for num := 1 to 9 do
  171. Plus( dp[ i ][ p[ queue[ j ][ 1 ] + sum[ num ][ 1 ] ][ queue[ j ][ 2 ] + sum[ num ][ 2 ] ][ queue[ j ][ 3 ] + sum[ num ][ 3 ] ][ queue[ j ][ 4 ] + sum[ num ][ 4 ] ] ], dp[ i xor 1 ][ j ] );
  172. end
  173. else
  174. if ( m[ now ] = '0' ) then
  175. Plus( dp[ i ][ node ], dp[ i xor 1 ][ j ] )
  176. else
  177. begin
  178. num := ord( m[ now ] ) - ord( '0' );
  179. Plus( dp[ i ][ p[ queue[ j ][ 1 ] + sum[ num ][ 1 ] ][ queue[ j ][ 2 ] + sum[ num ][ 2 ] ][ queue[ j ][ 3 ] + sum[ num ][ 3 ] ][ queue[ j ][ 4 ] + sum[ num ][ 4 ] ] ], dp[ i xor 1 ][ j ] );
  180. end;
  181. if ( m[ now ] = '?' ) then
  182. for j := 1 to 10 do
  183. Plus( dp[ i ][ node ], dp[ i xor 1 ][ node ] )
  184. else
  185. Plus( dp[ i ][ node ], dp[ i xor 1 ][ node ] );
  186. end;
  187. final := i;
  188. end;
  189. procedure Work;
  190. var
  191. i, w : longint;
  192. begin
  193. d[ 0 ] := 1;
  194. for i := 1 to base do
  195. d[ i ] := d[ i - 1 ] * 10;
  196. Calculate( a, dpa );
  197. Calculate( b, dpb );
  198. ans[ 0 ] := 1;
  199. ans[ 1 ] := 0;
  200. Mul( dpa[ final ][ node ], dpb[ final ][ node ] );
  201. for i := 1 to node - 1 do
  202. Mul( dpa[ final ][ i ], dpb[ final ][ i ] );
  203. Print;
  204. w := 0;
  205. for i := 1 to n do
  206. inc( w, ord( a[ i ] = '?' ) + ord( b[ i ] = '?' ) );
  207. Minus( w );
  208. Print;
  209. end;
  210. begin
  211. assign( input, 'pku1608.in' );
  212. reset( input );
  213. assign( output, 'pku.out' );
  214. {36.out}
  215. rewrite( output );
  216. ReadData;
  217. PreWork;
  218. Work;
  219. close( input );
  220. close( output );
  221. end.