4.4 Cân Olimpic các nước vùng Baltic, 2004 Người ta cần cân một vật có khối lượng là một số tự nhiên n gam bằng một bộ quả cân khối lượng 1, 3, 9, ..., 3k, ... gam, k = 0, 1, 2, ... , mỗi loại có đúng một quả cân. Vật cần cân được đặt trên đĩa trái. Hãy chọn các quả cân đặt trên hai đĩa để cân thăng bằng.
can.inp | can.out | Giải thích Input text file: số n; 1 n 1000000000 (1 tỷ). Output text file: 2 dòng Dòng 1: số quả cân đặt trên đĩa trái, tiếp đến là các quả cân cụ thể. Dòng 2: số quả cân đặt trên đĩa phải, tiếp đến là các quả cân cụ thể. Thí dụ, với khối lượng vật cân n = 69 g đặt trên đĩa trái, ta cần đặt thêm 2 quả cân trên đĩa trái là 3 và 9g; 1 quả cân trên đĩa phải là 81 g. Ta có: 69 + 3 + 9 = 81. | 69 | 2 3 9 1 81 |
|
Thuật toán
Đầu tiên ta tạm giả thiết là số lượng quả cân mỗi loại là đủ nhiều để có thể cân mọi khối lượng trong giới hạn cho trước. Khi đó ta biểu diễn n dưới dạng hệ đếm 3 rồi đặt vật cần cân trên đĩa trái và đặt các quả cân tương ứng trên đĩa phải. Để biểu diễn n dưới dạng hệ b tùy ý ta chia liên tiếp n cho b và ghi nhận các số dư. Trong các phiên bản dưới đây p là mảng nguyên chứa các chữ số trong dạng biểu diễn ngược của số n dưới dạng hệ đếm b, đầu ra của các hàm ToBase là số chữ số trong dạng biểu diễn đó. type mi1 = array[0..30] of integer;
(* Pascal *)
function ToBase(n: longint; b: integer; var p: mi1): longint;
var i: longint;
begin
fillchar(p, sizeof(p),0);
i := 0;
repeat
p[i] := n mod b;
n := n div b;
inc(i);
until n = 0;
ToBase := i;
end;
// DevC++
int ToBase(int n, int b, int *p) {
int i = 0;
memset(p, 0, sizeof(p));
do {
p[i++] = n % b;
n /= b;
} while (n != 0);
return i;
}
Để tiện lập luận ta tạm qui ước gọi quả cân 3i là quả cân loại i, tức là ta gọi theo số mũ của hệ số 3. Với thí dụ dã cho n = 69, lời gọi k = ToBase(69, 3, phai) sẽ cho k = 4 và mảng phai[0..3] = (0, 2, 1, 2) chính là các chữ số hệ đếm 3 trong dạng biểu diễn của số 69. Cụ thể là số 69 được biểu diễn ngược trong hệ đếm 3 sẽ là một số gồm k = 4 chữ số lần lượt tính từ chữ số hàng đơn là 0, 2, 1 và 2, cụ thể là: 69 = 0.30 + 2.31 + 1.32 + 2.33 = 21203.
Loại quả cân | 0 (30=1) | 1 (31=3) | 2 (32=9) | 3 (33=27) | 4 (34=81) | Vật cần cân khối lượng n = 69 được đặt trên đĩa trái. Trên đĩa phải đặt 3 quả cân: phai[1] = 2 quả cân loại 1, 2.31 = 6 g, phai[2] = 1 quả cân loại 2, 1.32 = 9 g, phai[3] = 2 quả cân loại 3, 2.33 = 2.27 = 54 g, 69 = 6 + 9 + 54. Đĩa trái tạm thời để trống | Đĩa trái (69+...) | 0 | 0 | 0 | 0 | 0 | Đĩa phải | 0 | 2 | 1 | 2 | 0 |
Vì mỗi loại quả cân chỉ có đúng 1 quả nên ta cần tìm cách thay 2 quả cân cùng loại i bằng tổ hợp khác. Ta có 2.3i = 3.3i – 3i = 3i+1 3i. Hệ thức trên cho ta thấy rằng có thể thay 2 quả cân loại i ở đĩa cân phải bằng cách đặt 1 quả cân loại i+1 trên đĩa phải và 1 quả cân loại i trên đĩa trái. Với thí dụ đã cho, phai[1] = 2 nên ta thay 2 quả cân loại 1 bằng 1 quả cân loại 2 trên đĩa phải và 1 quả cân loại 1 trên đĩa trái. Vì trên đĩa phải đã có sẵn 1 quả cân loại 2 nên số quả cân loại này sẽ được tăng thêm 1 và bằng 2. Ta thu được:
Loại quả cân | 0 (30=1) | 1 (31=3) | 2 (32=9) | 3 (33=27) | 4 (34=81) | phai = (0,2,1,2) (0,0,2,2); trai = (0,1,0,0). Đĩa trái (69 g)+1 quả cân loại 1 = 69 + 3 = 72g; Đĩa phải: 2 quả cân loại 2 + 2 quả cân loại 3 = 2.32+2.33 = 2.9 + 2.27 = 18 + 54 = 72g.
| Đĩa trái (69+...) | 0 | 1 | 0 | 0 | 0 | Đĩa phải | 0 | 0 | 2 | 2 | 0 |
Lại thức hiện phép thay 2 quả cân loại 2 trên đĩa phải bằng 1 quả cân loại 2 trên đĩa phải và 1 quả cân loại 3 trên đĩa trái ta thu được:
Loại quả cân | 0 (30=1) | 1 (31=3) | 2 (32=9) | 3 (33=27) | 4 (34=81) | phai = (0,0,2,2) (0,0,0,3); trai = (0,1,1,0). Đĩa trái (69g) + 1 quả cân loại 1 + 1 quả cân loại 2 = 69 + 1.31 + 1.32 = 69 + 3 + 9 = 81 g; Đĩa phải: 3 quả cân loại 3 = 3.27 = 81 g.
| Đĩa trái (69+...) | 0 | 1 | 1 | 0 | 0 | Đĩa phải | 0 | 0 | 0 | 3 | 0 |
Cuối cùng ta thay 3 quả cân loại 3 trên đĩa phải bằng 1 quả cân loại 4 là hoàn tất. phai = (0,0,0,3) (0,0,0,0,1). trai = (0,1,1,0). Kết quả ta thu được: Để cân vật n = 69 g ta đặt vật đó trên đĩa trái và Đặt tiếp trên đĩa trái 2 quả cân 3 và 9 g; Đặt trên đĩa phải 1 quả cân 81 g. Tổng hợp lại ta có thuật toán Replace thực hiện phép thay các quả cân loại i trên đĩa phải như sau: Nếu trên đĩa phải có 2 quả cân loại i thì thay bằng 1 quả loại i+1 trên đĩa phải và 1 quả loại i trên đĩa trái; Nếu trên đĩa phải có 3 quả cân loại i thì thay bằng 1 quả loại i+1 trên đĩa phải. Hàm Replace nhận vào là dãy k quả cân trên đĩa phải p[0..k1], cho ra dãy m quả cản trên đĩa trái t[0..m1]:
(* Pascal *)
function Replace(var p: mi1; var k: integer; var t: mi1): longint;
var m, i: longint;
begin
fillchar(t, sizeof(t),0);
for i := 0 to k do
if p[i] = 3 then begin p[i] := 0; inc(p[i+1]) end
else if p[i] = 2 then
begin p[i] := 0; inc(p[i+1]); inc(t[i]) end;
m := k;
if p[k] > 0 then inc(k);
Replace := m;
end;
// DevC++
int Replace(int * p, int &k, int * t) {
int i, m;
memset(t, 0, sizeof(t));
for (i = 0; i < k; ++i)
if (p[i] == 3) { p[i] = 0; ++p[i+1]; }
else if (p[i] == 2) { p[i] = 0; ++p[i+1]; ++t[i]; }
m = k;
if (p[k] > 0) ++k;
return m;
}
Trước khi ghi file chúng ta cần thu dọn sơ bộ dữ liệu. Ta duyệt các phần tử của hai dãy trái và phải để đếm xem có bao nhiêu quả cân và qui các loại quả cân đó thành giá trị cụ thể, tức là thay vì viết i ta phải viết 3i.
(* can.pas *)
uses crt;
const fn = 'can.inp'; gn = 'can.out';
mn = 30; bl = #32; nl = #13#10;
type mi1 = array[0..mn] of longint;
function Doc: longint;
var n: longint;
f: text;
begin
assign(f,fn); reset(f);
readln(f,n); close(f);
Doc := n;
end;
function ToBase(n: longint; b: longint; var p: mi1): longint;
var i: longint;
begin
fillchar(p, sizeof(p),0);
i := 0;
repeat
p[i] := n mod b;
n := n div b;
inc(i);
until n = 0;
ToBase := i;
end;
function Replace(var p: mi1; var k: longint; var t: mi1): longint;
var m, i: longint;
begin
fillchar(t, sizeof(t),0);
for i := 0 to k do
if p[i] = 3 then begin p[i] := 0; inc(p[i+1]) end
else if p[i] = 2 then
begin p[i] := 0; inc(p[i+1]); t[i] := 1 end;
m := k;
if p[k] > 0 then inc(k);
Replace := m;
end;
procedure Ghi(var t: mi1; dt: longint; var p: mi1; dp: longint);
var i, v, nt, np: longint;
g: text;
begin
v := 1; nt := 0;
for i := 0 to dt-1 do
begin
if t[i] > 0 then begin inc(nt); t[i] := v; end;
v := v * 3;
end;
v := 1; np := 0;
for i := 0 to dp-1 do
begin
if p[i] > 0 then begin inc(np); p[i] := v; end;
v := v * 3;
end;
assign(g,gn); rewrite(g);
write(g,nt,bl);
for i := 0 to dt-1 do
if t[i] > 0 then write(g,t[i],bl);
write(g,nl,np,bl);
for i := 0 to dp-1 do
if p[i] > 0 then write(g,p[i],bl);
close(g);
end;
procedure Run;
var trai, phai: mi1;
n, dt, dp: longint;
begin
n := Doc;
dp := ToBase(n,3,phai);
dt := Replace(phai, dp, trai);
Ghi(trai,dt,phai,dp);
end;
BEGIN
Run;
write(nl,' Fini');
readln;
END.
// Devcpp Can.cpp
#include
#include
using namespace std;
// D A T A A N D V A R I A B L E
const char * fn = "CAN.INP";
const char * gn = "CAN.OUT";
// P R O T O T Y P E S
int main();
int Doc();
void Ghi(int *t, int n, int *p, int m);
int ToBase(int n, int b, int *p);
int Replace(int *p, int &n, int *t);
void Run();
// I M P L E M E N T A T I O N
int main() {
Run();
cout << endl << endl << " Fini ";
cin.get();
return 0;
}
void Run() {
const int mn = 20;
int phai[mn], trai[mn];
int dp, dt, n;
n = Doc();
dp = ToBase(n, 3, phai);
dt = Replace(phai, dp, trai);
Ghi(trai,dt,phai,dp);
}
int Doc() {
int n;
ifstream f(fn);
f >> n;
f.close();
return n;
}
void Ghi(int *t, int dt, int *p, int dp) {
int i, v, nt, np;//dt,dp: so qua can tren dia trai va phai
nt = np = 0;
for (v = 1,i = 0; i < dt; ++i, v*= 3)
if (t[i] > 0) { ++nt; t[i] = v; }
for (v = 1,i = 0; i < dp; ++i, v*= 3)
if (p[i] > 0) { ++np; p[i] = v; }
ofstream g(gn);
g << nt << " ";
for (i = 0; i < dt; ++i)
if (t[i] > 0) g << t[i] << " ";
g << endl << np << " ";
for (i = 0; i < dp; ++i)
if (p[i] > 0) g << p[i] << " ";
g.close();
}
// Bieu dien so n qua he b
// return i - chieu dai so trong he b
// n = p[0].b^0 + p[1].b^1 + ... + p[i].bi
int ToBase(int n, int b, int *p) {
int i = 0;
memset(p, 0, sizeof(p));
do {
p[i++] = n % b;
n /= b;
} while (n != 0);
return i;
}
int Replace(int * p, int &k, int * t) {
int i, m;
memset(t, 0, sizeof(t));
for (i = 0; i < k; ++i)
if (p[i] == 3) { p[i] = 0; ++p[i+1]; }
else if (p[i] == 2) { p[i] = 0; ++p[i+1]; ++t[i]; }
m = k;
if (p[k] > 0) ++k;
return m;
}
Độ phức tạp: cỡ log3(n); trong đó log3(n) + 1 là số chữ số trong dạng biểu diễn của n theo hệ đếm 3.
Chia sẻ với bạn bè của bạn: |