Đề thi HSG lớp 9 + thi chuyên Tin lớp 10

Kyanhdo said:

TPHCM (2016-2017)
P/S: Nhìn đề thấy bi quan quá ~~
.

Bấm để xem đầy đủ nội dung ...

Kyanhdo said:

Hà Nội (2015-2016)
Đề này còn đỡ đề kia là còn hiểu chút chút

Bấm để xem đầy đủ nội dung ...

Thử ngồi làm xem =)

Năng Khiếu:
Bài 1: giả sử S0 là giá trị ban đầu của biểu thức, S0 = a1 -a2 + a3 - a4 + ... = (a1 + a3 + a5 + ...) - (a2 + a4 + a6 + ...).
bạn thấy là nếu đổi chỗ 2 vị trí đều chẵn hay đều lẻ cho nhau thì já trị mới S ko thay đổi vẫn = S0.
Nếu đổi chỗ 1 vị trí chẵn cho 1 vị trí lẻ. giả sử a(c) chẵn đổi chỗ cho a(l) lẻ. Thì giá trị mới S là:
S = S0 + 2(a(c) - a(l))
S lớn nhất khi hiệu a(c) - a(l) lớn nhất.
Từ đó ta đi tới cách làm là: Tìm số lớn nhất trong dãy chẵn, và tìm số nhỏ nhất trong dãy lẻ. Và tính giá trị S kia. nếu S < S0 ban đầu thì chọn S0 còn S lớn hơn S0 thì chọn S.

Bài 2/. Cách làm là với mỗi số trong dãy, đếm xem có bao nhiêu số kề với nó và đều = nhau, rồi chọn vị trí mà có số lượng đếm đó lớn nhất.
như vậy, lúc đầu gán max = 0; count_max = 0; count_left = 0; count_right = 0;
i : 1 ----> n
// đếm các số = nhau liên tiếp bên trái C, dùng vòng lặp về phía trái:
Nếu i > 0:
gtt = C[i-1];
count_left = count_left + 1;
lặp j về phía trái i từ i -2 đến đầu dãy. Nếu C[j] = gtt thì count_left = count_left + 1;

// làm tương tự cho phía phải:
kiểm tra nếu gtt = gtp thì count_max = count_left + count_right; ngược lại gán count_max = số lớn hơn trong 2 số count_left và count_right, và gán giá_trị = gtt hay gtp tùy theo count_max gán = số nào tương ứng. gán số thay thế = C
sau mỗi lần lặp cho i, kiểm tra max với count_max, nếu count_max > max thì gán lại max = count_max và ghi lại vị trí của c;

Bài 3:/
để tìm bội chung nhỏ nhất thì ta fải phân tích các số ra thừa số nguyên tố, rồi với mỗi thừa số nguyên tố ta chọn số mũ lớn nhất mà 1 số nào đó chứa đc.
trường hợp riêng với các số liên tiếp từ 1 đến n. Thì suy ra BCNN sẽ là tích các số nguyên tố trong khoảng từ 1 đến n, với số mũ của mỗi số nguyên tố p là số k lớn nhất sao cho [tex]p^{k}[/tex] ko vượt quá n.
ví dụ n = 16 chẳng hạn, thì tích các số nguyên tố từ 1 đến 16 là: 2.3.5.7.11.13 trong đó số mũ của 2 là 4 vì 2^4 ko vượt quá 16, số mũ của 3 là 2 vì 3^2 = 9 ko vượt 16 (nếu lấy 3 thì 3^3 = 27 vượt quá 16 rồi), các số mũ từ 5 trở đi đều = 1.
vậy BCNN (của các số từ 1 đến 16) = [tex]2^{4}.3^{2}.5.7.11.13[/tex]
Như vậy ta cần tìm các số nguyên tố từ 1 đến n, cùng với số mũ của chúng. lần lượt nhân các số hạng đó với nhau, mỗi 1 kết quả thì chia lấy số dư cho L = 10^9 + 7. rồi lại tiếp.
Để kiểm tra 1 số p là nguyên tố, bạn kiểm tra nó có ước trong khoảng từ 2 đến [căn(p)]
ko.
// Đọc n từ file vào.
ket_qua = 1;
for i = 2 to n do:
if ( i là nguyên tố)
{
a = số_mũ = [tex]\left \lfloor log_{i}(n) \right \rfloor[/tex];
if (số_mũ > 1) thì tính P = [tex]i^{a}[/tex] else P = i;
kết_quả = (ket_quả * P) mod L;
}
// Ghi ket_qua ra file.
Bạn tự viết thêm hàm kiểm tra số nguyên tố và hàm tính mũ.

Bài 4:
Trước hết sắp xếp dãy vào tăng dần. Sau đó đi từ trái sang phải (nhỏ đến lớn), tìm phần tử xa nhất tiếp theo mà đặt trạm tại đó nó vẫn có thể phủ kín tiếp đc hết về phía trái. mỗi lần tìm đc thì ghi lại vị trí và tăng số đếm cho các trạm lên 1. Sau khi đi hết dãy thì ta đc kết quả.
Lấy ví dụ như đầu vào trong đề: sắp xếp lại tăng dần ta đc dãy: 0, 1, 3, 5, 6, 9, 10, 11. Từ trái sang phải ta thấy vị trí xa nhất mà vẫn phủ đc hết phía trái là 1, vì đặt trạm tại 1 với bán kính 2 thì ta vẫn phủ đc hết phía bên trái, còn đặt trạm tại 3 thì ko phủ đc hết bên trái. như vậy vị trí 1 là 1 vị trí cần tìm. Khi đặt trạm tại 1 thì vị trí tọa độ trái cần phủ đc sẽ tăng lên 1 + 2 + 1 = 4. Xét các giá trị tiếp theo xem tọa độ nào xa nhất mà phủ đc vị trí 4, đó là tọa độ 6, vì nếu đặt sang tọa độ 9 thì ko thể phủ tới vị trí 4 đc. Vậy ghi lại vị trí 6 và làm tiếp. lúc này tọa độ trái sẽ chuyển sang vị trí 6 + 2 + 1 = 9. Tiếp theo vị trí nào xa nhất trong dãy mà có thể phủ tới vị trí 9, đó là 11, cũng là tọa độ cuối cùng trong dãy. Ghi lại tọa độ 11 này. Số lượng trạm tổng cộng đc đếm là 3.

Input: n, R và dãy vào a1, a2, ...., am
Output: k - số trạm ít nhất cần xây, và các vị trí đặt trạm theo dãy trên.

// k = 0;
// b = dãy a.
// sắp xếp b tăng dần.
// có thể khai báo mảng logic c (bool) để ghi lại vị trí trong mảng a. cỡ của c và a = nhau.
// khởi tạo tọa độ phủ kín phía trái = 0 (vì trạm đầu tiên tọa độ 0), tdt = 0;
// biến logic check = true; // kiểm tra xem có xây được các trạm để phủ kín ko.
for i = 1 to m:
{
// kiểm tra i có là vị trí xa nhất trong b sao cho vẫn phủ kín đc phía trái hay ko:
if ((b(i) - R) <= tdt)
{
if (i < m)
{
if ((b[i+1] - R) > tdt)
{
k = k + 1; // tăng biến đếm thêm 1
// Ghi lại vị trí trạm là vị trí có tọa độ b, bằng cách tìm trong dãy a vị trí nào có giá trị = b, rồi gán c tại vị trí đó = true:
for j = 1 to m do
if (a[j] == b(i)) then c[j] = true;
// thay đổi lại vị trí của tọa độ trái:
tdt = b(i) + R + 1; // vị trí mới lúc này là vị trí xa nhất bên trái tiếp theo.
}
}
else
{
// duyệt đến tọa độ cuối trong dãy b.
if (tdt < n-1) // tức là chưa phủ hết.
{
// Lại làm jống trên:
k = k + 1; // tăng biến đếm thêm 1
// Ghi lại vị trí trạm là vị trí có tọa độ b, bằng cách tìm trong dãy a vị trí nào có giá trị = b, rồi gán c tại vị trí đó = true:
for j = 1 to m do
if (a[j] == b(i)) then c[j] = true;
// thay đổi lại vị trí của tọa độ trái:
tdt = b(i) + R + 1; // vị trí mới lúc này là vị trí xa nhất bên trái tiếp theo.
}
// Kiểm tra có phủ hết dãy nữa hay ko:
if (tdt < n-1) check = false;
}
}
else check = false;
}
// if (check) then Ghi ra file số k và các vị trí có giá trị true trong mảng c.
else In ra là ko thể có cách nào phủ kín đc.

Kyanhdo said:

Đây là đề thi quận 10

Bấm để xem đầy đủ nội dung ...

Bạn lm đc bn bài r?

Mình đọc cx chả hiểu lắm :v

cho mk hỏi tí sao mk thấy thi vào 10 lớp chuyên tin đều thi toán mà

Kyanhdo said:

Ở thành phố em lớp chuyên tin có người thi tin (70%), thi Toán (30%)

Bấm để xem đầy đủ nội dung ...

ở trường chuyên tỉnh mk muốn vào chuyên tin thì phải thi toán kiểu như là nguyện vọng 2 của toán á

Nhìn mấy cái đề chẳng hiểu gì sất