Trên bàn đặt một bộ bài gồm n-1 quân bài mã số 1,2,…,n-1, 3 £ n £ 10000. Trọng tài chỉ định bạn lấy k quân bài.
Sau đó trọng tài đưa ra một số tự nhiên s. Bạn cần cố gắng thực hiện ít nhất m
thao tác thuộc một trong hai loại sau đây:
- Lấy thêm một quân bài từ
trên bàn,
- Bỏ bớt một quân bài trên
tay,
để cuối cùng đạt được hệ thức
t mod n = s mod n (*)
trong đó t là tổng số hiệu các quân bài có trên tay bạn sau khi bạn
đã hoàn tất m thao tác như trên.
Dữ liệu vào: file văn bản BAI.INP
Dòng đầu tiên: 3 số tự nhiên n, k và s.
Từ dòng thứ hai trở đi: k số tự nhiên thể hiện mã số của các quân
bài cần lấy lúc đầu.
Dữ liệu ra: Hiển thị trên màn hình
Dòng đầu tiên: số tự nhiên m cho biết số thao tác ít nhất cần thực
hiện
Tiếp đến là m dòng, mỗi dòng là một thao tác lấy thêm hoặc bỏ bớt một quân bài v. v > 0 cho biết
cần lấy thêm (từ trên bàn) quân bài v; v < 0 cho biết cần bớt (từ trên tay)
quân bài v để đạt được hệ thức (*).
Thí dụ, với n = 8, trọng tài cho số s = 22 và chỉ định bạn lấy k =
3 quân bài là 2, 3 và 6.
Nếu bạn bỏ quân bài 2 và lấy quân bài 5 thì tổng t = 3 + 6 + 5 =
14. Khi đó
t mod n = 14 mod 8 = 6 = s mod n = 22 mod 8.
Vậy một lời giải cho bộ dữ liệu này là
Thực hiện 2 thao tác: -2 và +5
|
BAI.INP
|
MÀN HÌNH
|
Ý NGHĨA
|
|
8 3 22
2 3 6
|
2
-2
5
|
Cho bộ bài gồm 8 quân. Lúc đầu trọng tài chỉ
định bạn lấy k = 3 quân bài mã số 2, 3 và 6. Ngoài ra trọng tài đưa ra số s =
22.
Sau đó bạn thực hiện 2 thao tác
- bỏ quân bài 2
- lấy thêm quân bài 5.
Khi đó tổng số hiệu các quân bài có trên
tay bạn sẽ là:
T
= 3 + 6 + 5 = 14
T
mod N = 14 mod 8 = 6 = s mod 8 = 22 mod 8.
|
 |
|
n = 8; s = 22; Trên tay giữ k = 3 quân bài 2, 3, 6.
Lời giải: Bỏ quân bài 2, lấy thêm
quân bài 5.
t = 3+6+5 = 14,
t mod 8 = 14 mod 8 = 6 = s mod 8 = 22
mod 8.
|
Thuật toán
Ta sẽ chứng minh rằng với không quá 2 thao tác (+) lấy thêm
/ (-)
bỏ bớt một quân bài ta có thể đạt được hệ thức (*).
Trước hết ta nhắc lại các phép toán đồng dư. Với số nguyên
dương n cho trước ta xét tập các số dư trong phép chia một số tự nhiên x cho n, x mod n, Zn =
{0,1,2,…,n-1}. Trên Zn các phép toán cộng và nhân được thực hiện như
bình thường sau đó lấy kết quả chia dư cho n. Phép toán lấy số đối của số x cho
ta n-x.
Phép trừ x-y
được đổi thành phép cộng x với số đối của y. Ta có
Cộng: (x + y) mod
n
Nhân: x*y mod n
Lấy số đối của x:
n - x
Trừ: (x + (n-y)) mod n.
Hãy tưởng tượng
các số của Zn là 0, 1, …, n-1 được bố trí trên một vòng tròn như
trên mặt đồng hồ. Để tính tổng x+y ta xuất phát từ x và di chuyển y bước theo
chiều kim đồng hồ (còn gọi là di chuyển
xuôi), mỗi bước ta chuyển qua một số. Kết quả sẽ là điểm dừng cuối cùng. Để
tính hiệu x - y ta cũng xuất phát từ x và di chuyển y
bước theo chiều ngược lại (di chuyển
ngược). Để ý rằng, trên vòng tròn gồm n số,
di chuyển xuôi y bước sẽ cho cùng kết quả như di chuyển ngược (n-y) bước, và ngược lại, di chuyển ngược y
bước sẽ tương đương như di chuyển xuôi (n-y) bước. Điều này có nghĩa là muốn thêm b đơn vị
cho đại lượng t ta có thể bớt (n-b) đơn vị và ngược lại, muốn bớt b đơn vị từ đại
lượng t ta có thể thêm cho t (n-b) đơn vị. Ta cũng để ý rằng số hiệu của mọi quân
bài đều nhỏ thua n và mỗi quân bài hoặc là có trên tay người chơi, hoặc là nằm
trên bàn. Vì lẽ trên, đôi khi người ta nói tính toán theo đồng dư (modulo) chính là tính toán trên vòng tròn.
Bạn cũng cần ghi
nhớ tính chất sau đây:
Với mọi số tự nhiên x, y và n, n > 0 và với mọi
phép toán số học q Î
{+, -,*} ta luôn có
(x q y) mod n = ((x mod n) q
(y mod n)) mod n
Công thức trên
cho ta quy tắc dễ hiểu sau đây: Khi tính trị của các biểu thức số học chỉ chứa
các phép toán cộng, trừ và nhân trong Zn ta có thể thực hiện phép
lấy số dư mod n trên các hạng tử và
các kết quả trung gian.
Vì lũy thừa
nguyên dương tương đương với phép nhân liên tiếp, ta suy ra hệ quả sau:
ak mod n =
(a mod n)k mod n
Sau khi đã biết các giá trị input là n, k, s và số hiệu các
quân bài cần lấy lên tay, ta gán trị cho
mảng a[1..n-1]
như sau: a[i] = 1 cho biết quân bài i có trên tay, ngược lại, a[i] = 0 cho biết
quân bài i còn nằm trên bàn. Với thí dụ đã cho, trọng tài yêu cầu ta lấy 3 quân
bài có số hiệu 2, 3 và 6 nên a = (0,1,1,0,0,1,0) ứng với a[2] = a[3] = a[6] =
1, các giá trị a[i] còn lại đều bằng 0.
Trước hết ta tính tổng số hiệu của các quân bài có trong tay
lúc đầu và đặt trong biến t. Sau đó ta tính t := t mod n và s := s mod n. Với
thí dụ đã cho ta tính được
t = 2+3+6 = 11,
do đó t mod n = t mod 8 = 3
và s mod 8 = 22
mod 8 = 6
Tức là t = 3 và s
= 6.
Giả sử t ³ s, ta đặt b = t - s và xét các trường hợp loại trừ nhau sau
đây:
1.
b = 0: Hệ thức (*) đã thỏa, ta
không phải làm gì. Ta thông báo m = 0, trong đó m là số thao tác +/-
cần thực hiện.
2.
Quân bài b có trên tay, tức là a[b] = 1: Ta chỉ việc bỏ quân bài này
xuống, khi đó tổng t sẽ giảm b đơn vị theo mod n.
3.
Quân bài (n-b) có trên
bàn, tức là a[n-b] = 0: Ta
chỉ việc lấy thêm quân bài này. Khi đó tổng t sẽ được thêm (n-b) đơn vị theo
mod n, điều này tương đương với việc giảm tổng t đi b đơn vị theo mod n.
4. Nếu không xảy ra các trường hợp 1, 2
và 3 như trên, tức là b ¹ 0, a[b] = 0,
a[n-b] = 1, ta tiến hành như sau:
Tìm hai quân bài
u và v thỏa các điều kiện sau
Quân bài u có
trên tay, a[u] = 1,
Quân bài v có
trên bàn, a[v] = 0,
u = (k*b) mod n;
v = ((k-1)*b) mod n, k là một số tự nhiên. Điều
này có nghĩa là u lớn hơn v b đơn vị theo mod n.
Nếu tìm được hai
quân bài u và v như trên ta sẽ thực hiện hai thao tác: bỏ quân bài u (-u) và lấy thêm quân bài v (+v). Khi đó tổng t sẽ được giảm một lượng b theo mod n. Thật vậy,
(u - v) mod n = (k*b - (k-1)*b) mod n = b.
Trường hợp t < s ta phải thêm b = s - t
đơn vị cho cho t. Việc này tương đương với giảm
t bớt (n-b) đơn vị. Đặt b =
n-b rồi lặp lại thủ tục trên sẽ cho ta kết quả tương ứng.
Ta chứng minh
rằng nếu gặp tình huống 4 thì bao giờ cũng có thể tìm được hai quân bài u và v
như đã mô tả. Trên hai ngàn năm trước nhà toán học Cổ Hy Lạp Diophantus đã phát
biểu và chứng minh định lý sau:
Định lý Cho phương trình ax mod n = b mod n, với các hệ số a, b, n là các số tự
nhiên, n > 0. Gọi d là ước chung lớn nhất của a và n, d = (a,n). Khi đó
a) Nếu d không là ước của b thì phương trình
vô nghiệm.
b) Nếu b = kd thì phương trình có đúng d
nghiệm trong tập Zn. Các nghiệm này có dạng (x + i(n/d) ) mod n,
trong đó x là một nghiệm tùy ý, i = 0,1,2...(d-1).
Phương trình ax
mod n = b mod n được người đời sau gọi là phương trình Diophantus.
Chứng minh
Nếu x là nghiệm của phương trình ax mod n = b mod n thì ax và
b có cùng số dư theo mod n nên hiệu của chúng sẽ chia hết cho
n, ax – b = kn, hay ax – kn = b. Mặt khác, do d = (a,n)
nên a và n đều chia hết cho d và
do đó hiệu ax-kn cũng chia hết cho d, thế tức là b phải chia hết cho d. Giả sử b = md tức là
phương trình có nghiệm. Gọi x là
nghiệm nguyên không âm nhỏ nhất của phương trình trên, ta dễ dàng kiểm tra được
rằng x+i(n/d), i = 0,1,…,(d-1) cũng là nghiệm của phương trình đó. Thật vậy, ta để ý rằng nếu d là ước chung lớn nhất của a và n
thì an/d chính là bội chung nhỏ nhất
của chúng, nghĩa là an/d chia hết cho
a và n. Ta có
a(x+i(n/d)) mod n = ((ax mod n) + (i(an)/d) mod n) mod n
= (b mod n + 0) mod
n = b mod n.
Ta chứng minh xong.
Thí dụ 1. Giải phương trình sau
6x mod 9 = 21 mod 9
Phương trình trên tương đương với phương trình sau:
6x mod 9 = 3
Ta có d = (6,9) =
3. Vì 3 là ước của vế phải nên phương trình đã cho có 3 nghiệm. Dễ thấy x = 2 là một nghiệm của phương trình. Vậy
các nghiệm của phương trình dưới dạng tổng quát là
x + i(n/d)
= 2 + i(9/3) = 2 + 3i, i
= 0, 1, 2
Cụ thể là x1
= 2, x2 = 5 và x3 = 8 là 3 nghiệm trong tập
Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}.
Thí dụ 2. Giải phương trình
4x mod 12 = 5
Ta có, d = (4,12) = 4 không phải là ước của 5.
Phương trình vô nghiệm.
Trở lại bài toán
trên, khi gặp tình huống 4 ta có a[b] = 0 và a[n-b] = 1. Xét phương trình bx mod
n = (n-b) mod
n. Vì 1 £ b < n
nên 1 £ n-b < n
và do đó (n-b) mod
n = n-b, phương trình đã cho có thể viết lại là bx mod n = n-b.
Theo tính chất:
ước chung lớn nhất của hai số tự nhiên (a,b)
sẽ không đổi nếu ta thay số lớn nhất trong hai số đó bằng hiệu của nó với số
thứ hai, đặt d = (b,n), ta có d = (b,n-b), tức là n-b chia hết cho d, do đó phương trình bx mod
n = n-b luôn có nghiệm. Từ nhận xét này suy
ra rằng vòng lặp repeat trong đoạn trình dưới đây luôn kết thúc.
u := b;
repeat
v := u;
u := (u+b) mod n;
until
a[u] = 1;
Thật vậy, sau k lần lặp ta thu được u = kb do phương trình bx mod
n = n-b có nghiệm nên sẽ tồn tại một giá trị k để u = kb mod n = n-b. Do a[n-b] = 1 nên tối đa sau k lần lặp thì vòng lặp phải kết thúc và ta sẽ thu được u
= kb mod n. Vì v mang giá trị sát trước của u nên v = (k-1)b
mod n.
Ta có thuật toán sau đây
1. Đọc dữ liệu vào
các biến n, k và s
2. Khởi trị cho mảng
a[1..n-1] với a[i] = 1 nếu quân bài i có trên
tay, a[i] = 0 nếu quân bài i còn trên bàn.
3. Tính t = tổng số
hiệu các quân bài có trên tay.
4. Tính t := t mod
n; s := s mod n.
5. Nếu t ³
s: đặt b := t - s; ngược lại đặt b := n -
(s - t).
Ý nghĩa: cần giảm b đơn vị từ tổng t để đạt hệ thức
t mod n = s mod n (*)
6. Xét các trường
hợp loại trừ nhau sau đây
6.1 b = 0: Đặt m = 0; Thông báo: “Không làm gì”; Stop.
6.2 a[b] = 1 (Quân bài b có trên tay):
Thông
báo: “Thực hiện m = 1 thao tác - b: Bỏ quân bài b”; Stop.
6.3 a[b] = 0 và a[n-b] = 0 (Quân bài b không có trên tay,
quân bài (n-b) có trên bàn):
Thông báo: “Thực
hiện m = 1 thao tác +(n-b): Lấy quân bài (n-b)”; Stop.
6.4 a[b] = 0 và a[n-b] = 1: (Quân bài b không có trên tay,
quân bài (n-b) không có trên bàn)
6.4.1
Tính u và v
u
:= b;
repeat
v := u;
u := (u+b) mod n;
until
a[u] = 1;
6.4.2
Thông báo: “Thực hiện m = 2 thao tác
-u:
Bỏ quân bài u
+v:
Lấy quân bài v.”
6.4.3 Stop
Từ chứng minh
trên ta rút ra độ phức tạp của thuật toán là O(n) vì trong trường hợp xấu nhất
ta duyệt 1 lần mảng a chứa n-1 phần tử.
Tổ chức dữ liệu:
const mn = 10000; {
Max n }
bl = #32; { Dấu cách }
nl = #13#10; { New
line: xuống dòng }
ESC = #27;
fn = 'bai.inp';
type mi1 = array[0..mn] of integer;
var a: mi1; { Dánh dấu các quân bài }
n, k : integer; { n-1: số lượng quân bài }
{ k: số lượng các quân bài trên tay }
t , s: longint; { t: tổng số hiệu các quân bài trên tay }
{ s: số đối chứng của trọng tài }
f: text; { input file }
Thủ tục đọc dữ liệu: Mở input file, đọc các giá trị n, k và
s, đọc số hiệu và đánh dấu k quân bài được chọn. tính tổng t của chúng }
procedure Doc;
var i,j: integer;
begin
assign(f,fn); reset(f);
read(f,n,k,s);
t := 0;
fillchar(a,sizeof(a),0);
for i := 1 to k do
begin
read(f,j); a[j] := 1; t
:= t+j;
end;
close(f);
end;
Thủ tục xử lí.
procedure XuLi;
var b,u,v: integer;
begin
t := t mod n; s := s mod
n;
if t >= s then b :=
t-s else b := n-(s-t);
if (b = 0) then
begin
Ket(0,0,0);
exit
end;
if (a[b] = 1) then
begin { Quan bai b co
tren tay }
Ket(1,-b,0); { bo
xuong }
exit
end;
if (a[n-b] = 0) then
begin { Quan bai n-b co
tren ban }
Ket(1,n-b,0); { Lay
len }
exit
end;
{ Quan bai b khong co
tren tay
Quan bai n-b khong co
tren ban }
u := b;
repeat
v := u;
u := (u+b) mod n;
until (a[u] = 1);
Ket(2,-u,v); { bo u, lay
v }
end;
Thủ tục Ket(m,u,v) thông báo kết quả ứng
với các trường hợp:
m = 1: Bỏ bớt hoạc
lấy thêm 1 quân bài u;
m = 2: Bỏ quân bài u,
lấy quân bài v.
procedure Ket(m,u,v: integer);
begin
case m of
0: write(nl,'Khong lam
gi',nl);
1: begin
write(nl,' Thuc
hien 1 thao tac: ');
if (u > 0) then
write('+',u,nl)
else write(u,nl);
end;
2: begin
write(nl,' Thuc
hien 2 thao tac: ');
if (u > 0) then
write('+',u,bl)
else write(u,bl);
if (v > 0) then
write('+',v,nl)
else write(v,nl);
end;
end;
end;
Độ phức tạp tính
toán: N.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét