Bài Toán Tạo Số Lớn Nhất: | Cộng đồng Học Sinh Việt Nam

• Diễn đàn Bài viết mới Tìm kiếm trên diễn đàn
• Đăng bài nhanh
• Có gì mới? Bài viết mới New media New media comments Status mới Hoạt động mới
• Thư viện ảnh New media New comments Search media
• Story
• Thành viên Đang truy cập Đăng trạng thái mới Tìm kiếm status cá nhân

Đăng nhập Đăng ký

Tìm kiếm

Everywhere Đề tài thảo luận This forum This thread Chỉ tìm trong tiêu đề By: Search Tìm nâng cao… Everywhere Đề tài thảo luận This forum This thread Chỉ tìm trong tiêu đề By: Search Advanced…

• Bài viết mới
• Tìm kiếm trên diễn đàn

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

• Thread starter hai6f2009
• Ngày gửi 1 Tháng tư 2013
• Replies 36
• Views 16,424

• Bạn có 1 Tin nhắn và 1 Thông báo mới. [Xem hướng dẫn] để sử dụng diễn đàn tốt hơn trên điện thoại

• Diễn đàn
• CÁC MÔN HỌC KHÁC
• Tin học - máy tính
• Học lập trình
• Thảo luận chung

You are using an out of date browser. It may not display this or other websites correctly.You should upgrade or use an alternative browser.

• 1
• 2

Tiếp 1 of 2

Go to page

Tới Tiếp Last H

hai6f2009

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

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 T

tung5amkb

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. M

megamanxza

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! T

thienvamai

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! Bấm để xem đầy đủ nội dung ...

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 Last edited by a moderator: 1 Tháng bảy 2013 M

myokicrystal

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 Bấm để xem đầy đủ nội dung ...

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 &gt;- L

lamdetien36

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. M

megamanxza

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. Bấm để xem đầy đủ nội dung ...

Đâ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): C

cuong276

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 Bấm để xem đầy đủ nội dung ...

M

myokicrystal

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 à? Bấm để xem đầy đủ nội dung ...

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

cuong276

myokicrystal said: để mảng char ý bạn ơi =))) để int làm gì cho hại đầu Bấm để xem đầy đủ nội dung ...

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 L

lamdetien36

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 . T

thienvamai

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 à? Bấm để xem đầy đủ nội dung ...

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. Bấm để xem đầy đủ nội dung ...

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 M

mikelhpdatke

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 Bấm để xem đầy đủ nội dung ...

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

thienvamai

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 L

lamdetien36

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. Last edited by a moderator: 2 Tháng bảy 2013 M

myokicrystal

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 Bấm để xem đầy đủ nội dung ...

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* T

thienvamai

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. Bấm để xem đầy đủ nội dung ...

thử test chạy input này đi https://docs.google.com/file/d/0B0AoSRWk1U3YRm44ZktQREktc2c/edit?usp=sharing L

lamdetien36

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ử Last edited by a moderator: 2 Tháng bảy 2013 C

cuong276

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. T

thienvamai

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. Bấm để xem đầy đủ nội dung ...

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 Last edited by a moderator: 2 Tháng bảy 2013

• 1
• 2

Tiếp 1 of 2

Go to page

Tới Tiếp Last You must log in or register to reply here. Chia sẻ: Facebook Reddit Pinterest Tumblr WhatsApp Email Chia sẻ Link

• Diễn đàn
• CÁC MÔN HỌC KHÁC
• Tin học - máy tính
• Học lập trình
• Thảo luận chung

Top Bottom

• Vui lòng cài đặt tỷ lệ % hiển thị từ 85-90% ở trình duyệt trên máy tính để sử dụng diễn đàn được tốt hơn.