Đề thi tin học trẻ không chuyên huyện Hải Lăng

[hoanghuy200515]

Bài 1: BÀI TOÁN DIỆN TÍCH TAM GIÁC (6 điểm)
Cho một hình chữ nhật ABCD, cạnh AB=a, cạnh BC=b; a,b là các số nguyên dương trong khoảng [1..100] (a>b)
Một điểm M chạy trên đoạn BC với Bm=x; x là số nguyên dương trong khoảng [0..b], một điểm N chạy trên đoạn CD với CN=x.
Tính giá trị lớn nhất và giá trị nhỏ nhất của diện tích tam giác ABCD khi M,N di động

Dữ liệu vào: Được cho trong tập tin CHUNHAT.INP, gồm một dòng ghi hai số nguyên dương a và b. Hai số cách nhau một khoảng trắng.
Dữ liệu ra: Yêu cầu xuất ra tập tin CHUNHAT.OUT gồm 4 dòng:
- Dòng đầu là giá trị lớn nhất của diện tích tam giác AMN (số thập phân)
- Dòng thứ hai là một giá trị của x để diện tích tam giác AMN đạt giá trị lớn nhất (số nguyên)
- Dòng thứ ba là giá trị nhỏ nhất của diện tích tam giác AMN (số thập phân)
- Dòng thứ tư là một giá trị của x để diện tích tam giác AMN đạt giá trị nhỏ nhất (số nguyên)
Ví dụ:
CHUNHAT.INP
10 6
CHUNHAT.OUT
30.0
0
17.5
5
Bài 2: (6 điểm)
Một số K được gọi là số chính phương khi và chỉ khi tồn tại một số x sao cho x*x=K
Viết chương trình thực hiện các yêu cầu sau:
a/ Nhập vào 2 số nguyên dương N,M lớn hơn hoặc bằng 2. Chương trình có kiểm tra giá trị nhập vào.
b/ Nhập vào một mảng 2 chiều A gồm N hàng và M cột.
c/ Tìm tất cả các số chính phương trong mảng ở câu b và lưu vào mảng một chiều.
d/ In ra mảng một chiều chứa các số chính phương của mảng hai chiều A vừa tìm được ở câu c ra màn hình.
Câu 3: HOÁN VỊ THUẬN THẾ (6 điểm)
Cho a=(a1,a2,......,an) là một hoán vị của dãy số tự nhiên 1..N. Ta xây dựng dãy b=(b1,b2,....,bn) và gọi là thuận thế của hoán vị như sau:
Mới mọi i=1..N, bi là số lượng các phần tử nhỏ thua ai và đứng trước ai
a/ Cho N và một hoán vị a. Hãy tìm thuận thế của a.
b/ Cho N và một thuận thế b. Hãy tìm hoán vị sinh ra thuận thế b.
Dữ liệu vào: vào từ bàn phím
a/ Nhập vào từ bàn phím số N và hoán vị a
b/ Nhập vào từ bàn phím số N và một thuận thế b
Dữ liệu ra: in ra màn hình
a/ in ra thuận thế của a
b/ in ra hoán vị sinh ra thuận thế b
Ví dụ:
a/ N = 9
a = 2 1 7 6 5 4 3 8 9
Thuận thế của a là: 0 0 2 2 2 2 2 7 8
b/ N = 9
b = 0 1 1 2 4 1 5 5 8
Hoán vị sinh ra thuận thế b là: 1 5 3 4 8 2 7 6 9
---------------------------------Bài viết đã được trộn ---------------------------------
Câu 3b ngồi nát óc hết 1h30p' mà làm ko ra đành chấp nhận giải KK. Hjx!!! [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[hungsanphuongdong]

Bạn chỉ còn câu 3b thôi chứ gì?
Theo mình thì thuật toán câu 3b nói chung sẽ như này thôi:
Duyệt từ cuối dãy B, với 1 phần tử của B, ta xác định phần tử đúng của A ở vị trí đó.
Còn để xác định đúng phần tử A như nào thì bạn quan sát kĩ test đề ra sẽ tự thấy cách tìm, còn không thì xem bên dưới đây:
Test đề bài: 0 1 1 2 4 1 5 5 8
Tạo mảng C có ý nghĩa A được xác định rồi thì C = false không thì = true
Duyệt i=9, B = 8 => A=9 (vì C[1->8] chưa false, A[9] thỏa mãn), C[9]=F.
i=8, B=5 => phần tử BÉ NHẤT trong A thỏa mãn là 6. C[6]=F.
i=7, B=5 => phần tử BÉ NHẤT trong A thỏa mãn LÚC NÀY là 7 (vì C[6]=F nên coi như không có 6 trong dãy đằng trước i). C[7]=F.
i=6, B=1 => phần tử BÉ NHẤT trong A thỏa mãn là 2. C[2]=F.
Tới lúc này mình nghĩ bạn đã hiểu làm thế nào rồi chứ, đơn giản thôi phải không?

[kaysone2911]

Bạn chỉ còn câu 3b thôi chứ gì?
Theo mình thì thuật toán câu 3b nói chung sẽ như này thôi:
Duyệt từ cuối dãy B, với 1 phần tử của B, ta xác định phần tử đúng của A ở vị trí đó.
Còn để xác định đúng phần tử A như nào thì bạn quan sát kĩ test đề ra sẽ tự thấy cách tìm, còn không thì xem bên dưới đây:
Test đề bài: 0 1 1 2 4 1 5 5 8
Tạo mảng C có ý nghĩa A được xác định rồi thì C = false không thì = true
Duyệt i=9, B = 8 => A=9 (vì C[1->8] chưa false, A[9] thỏa mãn), C[9]=F.
i=8, B=5 => phần tử BÉ NHẤT trong A thỏa mãn là 6. C[6]=F.
i=7, B=5 => phần tử BÉ NHẤT trong A thỏa mãn LÚC NÀY là 7 (vì C[6]=F nên coi như không có 6 trong dãy đằng trước i). C[7]=F.
i=6, B=1 => phần tử BÉ NHẤT trong A thỏa mãn là 2. C[2]=F.
Tới lúc này mình nghĩ bạn đã hiểu làm thế nào rồi chứ, đơn giản thôi phải không?

Sao bạn Long k làm típ nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]. Mình làm theo ý tưởng của bạn thì được thế này cơ: 1 8 4 3 5 2 7 6 9

[quataovang]

Bạn chỉ còn câu 3b thôi chứ gì?
Theo mình thì thuật toán câu 3b nói chung sẽ như này thôi:
Duyệt từ cuối dãy B, với 1 phần tử của B, ta xác định phần tử đúng của A ở vị trí đó.
Còn để xác định đúng phần tử A như nào thì bạn quan sát kĩ test đề ra sẽ tự thấy cách tìm, còn không thì xem bên dưới đây:
Test đề bài: 0 1 1 2 4 1 5 5 8
Tạo mảng C có ý nghĩa A được xác định rồi thì C = false không thì = true
Duyệt i=9, B = 8 => A=9 (vì C[1->8] chưa false, A[9] thỏa mãn), C[9]=F.
i=8, B=5 => phần tử BÉ NHẤT trong A thỏa mãn là 6. C[6]=F.
i=7, B=5 => phần tử BÉ NHẤT trong A thỏa mãn LÚC NÀY là 7 (vì C[6]=F nên coi như không có 6 trong dãy đằng trước i). C[7]=F.
i=6, B=1 => phần tử BÉ NHẤT trong A thỏa mãn là 2. C[2]=F.
Tới lúc này mình nghĩ bạn đã hiểu làm thế nào rồi chứ, đơn giản thôi phải không?

Sao mình làm theo mà không chạy ra được??????
---------------------------------Bài viết đã được trộn ---------------------------------
Hình như bạn Long hiểu sai đề hay sao nhỉ? Bài 3 là 2 câu a,b tách riêng luôn mà! :-/

[anhdgc]

Sao bạn Long k làm típ nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]. Mình làm theo ý tưởng của bạn thì được thế này cơ: 1 8 4 3 5 2 7 6 9

Hình như bạn nhầm thì phải, theo đúng trình tự các bước mình đưa ra và mình đã làm thử thì kết quả sẽ là 1 5 3 4 8 2 7 6 9. Bạn có thể kiểm tra lại. Có thể bạn nhầm ở bước tìm phần tử thứ 5 (tính từ phải sang), bạn chọn luôn phần tử thứ 4 của mảng A thỏa mãn nhưng nếu đúng thì phải chọn phần tử thứ 5 của mảng A thỏa mãn. Bạn nên xem lại chỗ đó.
TO Speed: chương trình bạn làm không chạy thì có lẽ bạn nên xem lại. Do bạn nói rằng câu b bạn không nghĩ được nên mình chỉ thuật toán câu b thôi, còn câu a với câu b có liên quan hay không thì mình không quan tâm tới nữa. Nếu bạn sửa chương trình vẫn không chạy được, bạn có thể kiểm tra lại mảng đánh dấu, đó là điểm dễ mắc lỗi, còn nếu vẫn không chạy được, bạn có thể add nick chat của mình để mình trực tiếp xem code cho bạn.

[dangnguyencctv]

Mình nghĩ đầu tiên chủ topic phải cho mọi người biết cái giới hạn của bài 3 đã

[iseovip5]

N giới hạn trong [1..MaxInt]
--------------------------

[phimbovn]

MaxInt của bạn cụ thể bằng bao nhiêu??? Có nhiều kiểu Int lắm.

Thêm nữa là mình đang muốn biết cách bạn giải quyết câu a thế nào :-? Nếu cách của bạn thuần tuý N^2 và vẫn ăn được hết điểm câu A thì câu b bạn có thể làm theo cách của TieuLong. TieuLong chú ý là cách đấy có độ phức tạp là O(N^2) chứ không phải O(N) như TieuLong nói hôm trước. Tại vì chạy một vòng lặp từ N về 1, trong đó lại for để tìm phần tử thích hợp nữa thì đúng là O(N^2) nhé [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[aaronmax]

Nghĩ kĩ thì đúng là N^2 thật, để em xem xét lại cách N đã.

[blackcatcn]

Thuật toán cải tiến thuật toán cũ của TieuLong như này: Khi tìm A đúng vị trí, ta không chạy for tìm kiếm mà thay vào đó, bước khởi tạo ta xây dựng 1 mảng có ý nghĩa lưu trứ phần tử A đúng ở vị trí i, khi nào cần lấy A chỉ cần lấy phần tử tương ứng trong mảng đó là được, tuy nhiên sau mỗi bước lấy A ra, ta phải hiệu chỉnh lại mảng đó 1 chút.