# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Đề 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
> ...


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


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

----------


## phimlen1

Code của bạn lehuukyquan chạy có test sai rồi kìa. Lấy ví dụ mình nói ở bài post trước thì với test sau:



> 2
> 343
> 34


Thì đáp án đúng sẽ là 34343 nhưng chương trình của bạn sẽ chạy ra kq 34334 [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Bạn sửa lại chương trình nhé [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## Ricky1990

Cái bài này của hs làm...hihi
Cả mấy cái diễn đàn mình tham gia có bao giờ mình code đâu ah...
Chắc có sai 1 ít vì có 13 điểm ah, cũng may là vừa HCV (12 điểm)...
Thật ra bài connect là do mình gởi đề nghị (cho học sinh làm đề thi đề nghị 1 bài - chọn ngay bài này!)
Với lại năm nay chấm thi file *.pas (mọi năm phải biên dịch trước) tuy nhiên năm nay vẫn có 1 số trục trặc kỹ thuật của thí sinh làm tràn bộ nhớ nên cũng có chấm lại bằng tay 1 số bài (thường điểm không cao hoặc không có điểm khi chấm bằng tay...)
Có lẽ bạn nào rãnh post tiếp đề 11 đi, tôi vẫn còn bài phân tích và test kiểm tra nè...

----------


## daikin

Bài 2 và bài 3 tổng là bao nhiêu điểm thầy? Bài 1 nếu làm theo so sánh xâu thì được bao nhiêu %? Mong đề 11 quá, muốn thử sức tí, em sắp phải vào Ninh Bình thi rồi.

----------


## sanxuattudien

Mình nghĩ là khung điểm của đề sẽ là 6-7-7, giống đề thi quốc gia. Bài 1 nếu làm theo kiểu so sánh xâu thì mình nghĩ cũng sẽ được full điểm nếu thuật toán của bạn là chuẩn xác [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Ơ mà TieuLong sắp vào Ninh Bình thi gì vậy???

----------


## thuhongnt

Nguyên chỉ được HCB thôi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] thang điểm là 7-6-7

----------


## SongwolVina

Thi hsg vùng duyên hải Bắc Bộ hay sao ấy. Thấy cô giáo chọn ra 3 người khối 11 đi thi, khối 10 hình như cũng 3 em nữa. Các đội tuyển môn khác cũng đi nữa. Mình cũng không biết rõ ngày tháng đi, nhưng mà tầm cuối tháng 4.

----------


## metoodiep247

Vậy là TieuLong đang học lớp 11 à? Bạn học trường nào thế??? Trường mình thì thấy chẳng bao giờ được đi thi ở đâu hết, có mỗi đi thi quốc gia thôi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## seominhthanhvip

Vùng duyên hải chắc là các tỉnh ven biển phải không nhỉ ?

----------


## hoangthikd

*T*ừ năm 1995 kỳ thi Olympic truyền thống 30/4 hằng năm, dành cho học sinh khối 10 và 11 của các trường THPT chuyên ở khu vực phía Nam, được trường THPT chuyên Lê Hồng Phong - TP. Hồ Chí Minh - khởi xướng nhằm mục đích:
 1. Phát hiện và động viên phong trào học tập rèn luyện của học sinh năng khiếu lớp 10 và 11 các tỉnh thành miền Nam, miền Trung và Tây Nguyên chuẩn bị đội ngũ dự thi học sinh giỏi quốc gia hàng năm.
2. Trao đổi kinh nghiệm về bồi dưỡng học sinh giỏi giữa giáo viên của các trường có học sinh tham gia kỳ thi.
3. Tạo điều kiện để các học sinh giỏi ở các tỉnh thành giao lưu, làm quen với hình thức thi Olympic và trao đổi lẫn nhau về kinh nghiệm học tập.
Chi tiết: http://www.thpt-lehongphong-tphcm.edu.vn/thongtin/olympic.htm

​

----------


## vanthangicom

Mình học 11 Tin Lê Hồng Phong Nam Định. Năm ngoái miền Bắc cũng tổ chức kì thi cho hs 10 rồi nhưng mà mình không được đi. Năm nay không muốn đi nhưng cô giáo lôi đi cùng 2 ông quốc gia. Mình cũng không biết kì thi nay bao gồm những tỉnh nào nữa, nhưng chắc đề thi cũng khá khó.
Mà trunga0 học ở đâu thế?

----------


## lehue2603

Mình học ở khối chuyên Toán Tin - ĐHKHTN [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Nốt năm nay là ra trường rồi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Mà TieuLong được đi thi thích thế còn gì? Cố gắng giành cái HCV về nhé!

----------


## superman

Thế ra phải gọi là anh Trung rồi, tiểu đệ thất kính, mong huynh bỏ quá cho.
Em đi thi lần này mục đích chính là để cọ xát học hỏi kinh nghiệm thôi, mong gì huy chương. Từ hồi xẩy chân vào đội tuyển quốc gia tới giờ có học mấy về Tp đâu, cô giáo bảo đi thì đi thôi. Với lại thi lần này gần sát ngày thi cuối năm, đúng là 1 cổ 2 chòng, chẳng biết nên ôn tập thế nào nữa, bỏ kì thi cuối năm thì không được rồi, nhưng nếu bỏ kì thi tin thì thấy lương tâm cắn rứt, áp lực từ bạn bè, cô giáo, bố mẹ cũng nặng lắm anh ạ.

----------


## hoabaybay

Anh nghĩ là em được đi thi thì cứ cố gắng hết sức mình là được rồi, không phải lo nghĩ nhiều đâu. Em không phải bỏ ở đâu hết, thi học kì thì cứ như bình thường thôi, tại đi thi tin thì cùng lắm cũng chỉ 3 ngày chứ mấy [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Điểm thi trên lớp kém đi chút ít cũng có chết ai đâu em [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## phimvznet

> Anh nghĩ là em được đi thi thì cứ cố gắng hết sức mình là được rồi, không phải lo nghĩ nhiều đâu. Em không phải bỏ ở đâu hết, thi học kì thì cứ như bình thường thôi, tại đi thi tin thì cùng lắm cũng chỉ 3 ngày chứ mấy [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Điểm thi trên lớp kém đi chút ít cũng có chết ai đâu em [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]


Chết em .... [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]( Nhưng dù sao cũng phải cố hết mình thôi, em còn không biết thi 1 hay 2 ngày nữa. Nếu là 1 ngày thì mệt lắm. 2 ngày thì đỡ hơn, chắc làm bài tốt hơn.

----------

