//
you're reading...
Bài tập huấn luyện, Dùng cho thi học sinh giỏi

Đề thi Olympic 30/4 lần thứ 20 năm 2014 – Tin học 11


Đề bài


Bài 1. Chuỗi gen đặc trưng (10 điểm)

Tế bào của một cá thể sinh vật ngoài hành tinh mới được phát hiện gồm rất nhiều gen, mỗi gen trong chuỗi gen của tế bào đều có số lượng nào đó các nucleotide (ký hiệu là nu). Các chuyên gia thường quan tâm chuỗi gen của mỗi cá thể dưới góc độ một chuỗi số lượng tương ứng các nu (gọi tắt là chuỗi nu), do đó chuỗi sẽ như là một dãy số nguyên dương đồng thời số số hạng của dãy này sẽ được gọi là độ dài của chuỗi. Mỗi gen được xem là đặc biệt nếu số nu của nó hoặc là bình phương của một số nguyên hoặc là lập phương của một số nguyên tố.

Để nghiên cứu khả năng biến đổi gen của loài sinh vật nói trên, các nhà khoa học xem xét hai mẫu chuỗi nu của hai cá thể và quan tâm đến mức độ “giống nhau” giữa chúng theo cách tìm ra chuỗi con chỉ gồm các gen đặc biệt mà cùng xuất hiện ở cả hai chuỗi nu (mỗi chuỗi con như vậy đều được gọi là chuỗi đặc trưng chung của hai chuỗi nu).

Lưu ý rằng, chuỗi con của một chuỗi nu X, là chuỗi thu được từ X bằng cách giữ nguyên tất cả hoặc loại bỏ đi một số nào đó các gen mà vẫn giữ thứ tự xuất hiện trong chuỗi X.

Yêu cầu: Xác định độ dài lớn nhất L của chuỗi đặc trưng chung của hai chuỗi nu cho trước.

Dữ liệu: Cho trong file văn bản GEN.INP có:

Dòng đầu ghi lần lượt các số hạng của chuỗi nu thứ nhất.

Dòng tiếp theo ghi lần lượt các số hạng của chuỗi nu thứ hai.

Tất cả các số hạng của hai chuỗi đều nguyên dương và không vượt quá 1019. Độ dài của mỗi chuỗi nu đều không vượt quá 1000.

Kết quả: Ghi ra file văn bản GEN.OUT duy nhất một số nguyên L tìm được.
Ví dụ:

GEN.INP GEN.OUT
2 9 8 4 1 27 4 6 4 4
5 6 9 1 8 2 6 27 1 4

(Giải thích: L = 4, một trong các chuỗi đăc trưng chung là: 9, 1, 27, 4)

Ràng buộc: 60% số test ứng với 60% số điểm của bài ứng với tình huống độ dài của hai chuỗi nu không vượt quá 255 và giá trị của mỗi số hạng đều không vượt quá 106.

Bài 2.  Đường lên Tây Trúc (10 điểm)

Một hành giả (nhà tu hành) muốn đến được Tây Trúc cần lần lượt thỉnh hết N ngôi chùa (các ngôi chùa được  đánh số từ 1 đến N theo trình tự thỉnh ) đồng thời phải trút bỏ hết số hồ lô mang trên  người sau khi  thỉnh hết N  ngôi chùa  đó và tích lũy được càng nhiều càng tốt số hạt xá lợi  khi kết thúc hành trình. Tại mỗi  ngôi chùa  đều đặt một hồ lô có chứa một số nào đó các hạt xá lợi: hồ lô ở  ngôi  chùa  i có chứa X i hạt. Xuất phát từ  ngôi chùa  1 (trước khi xuất phát, hành giả không có hồ lô nào mang trên người) , mỗi khi đặt chân đến một  ngôi chùa  i hành giả có thể có một trong hai lựa chọn:

  • Lấy quả hồ lô ở đó và được thu giữ toàn bộ xá lợi có trong hồ lô . Trường hợp này khiến hành giả phải mang theo trên người hồ lô này để tiếp tục hành trình .
  • Bỏ qua, không lấy quả hồ lô đó. Trườ ng hợp này khiến hành giả không lấy được số xá  lợi có trong  hồlô . Việc lấy thêm hoặc trút bỏ bớt hồ lô phải tuân theo quy tắc nghiêm ngặt sau đây . Khi đang thỉnh tại chùa i  (1 ≤ i ≤ N) và số hồ lô đang mang trên người là K  (K ≥ 0)  thì :
  1. Trong mọi tình huống, hành giả được quyền không lấy hồ lô tại đây nếu muốn. 2. Hành giả chỉ được lấy thêm hồ lô tại đây khi một trong hai trường hợp sau xảy ra:

– Trường hợp 1: K = 0 ;

– Trường hợp 2:  0 <  K  < M và trước đó, tại chùa i  – 1 hành giả có lấy hồ lô.

3 . Hành giả chỉ được bỏ bớt đúng một hồ lô mang trên người khi K > 0 đồng thời tại chùa  này hành giả đã không lấy hồ lô. (Như vậy, nếu tại chùa i hành giả không lấy hồ lô và số hồ lô đang mang trên người là K thì  hành giả được trút bỏ bớt 1 hồ lô tại đây nhưng nếu K > 1 thì hành giả không được lấy hồ lô  tại K – 1 chùa tiếp theo để trút bỏ hết K – 1 hồ lô đó rồi mới có thể tiếp tục lấy thêm hồ lô (nếu  còn và nếu muốn) ) .

Yêu cầu: Xác định số S, là số nhiều nhất hạt xá lợi mà hành giả có thể thu được sau khi đến được Tây Trúc.

Dữ liệu: Đọc từ file văn bản TAYTRUC.INP, có cấu trúc:

  • Dòng đầu ghi lần lượt 2 số nguyên N và M (2 ≤ N ≤ 10000; 1 ≤ M ≤ 500);
  • N dòng tiếp theo, mỗi dòng ghi một số nguyên dương: dòng i+1 ghi số Xi , ( Xi ≤ 1000) .

Kết quả: Ghi ra file văn bản  TAYTRUC.OUT duy nhất số  nguyên S tìm được .

Ví dụ:

TAYTRUC.INP TAYTRUC.OUT
9 4 35
1
9
8
3
4
9
8
9
7

Giải thích: Hành giả sẽ lấy hồ lô tại các chùa 2, 3, 6, 8

Bài 3.  Thủ đô   (  10 điểm  ) 

Đất nước Megaland  rộng lớn có địa hình hiểm trở, giao thông đi lại khá khó khăn. N thành phố ở quốc gia này (được đánh số từ 1 đến N) phân bố rải rác khắp đất nước. Hệ thống giao thông cả nước chỉ gồm N  –  1 đoạn đường, mỗi đoạn đường này là đường đi hai chiều nối trực tiếp hai thành phố nào đó. Thú vị là ở chỗ, chỉ với các đoạn đường đó, cư dân từ mỗi thành phố đều có thể đến được bất  kỳ thành phố nào khác trong đất nước rộng lớn này.  Với việc thủ đô hiện tại là thành phố P (1   £  P   £  N), chính quyền Megaland nhận thấy có   những thành phố khác phải mất một chặng đường dài tới K mile (mile   –  một đơn vị tính chiều dài   được sử dụng tại đây) để đến được thủ đô và điều này đã gây không ít ảnh hưởng đến sự phát triển của đất nước. Bởi vậy, chính quyền có dự định thực hiện một dự án   theo đó sẽ chọn một thành phố Q thích hợp   (1   £  Q   £  N, Q   ¹  P)   để   nâng cấp thành một đơn vị hành chính ngang tầm thủ đô (xem như là  thủ đô thứ hai). Nếu dự án được thực hiện thì từ thành phố bất kỳ, chỉ mất một chặng đường không quá L mile để đến được một trong hai thủ đô P hoặc Q.  Giới đầu tư cho dự án quan tâm đến mức độ hiệu quả của dự án là bao nhiêu nếu hiệu quả này được đặc trưng bởi hiệu số M = K   –  L.

Yêu cầu:   Xác định giá trị lớn nhất của M.

Dữ liệu  : Được cho trong file CAPITAL.INP có cấu trúc như   sau:

  • Dòng thứ nhất ghi số nguyên N (3 £  N   £  10000) và số P.
  • N –  1 dòng tiếp theo, mỗi dòng ghi ba số nguyên I, J, D với ý nghĩa: có đoạn đường nối trực tiếp hai thành phố I, J và chiều dài đoạn đường này là D mile (1   £  I, J   £  N, 1   £  D   £  106  ).

Kết quả  : Ghi ra file CAPITAL.OUT số M tìm được.

Ví dụ:

CAPITAL.INP CAPITAL.OUT
10 2 10
10 3 2
10 4 1
4 2 9
9 5 4
6 2 8
7 10 8
9 10 7
8 6 1
1 10 5

Ràng buộc:

  • Có 40% số test ứng với 40% số điểm của bài ứng với N ≤ 100.
  • Có 60% số test ứng với 60% số điểm của bài ứng với N ≤ 1000.
  • Có 80% số test ứng với 80% số điểm của bài ứng với N ≤ 5000.

—  HẾT   —

 

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: