Previous Next Close Move
Đề thi HSG tỉnh môn Tin học năm 2009-2010 vòng 2 - HIỆP HỘI HỌC SINH TRƯỜNG THPT CHUYÊN NGUYỄN TRÃI
Cũ 13-12-2009, 02:36 PM   #1
Tedomi084
Ted & Che
 
Avatar của Tedomi084
 
Họ tên: Nguyễn Văn Đức
Giới tính: Nam [♂]
Lớp: chuyên Toán 1
Khóa: 07-10
Trường: THPT Nguyễn Trãi
Bài gửi: 2,843
Gửi cảm ơn: 172
Nhận được 441 thanks


Mặc định Đề thi HSG tỉnh môn Tin học năm 2009-2010 vòng 2

---------------Tổng quan về các bài thi
----------- Tên file chương trình ---- Dữ liệu vào-------- Dữ liệu ra

Bài 1 ----------BUS.pas------------- BUS.inp ------------ BUS.out
Bài 2 ----------POST.pas -------------POST.inp -----------POST.out
Bài 3 ----------WATER.pas -----------WATER.inp ---------WATER.out


(Chương trình của thí sinh được viết bằng ngôn ngữ Turbo Pascal 7.0 hoặc Free Pascal 2.0.4)

Hãy lập trình giải các bài toán sau:

Bài 1: Đi xe bus (6 điểm)
---Trên một tuyến đường nối 2 thành phố có xe ô tô buýt công cộng phục vụ việc đi lại của hành khách. Bến xe buýt có ở từng km của tuyến đường. Mỗi lần đi qua bến, xe đều đỗ lại cho khách lên xuống. Từ mỗi bến đều có xe xuất phát, nhưng mỗi xe chỉ chạy không quá N km kể từ bến xuất phát của nó. Hành khách khi đi xe sẽ phải trả tiền cho độ dài đoạn đường mà họ ngồi trên xe. Cước phí cần trả để đi trên đoạn đường i là C[i] (i=1,2,..n). Một hành khách xuất phát từ một bến nào đó, muốn đi L km trên tuyến đường nói trên. Hỏi người đó phải lên xuống như thế nào để tổng số tiền phải trả cho hành trình xe buýt là ít nhất.

--- Dữ liệu vào: Vào từ file văn bản BUS.INP. Trong đó:
- Dòng 1 ghi hai số nguyên dương N,L (N<=20; L<=200)
- Dòng 2 ghi N số nguyên dương C[1],C[2],...,C[n] được ghi cách nhau bởi dấu cách.

--- Kết quả: GHi ra file văn bản BUS.OUT. Trong đó:

- Dòng 1: Ghi cước phí ít nhất phải trả
- Dòng 2: Ghi số lần lên xuống xe
- Dòng 3: Ghi K là độ dài của các đoạn đường của K lần ngồi xe. Các số cách nhau ít nhất 1 dấu cách.

Ví dụ:
--------------BUS.INP------------------BUS.OUT
10 15------------------------------------142
12 21 31 40 49 58 65 79 90 101-----------3
------------------------------------------1 7 7


Bài 2: Bưu điện (7 điểm)

---Có N ngôi làng, đánh số từ 1 đến N, được nối với nhau bởi các tuyến đường nối trực tiếp giữa hai làng sao cho từ một làng bất kì có thể đi đến một làng bất kì khác bằng con đường này. Hãy chọn ra một làng để đặt trạm bưu điện sao cho quãng đường xa nhất từ làng khác đến nó là nhỏ nhất

---Dữ liệu vào: Vào từ file POST.INP

- Dòng 1: Ghi N là số ngôi làng (n<=100)
- Tiếp theo là một số dòng, mỗi dòng ghi 3 số nguyên dương u,v,w,thể hiện có một con đường (hai chiều) nối làng u và làng v với độ dài w (lưu ý rằng giữa 2 làng có thể có nhiều hơn một đường đi trực tiếp). Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.

---Kết quả: Ghi ra file văn bản POST.OUT, gồm 2 dòng

- Dòng 1: ghi số hiệu ngôi làng sẽ đặt trạm bưu điện
- Dòng 2: ghi độ dài đoạn đường xa nhất từ một làng đến bưu điện, trong phương án tối ưu.

Ví dụ:
---------POST.INP-------------POST.OUT
----------3--------------------2
----------1 2 3----------------3
----------2 3 1
----------1 3 8



Bài 3: Đổ nước (7 điểm)

--- Có N chai dung tích L[1], L[2],...,L[N] (lít), trong đó chai thứ nhất đổ đầy nước. Hãy tìm cách lấy ra M lít nước(với 0<=M<=L, L[1]<=100)

---Dữ liệu vào: Từ file WATER.INP, gồm dòng đầu là 2 số nguyên dương N và M (với N<=10). Dòng thứ hai ghi N số nguyên dương L[1],L[2],...,L[N] là dung tích của các chai.

---Kết quả: Đưa ra file WATER.OUT, theo quy cách

-----------Nếu không tìm được cách đổ thì ghi -1
-----------Nếu tìm được cách đổ thì trong K dòng đầu tiên (với K là số bước cần thực hiện), mỗi dòng ghi 2 số nguyên p và q, với ý nghĩa là phải đổ nước từ chai p sang chai q. Tiếp theo là K dòng, mỗi dòng ghi N số, trong dòng thứ j (1<=j<=K) , số thứ i là dung tích nước trong trai i tại bước thứ j. Dòng cuối cùng ghi số nguyên K là số bước thực hiện
--- Các số trên một dòng của Input/Outpuc File được ghi cách nhau ít nhất một dấu cách.

Ví dụ:
-------------WATER.INP--------WATER.OUT
-------------3 6----------------1 2
-------------12 10 2------------2 3
--------------------------------3 1
--------------------------------2 3
--------------------------------2 10 0
--------------------------------2 8 2
--------------------------------4 8 0
--------------------------------4 6 2
--------------------------------4

__________________




Tedomi084 đang ẩn   Trả lời với trích dẫn
Danh sách cám ơn: (3)
Fermi (13-12-2009), ngheo_11a1 (25-01-2010), VuiKCT (30-01-2010)
Cũ 13-12-2009, 02:38 PM   #2
Sóng Đánh Tụt Quần
Bronze Member
 
Avatar của Sóng Đánh Tụt Quần
 
Họ tên: Nhật Vô Song
Giới tính: Nam [♂]
Lớp: ???
Khóa: 05-08
Trường: H.U.T
Bài gửi: 182
Gửi cảm ơn: 2
Nhận được 35 thanks


Mặc định

Đề thế này thì vào hết chứ các chú

__________________

....Sóng Đánh Tụt Quần.....
.....Gió Thổi Tung Áo......
Sóng
Gió
Trần
Truồng


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
Sóng Đánh Tụt Quần đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 02:39 PM   #3
Tedomi084
Ted & Che
 
Avatar của Tedomi084
 
Họ tên: Nguyễn Văn Đức
Giới tính: Nam [♂]
Lớp: chuyên Toán 1
Khóa: 07-10
Trường: THPT Nguyễn Trãi
Bài gửi: 2,843
Gửi cảm ơn: 172
Nhận được 441 thanks


Mặc định

Anh nghĩ đề thế này dễ à.
Làm thử coi.

__________________




Tedomi084 đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 02:41 PM   #4
(¯’·.HoTaRu.·’¯)
...:::hopeless:::...
 
Avatar của (¯’·.HoTaRu.·’¯)
 
Họ tên: Hoàng Thái Dương
Giới tính: Nam [♂]
Lớp: chemistry
Khóa: 09-12
Trường: THPT Nguyễn Trãi
Nơi ở: TP Hải Dương
Tuổi: 20
Bài gửi: 5,519
Gửi cảm ơn: 561
Nhận được 232 thanks
Gửi tin nhắn qua Yahoo! tới (¯’·.HoTaRu.·’¯)


Mặc định

eo khiếp.... đọc mà lạnh sống lưng... chả hiểu j cạ....
(¯’·.HoTaRu.·’¯) đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 02:46 PM   #5
Sóng Đánh Tụt Quần
Bronze Member
 
Avatar của Sóng Đánh Tụt Quần
 
Họ tên: Nhật Vô Song
Giới tính: Nam [♂]
Lớp: ???
Khóa: 05-08
Trường: H.U.T
Bài gửi: 182
Gửi cảm ơn: 2
Nhận được 35 thanks


Mặc định

Originally Posted by Tedomi084 Xem bài vi***7871;t
Anh nghĩ đề thế này dễ à.
Làm thử coi.
Tình hình là lên đại học anh bỏ Tin rồi chú ợ.giờ cho anh mấy đề giải tích anh may ra còn làm đcNhưng nói chung có mỗi trường mình học Tin thì vào tất còn gì.

__________________

....Sóng Đánh Tụt Quần.....
.....Gió Thổi Tung Áo......
Sóng
Gió
Trần
Truồng


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
Sóng Đánh Tụt Quần đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 02:49 PM   #6
second_half
Water Member
 
Avatar của second_half
 
Họ tên: Nguyễn Hữu Hiệp Hai
Giới tính: Nam [♂]
Lớp: Toán 1
Khóa: 05-08
Trường: THPT Nguyễn Trãi
Tuổi: 24
Bài gửi: 146
Gửi cảm ơn: 23
Nhận được 20 thanks
Gửi tin nhắn qua Yahoo! tới second_half Gửi tin nhắn qua Skype™ tới second_half


Mặc định

Đề này cũng khá hay mà .

__________________

I am

To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
second_half đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 03:21 PM   #7
nhidaigia22_3
NTOL member
 
Avatar của nhidaigia22_3
 
Họ tên: Trương Thành Công
Giới tính: Nam [♂]
Lớp: chuyên Toán 1
Khóa: 07-10
Trường: THPT Nguyễn Trãi
Bài gửi: 62
Gửi cảm ơn: 3
Nhận được 2 thanks


Mặc định

Làm bài đc ko mà có tâm trí post đề thế này

__________________

Chào t.a và q.t!
nhidaigia22_3 đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 07:14 PM   #8
Tedomi084
Ted & Che
 
Avatar của Tedomi084
 
Họ tên: Nguyễn Văn Đức
Giới tính: Nam [♂]
Lớp: chuyên Toán 1
Khóa: 07-10
Trường: THPT Nguyễn Trãi
Bài gửi: 2,843
Gửi cảm ơn: 172
Nhận được 441 thanks


Mặc định

Có làm được đâu. Post lên cho mọi người vào đóng góp ý kiến.
Nhìn chung đề vòng 2 hay hơn đề vòng 1, đòi hỏi h/s cần có một kiến thức nhất định, không dễ dàng ăn điểm như vòng 1.

Bài 1: Quy hoạch động
Bài 2: Floy
Bài 3: Móm


Bác nào có ý tưởng bài 3 xin biết nhá.

__________________




Tedomi084 đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 07:33 PM   #9
Fermi
The Smile Maker
 
Avatar của Fermi
 
Họ tên: Tạ Huy Thành
Giới tính: Nam [♂]
Lớp: Toán 1
Khóa: 06-09
Trường: THPT Nguyễn Trãi
Bài gửi: 5,068
Gửi cảm ơn: 2,040
Nhận được 1,245 thanks
Gửi tin nhắn qua Yahoo! tới Fermi


Mặc định

Bài 3 khó thật đấy. Nếu hai bài kia đã QHĐ với Graph rồi thì bài 3 chắc là phải duyệt thôi. Phương pháp làm thô thiển kiểu như bài DOMINO năm ngoái, ăn non được 30% số trường hợp

Cao thủ đâu, ra tay đê

__________________

. dot
Fermi đang ẩn   Trả lời với trích dẫn
Cũ 13-12-2009, 07:36 PM   #10
Tedomi084
Ted & Che
 
Avatar của Tedomi084
 
Họ tên: Nguyễn Văn Đức
Giới tính: Nam [♂]
Lớp: chuyên Toán 1
Khóa: 07-10
Trường: THPT Nguyễn Trãi
Bài gửi: 2,843
Gửi cảm ơn: 172
Nhận được 441 thanks


Mặc định

Thầy Bình bảo có 2 bài đồ thị, 1 bài quy hoạch động nên cứ nghĩ bài này là đồ thị.
Làm không ra quay ra duyệt nhưng duyệt cũng chẳng làm được.
Cuối cùng lại phải in ra test ví dụ.

__________________




Tedomi084 đang ẩn   Trả lời với trích dẫn
Danh sách cám ơn: (1)
Fermi (13-12-2009)
Trả lời

Tags
đề thi tỉnh vòng 2

Công cụ bài viết Tìm trong chủ đề này
Tìm trong chủ đề này:

Tìm chi tiết
Kiểu hiển thị

Quyền viết bài
Bạn không thể gửi chủ đề mới
Bạn không thể gửi trả lời
Bạn không thể gửi file đính kèm
Bạn không thể sửa bài viết của mình

BB code đang Mở
Mặt cười đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT +8. Hiện tại là 01:56 PM
Mã nguồn: vBulletin® Phiên bản 3.8.4.
vBCredits v1.4 Copyright ©2007 - 2008, PixelFX Studios
Thiết kế: Hoàn đì zai và các đồng nghiệp

Hiển thị tốt nhất với trình duyệt FireFox