Đề thi Olympic 30-4 lớp 10

[hoaican]

Bài 1./ Cho một số N (<=100) và dãy số từ a[1]->a[n] (<=10^9). Hãy in ra một cách nối các số đó lại với nhau sau cho đạt được số lớn nhất.
INPUT:
- Dòng đầu là số N.
- N dòng tiếp là dãy A.
OUTPUT:
Một dòng duy nhất là số lớn nhất nhận được khi nối các số trong dãy A.
VD:
INPUT:
4
12
34
567
890
OUTPUT:
8905673412

Bài 2./ Một người muốn đi tham quan một số các thành phố rồi quay lại thành phố xuất phát, sao cho đường đi là ngắn nhất. Có N thành phố (<=1000). Thành phố xuất phát S đi qua K thành phố (1<=S,K<=N), K thành phố cho trước, đi tuần tự.
INPUT:
- Số N.
- Số S và K (cách nhau ít nhất một khoảng trắng).
- K thành phố trên dòng thứ 3. (cách nhau ít nhất một khoảng trắng).
- Cặp các thành phố mang ý nghĩa là có đường đi 2 chiều từ thành phố này qua thành phố kia.
OUTPUT:
Một dòng duy nhất in số các thành phố ít nhất phải qua
< Bài này Nguyên quên mất VD rồi, thông cảm>

Bài 3./ Một con robot đi từ tọa độ đầu bên trái cùng đến tọa độ dưới bên phải cùng trong một ma trận NxN (<=50). Ma trận chỉ chứa giá trị 0 và 1. Hãy chỉ ra số nhị phân nhỏ nhất mà robot tạo ra trên đường đi từ tọa độ [1;1] -> [n;n].
INPUT:
- Số N.
- N dòng, N cột tiếp là ma trận.
OUTPUT:
Số nhị phân nhỏ nhất tìm được.

< Nguyên cũng không nhớ rõ ví dụ bài này, thông cảm>

Nguyên chỉ làm được có 2 bài 1 và 3 thôi, bài 2 không làm được.

Các bạn cùng giải nhé!

[tranbaokieu]

Mình có một số suy nghĩ như thế này:

Bài 1

Bài 1 thì có nhận xét là với hai số có cùng số chữ số (cùng độ dài) thì số nào lớn hơn thì đặt bên trái. (với 2 số 12 và 24 thì cách xếp 2412 có lợi hơn là cách xếp 1224)

Ta sẽ đọc các số vào và chuyển sang kiểu xâu cho dễ xử lí. Sau đó chia dãy số ra thành 9 nhóm:
- nhóm 1 là các số có S[1] = 1
- nhóm 2 là các số có S[1] = 2
....
- nhóm 9 là các số có S[1] = 9

Ta có thể thấy là nếu đặt các số thuộc nhóm 9 trước thì sẽ có lợi hơn là các số ở nhóm 8 hay 3 hay gì đó. Tức là số thuộc nhóm lớn hơn sẽ được ưu tiên đứng trước! Vấn đề bây giờ là xử lí các số trong cùng một nhóm ra sao.

Với các số trong cùng một nhóm thì rắc rối hơn, vì giữa hai số 343 và 34 ta phải xếp là 34 trước 343, còn giữa hai số 344 và 34 ta lại phải xếp 344 trước 34. Ta có nhận xét là số đứng trước có chữ số cuối cùng kề với chữ số biểu diễn nhóm đấy. -> Ta có thể cộng thêm kí tự biểu diễn tên nhóm vào sau các số trong nhóm, rồi thêm các kí tự 'A' vào sau các số thuộc nhóm sao cho độ dài các số là bằng nhau. Rồi sắp xếp chúng theo trật tự tăng dần rồi loại bỏ đi phần vừa được thêm vào!

Nói thì khó hiểu, lấy VD cho dễ hiểu nhé!

Xét 343, 344, 34 -> cùng thuộc nhóm 3. Ta sẽ biến đổi chúng thành 3433, 3443, 343 rồi qua một bước nữa (thêm 'A' để được độ dài bằng nhau) thì thành 3433, 3443, 343A. Qua quá trình sắp xếp thì sẽ được thứ tự của chúng là 3443, 343A, 3433. Cuốt cùng ta khôi phục lại trạng thái ban đầu của các số -> được 344, 34, 343. Và cách xếp 34434343 là cách xếp tối ưu nhất.

Sau khi đã sắp xếp được tất cả các nhóm ta sẽ tiến hành in lần lượt ra, từ nhóm 9 về nhóm 1, trong mỗi nhóm thì in theo thứ tự ta vừa xếp -> Tìm được phương án tối ưu.

Độ phức tạp: Chia nhóm O(N) + Sắp xếp O(N.logN) + In kq O(N) -> O(N.logN) Quá thoải mái với N = 100.
____

Thực ra bài này các bạn cũng có thể dùng thuật toán quay lui, đặt nhánh cận để loại nghiệm nhưng không có gì chắc chắn là cách quay lui này sẽ không dính phải test chết [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Ai có cách nào khác nữa không??? Mình chỉ nghĩ ra thế này thôi. Biết đâu có bạn nghĩ ra cách O(N) :X

[quangbds19]

Bài 2 bạn Nguyên nhầm đề thì phải, hình như đề yêu cầu tìm số ĐOẠN ĐƯỜNG ít nhất cần phải đi qua chứ không phải số thành phố ít nhất cần phải đi qua. Với yêu cầu này thì ta sẽ thực hiện K lần thuật toán tìm đường đi ngắn nhất rồi cộng các đoạn đường đi ngắn nhất đó lại ta sẽ tìm được đáp số.

Bài 3 thì mình nghĩ là QHD, và đây là một bài QHD khá cơ bản [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[cameraquansat]

Mình có một số suy nghĩ như thế này:

Bài 1

Bài 1 thì có nhận xét là với hai số có cùng số chữ số (cùng độ dài) thì số nào lớn hơn thì đặt bên trái. (với 2 số 12 và 24 thì cách xếp 2412 có lợi hơn là cách xếp 1224)

Ta sẽ đọc các số vào và chuyển sang kiểu xâu cho dễ xử lí. Sau đó chia dãy số ra thành 9 nhóm:
- nhóm 1 là các số có S[1] = 1
- nhóm 2 là các số có S[1] = 2
....
- nhóm 9 là các số có S[1] = 9

Ta có thể thấy là nếu đặt các số thuộc nhóm 9 trước thì sẽ có lợi hơn là các số ở nhóm 8 hay 3 hay gì đó. Tức là số thuộc nhóm lớn hơn sẽ được ưu tiên đứng trước! Vấn đề bây giờ là xử lí các số trong cùng một nhóm ra sao.

Với các số trong cùng một nhóm thì rắc rối hơn, vì giữa hai số 343 và 34 ta phải xếp là 34 trước 343, còn giữa hai số 344 và 34 ta lại phải xếp 344 trước 34. Ta có nhận xét là số đứng trước có chữ số cuối cùng kề với chữ số biểu diễn nhóm đấy. -> Ta có thể cộng thêm kí tự biểu diễn tên nhóm vào sau các số trong nhóm, rồi thêm các kí tự 'A' vào sau các số thuộc nhóm sao cho độ dài các số là bằng nhau. Rồi sắp xếp chúng theo trật tự tăng dần rồi loại bỏ đi phần vừa được thêm vào!

Nói thì khó hiểu, lấy VD cho dễ hiểu nhé!

Xét 343, 344, 34 -> cùng thuộc nhóm 3. Ta sẽ biến đổi chúng thành 3433, 3443, 343 rồi qua một bước nữa (thêm 'A' để được độ dài bằng nhau) thì thành 3433, 3443, 343A. Qua quá trình sắp xếp thì sẽ được thứ tự của chúng là 3443, 343A, 3433. Cuốt cùng ta khôi phục lại trạng thái ban đầu của các số -> được 344, 34, 343. Và cách xếp 34434343 là cách xếp tối ưu nhất.

Sau khi đã sắp xếp được tất cả các nhóm ta sẽ tiến hành in lần lượt ra, từ nhóm 9 về nhóm 1, trong mỗi nhóm thì in theo thứ tự ta vừa xếp -> Tìm được phương án tối ưu.

Độ phức tạp: Chia nhóm O(N) + Sắp xếp O(N.logN) + In kq O(N) -> O(N.logN) Quá thoải mái với N = 100.
____

Thực ra bài này các bạn cũng có thể dùng thuật toán quay lui, đặt nhánh cận để loại nghiệm nhưng không có gì chắc chắn là cách quay lui này sẽ không dính phải test chết [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Ai có cách nào khác nữa không??? Mình chỉ nghĩ ra thế này thôi. Biết đâu có bạn nghĩ ra cách O(N) :X

Suy nghĩ đơn giản thôi bạn, dùng một hàm boolean ss(a,b) để kiểm tra xem a>b thì ss:=true ngược lại false. Trong hàm đó, chuyển số a sang chuỗi, so sánh số đầu, nếu số đầu giống thì so sánh số cuối, vòng lặp dừng khi có số khác nhau hoặc là đã xét đến số hàng đơn vị.
Dùng Qsort sắp xếp với hàm ss đã nêu trên, rồi sau đó in ra. Khá đơn giản.
Bài 3 thì thế này:
Công thức chính: gọi d[i,j] là dãy nhị phân bé nhất khi xét đến tọa độ [i,j], ta có:
d[i,j]=min{d[i-i,j]+a[i,j];d[i,j-1]+a[i,j]}
Với dấu "+" được hiểu là phép nối chứ không phải là phép cộng.
Bài 2 thì mình không biết làm.

[quechi]

Mình có một số suy nghĩ như thế này:

Bài 1

Bài 1 thì có nhận xét là với hai số có cùng số chữ số (cùng độ dài) thì số nào lớn hơn thì đặt bên trái. (với 2 số 12 và 24 thì cách xếp 2412 có lợi hơn là cách xếp 1224)

Ta sẽ đọc các số vào và chuyển sang kiểu xâu cho dễ xử lí. Sau đó chia dãy số ra thành 9 nhóm:
- nhóm 1 là các số có S[1] = 1
- nhóm 2 là các số có S[1] = 2
....
- nhóm 9 là các số có S[1] = 9

Ta có thể thấy là nếu đặt các số thuộc nhóm 9 trước thì sẽ có lợi hơn là các số ở nhóm 8 hay 3 hay gì đó. Tức là số thuộc nhóm lớn hơn sẽ được ưu tiên đứng trước! Vấn đề bây giờ là xử lí các số trong cùng một nhóm ra sao.

Với các số trong cùng một nhóm thì rắc rối hơn, vì giữa hai số 343 và 34 ta phải xếp là 34 trước 343, còn giữa hai số 344 và 34 ta lại phải xếp 344 trước 34. Ta có nhận xét là số đứng trước có chữ số cuối cùng kề với chữ số biểu diễn nhóm đấy. -> Ta có thể cộng thêm kí tự biểu diễn tên nhóm vào sau các số trong nhóm, rồi thêm các kí tự 'A' vào sau các số thuộc nhóm sao cho độ dài các số là bằng nhau. Rồi sắp xếp chúng theo trật tự tăng dần rồi loại bỏ đi phần vừa được thêm vào!

Nói thì khó hiểu, lấy VD cho dễ hiểu nhé!

Xét 343, 344, 34 -> cùng thuộc nhóm 3. Ta sẽ biến đổi chúng thành 3433, 3443, 343 rồi qua một bước nữa (thêm 'A' để được độ dài bằng nhau) thì thành 3433, 3443, 343A. Qua quá trình sắp xếp thì sẽ được thứ tự của chúng là 3443, 343A, 3433. Cuốt cùng ta khôi phục lại trạng thái ban đầu của các số -> được 344, 34, 343. Và cách xếp 34434343 là cách xếp tối ưu nhất.

Sau khi đã sắp xếp được tất cả các nhóm ta sẽ tiến hành in lần lượt ra, từ nhóm 9 về nhóm 1, trong mỗi nhóm thì in theo thứ tự ta vừa xếp -> Tìm được phương án tối ưu.

Độ phức tạp: Chia nhóm O(N) + Sắp xếp O(N.logN) + In kq O(N) -> O(N.logN) Quá thoải mái với N = 100.
____

Thực ra bài này các bạn cũng có thể dùng thuật toán quay lui, đặt nhánh cận để loại nghiệm nhưng không có gì chắc chắn là cách quay lui này sẽ không dính phải test chết [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Ai có cách nào khác nữa không??? Mình chỉ nghĩ ra thế này thôi. Biết đâu có bạn nghĩ ra cách O(N) :X

Cách đơn giản nhất là so sánh xâu! 10^9 chỉ có 10 chữ số, nhét vào xâu là ok.
Bài 3: giống hệt bài toán con kiến tìm đường trong ma trận, là bài toán qhd cơ bản.
Bài 2: chưa hiểu đề! k thành phố này là bắt buộc phải đi qua hay là sao mà out lại in ra số thành phố nhỏ nhất? Nếu bắt buộc phải qua k thành phố trên theo tuần tự thì mình nghĩ thế này:
_ xét 2 thành phố liên tiếp trong hành trình k thành phố, tìm đường đi min giữa chúng
_ đi theo con đường đó chắc chắn là nhỏ nhất để đi giữa 2 thành phố, tức là số thành phố nhỏ nhất.
_ cứ xét như thế tới hết hành trình, đảm bảo là đường đi sẽ là ít thành phố nhất đề bài không yêu cầu 1 thành phố không được đi tới 2 lần.

[Hatobaby]

Cách đơn giản nhất là so sánh xâu! 10^9 chỉ có 10 chữ số, nhét vào xâu là ok.
Bài 3: giống hệt bài toán con kiến tìm đường trong ma trận, là bài toán qhd cơ bản.
Bài 2: chưa hiểu đề! k thành phố này là bắt buộc phải đi qua hay là sao mà out lại in ra số thành phố nhỏ nhất? Nếu bắt buộc phải qua k thành phố trên theo tuần tự thì mình nghĩ thế này:
_ xét 2 thành phố liên tiếp trong hành trình k thành phố, tìm đường đi min giữa chúng
_ đi theo con đường đó chắc chắn là nhỏ nhất để đi giữa 2 thành phố, tức là số thành phố nhỏ nhất.
_ cứ xét như thế tới hết hành trình, đảm bảo là đường đi sẽ là ít thành phố nhất đề bài không yêu cầu 1 thành phố không được đi tới 2 lần.

bài 1 ss xâu sẽ ra kq sai, bài 2 in ra số cạnh ấy.

[huongtmbn]

Đáp án môn Tin khối 10 - Ban tổ chức

Bài 1. Connect
Thuật toán:
- Gọi a là dãy gồm n chuỗi số đã cho
- Sắp xếp theo tiêu chuẩn nếu ai + aj < aj + ai thì hoán vị ai và aj
- Xuất a ta được kết quả
Các giá trị của n: 3 – 10 – 20 – 47 – 58 – 73 – 100

Bài 2. Tour
Thuật toán:
- Goi d1,d2,…,dk là danh sách các đỉnh phải đi qua rồi trở về S
- Gọi NN(a,b) là đường đi ít (ngắn) nhất từ a tới b (duyệt BFS hay Dijkstra)
- Kết quả = NN(S,d1) + NN(d1,d2) + … + NN(dk,S)
Các giá trị: N – K – M – Kết quả
Test 1. 8 – 3 – 11 – 7
Test 2. 100 – 9 – 100 – 710
Test 3. 255 – 7 – 254 – 14
Test 4. 500 – 9 – 124750 – 10
Test 5. 1000 – 4 – 999 – 3992
Test 6. 1000 – 10 – 999 – 1016

Bài 3. Robot
Thuật toán: Quy hoạch động như sau
- Gọi S[i, j] là chuỗi nhị phân nhỏ nhất có được khi đi từ ô (1, 1) đến (i, j)
- S[1, 1] = a[1, 1]
- Điền dòng 1 và cột 1 của S
For i:= 2 to n do
For j:=2 to n do s[i, j]:=min(s[i – 1, j],s[i, j – 1]+a[i, j];
- Kết quả = S[n, n]
Các giá trị của n: 6 – 10 – 15 – 25 – 31 – 40 – 50


Link các test file in-out: http://www.mediafire.com/?zuggj2ni13m

[binhseo2800]

Bài 1 mình bị dùng dao mổ trâu để giết gà rồi, quên mất là giới hạn có 100 thì không cần thiết phải NlogN như vậy.

Cảm ơn bạn lehuukyquan về bộ test nhé.

[vietthuongmusic]

So sánh xâu thì sao lại ra kết quả sai được nhỉ? Bạn post code của bạn làm bằng so sánh xâu mình xem nào. So sánh xâu thực tế là so sánh từng kí tự đầu tiên của các xâu để tìm ra xâu có các kí tự đầu tiên lớn nhất. Do đó áp dụng vào bài này là hoàn toàn hợp lí. Sai ở đâu được nhỉ?
Hề hề, thế là mình làm đề này cũng chắc chân 2 bài 2,3 rồi, bài 1 còn xem lại cái so sánh xâu cái nhỉ.

[greenhome]

const fi='connect.inp';
      fo='connect.out';
      maxn=100;
var a:array[1..maxn] of string[10];
    f,g:text;
    n:integer;
procedure doc;
          var i,k:longint;
              s:string;
          begin
            assign(f,fi);
            reset(f);
              readln(f,n);
              for i:=1 to n do
                begin
                  read(f,k);
                  str(k,s);
                  a[i]:=s;
                end;
            close(f);
          end;
procedure xuli;
          var i,j:longint;
              k:string;
          begin
            for i:=1 to n-1 do
              for j:=i+1 to n do
                if a[i]<a[j] then
                  begin
                    k:=a[i];
                    a[i]:=a[j];
                    a[j]:=k;
                  end;
          end;
procedure xuat;
          var i:integer;
          begin
            assign(g,fo);
            rewrite(g);
            for i:=1 to n do
               write(g,a[i]);
            close(g);
          end;
begin
  doc;
  xuli;
  xuat;
end.