Thông Báo:

Mọi thắc mắc xin liên hệ facebook: Bá Sơn
fb.com/sonden2000

Bài tập về sắp xếp có lời giải.

Posted by : Unknown Wednesday, March 15, 2017

                                                         BÀI TẬP VỀ SẮP XẾP.
1.NUMCON - Ghép số lớn
Vaxia đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với anh trai Petia về thành quả vừa đạt được. Tuy nhiên,  khi Vaxia vừa ra khỏi phòng để gọi anh trai thì cô em Kachia chạy vào phòng và xé rách cuộn giấy thành một số mảnh. Kết quả là trên mỗi mảnh có một hoặc vài kí số theo thứ tự đã viết.
Bây giờ Vaxia không thể nhớ chính xác mình đã viết số gì. Vaxia chỉ nhớ rằng đó là một số rất lớn.
Để làm hài lòng cậu em trai, Petia quyết định truy tìm  số nào là lớn nhất mà Vaxia đã có thể viết lên cuộn giây trước khi bị xé. Bạn hãy giúp Petia làm việc này.
Dữ liệu vào:
Ghi một hoặc nhiều dòng. Mỗi dòng ghi một dãy kí số. Số dòng không vượt quá 100. Mỗi dòng ghi từ 1 đến 100 kí số. Bảo đảm rằng có ít nhất một dòng mà kí số đầu tiên khác 0.
Dữ liệu ra:
Ghi ra số lớn nhất đã có thể viết trên cuộn giấy trước khi bị xé rách.
Ví dụ
Input
Output
2
20
004
66
66220004
3
3
HƯỚNG DẪN:
•  Lấy tư tưởng Quick Sort, ta tiến hành thêm vào đuôi số đó chữ số đầu tiên của nó cho đến khi có độ dài bằng với số có độ dài lớn nhất. Khi này các số có độ dài bằng nhau ta tiến hành sắp xếp chúng giảm dần rồi ghi ra. Với mỗi số ta chỉ ghi m chữ số đầu tiên với m là độ dài ban đầu của nó.
/// code tham khảo:
  1. Program NUMCON;
  2. Var
  3. n :Byte;
  4. A :Array[1..101] of String[100];
  5.  
  6. procedure Enter;
  7. begin
  8. n:=0;
  9. while not EoF do
  10. begin
  11. Inc(n); ReadLn(A[n]);
  12. end;
  13. end;
  14.  
  15. procedure Swap(i,j :Byte);
  16. var
  17. tmp :String[100];
  18. begin
  19. tmp:=A[i]; A[i]:=A[j]; A[j]:=tmp;
  20. end;
  21.  
  22. procedure Greedy;
  23. var
  24. i,j :Byte;
  25. begin
  26. for i:=1 to n-1 do
  27. for j:=i+1 to n do
  28. if (A[i]+A[j]<A[j]+A[i]) then Swap(i,j);
  29. end;
  30.  
  31. procedure Escape;
  32. var
  33. i :Byte;
  34. begin
  35. for i:=1 to n do Write(A[i]);
  36. end;
  37.  
  38. Begin
  39. Assign(Input,''); Reset(Input);
  40. Assign(Output,''); Rewrite(Output);
  41. Enter;
  42. Greedy;
  43. Escape;
  44. Close(Input); Close(Output);
  45. End.
2.

INSUL - Cách nhiệt
Cho một dãy N viên gạch lần lượt có độ cách nhiệt là các số a1.. aN. Nếu xếp lần lượt các viên gạch theo trình tự đó thì độ cách nhiệt cả khối là a1 + a2 + ... + aN + max(0, a2 - a1) + max(0, a3 - a2) + ... + max(0, aN - aN - 1). Nhiệm vụ của bạn là tìm cách xếp sao cho độ cách nhiệt của cả khối là lớn nhất có thể.

Dữ liệu

  • Dòng đầu ghi số nguyên dương N (0 < n ≤ 10^5).
  • N dòng sau mỗi dòng ghi một số ai ( 1 ≤ i ≤ N và 1 ≤ ai ≤ 10000).

Kết qủa

Ghi trên một dòng kết quả cần tìm.

Ví dụ

 
Dữ liệu: 
4
5
4
1
7
Kết qủa 
24

CODE:
  1. Program INSUL;
  2. Var
  3. n,res :LongInt;
  4. A :Array[1..100000] of LongInt;
  5.  
  6. procedure Enter;
  7. var
  8. i :LongInt;
  9. begin
  10. ReadLn(n); res:=0;
  11. for i:=1 to n do
  12. begin
  13. ReadLn(A[i]); res:=res+A[i];
  14. end;
  15. end;
  16.  
  17. procedure Swap(i,j :LongInt);
  18. var
  19. tmp :Integer;
  20. begin
  21. tmp:=A[i]; A[i]:=A[j]; A[j]:=tmp;
  22. end;
  23.  
  24. procedure Sort(l,h :LongInt);
  25. var
  26. i,j,k :LongInt;
  27. begin
  28. if (l>=h) then Exit;
  29. i:=l; j:=h; k:=A[(l+h) div 2];
  30. repeat
  31. while (A[i]<k) do Inc(i);
  32. while (A[j]>k) do Dec(j);
  33. if (i<=j) then
  34. begin
  35. if (i<j) then Swap(i,j);
  36. Inc(i); Dec(j);
  37. end;
  38. until (i>j);
  39. Sort(l,j); Sort(i,h);
  40. end;
  41.  
  42. procedure Greedy;
  43. var
  44. i,j :LongInt;
  45. begin
  46. i:=1; j:=n;
  47. while (i<j) do
  48. begin
  49. res:=res+A[j]-A[i];
  50. Inc(i); Dec(j);
  51. end;
  52. end;
  53.  
  54. Begin
  55. Assign(Input,''); Reset(Input);
  56. Assign(Output,''); Rewrite(Output);
  57. Enter;
  58. Sort(1,n);
  59. Greedy;
  60. Write(res);
  61. Close(Input); Close(Output);
  62. End.

NOIXICH - Nối Xích
Người ta có N đoạn dây xích(N <= 20000), mỗi đoạn dây xích là chuỗi các mắt xích được nối với nhau. Các đoạn dây xích này tách rời nhau. Mỗi đoạn mắt xích có không quá 20000 mắt xích. Bằng cách cắt ra một mắt xích, sau đó hàn lại, ta có thể nối hai dây xích thành một đoạn. Thời gian để cắt và hàn mỗi mắt xích là 1 đơn vị thời gian và được xem là bằng nhau với mọi mắt xích. Nhiêm vụ của bạn là phải nối chúng lại thành một đoạn dây xích duy nhất với thời gian ít nhất( hay số mắt xích bị cắt và hàn lại là ít nhất).

Input

Dữ liệu vào cho trong file văn bản có cấu trúc như sau: Dòng đầu tiên là số N, số đoạn xích. Những dòng tiếp theo ghi N số nguyên dương, số thứ i là số mắt xích có trong đoạn xích thứ i(i <= i <= N) Hai số cạnh nhau trên cùng một dòng cách nhau ít nhất một dấu cách.

Output

Một dòng duy nhất là số đơn vị thời gian mà bạn cần để nối N đoạn xích đã cho.

Example

Input:
3
2 3
4
 
Output:
2
Hướng dẫn thuật toán: – Sắp xếp số đoạn xích tăng dần.
– Luôn xử lý các đoạn xích có độ dài bằng 1 theo cách chặt ra rồi đem đi nối 2 đoạn xích khác.
– Xử lý chặt từ đoạn xích ngắn nhất, tăng dần khi không còn đoạn xích ngắn hơn. Chặt các đoạn xích ngắn (có độ dài lớn hơn 1) theo cách chặt dần mắt xích của nó đem đi nối các đoạn xích khác, cho tới khi nó có độ dài là 1.
– Việc chặt-hàn dừng lại khi số đoạn xích chỉ còn 1.
Code tham khảo:
  1. Program NOIXICH;
  2. Var
  3. n,m :Integer;
  4. A :Array[1..20000] of Integer;
  5.  
  6. procedure Enter;
  7. var
  8. i :Integer;
  9. begin
  10. ReadLn(n); i:=0;
  11. while not EoF do
  12. while not EoLn do
  13. begin
  14. Inc(i); Read(A[i]);
  15. end;
  16. end;
  17.  
  18. procedure Swap(i,j :Integer);
  19. var
  20. tmp :Integer;
  21. begin
  22. tmp:=A[i]; A[i]:=A[j]; A[j]:=tmp;
  23. end;
  24.  
  25. procedure Sort(l,h :Integer);
  26. var
  27. i,j,k :Integer;
  28. begin
  29. if (l>=h) then Exit;
  30. i:=l; j:=h; k:=A[(l+h) div 2];
  31. repeat
  32. while (A[i]<k) do Inc(i);
  33. while (A[j]>k) do Dec(j);
  34. if (i<=j) then
  35. begin
  36. if (i<j) then Swap(i,j);
  37. Inc(i); Dec(j);
  38. end;
  39. until (i>j);
  40. Sort(l,j); Sort(i,h);
  41. end;
  42.  
  43. procedure Solve;
  44. var
  45. i :Integer;
  46. begin
  47. i:=1; m:=0;
  48. while (n>1) do
  49. begin
  50. if (A[i]>n-1) then Break;
  51. m:=m+A[i];
  52. Dec(n,A[i]+1);
  53. Inc(i);
  54. end;
  55. m:=m+n-1;
  56. end;
  57.  
  58. Begin
  59. Assign(Input,''); Reset(Input);
  60. Assign(Output,''); Rewrite(Output);
  61. Enter;
  62. Sort(1,n);
  63. Solve;
  64. Write(m);
  65. Close(Input); Close(Output);
  66. End.
BWPOINTS - VOI 2011 Nối điểm đen trắng
Trên trục số thực cho n điểm đen và n điểm trắng hoàn toàn phân biệt. Các điểm đen có tọa độ nguyên a1, a2, …, an còn các điểm trắng có tọa độ nguyên b1, b2, …, bn. Người ta muốn chọn ra k điểm đen và k điểm trắng để nối mỗi một điểm đen với một điểm trắng sao cho k đoạn thẳng tạo được đôi một không có điểm chung.
Yêu cầu: Cho tọa độ của n điểm đen a1, a2, …, an và tọa độ của điểm trắng b1, b2, …, bn. Hãy tìm giá trị k lớn nhất thỏa mãn yêu cầu trên.
Dữ liệu:
  • Dòng thứ nhất chứa số nguyên dương n (n <= 10^5).  
  • Dòng thứ hai chứa các số a1, a2, …, an (|ai| <= 10^9, i = 1, 2,…, n)
  • Dòng thứ ba chứa các số b1, b2, …, bn (|bi| <= 10^9, i = 1, 2,…, n)
      Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra một số nguyên duy nhất là số k lớn nhất tìm được
Ví dụ:
Dữ liệu
Kết quả
3
0 3 1
-3 5 -1
2




Description: http://vn.spoj.com/content/voj:BWPOINTS.png
Ràng buộc: 50% số test ứng với 50% số điểm của bài có 1 <= n <= 100
CODE THAM KHẢO:
  1. type
  2. arr1 = array[1..200001] of longint;
  3. var
  4. fi,fo : text;
  5. n,res,nhoa,nhob:longint;
  6. a:arr1;
  7. b,vt:arr1;
  8. {------------------------------------------------------------------------}
  9. procedure nhap;
  10. var i,j:longint;
  11. begin
  12. readln(n);
  13. for i:=1 to n do
  14. read(a[i]);
  15. readln;
  16. for i:=1 to n do
  17. read(b[i]);
  18. end;
  19. {------------------------------------------------------------------------}
  20. procedure khoitao;
  21. var i,j:longint;
  22. begin
  23. res:=0;
  24. fillchar(vt,sizeof(vt),0);
  25. end;
  26. {------------------------------------------------------------------------}
  27. procedure doicho(var x,y:longint);
  28. var tg:longint;
  29. begin
  30. tg:=x;
  31. x:=y;
  32. y:=tg;
  33. end;
  34. {------------------------------------------------------------------------}
  35. procedure sort(l,r:longint);
  36. var i,j,mid:longint;
  37. begin
  38. i:=l;
  39. j:=r;
  40. mid:=a[(l+r)div 2 ];
  41. repeat
  42. while a[i]<mid do inc(i);
  43. while a[j]>mid do dec(j);
  44. if i<=j then
  45. begin
  46. doicho(a[i],a[j]);
  47. doicho(vt[i],vt[j]);
  48. inc(i);
  49. dec(j);
  50. end;
  51. until i>j;
  52. if l<j then sort(l,j);
  53. if i<r then sort(i,r);
  54. end;
  55. {------------------------------------------------------------------------}
  56. {------------------------------------------------------------------------}
  57. procedure xuly;
  58. var i,j,tg:longint;
  59. begin
  60. for i:=n+1 to n*2 do
  61. begin
  62. a[i]:=b[i-n];
  63. vt[i]:=1;
  64. end;
  65. sort(1,n*2);
  66. i:=1;
  67. while i<2*n do
  68. begin
  69. if vt[i]<>vt[i+1] then
  70. begin
  71. inc(res);
  72. i:=i+2;
  73. end
  74. else inc(i);
  75. end;
  76. end;
  77. {------------------------------------------------------------------------}
  78. procedure inkq;
  79. begin
  80. write(res);
  81. readln;
  82. end;
  83. {------------------------------------------------------------------------}
  84. {------------------------------------------------------------------------}
  85. {------------------------------------------------------------------------}
  86. {------------------------------------------------------------------------}
  87. BEGIN
  88. nhap;
  89. khoitao;
  90. xuly;
  91. inkq;
  92. END.

NKSGAME - VOI08 Trò chơi với dãy số
Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:
b1, b2, ..., bn
còn dãy số mà bạn thứ hai chọn là
c1, c2, ..., cn
Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |bi+cj|.
Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2).

Yêu cầu

Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên dương n (n ≤ 105)
  • Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 109, i=1, 2, ..., n)
  • Dòng thứ hai chứa dãy số nguyên c1, c2, ..., cn (|ci| ≤ 109, i=1, 2, ..., n)
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.

Kết quả

Ghi ra giá nhỏ nhất tìm được.

Ràng buộc

  • 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.

Ví dụ

Dữ liệu:
2
1 -2
2 3
 
Kết qủa
0

HƯỚNG DẪN:

Bài yêu cầu với mỗi số b[i] tìm c[j] sao cho |b[i]+c[j]| nhỏ nhất. Suy ra chọn sao cho b[i]+c[j] có giá trị gần 0 nhất
Thuật toán sẽ là:
1.     Sắp xếp lại mảng c[].
2.     Với mỗi b[i] tìm kiếm nhị phân c[j] thỏa mãn b[i]+c[j] có giá trị gần 0 nhất.

CODE THAM KHẢO:
(UNDATE)….
.







Powered by Blogger.

- Copyright © Luyện thi HSG pascal - blog hướng dẫn tin 11 nâng cao - Powered by Blogger - Designed by Bá Sơn -