Bài toán
Vũ Văn Th oả
Ta b t đ u b ng bài toán trong ch ng trình"Đ ng lên đ nh olimpia".ắ ầ ằ ươ ườ ỉ
Bài toán 1. M t dãy g m 10 bóng đèn đ c đánhs t 1 đ n 10 tr ng thái t t. Ng iộ ồ ượ ố ừ ế ở ạ ắ ườ
ta thay đ i tr ng thái cácbóng đèn th o qui t c sau đây.ổ ạ ẻ ắ
L n 1: thay đ i tr ng thái t t c các bóng đèn.L n 2: thay đ i tr ng thái các đèn có sầ ổ ạ ấ ả ầ ổ ạ ố
hi u chia h t cho 2. L n3: thay đ i tr ng thái các bóng đèn có s hi u chia h t cho 3.ệ ế ầ ổ ạ ố ệ ế
C nh v y cho đ n l n th 10 thì thay đ i tr ng thái các bóng đèncó s hi u chia h tứ ư ậ ế ầ ứ ổ ạ ố ệ ế
cho 10.
H i nh ng bóng đèn có s hi u nào còn sáng?ỏ ữ ố ệ
Gi i. Khi th c hi n vi c thay đ i tr ng thái, m ts bóng đèn t t, m t s khác sáng. Doả ự ệ ệ ổ ạ ộ ố ắ ộ ố
đó trên dãy đèn đã chotr thành dãy đèn nh p nháy.ở ấ
Tr c h t ta nh n xét r ng, sau 10 l n thay đ itr ng thái nh bài ra, nh ng bóng đènướ ế ậ ằ ầ ổ ạ ư ữ
có s l l n thay đ i s là bóng đèn còn sáng. Ký hi u S[k] là t p h p các s i,ố ẻ ầ ổ ẽ ệ ậ ợ ố
1<=i<=1,sao cho i là b i c a k. Khi đó s l n k s thay đ i tr ng thái cácbóng đèn cóộ ủ ố ầ ẽ ổ ạ
s hi u i thu c S[k], hay k là cc a i. Do đó s l n thay đ i t ng thái c a bóng đèn iố ệ ộ ướ ủ ố ầ ổ ạ ủ
b ng các cs T(i) c a i.ừ ướ ố ủ
Ta có th gi i b ng toán h c nh sau. Ta đã bi tr ng, n u:ể ả ằ ọ ư ế ằ ế
+i=P1a1...pkak,trong đó p1,...,pk là các s nguyên t khác nhau;thì T(i)=(a1+1)...(ak+1). Doố ố
đó n u i là s chính ph ng thì T(i) l ,còn các tr ng h p khác T(i) ch n. Suy ra cácế ố ươ ẻ ườ ợ ẵ
bóng đèn có s hi u1, 4, 9 còn sáng. Các bóng đèn khác b t t.ố ệ ị ắ
+Ta có thu t toán nh sau.ậ ư
-V i m i i, 1<= i<= 10 đ t T(i)=0ớ ỗ ặ
-Xét t t c k, 1<= k<= i, n u k là c c a i thì T(i)=T(i)+1ấ ả ế ướ ủ
-N u T(i) l thì đèn T(i) sáng, n u T(i) ch n thì đèn T(i) t t.ế ẻ ế ẵ ắ
1.Rõ ràng là v i s l ng bóng đèn n l n h n 10r t nhi u thì gi i b ng toán h cớ ố ượ ớ ơ ấ ề ả ằ ọ
không th xác đ nh đ c ngay s hi u bóng đèn còn sáng. Khi đó nh cách gi i quy tể ị ượ ố ệ ờ ả ế
tr c ti p trênmáy tính ta s nhanh chóng xác đ nh đ c s hi u bóng đèn cònsáng.ự ế ẽ ị ượ ố ệ
H n n a, n u s l n thay đ i tr ng thái là m b tkì thì cách gi i 2 càng thu n ti n h n.ơ ữ ế ố ầ ổ ạ ấ ả ậ ệ ơ
Các b n t l p ch ng trình gi i bài toán 1 v in,m và tr ng thái ban đ u c a dãy bóngạ ự ậ ươ ả ớ ạ ầ ủ
đèn là tuỳ ý. B n có th tham kho thêm thu t gi i bài toán 2.ạ ể ả ậ ả
Ta chuy n sang gi i bài toán " đèn nh p nháy"là bài toán ra trong kì thi Tion h c qu cể ả ấ ọ ố
t l n th 10 (năm 1998 t iB Đào Nha)ế ầ ứ ạ ồ
Bài toán 2. Đèn cho ngày h i (PARTY)ộ
Có N đèn màu đánh s tùe 1 đ n N và 4 nút thay đ itr ng thái c a chúng. n nút 1 thayố ế ổ ạ ủ ấ
đ i tr ng thái các đèn; nnút 2 thay đ i tr ng thái các đèn có s hi u l ; n nút 3 thauổ ạ ấ ổ ạ ố ệ ẻ ấ
đ itr ng thái đèn có s hi u ch n; n nút 4 thay đ i các đèn có s hi u d ng 3k+1ổ ạ ố ệ ẵ ấ ổ ố ệ ạ
(k>=0);
Có m t máy đ m C đ đ m t ng s các l n n núttrên. Ban đ u, t t c ác đèn đ uộ ế ể ế ổ ố ầ ấ ầ ấ ả ề
sáng và C ch 0.ỉ
Yêu c u: Cho giá tr C và tr ng thái cu i cùng c am t s đèn. Hãy l p ch ng trìnhầ ị ạ ố ủ ộ ố ậ ươ
xác đ nh t t c các tr ng thái( có th có) cu i cùng c a N đèn t ng ng v i các thôngị ấ ả ạ ể ố ủ ươ ứ ớ
tin đãcho.
D li u vào: T p PARTY.IN ch a 4 dòng. Dong 1 cho s N. Dòng 2 cho giá tr c a C.ữ ệ ệ ứ ố ị ủ
Dòng 3 và 4 cho danh sách các đèn cótr ng thái cu i cùng t ng ng lad sáng hay t t.ạ ố ươ ứ ắ
S hi u các đèntrong m i danh sách cách nhau m t d u cách và k t thúc b i s -1.ố ệ ỗ ộ ấ ế ở ố
Víd t p PARTY.IN có d ngụ ệ ạ
10
1
-1
7
-1
đây s đèn là 10, ch n 1 nút và tr ngthái cu i cùng đèn 7 t t.ở ố ỉ ấ ở ạ ố ắ
D li u ra: T p PARTY.OUT ch a t t c các tr ngkthái cu i cùng có th có (khácữ ệ ệ ứ ấ ả ạ ố ể
nhau) c a các đèn. M i tr ng tháighi trên 1 dòng g m N kí t 0 và 1, trong đó 0 ngủ ỗ ạ ồ ự ứ
v i đèn t t,còn 1 là đèn sáng. Th t các dòng tuỳ ý.ớ ắ ứ ự
V i d li u vào nh trên t p PARTY.Out có d ng.ớ ữ ệ ư ệ ạ
0000000000
0110110110
0101010101
H n ch : 0<= N<= 100, 1<= C<= 10000. S l ng các đèn sáng và đèn t t tr ng tháiạ ế ố ượ ắ ở ạ
cu i cùng <= 2. D li u vào đ m b o có ít nh t 1 tr ng thái c a N đèn thoã mãn.ố ữ ệ ả ả ấ ạ ủ
Gi i. Ta chia N đèn thành 4 nhóm không giao nhau:ả
+Nhóm 1 g m các đèn s hi u l và khác d ng 3k+1ồ ố ệ ẻ ạ
+Nhóm 2 g m các đèn s hi u ch n và khác d ng 3k+1ồ ố ệ ẵ ạ
+Nhóm 3 g m các đèn s hi u l có d ng 3k+1ồ ố ệ ẻ ạ
+Nhóm 4 g m các đèn có s hi u ch n có d ng 3k+1ồ ố ệ ẵ ạ
+Khi n nút 1 các đèn thu c t t c các nhóm thay đ itr ng thái.ấ ộ ấ ả ổ ạ
+Khi n nút 2 các đèn thu c nhóm 1và 3 thay đ itr ng thái.ấ ộ ổ ạ
+Khi n nút 3 các đèn thu c nhóm 3 và 4 thay đ itr ng thái.ấ ộ ổ ạ
+Khi n nút 4 các đèn thu c nhóm 3 và 4 thay đ itr ng thái.ấ ộ ổ ạ
+Khi n m t nút b t kì các đèn trong 1 nhóm ho ccùng thay đ i tr ng thái ho c không.ấ ộ ấ ặ ổ ạ ặ
Do đô ta ch c n xét 4 đènđ i di n cho 4 nhóm. H n n a, m t đèn b t kỳ không thayỉ ầ ạ ệ ơ ữ ộ ấ
đ i tr ngthái n u s l n thay đ i tr ng thái c a nó ch n. Ng c l i, đèns thay đ iổ ạ ế ố ầ ổ ạ ủ ẵ ượ ạ ẽ ổ
tr ng thái. Suy ra đ i v i m i nút ch c n xét 2 kh năng: s l n n nút ch n kí hi u 0ạ ố ớ ỗ ỉ ầ ả ố ầ ấ ẵ ệ
và s l n n nút l kí hi u1. Nh v y, ta ch càn xet 2ố ầ ấ ẻ ệ ư ậ ỉ 4 =16 kh năng có th x y ra.ả ể ả
Ký hi u ON là t p các đèn sáng và OFF là t p cácđèn t t trong tr ng thái cu i cùng đãệ ậ ậ ắ ạ ố
cho, còn s là t p đèn sángtrong tr ng thái cu i cùng nào đó. Khi đó tr ng thái này th aậ ạ ố ạ ừ
nh nđ c n u thoã mãn (ON<=S) và (OFF<=[1..4]-S)ậ ượ ế
Ta có ch ng trình Pascal đ y đ nh sau:ươ ầ ủ ư
Program Party;
Uses Crt;
Type t= Set Of 1..4
Var c,i1,i2,i3,i4,j,k,m,n:integer;
On,off,s:T;
X:Array [ 1..50 ] Of Integer;
Contr:Array [ 1..16 ] Of t;
Flag:Boolean;
Inp,outp:Text;
Procedure ReadData; { thu tuc nhap du lieu }
Begin
Assign(inp,'a:pasparty.inp');Reset(inp);
Readln(inp,a);Readln(inp,c);
On:=[];Read(inp,j);
While j<>-1 Do
Begin
If j mod 3 <>1 Then
If ođ(j) Then On:=On+[1] Else On:=On+[2]
Else If Ođ(j) Then On:=On+[3] Else On:=On+4;
Read(inp,j);
End;
If j=-1 Then Readln(inp);
Off:=[];readln(inp,j);
While j<>-1 Do
Begin
If j mod 3 <>1 Then
If ođ(j) Then off:=off+[1] Else off:=off+[2]
Else If Ođ(j) Then off:=off+[3] Else off:=off+4;
Read(inp,j);
End;
Close(inp);
End;
Procedure Solve {Thu tuc tim cac trang thai N den thoa man}
Begin
Asign(out,'a:pasparty.out');rewrite(out);
For i4:=0 To 1 Do
For i3:=0 to 1 Do
For i2:=0 To 1 Do
For i3:=0 To 1 Do
Begin
K:=i1+i2+i3+i4;
If (c>=k) Then
Begin
S:=[1..4];
For m:=1 To 4 Do
Case m Of
1:If Ođ(i1+i2) Then s:=s-[1];
2:If ođ(i1+i3) Then S:=S-[2];
3:If ođ(i1+i2+i4) Then S:=S-[3];
4:If ođ(i1+i3+i4) Then s:=s-[4];
End;
If (on<=s) and(off<=[1..4]-s) Then
