Đề thi học sinh giỏi Tin thành phố Hà Nội Lớp 12 năm 2010 - 2011

[noel_trang]

nick YH của mình cũng là noel_trang

[Lucifer94st]

add nick bạn trang spam đê ^^

[truongngocdai]

đề này cũng vừa thi xong hôm nọ , được 17.8, nhìn số điểm như vậy ko đoán được mình trượt test ở những bài nào =).

Bài 1 tìm BCNN của từng cặp 2 số (tích / USCLN) + sử dụng comp để lên được 20 chữ số

Bài 2 check như bt

Bài 3 vét cạn kết hợp nhánh cận , nhánh cận so sánh trạng thái max với trường hợp tốt nhất có thể của cả map, hay tốt nhất có thể của trạng thái hiện tại với trạng thái max . Chủ yếu dựa vào cận : trong 4 ô 2x2 thì sẽ chỉ có thể có 1 quân vương . Cận chi tiết như nào thì tự các bạn suy nghĩ cụ thể =)

Ngó sol bài 3 của bạn noel_trang, khá là tối ưu . Tuy nhiên mình chưa thử chứng minh sự đúng đắn của thuật toán

Btw, noel_trang có thể cho mình cái full name được ko ? 16.5 (mất 3.5 điểm) thì có lẽ bạn chết mất 50% số test bài 1

[noel_trang]

Ôi, sao mình ngốc vậy, quên mất kiểm comp.
Mình cũng làm như vậy nhưng 50% test lớn, mình viết theo hướng xử lí số lớn. Thực ra cách này chạy limit, có như không. Chắc bị mất 3.5 điểm ở đây. Và mình nghĩ test còn có thể lớn hơn 20 chữ số.
Bạn tính ucln như thế nào? Ko sử dụng đc phép div, mod đối với kiểu comp thì phải.
Bài 3: nhánh cận thì khá chậm, mình nghĩ cách của mình là tối ưu rồi.
Mình là Trần K. Hiệp.

[truongngocdai]

Ôi, sao mình ngốc vậy, quên mất kiểm comp.
Mình cũng làm như vậy nhưng 50% test lớn, mình viết theo hướng xử lí số lớn. Thực ra cách này chạy limit, có như không. Chắc bị mất 3.5 điểm ở đây. Và mình nghĩ test còn có thể lớn hơn 20 chữ số.
Bạn tính ucln như thế nào? Ko sử dụng đc phép div, mod đối với kiểu comp thì phải.
Bài 3: nhánh cận thì khá chậm, mình nghĩ cách của mình là tối ưu rồi.
Mình là Trần K. Hiệp.

bài 3 của mình chưa phải là tối ưu, cũng ko ngờ là có cách tham lam tốt đến thế , đúng là cách tiếp cận bài toán khác nhau, mang lại những suy nghĩ hoàn toàn khác nhau =)

USCLN bạn có thể sử dụng thuật toán Euclid

While (a<>b) do
begin
if (a>b) then a:=a-b
else b:=b-a;
end;

USCLN sau khi chạy vòng lặp kia chính là a = b

Bài này nếu viết xử lý số lớn thì cũng hơi khó, vì phải sử dụng cả phép chia để tính ra BCNN . Còn limit thì ko sợ lắm , vì có thể cài số lớn theo hệ cơ số 10^9 mà ). Mình cũng đánh liều thôi, 20 chữ số =), nếu to hơn thì thời gian chạy cũng > 2s =)

[technolt]

@Đại: anh cũng chưa đọc đề nhưng nhìn qua qua thì thấy là: ai lại viết hàm gcd như thế em :P Em nên viết như thế này:

function gcd(x,y:longint):longint;
begin
if y=0 then exit(x)
else exit(gcd(y,x mod y));
end;

[noel_trang]

Cách viết hàm ucln của bạn đại chắc là chạy rất chậm khi x và y chênh lệch rất nhỏ.
VD x=1000000; y=999999. Trường hợp này phải trừ khá nhiều đấy.

[truongngocdai]

@Đại: anh cũng chưa đọc đề nhưng nhìn qua qua thì thấy là: ai lại viết hàm gcd như thế em :P Em nên viết như thế này:

function gcd(x,y:longint):longint;
begin
if y=0 then exit(x)
else exit(gcd(y,x mod y));
end;

em dùng comp có div/mod được đâu anh

@noel_trang : bạn có thể nêu cách viết khác có thể dùng cho kiểu dữ liệu comp được ko ?

[noel_trang]

mình nghĩ có thể làm thế này:

function ucln(x,y:comp):comp;
var r,b:comp;
begin
if y=0 then exit(x);
b:=trunc(x/y);
r:=x-b*y;
while r<>0 do
begin
x:=y;y:=r;b:=trunc(x/y);r:=x-b*y;
end;
ucln:=y;
end;

Nhưng nếu bạn dùng kiểu comp, sao ko dùng luôn kiểu extended? Kiểu này có đến 4932 chữ số đấy.

[=========> Bổ sung bài viết <=========]

Trời ơi, vòng 2 mình có số thứ tự 17, số báo danh 17, thi ở phòng 17. Không biết có dc nổi 7 điểm không.

[truongngocdai]

^ bạn xem số thứ tự ở đâu vậy =)