# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Đề thi học sinh giỏi THPT chuyên tỉnh Nam Định 2009-2010

## baoquyen3005

Bài 1: DÁN GIẤY
Có n gian hang được đánh số thứ tự từ 1 tới n. Tại mỗi gian hàng , người ta cho bạn Bi mảnh giấy và lấy đi Ci mảnh giấy. Bạn đi theo nguyên tắc: khi bạn ở gian i thì bạn đi tiếp sang gian i+1, nếu đang ở gian thứ n mà gian 1 chưa đi thì bạn đi sang gian 1. Hãy lựa chọn gian hàng đầu tiên xuất phát để có thể đi hết n gian hàng.
Inp: dòng 1 chứa số nguyên dương n<=100K
N dòng tiếp, dòng i chứa 2 số Bi và Ci nguyên dương <=1K
Out in ra K là gian đầu tiên xuất phát, nếu không có phương án phù hợp thì i ra 0.
VD inp:
4
5 6
5 8
8 3
6 5
out: 
3
Bài 2: GIẢM MẬT ĐỘ Ô NHIỄM
Có N công việc đánh số hiệu từ 1 tới N. Cần phân chia các công việc thành các giai đoạn, giai đoạn làm công việc i là trước hay cùng giai đoạn làm công việc j nếu j>i. Công việc i khi thực hiện cần Ti thời gian, lượng khí thải là Ki. Thời gian thực hiện 1 giai đoạn là thời gian thực hiện công việc mất nhiều thời gian nhất của giai đoạn đó. Tổng lượng khí thải của 1 giai đoạn không được vượt quá D. Hãy phân chia các công việc trong cùng 1 giai đoạn sao cho tổng thời gian thực hiện của các giai đoạn là nhỏ nhất.
Inp: dòng 1: N,D
N dòng tiếp dòng i chứa 2 số Ti và Ki với Ki<=D
(các số trong tệp đều nguyên dương và <=1K)
Out: dòng 1 chứa S là tổng thời gian thực hiện các giai đoạn nhỏ nhất tìm được.
dòng 2 chứa Q số, số thứ i thể hiện công việc có số hiệu nhỏ nhất được thực hiện trong giai đoạn i
VD inp:
4 10
5 6
6 3
6 7
3 8
out: 
14
1 2 4
Bài 3: KHO BẢO QUẢN
Có N loại hàng cần bảo quản, loại i có Xi phần, mỗi phần cần Yi ô bảo quản. Kho bảo quản có K ô bảo quản liên tiếp, ô j có tiêu chuẩn bảo quản là j. Xác định S là số ô bảo quản được sử dụng nhiều nhất mà phải đảm bảo 2 yêu cầu sau:
+ Mỗi phần loại hàng đưa vào phải bố trí đủ vào các ô liên tiếp.
+ Phần loại hàng i bảo quản tại ô có tiêu chuẩn bảo quản không vượt quá Zi
1<=N<=200;1<=Xi<=10;1<=Yi<=200;1<=Zi<=30K
Inp: dòng 1 chứa số nguyên N
N dòng tiếp, dòng i chứa 3 số nguyên dương Xi,Yi,Zi 
Out: số S thỏa mãn yêu cầu
VD: inp:
3
3 7 13
8 5 10
2 3 14
out: 
13
Bài 4:QUA SUỐI
1 con suối có độ rộng là R (bờ trái có hoành độ là 0, bờ phải có hoành độ là R)
Giữa dòng có n tảng đá, vị trí là Xi, Yi. Lúc đầu bạn ở bờ trái, cần nhảy sang bờ phải, có thể dựa vào các tảng đá hoặc nhảy sang luôn nếu có đủ khả năng. Bạn nhảy xa không quá L, lương sức khỏe ban đầu là S. Khoảng cách từ tảng đá a tới tảng đá b là d=sqrt(sqr(xa-xb)+(sqr(ya-yb)). Để từ a tới được b thì phải đảm bảo 2 yêu cầu:
+ Sức khỏe tại vị trí trước khi nhảy >=d^2
+ L>=d
sau khi nhảy, sức khỏe giảm đi d^2. Tìm cách qua suối để S1 - lượng sức khỏe còn lại khi tới được bờ suối phải- là lớn nhất.
Inp: dòng 1: N,R,S,L
N dòng tiếp, dòng i chứa Xi và Yi
Xi<=200;Yi<=200;0<=N<=1k;1<R<=200;1<L<200;s<=20K
Out: in ra S1, nếu không qua được thì ghi -1.
VD inp:
4 8 25 5
4 2
6 2
5 3
7 3
out:
2
4 bài này bạn nào rảnh thì thử ngồi làm trong 6 tiếng thử nha. 2 bài đầu làm trong 3 tiếng rồi "thu bài". 2 bài sau cũng thế.[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

----------


## letien1993

Nhiều người đọc rồi mà chưa thấy ai có ý kiến là sao?

----------


## viettu169

Buồn quá cả diễn đàn mình mình làm à?

----------


## diennguyen59

Đề nè khó ghê, mình chịu rồi, chưa cả có thuật toán, bạn nào có giúp đi.

----------


## 513minh891

Toàn kiến thức mình chưa học, duyệt đồ thị, quy hoạch động .v..vv...
Bạn Tieulong cũng đừng nóng quá, từ từ sẽ có người giúp, ai biết sẽ giải.

----------


## AnhKhoa

Mình thấy sốt ruột thui mà, ngày mai hoặc ngày kia biết điểm rùi mà chưa chắc thuật toán của mình có đúng không. Binhnguyen chưa học tới đồ thị với Qhd sao? Hay là đọc thử tài liệu của thầy Lê Minh Hoàng nhé, giúp ích nhiều đó
http://diendantinhoc.vn/showthread.php?t=7140

----------


## huynhthanhchau

dạo này ôn thi học kì , chẳng có tg [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Bik kq chưa ? Đề chọn đội tuyển trường hay đề chọn đội tuyển qg của tỉnh thế ?

----------


## nguyenvanan91

> Mình thấy sốt ruột thui mà, ngày mai hoặc ngày kia biết điểm rùi mà chưa chắc thuật toán của mình có đúng không. Binhnguyen chưa học tới đồ thị với Qhd sao? Hay là đọc thử tài liệu của thầy Lê Minh Hoàng nhé, giúp ích nhiều đó
> http://diendantinhoc.vn/showthread.php?t=7140


 Đọc thì rồi, hiểu thì có, do ít làm bài và tiếp xúc các dạng bài nên mình nghĩ cũng như chưa học.

----------


## toannechan

Đề thi chọn đội tuyển QG. CHán quá đội 6 người mình đứng thứ 7. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]( Thua 2 ông bạn ở lớp và 4 ông lớp 12. (Đội tuyển gồm cả 11 và 12 mà.
Binhnguyen học tới đồ thị chưa? Còn phần hình học thì sao? Nếu có gì không hiểu thì cứ nói nhé.

----------


## phuonganh2012

> Đề thi chọn đội tuyển QG. CHán quá đội 6 người mình đứng thứ 7. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]( Thua 2 ông bạn ở lớp và 4 ông lớp 12. (Đội tuyển gồm cả 11 và 12 mà.
> Binhnguyen học tới đồ thị chưa? Còn phần hình học thì sao? Nếu có gì không hiểu thì cứ nói nhé.


Thế đc thứ mí tỉnh . Tỉnh mình học 1 tháng mới thi chọn qg cơ nhưng k bik khi nào bắt đầu học =)) . Có thì post đề tỉnh lên tham khảo [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

----------


## songdonggun

Đề thi đó là đề thi tỉnh mình kiêm luôn nhiệm vụ chọn đội tuyển qg. Bạn cố lên nhé. Lần này thi được giải khúc khích, xếp thứ 7/15 toàn đội ( trường chỉ lấy 6 người OMG ). Buồn suốt từ hum trước tới giờ. Thuật toán mình dùng khá dễ hỉu, chắc mắc test hiểm. Tức nhất là mấy lão 12 năm trước có giải qg rồi mà năm nay lại cản trở mình, mấy lão pro bỏ xừ, đọc đề mỗi bài liếc 2' ngồi gõ code trong khi mình nhai bút 10' mới làm. Thua 2 thằng ở lớp cũng không có gì tiếc vì nó cũng pro lắm. Cả diễn đàn nè chưa chắc có ai bì được trình độ tụi nó. Sr bạn nào tự tin mình pro nha. Nhớ vụ 2 thằng ý chỉ ra chỗ chưa tối ưu trong sách tham khảo, lên ngôi bằng thuật toán của tụi nó mà mình thấy ớn. Buồn quá ai chia buồn cùng tớ.......

----------


## vietnamtui11

HSG nghĩ cả 4 bài đều dùng qhđ . Không biết có tối ưu không ?

----------


## inbaongoc007

Bài 1 không cần QHD đâu anh. Cùng lắm duyệt file inp 2 lần là có kết quả chính xác.
Bài 3 vs 4 thì QHD, bài 2 như nào ấy, kô nhớ nữa, nhưng hình như cũng QHD thì phải. 
Bài 4 quy về đồ thị nhanh hơn anh à.
Tóm lại: Mọi việc qua rồi, năm nay chưa được, năm sau sẽ páo chù.

----------

