bài toán tạo số lớn nhất:

hai6f2009 · 1 Tháng tư 2013

Cho một số gồm n chữ số. hãy tìm cách xoá đi k chữ số để tạo số lớn nhất!
Dữ liệu vào: cho vào file 'NUMBER.INP' gồm:
dòng 1 ghi n và k lần lượt là số chữ số và số chữ số cần xoá (1<=k<n<=500000)
dòng 2 ghi 1 số co n chữ số và không có số 0 ở đầu
Dữ liệu ra: ghi vào file 'NUMBER.OUT' là số lớn nhất sau khi đã xoá k chữ số.
ví dụ
NUMBER.INP
4 2
1924
NUMBER.OUT
94

tung5amkb · 30 Tháng sáu 2013

Uses crt;

Var kq,a: string;
vt,i,n,k,max: integer;
cs: array[1..100] of byte;

BEGIN
Clrscr;
Readln(n,k); Readln(a);
For i:= 1 to n do val(a,cs);
kq:=''; k:= n - k;
While k<>0 do
Begin
max:= 0;
For i:= 1 to n do
If (max<cs) and (n-i+1 >= k) and (vt < i) then
Begin
max:= cs;
vt:= i;
End;
str(max,a);
kq:= kq+a;
dec(k);
End;
Writeln('Ket qua la ',kq);
Readln
END.

megamanxza · 1 Tháng bảy 2013

Bài này thuật toán là xóa đi các chữ số nhỏ nhất!

Mã:

[B][COLOR="Blue"]
Uses crt;
var F: Text;
stchu, st, tg, min: string;
i, j, k, n, code: integer;
begin
clrscr;
assign (F,'NUMBER.inp'); reset (F);
readln (F,st); 
val (st[1],n,code);
val (st[length(st)],k,code);
readln (F,stchu);
close (F);
for i:= 1 to k do
begin
min:=stchu[1];
for j:= 2 to length(stchu) do
if stchu[j]<min then min:=stchu[j];
delete (stchu,POS(min,stchu),1);
end;
assign (F,'NUMBER.out'); rewrite (F);
write (F,stchu);
close (F);
end.[/COLOR][/B]

Good Luck! Nhấn Thanks và Đúng cho mình nha!

thienvamai · 1 Tháng bảy 2013

megamanxza said:

Bài này thuật toán là xóa đi các chữ số nhỏ nhất!

Mã:

[B][COLOR=Blue]
Uses crt;
var F: Text;
stchu, st, tg, min: string;
i, j, k, n, code: integer;
begin
clrscr;
assign (F,'NUMBER.inp'); reset (F);
readln (F,st); 
val (st[1],n,code);
val (st[length(st)],k,code);
readln (F,stchu);
close (F);
for i:= 1 to k do
begin
min:=stchu[1];
for j:= 2 to length(stchu) do
if stchu[j]<min then min:=stchu[j];
delete (stchu,POS(min,stchu),1);
end;
assign (F,'NUMBER.out'); rewrite (F);
write (F,stchu);
close (F);
end.[/COLOR][/B]

Good Luck! Nhấn Thanks và Đúng cho mình nha!

xin lỗi , bạn đã làm sai
test:
5 1
29214

bài của bạn ra 2924
đáp án đúng là 9214

myokicrystal · 1 Tháng bảy 2013

thienvamai said:
xin lỗi , bạn đã làm sai
test:
5 1
29214

bài của bạn ra 2924
đáp án đúng là 9214

Thánh code đã suất hiện :v

bonus bạn xóa các số từ bé đến lớn + từ phải > trái

>-

lamdetien36 · 1 Tháng bảy 2013

Bạn xem thế này có được không

Mã:

var
   st: string;
   N, k, i: integer;
   f: text;
begin
     assign(f, 'NUMBER.INP');
     reset(f);
     readln(f, N, k);
     readln(f, st);
     close(f);

     assign(f, 'NUMBER.OUT');
     rewrite(f);
     repeat
           N := length(st);
     	   for i := 1 to N - 1 do
           begin
             	if st[i] < st[i + 1] then
                begin
                     delete(st, i, 1);
                     break;
                end;
           end;
           if length(st) = N then delete(st, N, 1);
           k := k - 1;
     until k = 0;
     write(f, st);
     close(f);
end.

megamanxza · 1 Tháng bảy 2013

lamdetien36 said:

Bạn xem thế này có được không

Mã:

var
   st: string;
   N, k, i: integer;
   f: text;
begin
     assign(f, 'NUMBER.INP');
     reset(f);
     readln(f, N, k);
     readln(f, st);
     close(f);

     assign(f, 'NUMBER.OUT');
     rewrite(f);
     repeat
           N := length(st);
     	   for i := 1 to N - 1 do
           begin
             	if st[i] < st[i + 1] then
                begin
                     delete(st, i, 1);
                     break;
                end;
           end;
           if length(st) = N then delete(st, N, 1);
           k := k - 1;
     until k = 0;
     write(f, st);
     close(f);
end.

Đây mới gọi là Thánh code bạn myokicrystal ạ! Thuật toán chính xác hơn bài mình nhiều! :khi (24):

cuong276 · 1 Tháng bảy 2013

Sao ở đây ai cũng khai báo n,k ở dạng integer thế nhỉ. Đọc kĩ đề đi, các bạn chưa thử các test lớn à?

hai6f2009 said:
Cho một số gồm n chữ số. hãy tìm cách xoá đi k chữ số để tạo số lớn nhất!
Dữ liệu vào: cho vào file 'NUMBER.INP' gồm:
dòng 1 ghi n và k lần lượt là số chữ số và số chữ số cần xoá (1<=k<n<=500000)
dòng 2 ghi 1 số co n chữ số và không có số 0 ở đầu
Dữ liệu ra: ghi vào file 'NUMBER.OUT' là số lớn nhất sau khi đã xoá k chữ số.
ví dụ
NUMBER.INP
4 2
1924
NUMBER.OUT
94

myokicrystal · 1 Tháng bảy 2013

cuong276 said:
Sao ở đây ai cũng khai báo n,k ở dạng integer thế nhỉ. Đọc kĩ đề đi, các bạn chưa thử các test lớn à?

để mảng char ý bạn ơi =))) để int làm gì cho hại đầu

cuong276 · 1 Tháng bảy 2013

myokicrystal said:
để mảng char ý bạn ơi =))) để int làm gì cho hại đầu

Thế cơ à?
Thế bạn định khai báo n,k ở dạng char hở. Chạy bằng niềm tin và hi vọng hở bạn

lamdetien36 · 1 Tháng bảy 2013

Bạn cho mình xin cái test lớn với. Cóp về cho khỏe chứ ngồi tự viết test ra mệt lắm

.

thienvamai · 1 Tháng bảy 2013

cuong276 said:
Sao ở đây ai cũng khai báo n,k ở dạng integer thế nhỉ. Đọc kĩ đề đi, các bạn chưa thử các test lớn à?

còn tùy trình biên dịch, ở FPC thì integer là số 32 bit , thừa sức chứa mấy số n,k bé tí

lamdetien36 said:

Bạn xem thế này có được không

Mã:

var
   st: string;
   N, k, i: integer;
   f: text;
begin
     assign(f, 'NUMBER.INP');
     reset(f);
     readln(f, N, k);
     readln(f, st);
     close(f);

     assign(f, 'NUMBER.OUT');
     rewrite(f);
     repeat
           N := length(st);
            for i := 1 to N - 1 do
           begin
                 if st[i] < st[i + 1] then
                begin
                     delete(st, i, 1);
                     break;
                end;
           end;
           if length(st) = N then delete(st, N, 1);
           k := k - 1;
     until k = 0;
     write(f, st);
     close(f);
end.

thuật toán thì có vẻ đúng nhưng độ phức tạp thì đừng hỏi vì sao nó ko chạy đc test lớn

mikelhpdatke · 1 Tháng bảy 2013

thienvamai said:
còn tùy trình biên dịch, ở FPC thì integer là số 32 bit , thừa sức chứa mấy số n,k bé tí

thuật toán thì có vẻ đúng nhưng độ phức tạp thì đừng hỏi vì sao nó ko chạy đc test lớn

Thay vì nói thế a đưa ra thuật toán đi

).............................

thienvamai · 1 Tháng bảy 2013

thuật toán chuẩn bài này là O(n+k)
gợi ý: dùng stack
giờ đi ngủ, mai nói :v

lamdetien36 · 2 Tháng bảy 2013

Anh xem thế này có đúng không? Em thử N = 1 triệu, k cỡ 500k thì chưa tới 1.5s

Mã:

var
   st, kq: ansistring;
   max, max1, i, j, n, k: longint;
   f: text;
begin
     assign(f, 'NUMBER.INP');
     reset(f);
     readln(f, N, K);
     readln(f, st);
     close(f);

     assign(f, 'NUMBER.OUT');
     rewrite(f);
     max := 0;
     kq := '';
     max1 := 0;
     for i := 1 to N do if st[i] > st[max1] then max1 := i;
     for i := 1 to n - K do
     begin
          max := max + 1;
     	  for j := max to i + K do
          begin
               if st[j] = st[max1] then
               begin
                    max := j;
                    break;
               end
               else if st[j] > st[max] then max := j;
          end;
          kq := kq + st[max];
     end;
     for i := 1 to n - k do write(f, kq[i]);
     close(f);
end.

myokicrystal · 2 Tháng bảy 2013

cuong276 said:
Thế cơ à?
Thế bạn định khai báo n,k ở dạng char hở. Chạy bằng niềm tin và hi vọng hở bạn

không có gì là không làm được. kể cả để hết là char *xin lỗi nhưng mình dùng C++, không biết pascal nhiều lắm*

thienvamai · 2 Tháng bảy 2013

lamdetien36 said:

Anh xem thế này có đúng không? Em thử N = 1 triệu, k cỡ 500k thì chưa tới 1.5s

Mã:

var
   st, kq: ansistring;
   max, max1, i, j, n, k: longint;
   f: text;
begin
     assign(f, 'NUMBER.INP');
     reset(f);
     readln(f, N, K);
     readln(f, st);
     close(f);

     assign(f, 'NUMBER.OUT');
     rewrite(f);
     max := 0;
     kq := '';
     max1 := 0;
     for i := 1 to N do if st[i] > st[max1] then max1 := i;
     for i := 1 to n - K do
     begin
          max := max + 1;
           for j := max to i + K do
          begin
               if st[j] = st[max1] then
               begin
                    max := j;
                    break;
               end
               else if st[j] > st[max] then max := j;
          end;
          kq := kq + st[max];
     end;
     for i := 1 to n - k do write(f, kq[i]);
     close(f);
end.

thử test chạy input này đi

https://docs.google.com/file/d/0B0AoSRWk1U3YRm44ZktQREktc2c/edit?usp=sharing

lamdetien36 · 2 Tháng bảy 2013

Bài này em mới chế thuật toán khi sang rồi code luôn

. Từ từ rồi em cải tiến thuật toán sau. Mà hiện tại thì chạy test random cũng nhanh mà. Còn test anh đưa thì :|. Mà anh cho em mấy cái test luôn để em về thử

cuong276 · 2 Tháng bảy 2013

This is my bài làm

Mã:

var     st:string;
        n,k,i,j:longint;
        f,g:text;
BEGIN
        assign(f,'number.inp');reset(f);
        readln(f,n,k);
        readln(f,st);
        close(f);
        assign(g,'number.out'); rewrite(g);
        i:=1;
        j:=1;
        while j<=k do
                begin
                        if st[i]<=st[i+1] then
                                begin
                                        delete(st,i,1);
                                        inc(j);
                                end
                        else inc(i);
                end;
        write(g,st);
        close(g);
END.

thienvamai · 2 Tháng bảy 2013

cuong276 said:

This is my bài làm

Mã:

var     st:string;
        n,k,i,j:longint;
        f,g:text;
BEGIN
        assign(f,'number.inp');reset(f);
        readln(f,n,k);
        readln(f,st);
        close(f);
        assign(g,'number.out'); rewrite(g);
        i:=1;
        j:=1;
        while j<=k do
                begin
                        if st[i]<=st[i+1] then
                                begin
                                        delete(st,i,1);
                                        inc(j);
                                end
                        else inc(i);
                end;
        write(g,st);
        close(g);
END.

về cơ bản thuật toán là đúng nhưng vẫn cần sửa lại, bạn cần xét trường hợp đầy đủ vì những test sau bạn vẫn sai:
4 1
1102
và
4 1
4321

p.s: thuật toán của mình như sau: có 1 stack s, khi xét tới chữ số a nếu a > đỉnh stack và k>0 thì pop đỉnh stack và giảm k đi 1 lặp lại đến khi nào stack rỗng, hoặc a<=đỉnh stack hoặc k<=0;
đến cuối nếu k>0 thì xóa k phần tử cuối stack
sau đó in các phần tử trong stack ra theo thứ tự cho vào stack

Tìm kiếm

Tìm kiếm

bài toán tạo số lớn nhất:

hai6f2009

tung5amkb

megamanxza

thienvamai

myokicrystal

lamdetien36

megamanxza

cuong276

myokicrystal

cuong276

lamdetien36

thienvamai

mikelhpdatke

thienvamai

lamdetien36

myokicrystal

thienvamai

lamdetien36

cuong276

thienvamai