Orshanskiy

ans := 0

// M;++*);,+ A/ -4,+ 7,)+*135E12+ 4/47/81*8+ for st in TerminalState do

ans := ans + sum[st]

9@1.+? L"& 31:1.+1. W*+..=1 D+0*# 0,*#/=-#C"0% N * |U| * |A|, D"& - A(/:1? 0*(D#1 ?&21" /&0"+<#"$ 60*1000*26 ! 1.5 ?+**+&.&- 3#F. H"&3&; 01,(./= .# L"& /&0"#"&D.&. J .# ,&'+3&-#.+% -31?1..&<& ?#00+-# sum2 - sum – "1? )&*11. !,&311 -01<&, /*% '13-&; D#0"+ .1 '&"31)(1"0% +0,#"$ )&*11 L>>1,"+-.&1 31:1.+1.

3.5. @#+(&/+A&8

H 31#*+F#@++ 3#00?&"31..&; F#/#D+ -#2.& D1",& 3#F/1*+"$ /-1 D#0"+ 31:1.+%: '31-3#M1.+1 W68 0 .1'&<*&M#CM+?+ 31)3#?+ - W68 )1F "#,+A 31)13 + /#*$.1;:+; '&/0D1" 0 '&?&M$C /+.#?+D10,&<& '3&<3#??+3&-#.+%. O#?1"+?, D"& ?&2.& .#D#"$ 0 31#*+F#@++ -"&3&; D#0"+, '31/'&*#<#%, D"& -01 31)3# – '&<*&M#CM+1. V&</# L"( D#0"$ ?&2.& 03#F( 21 '3&"10"+3&-#"$, &/.&-31?1..& '3&-13+- --&/ +F >#;*#, +?1.# -A&/.=A + -=A&/.=A >#;*&- + ". /. 60"#"+, .# L"#'1 31#*+F#@++ -01</# 0*1/(1" -.+?#"1*$.& '131D+"#"$ &'+0#.+1 >&3?#"# -A&/.=A + -=A&/.=A /#..=A.

P1&)A&/+?& *+ L>>1,"+-.& 31#*+F&-=-#"$ '13-(C D#0"$, 0-%F#..(C 0 (/#*1.+1? .1'&<*&M#CM+A 31)13? K0*+ -#? '3#,"+D10,+ -01 3#-.&, 31#*+F&-=-#"$ )&*11 +*+ ?1.11 L>>1,"+-.=; -#3+#.", +*+ )&*11 L>>1,"+-.=; -#3+#." (21

.#'+0#. .# )(?#<1, "& + +0'&*$F(;"1 1<&. H01</# ?&21" &,#F#"$0%, D"& /3(<(C D#0"$ '3&<3#??= -= 31#*+F&-#*+ .1 "#, L>>1,"+-.&, ,#, '31/'&*#<#*& 2C3+, + ?&2.& "1? 0#?=? '&-=0+"$ -13&%".&0"$ "&<&, D"& '3&<3#??# -01-"#,+ .1 '31-=0+" '31/1* -31?1.+.

53+-1/1..=1 -=:1 0&&)3#21.+%, '3+?1.+"1*$.& , 3#00?#"3+-#1?&; F#/#D1, '&,#F=-#C", D"& - .1; ?&2.& +0'&*$F&-#"$ .1L>>1,"+-.(C 31#*+F#@+C '13-&<& L"#'# 31:1.+%, ,&"&3#% -01-"#,+ '3+.@+'+#*$.& '3&M1, + - .1; 0*&2.11 &:+)+"$0%. I#F(?.& .#'+0#"$ 11, &"*#/+"$ '3&<3#??( +, *+:$ '&*(D+- 0&&)M1.+1 &" 2C3+ time limit exceeded ('31-=:1. '31/1* -31?1.+), D"& ?#*&-13&%".&, '131'+0#"$ L"( D#0"$ )&*11 L>>1,"+-.&. 53&0"&; -#3+#." '+:1"0% )=0"3&, + &. &)*1<D+" '&+0, &:+)&, - /3(<+A D#0"%A '3&<3#??=. P#:# ,&?#./# D#0"& 31#*+F&-=-#*# 0(M10"-1..& )&*11 0*&2.=1 31:1.+%, D1? "31)&-#*&0$ - F#/#D1, +0'&*$F(% &)M+1, &"3#)&"#..=1, .& "1A.+D10,+ 0*&2.=1 ?1"&/=. 6 0&2#*1.+C, .# '3#,"+,1 +F-F# 0'1@+>+,+ ,&.,31".&; F#/#D+ )&*11 0*&2.=1 31:1.+% +.&</# &,#F=-#*+0$ ?1.11 L>>1,"+-.=?+, D"& '31&/&*1-#*&0$ ?.&210"-&? *&,#*$.=A &'"+?+F#@+;.

501-/&,&/ /*% -"&3&; D#0"+ (21 )=* '3+-1/1. - 3#F/. 3.4. 6#, (21 )=*& &"?1D1.&, &"-1" ?&21" +?1"$ &D1.$ )&*$:&1 D+0*& 3#F3%/&-. 5&L"&?( '&"31)(1"0% #3+>?1"+,# '&-=:1..&; "&D.&0"+ («/*+..#% #3+>?1"+,#»). W*% .#'+0#.+% 31:1.+% .# %F=,1 Pascal (Borland Delphi) /*+..(C #3+>?1"+,( '3+/1"0% 31#*+F&-=-#"$ 0#?+?. W*% +F(D1.+% #3+>?1"+,+ '&-=:1..&; "&D.&0"+ + ,&?'$C"13.&; #3+>?1"+,+ - @1*&? 0*1/(1" '&31,&?1./&-#"$ ,.+<( W. 6.("# [20]. 53#,"+D10,+ -0% D1"-13"#% <*#-# («83+>?1"+,#») L"&; ,.+<+ %-*%1"0% &D1.$

21

'&*1F.&; /*% 31:1.+% &*+?'+#/.=A F#/#D '& '3&<3#??+3&-#.+C + /&*2.# )="$ -.+?#"1*$.& '3&D+"#.# 0 '13-&; 0"3#.+@= /& '&0*1/.1;. H'3&D1?, +F(D1.+% ,.+<+ W. 6.("# /*% L"&<& .1/&0"#"&D.&.

5&"31).&0"$ - /*+..&; #3+>?1"+,1 -&F.+,#1" - &*+?'+#/.=A F#/#D#A /&0"#"&D.& D#0"&. 5&L"&?( 31#*+F#@+% 0&&"-1"0"-(CM+A >(.,@+; /&*2.# )="$ A&3&:& &"3#)&"#.# + %-*%"$0%, - "13?+.&*&<++ 3#F/. 2.3, &/.+? +F «,+3'+D+,&-». H /#..&; F#/#D1 /*% '&-=:1.+% L>>1,"+-.&0"+ 3#F(?.& 31#*+F&-#"$ /*+..(C #3+>?1"+,( '& &0.&-#.+C 109 – A3#.+"$ '& /1-%"$ /10%"+D.=A @+>3 - &/.&; %D1;,1 ?#00+-#, F#/#CM1<& /*+..&1 D+0*&.

I#F3#)&"#..#% '3&<3#??# '3+-1/1.# - '3+*&21.++. J0A&/.=; ,&/ + 0,&?'+*+3&-#..#% '3&<3#??# &'()*+,&-#.= .# 0#;"1 http://is.ifmo.ru/, 3#F/1* «!"#"$+».

W*% +**C0"3#@++ "&<&, D"& 31:1.+1 '&0"3&1.& +F «,+3'+D+,&-», '3&<3#??# 3#F/1*1.# .# .10,&*$,& >3#<?1."&-, '3+?13.& L"+? «,+3'+D+,#?» 0&&"-1"0"-(CM+A.

3.6. B#=5&"'2+% & '5(+,9+

6#,+1 21 "10"= 0*1/(1" .#'+0#"$ - /#..&? 0*(D#1? P#D.1? 0 ?#,0+?#*$.& '3&0"=A. H-&/+?:

a 1

1 1 1

1

0

1

B"& ?&21" )="$ '3&M1? 9/+. 0+?-&*, &/.& 0&0"&%.+1 – .#D#*$.&1 + "13?+.#*$.&1, &/.& '&<*&M#CM11 31)3&, -1/(M11 - "& 21 0&0"&%.+1. B+0*& 0"3&, +F &/.&<& 0+?-&*# – &/.#. H <3#>+D10,&; >&3?1 L"&" "10" '31/0"#-*1. .# 3+0.3.

	1							a

I+0. 3. J**C0"3#@+% , '13-&?( "10"(

W*% L"&<& "10"# &"-1": 1.

K0*+ &"-1", -=/#..=; -#:1; '3&<3#??&;, 3#F&;/1"0% 0 '3#-+*$.=? .# 0"&*$ '3&0"&? '3+?131, -#? )(/1" *1<,& +0,#"$ &:+),(. P1 &0"#.#-*+-#;"10$ .# /&0"+<.("&?! 5&?1.%;"1 '&0*1/.CC 1/+.+@( .# /-&;,(. P# "3&;,(. P# 60. J0'&*$F(;"1 0-&; :#.0 &).#3(2+"$ '3&0"&; '3+?13, .# ,&"&3&? '3&<3#??#

.1-13.& 3#)&"#1". P1 /(?#;"1, D"& 10*+ '3&<3#??# 3#)&"#1" /*% /-(A, "& &.# )(/1" 3#)&"#"$ + /*% "31A (+?11"0% - -+/( '&0*1/.11 D+0*& -& -A&/.=A /#..=A).

V1'13$ '&?1.%;"1 .&*$ .# 1/+.+@( – 0/1*#;"1 31)3& .1'&<*&M#CM+?. 53#-+*$.=; &"-1": .&*$. 4&21"1 '3+ L"&? '&'="#"$0% F#?1.+"$ '&0*1/.11 D+0*& -& -A&/1 "#,21 .# .&*$, A&"% L"& + F#'31M1.& >&3?#"&? -A&/.=A /#..=A, "& 10"$

22

'&0D+"#"$ ,&*+D10"-& '(0"=A 0"3&,, /&'(0,#1?=A "#,+? #-"&?#"&? – - &"-1"1 /&*2.# )="$ 1/+.+@#.

!*1/(CM#% 0"#/+%: /-# 0&0"&%.+%, '3+D1? "&*$,& &/.& +F .+A "13?+.#*$.&1. HA&/.=1 /#..=1:

a 2

1 1 1

2

1

0

0

4

H <3#>+D10,&; >&3?1 L"&" "10" '31/0"#-*1. .# 3+0. 4.

a

1	2

a

I+0. 4. J**C0"3#@+% ,& -"&3&?( "10"(

W*% L"&<& "10"# &"-1": 1.

K0*+ '&?1.%"$ D1"-13,( .# "3&;,(, "& - &"-1"1 )(/1" .&*$ – +F-F# D1".&0"+. P10?&"3% .# -0C '3+?+"+-.&0"$ L"+A "10"&-, +A +0'&*$F&-#.+1 '&F-&*%1" .#;"+ 0(M10"-1..=; '3&@1." &:+)&,. 53+D+.# - "&?, D"& '3&<3#??# -&&)M1 F#/(?#.# /*% "&<&, D"&)= )="$ '3#-+*$.&;. 5&L"&?( 0*&2.=1 &:+),+ -'&*.1 ?&<(" '3&%-*%"$0% .# '3&0"=A "10"#A. 5&0*1 L"&<& &)=D.& '&.%".&, </1 &:+),#, + 11 ?&2.& +0'3#-+"$, .1 -/#-#%0$ - /1"#*+, '&D1?( '3&<3#??# .1 3#)&"#1" .# /#..&? "10"1. H'3&D1?, +.&</# *(D:1 -01-"#,+ -.+?#"1*$.& +F(D+"$, D"& 21 '3&+0A&/+" - '3&<3#??1 .# L"+A -A&/.=A /#..=A, +.#D1 ?&2.& +0'3#-+"$ &/.( &:+),( + '3&'(0"+"$ /3(<(C, +*+ /#21 /&)#-+"$ .&-(C, ,&"&3#%, "1? .1 ?1.11, '3+-1/1" , '3#-+*$.&?( &"-1"( .# /#..&? "10"1.

O#?1"$"1, D"& - -=:1'3+-1/1..=A '3+?13#A 0 /-(?% 0&0"&%.+%?+

.#D#*$.=? + "13?+.#*$.=? )=*& '13-&1 0&0"&%.+1. E"& .1@1*10&&)3#F.&, '&0,&*$,( .1,&"&3=1 &:+),+ ?&<(" &0"#"$0% .1F#?1D1..=?+. 5&L"&?( -#3$+3(;"1 L"+ '3&0"=1 "10"=, .#'3+?13, F#?1.+"1 “a” - '13-&; 0"3&D,1 .# “g” + ". /. 53&-13$"1 0*(D#;, ,&</# "13?+.#*$.=A 0&0"&%.+; .1" -&-01.

V1'13$ .1&)A&/+?& '3&-13+"$ «/*+..(C #3+>?1"+,(» + #3+>?1"+,( -&&)M1, '&0,&*$,( - '31/=/(M+A "10"#A '3&-13%*&0$ "&*$,& '3&0"&1 0*&21.+1. 5(0"$ "1'13$ - #*>#-+"1 /-# 0+?-&*#, # - #-"&?#"1 – &/.& 0&0"&%.+1.

sm 1

1 1 1

1 1

0 0

10

H <3#>+D10,&; >&3?1 L"&" "10" '31/0"#-*1. .# 3+0. 5.

s

m

1

23

I+0.5. J**C0"3#@+% , "31"$1?( "10"(

W*% L"&<& "10"# &"-1": 210 = 1024.

5&?1.%;"1 10 .# 20, 30, 60. !"#3#;"10$ ,#2/=; 3#F '&.%"$, '&A&21 *+ D+0*& - &"-1"1 .# 0&&"-1"0"-(CM(C 0"1'1.$ /-&;,+ '& '13-=? + '&0*1/.+?

@+>3#?, ,&*+D10"-( @+>3. H '3+.@+'1, '&*1F.& &/+. 3#F -=(D+"$ ,&*+D10"-& @+>3 + '& .10,&*$,& @+>3 - .#D#*1 + ,&.@1 ( ,#,&<&-.+)(/$ D+0*# -+/# 2100, "#, ,#, L"&

?&21" .1&/.&,3#".& '3+<&/+"$0% .# 0&31-.&-#.+%A.

!/1*#1? 1M1 &/+. A+"3=; "10". H01 L"&, .# 0#?&? /1*1, '3&+F-&/+"0% &D1.$ )=0"3&, /#21 10*+ "10"= .1 )=*+ '&/<&"&-*1.= F#3#.11 – .# )(?#<1. K0*+ -= <&"&-+"1 "10"= .# )(?#<1, '3&-13%;"1 +A + .#A&/+"1 &"-1" F#3#.11. K0*+ &"-1" 0*+:,&? /*+..=;, '3&/(?#;"1, ,#, '& -=A&/.=? /#..=? '3&<3#??= '3&-13+"$, «'&A&2+» *+ &.+ .# '3#-+*$.=; &"-1". X(/$"1 - 0&0"&%.++ &)T%0.+"$ +/1C "10"#. J"#,, 0*1/(CM+; "10":

jnm

2
2	1	1
1	1	1
2	1	2
1	1	1
0	0	0

10

H <3#>+D10,&; >&3?1 L"&" "10" '31/0"#-*1. .# 3+0.6.

j,n,m						n						j,m
	1						2

I+0.6. J**C0"3#@+% , D1"-13"&?( "10"(

H D1? 0?=0* L"&<& "10"#? P#D#*$.&1 0&0"&%.+1 – -"&3&1. 6&.1D.&1 – '13-&1. H01 31)3# +F '13-&<& -1/(" - '13-&1 + .1'&<*&M#CM+1. !*1/&-#"1*$.&, - '13-&1 0&0"&%.+1 .1&)A&/+?& '&'#/#"$ '&0*1/.+? :#<&?. JF -"&3&<& 0&0"&%.+% - '13-&1 -1/1" 31)3&, '&?1D1..&1 0+?-&*&? n. 53+ '131A&/#A '& &0"#*$.=? 31)3# 0&0"&%.+% .1 +F?1.%C"0%. H01 "3+ 31)3#, +0A&/%M+1 +F '13-&; -13:+.= – '&<*&M#CM+1.

W*% L"&<& "10"# &"-1": 29 = 512.

!"#3#;"10$ ,#2/=; 3#F '3+/(?=-#"$ A&"% )= &/+. 0&/132#"1*$.=; "10" – D("$-D("$ 0&/132#"1*$.=;. V#,&; "10" &)=D.& -0,3=-#1" &D1.$ ?.&<& -+/&- &:+)&,, A&"%, ,&.1D.&, ?&21" .1 '&-1F"+, + &:+),# .1 )(/1" &).#3(21.#.

!*1/(CM#% '3&-13,# – «?#,0+?#*$.=; "10"». W*% 1<& <1.13#@++ '+:1"0% 0'1@+#*$.#% '3&<3#??#. P# '3#,"+,1 &.# ?&21" )="$ -0"3&1.# - 31:1.+1. O#?1"+?, D"& <1.13+3(1?=; "10" .1 %-*%1"0% A(/:+? /*% '3&-13,+ (/#*1.+%

.1'&<*&M#CM+A 31)13, .& L"# '3&-13,# - .1? '3&-&/+"0%, '3+D1? /&-&*$.& #,"+-.&. W*% ,#2/&<& 31)3# 0*(D#;.=? &)3#F&? -=)+3#1"0%, %-*%1"0% *+ &.& '&<*&M#C:+?. U1.13#"&3 "10"#:

var i, j:integer; c : char;

begin

for c := 'a' to 'z' do write(c); writeln;

writeln(1000);

24

write('1 1000 ');

for i := 1 to 1000 do write(i,' '); writeln;

for i := 1 to 1000 do for j:=1 to 26 do

writeln(random(1000)+1); for i:=1 to 1000 do

for j:=1 to 26 do writeln(random(2));

writeln(60); end.

5&2#*(;0"#, -.+?#"1*$.& +F(D+"1, D"& /1*#1" L"# '3&<3#??#. 9"-1" .# L"&" "10" ?= F.#1?: 2660. H .1? 85 @+>3, ,#, + - "&?, D"& -=-&/+" '3&<3#??#, .& ,#, '&*.&0"$C ()1/+"$0% - '3#-+*$.&0"+ 3#)&"= 31:1.+% .# L"&? "10"1? KM1 3#F F#?1"$"1, D"& 0-&;0"-& 31)3# )="$ .1'&<*&M#CM+? <1.13+3(1"0% 0*(D#;.=? &)3#F&?. P1 '3+-1/1" *+ L"& , &:+),#?? Q1<,& F#?1"+"$, D"& D+0*& 2660 /&*2.& F#,#.D+-#"$0% .# @+>3( 6, "&</# ,#, -= L"& -3%/ *+ '&*(D+"1, F#'(0"+- '3&<3#??(

.# '3+?131, 0<1.13+3&-#..&? -=:1'3+-1/1..=? ,&/&?. 53+D+.# +?1..& -

.1'&<*&M#CM+A @+,*#A, (?1.$:#CM+A &"-1". P1 -01 0"3&,+ /*+.= 60 /&'(0,#C"0% 0<1.13+3&-#..=? W68. O#?1.+"1 random(2) .# .&*$, '131F#'(0"+"1 <1.13#"&3 + '&*(D+"1 ,&331,".=; "10", &"-1" .# ,&"&3=; )(/1" 2660, ,#, + &2+/#*&0$.

3.7. 6'=-(9+ %+ *"'2#"9; 2 C3"&

O/10$ .1" .+,#,+A 0'1@+#*$.=A 31,&?1./#@+; /*% /#..&; ,&.,31".&; F#/#D+. !*1/(;"1 &)M+? 0&-1"#?, &'+0#..=? - 3#F/. 2.7.

4. D+9(30#%

H /#..&; 3#)&"1 3#00?&"31.= &)M+1 '3+.@+'= 31:1.+% F#/#D - 3#?,#A ,&?#./.=A 0"(/1.D10,+A 0&31-.&-#.+; '& '3&<3#??+3&-#.+C >&3?#"# ACM ICPC. H='&*.1.# '&'=",# >&3?#*+F&-#"$ + &'+0#"$ '3&@100 31:1.+% F#/#D+ -?10"1 0 ,*CD1-=?+ #0'1,"#?+ /*% ,#2/&<& L"#'#. I#00?&"31. '3+?13. 53+-1/1.= ,&??1."#3++ + 31,&?1./#@++.

6&.1D.&, .+,#,#% +.0"3(,@+% .1 F#?1.+" 31#*$.&<& &'="#. 9/.#,&, .# >&3"1'+#.& '&D1?(-"& '3+.%"& (D+"$0% +<3#"$ ( '31'&/#-#"1*%, + "#, .#D+.#*+ '3#,"+D10,+ -01 -1*+,+1 ,&?'&F+"&3=. !&&"-1"0"-1..&, D"1.+1 L"+A 31,&?1./#@+; /&*2.& )="$ .1 '&'=",&; '3+?1.+"$ , 01)1 D(2+1 ?1"&/=, # 0&/132#"1*$.=? -&0'3+%"+1? D(2&<& &'="#, +F*&21..=? - -+/1 .#)&3# 31,&?1./#@+;. H '3&@1001 ?&1; &*+?'+#/.=; ,#3$13= % ?.&<& &)0(2/#* 3#F*+D.=1 "#,"+D10,+1 + 0"3#"1<+D10,+1 #0'1,"=, "&D,+ F31.+% +F?1.%*+0$ .# /+#?1"3#*$.& '3&"+-&'&*&2.=1 - "1D1.+1 /.%. 4&<*& )="$ + "#,, D"& - &/+. 01F&. ?= '3+/132+-#*+0$ &/.&; "#,"+,+, # - /3(<&; – /3(<&;. V#,"+,# F#-+0+" &" &'="#, @1*1;, 0&'13.+,&-.

25

H#2.& "31.+3&-#"$0% 0#?&0"&%"1*$.&, &0&)1..& 10*+ -= D(-0"-(1"1, D"& 0+*$.& &"0"#1"1 A&"% )= &" &/.&<& +F 0-&+A .#'#3.+,&-. H#2.& )="$ F#+."1310&-#..=?.

K0*+ -= 0+0"1?#"+D10,+ +F(D#1"1 L"( '3&)*1?(, "&, 0*1/&-#"1*$.&, -= -013$1F .#@1*1.= .# 31:1.+1 F#/#D. P1&)A&/+?& -"%.("$0% - L"&" '3&@100, 2+"$ 31:1.+1? F#/#D, ?&21" )="$, "&*$,& +?. P1&)A&/+?& '&*(D#"$ (/&-&*$0"-+1 &" L"&<&, D"&)= ?&2.& )=*& '3&0.("$0% .&D$C + '&;"+ 31:#"$ F#/#D+, )="$ <&"&-=? &)0(2/#"$ F#/#D+ - *C)&1 -31?% – -& -0%,&? 0*(D#1, "#,&1 '&?1:#"1*$0"-& /&*2.& )="$ .# .#D#*$.&? L"#'1 ,#3$13=. 6&.1D.&, '3+/1"0% '&"3#"+"$ 0&".+ D#0&- + 31:+"$ 0&".+ F#/#D, - "&? D+0*1 0#?&0"&%"1*$.&. H'3&D1?, L"& 1M1 .1 <#3#."+3(1" 31F(*$"#"#.

J )*#<&/#3+"1 0&F/#"1*1; ACM ICPC F# "&, D"& - .1? ?&2.& (D#0"-&-#"$ "&*$,& - 0"(/1.D10,+1 <&/=, '3+D1? - >+.#*1 – .1 )&*11 /-(A 3#F. !T1A#-:(C "#,+? &)3#F&? ,3=:( )(/1" &D1.$ .1'3&0"& -13.("$ .# ?10"&… G/#D+ H#?!

S )*#<&/#31. '3&>100&3( !5)UG JV49 8.8.R#*="&, ()1/+-:1?( ?1.%

.#'+0#"$ L"( 0"#"$C + -.10:1?( ?.&210"-& '31/*&21.+; '& 11 (*(D:1.+C.

I=5'0%&9&

1.;&*"'4 C.<., D*%A$"'4 B.E. Z+.#*$.=1 0&31-.&-#.+% D1?'+&.#"# ?+3# '& '3&<3#??+3&-#.+C. 5&"3%0#CM+; (0'1A '1"13)(3<0,+A ,&?#./ // 6&?'$C"13.=1 +.0"3(?1."= - &)3#F&-#.++. 2001, 7 2. http://ict.edu.ru/lib/

F',*"2"03 ($,@)'"*# ,)%* @' @%'>%*,,)%'4*"). ACM 2003/2004. !1-13&-

H&0"&D.=; K-3&'1;0,+; 31<+&. / 5&/ 31/. '3&>. H.P. H#0+*$1-# + '3&>. H.U. 5#3>1.&-#. !5).: !5)UG JV49. 2003.

2.G'>*#0%$4 H. 6 +0"&3++ D1?'+&.#"&- ?+3# ACM '& '3&<3#??+3&-#.+C //

4+3 56 – W+0,. 2004, 7 6. http://is.ifmo.ru/belletristic/_acmhist.pdf

3.G'>*#0%$4 H. P#0 .1 /&<&.%"?! // 4+3 56 – W+0,. 2005, 75. http://is.ifmo.ru/belletristic/_acm2005.pdf

4.G%92"' ;.I., F*@-*" I.!. 4&0,&-0,+1 &*+?'+#/= '& '3&<3#??+3&-#.+C.

4.: P#(,#, 1990.

6.G$%'4 B.!., I*@9"'4 ;.B., C*#.1)" B.;., D'"',*%$4 ;.J. 90&)1..&0"+

.#@+&.#*$.=A F#/#D '& +.>&3?#"+,1. 6+3&-: V3+#/#-!, 2000.

7.F)%.1)" B., I*@9"'4 ;., <=9-'4 :. O#/#D+ '& +.>&3?#"+,1. 412/(.#3&/.=1 &*+?'+#/= 1989-1996 <<. 4.: ABF, 1996.

8.<4&6"")='4 ;., <4&6"")='4* K., C*%($"=' ;., D%'1'%'4 H. JF)3#..=1 F#/#D+ &*+?'+#/ '& +.>&3?#"+,1. 4.: V3&-#.", 1997.

9.:=)$"* :., H$4)--* C. 9*+?'+#/.=1 F#/#D+ '& '3&<3#??+3&-#.+C. I(,&-&/0"-& '& '&/<&"&-,1 , 0&31-.&-#.+%?. 4: 6(/+@-9)3#F, 2005.

10.;2*,*% L. J00*1/&-#.+1 '0+A&*&<++ '3&@100# +F&)31"1.+% - &)*#0"+ ?#"1?#"+,+. 4.: 4NP49, 2001.

11.D9*"=*%$ ;. 9 .#(,1. 4.: P#(,#, 1983.

12.:*3# «U1.3+A !#(*&-+D 8*$":(**13, #-"&3 VIJO, IVH + VIVQ». http://www.altshuller.ru/

13.;"2%$$4* J.B. I1:1.+1 F#/#D XIII ?12/(.#3/.&; &*+?'+#/= //

J.>&3?#"+,#. 2001. 7 37, 40, 42–44.

14.<=9-'4 :.C., ?9-6#")='4 M.B. I#F)&3 F#/#D ?12/(.#3&/.&; &*+?'+#/= 2000 <&/# // J.>&3?#"+,#. 2001. 7 12.

26

15.:#*"=$4)( ;.:. I1:1.+1 F#/#D I H013&00+;0,&; ,&?#./.&; &*+?'+#/= '& '3&<3#??+3&-#.+C // J.>&3?#"+,#. 2001. 7 12.

16.:#*"=$4)( ;.:. II H013&00+;0,#% ,&?#./.#% &*+?'+#/# :,&*$.+,&- '& '3&<3#??+3&-#.+C // J.>&3?#"+,#. 2002. 7 12.

17.;"2%$$4* J.B. 9*+?'+#/= '& +.>&3?#"+,1. 5("$ , -13:+.1 // J.>&3?#"+,#. 2001. 7 38, 40, 42, 44, 46, 48; 2002. 7 6, 8, 10, 12, 14, 16.

18.N'@=%'A# M., C'#4*") H., O-+,*" M. H-1/1.+1 - "1&3+C #-"&?#"&-, %F=,&- + -=D+0*1.+;. 4.: H+*$%?0, 2002.

19.F*%@'4 P.E. V1&3+% #-"&?#"&-. !5).: 5+"13, 2002.

20.F"9# M.Q. J0,(00"-& '3&<3#??+3&-#.+%. V. 2. 5&*(D+0*1..=1 #*<&3+"?=.

4.: «H+*$%?0», 2001.

27

6"&('C#%. 6'(%-? &=.',%-? 5#9=5 "#$#%&8 /+,+0&

«E#*'1('<+3<&? ,#5#")&%&"'2+%%-? 9'%#0%-? +25')+5» %+

Borland Delphi

{$apptype console} // M/B037E :/14/5E1/, A)*5/O,1*,

// Q:5D>*7E A)/-,):* A,),A/51,1*8 * /7:5D>*7E /A7*+*B3J*D

{$o-,q+,r+}

uses Math, SysUtils; // (/0:5D>*7E +/0;5* Math * SysUtils

		{N5*1138 3)*6+,7*:3. M5/O,1*, * -2-/0 >*453}
const
pow	= 9;	// N5*1138 3)*6+,7*:3 A/ 9 0,487*>12. J*6)
base = round(1e9); // 10pow
m =	10;	// 9),@;,+/, :/5*>,47-/ 73:*. «J*6)»
type

long = array [0..m] of integer; // 9*A: 05*11/, >*45/

//()/J,0;)3 45/O,1*8 0-;. 05*112. >*4,5 a * b

//P,B;5E737 B3A*42-3,748 - a

//(,),0 A3)3+,7)/+ b 47/*7 :5D>,-/, 45/-/ var,

//73: :3: A,),03-37E +344*- A/ B13>,1*D 45*G:/+ +,05,11/,

//A/ 4425:, C/)3B0/ @247),,

procedure add(var a : long; var b : long); var i, c : integer;

begin

c := 0;

for i := 0 to m do begin

c := c + a[i] + b[i]; if c >= base then begin

a[i] := c - base; c := 1;

end else begin

a[i] := c; c := 0;

end; end;

//H45* -0);C “J*6)” - 7*A, long /:3O,748 1,0/4737/>1/,

//4*C135*B*);,748 /G*@:3

assert(c = 0); end;

// (,>37E 05*11/C/ >*453 procedure print(var x : long); var i, j : integer;

begin

i := m;

while (i > 0) and (x[i] = 0) do dec(i); write(x[i]);

for j := i - 1 downto 0 do

write(format('%.' + IntToStr(pow) + 'd', [x[j]]));

end;

28

	{=/1473172 * A,),+,112,}
const	// N-, :/1473172 *B ;45/-*8 B303>*
max_nst = 1000;	// S3:4*+35E1/, :/5*>,47-/ 4/47/81*?
max_na = 26;	// S3:4*+35E12? )3B+,) 3563-*73
var
alfa : string;	// Q./01/? 3563-*7 3-7/+373
na : integer;	// =/5*>,47-/ 4*+-/5/- -/ -./01/+ 3563-*7,
nst : integer;	// =/5*>,47-/ 4/47/81*? 3-7/+373
ist : integer;	// T3>35E1/, 4/47/81*, 3-7/+373

ntst : integer; // =/5*>,47-/ 7,)+*135E12. 4/47/81*? 3-7/+373

len : integer; // N5*13 )344+37)*-3,+2. 47)/:

//U-58,748 5* 4/47/81*, 7,)+*135E12+ term : array [1..max_nst] of boolean;

//V;1:J*8 A,),./0/-

fi : array [1..max_nst, 1..max_na] of integer;

//U-58,748 5* ),@)/ 1,A/C5/<3D<*+?

ee : array [1..max_nst, 1..max_na] of boolean;

sum, sum2 : array [0..max_nst] of long;

i, j, k, z : integer;		// Q),+,112, A,),+,112,
ans : long;
	{Q-/0 -./012. 03112.}
begin
readln(alfa);	// R*73,+ 3563-*7
na := length(alfa);//		K+,,7 B13>,1*, 7/5E:/ )3B+,) 3563-*73
read(nst);	//	R*73,+	:/5*>,47-/ 4/47/81*?
read(ist);	//	R*73,+	1/+,) 13>35E1/C/ 4/47/81*8
read(ntst);	//	R*73,+	:/5*>,47-/ 7,)+*135E12. 4/47/81*?

// R*73,+ 1/+,)3 7,)+*135E12. 4/47/81*? for i := 1 to nst do

term[i] := false; for i := 1 to ntst do begin

read(j);

term[j] := true; end;

//R*73,+ 6;1:J*D A,),./0/- " for i := 1 to nst do

begin

for j := 1 to na do read(fi[i][j]); end;

//R*73,+ 6;1:J*D &

for i := 1 to nst do begin

for j := 1 to na do begin

read(k);

ee[i][j] := k = 1; end;

end;

// R*73,+ N – 05*1; 47)/:, :/5*>,47-/ :/7/)2. 1,/@./0*+/ 13?7* read(len);

29

		{W73A 1. F47)31,1*, 1,A/C5/<3D<*. ),@,)}
for	j := 1	to na do	// (/ -4,+	4*+-/53+ 3563-*73
for	i := 1	to nst do	// (/ -4,+	4/47/81*8+ 3-7/+373
begin
k	:= i;		// 9,:;<,,	4/47/81*,
z	:= nst;		// =/5*>,47-/ 4/47/81*?

//(/:3 ),@)/-A,),./0 *B 4/47/81*8 k A/ 4*+-/5; j –

//A/C5/<3D<,,, * ,<, 45,531/ 1, />,1E +1/C/ A,),./0/- while (ee[k][j]) and (z > 0) do

begin
k := fi[k][j];	//	(,),?7*
dec(z);	//	F+,1EG*7E 4>,7>*:
end;

// H45* -4, ,<, />,),01/, ),@)/ – 1,A/C5/<3D<,,

if ee[k][j] then
begin
fi[i][j] := 0;	// I13>*7 – J*:5
end else
begin

fi[i][j] := fi[k][j];// K13>, A,),473-58,+ ),@)/

end;

// K 7,A,)E 41*+3,+ A/+,7:; «1,A/C5/<3D<,, ),@)/» ee[i][j] := false;

end;

{W73A 2. (/04>,7 :/5*>,47-3 47)/:, 0/A;4:3,+2. 3-7/+37/+,}

{4 A/+/<ED 0*13+*>,4:/C/ A)/C)3++*)/-31*8}

// K1*J*35*B3J*8

for i := 0 to nst do

fillchar(sum[i], sizeof(sum[i]), 0); sum[ist][0] := 1;

// (/45,0/-37,5E1/, -2>*45,1*, for k := 1 to len do

begin

sum2 := sum;

for i := 0 to nst do

fillchar(sum[i], sizeof(sum[i]), 0); for i := 1 to nst do

for j := 1 to na do begin

add(sum[fi[i][j]], sum2[i]); end;

end;

//(/5;>,1*, /7-,73

//N58 X7/C/ 4;++*);,+ :/5*>,47-/ 4A/4/@/- /:3B37E48

//- :3O0/+ 7,)+*135E1/+ 4/47/81**

fillchar(ans, sizeof(ans), 0); for i := 1 to nst do

if term[i] then add(ans, sum[i]);

{Q2-/0 /7-,73}

print(ans); end.

30