Về các phép biến đổi "Nhân 2 trừ 1"

Bài 67/2001 - Về các phép biến đổi "Nhân 2 trừ 1" 
(Dành cho học sinh THCS và PTTH)
Để biến đổi ma trận A thành 0, ta biến đổi từng cột thành 0 
Xét một cột bất kì có n số a1, ..., an (ai >= 0) 
Đặt X = max(a1, ..., an).
 - Bước 1:
 + Nếu dãy a1, ..., an có một số 0 và một số khác 0, dừng ở đây vì không thể đưa A về 0; 
- Bước 2: 
 + Nếu dãy a1, ..., an có ai = 0 (i = 1..n) thì cột này đã được biến đổi xong, qua cột tiếp theo, 
 + Nếu không thì ai = 2ai nếu 2ai <= X (nhân hàng có chứa số ai lên 2), tiếp tục thực hiện đến khi không nhân được nữa, qua bước 3; 
 - Bước 3: 
	X:= X-1;
	ai:= ai-1;
Quay lại bước 2. 
Đây không phải là lời giải tốt ưu nhưng rất đơn giản, dễ dàng cài đặt (việc viết chương trình tương đối đơn giản)
Nhận xét: Bài này thực sự dễ nếu chỉ dừng lại ở mức tìm thuật toán? Nếu đặt lại điều kiện là có thể nhân hàng, cột cho 2, trừ hàng, cột cho 1, tìm lời giải tối ưu với giới hạn của M, N thì hay hơn nhiều.
(Lời giải của bạn Vũ Lê An - Lớp 11T2 - Lê Khiết - Quảng Ngãi) 
Thuật toán của bạn Vũ Lê An rất đúng. Song trên thực tế thuật toán này còn một điểm chưa chuẩn vì nếu các số của mảng số thì nhỏ, số thì lớn thì thuật toán này mất rất nhiều bước. Việc nhân có thể gây ra tràn số.
Ví dụ:
2 3
1 100 1
100 1 100
số bước sẽ rất lớn.
Nhưng thuật toán này trên lý thuyết là giải được. Chương trình theo thuật toán trên.
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
program bai67_bien_doi_mang; {Author : Nguyen Van Chung}
uses crt;
const max =100;
 fi ='bai67.inp';
 fo ='bai67.out';
var a :array[1..max,1..max]of longint;
 m,n :integer;
procedure docf;
var f :text;
 i,j :integer;
 begin
 assign(f,fi);
 reset(f);
 read(f,m,n);
 for i:=1 to m do
 for j:=1 to n do read(f,a[i,j]);
 close(f);
 end;
procedure lam;
var f :text;
 i,j,ma,mi,k :longint;
 begin
 assign(f,fo);
 rewrite(f);
 for j:=1 to n do
 begin
 ma:=0;mi:=maxlongint;
 for i:=1 to m do
 begin
 if a[i,j]>ma then ma:=a[i,j];
 if a[i,j]<mi then mi:=a[i,j];
 end;
 if (ma>0)and(mi=0) then
 begin
 rewrite(f);
 writeln(f,'No solution');
 break;
 end;
 repeat
 for i:=1 to m do
 begin
 while a[i,j]*2<=ma do
 begin
 for k:=1 to n do a[i,k]:=a[i,k]*2;
 writeln(f,'nhan 2 dong :',i);
 end;
 a[i,j]:=a[i,j]-1;
 end;
 dec(ma);
 writeln(f,'tru 1 cot :',j);
 until ma=0;
 end;
 close(f);
 end;
BEGIN
 docf;
 lam;
END.