Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BLGEN - Chuỗi gen đặc trưng

 
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á 10
19
. Độ 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 
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á 10
6

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 vào :

  - 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  duy nhất một số nguyên L tìm được. 

 

Ví dụ :  

Input :

2 9 8 4 1 27 4 6

5 6 9 1 8 2 6 27 1 4

Output :

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


Được gửi lên bởi:Kata
Ngày:2014-04-14
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Olympic 30/4/2014 Tp.Hồ Chí Minh

hide comments
2016-10-01 06:26:45 GYC
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/348/blgen-spoj/
2016-06-02 03:19:49 Tiệp Anonymous
mất 1 đấm vì cái seekeoln ?!! cay vc =.=
2016-03-18 14:17:42
eoln 0 điểm, seekeoln AC ???, nhờ coi comments chứ 0 đi buội rồi :v
2015-12-10 11:19:24 The Flash
phán chuẩn như thần
chuẩn LÊ DUẪN cũng thua
2015-12-10 11:18:55 ptt
Bạn #DoHongHuan ăn gì mình cúng, phán chuẩn quá !!!!!! @@
2015-10-27 19:47:34
Blog Thuật toán SPOJ hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
2015-07-07 17:21:18 Do Hong Huan
Dùng round mới AC, trunc không được.
2015-04-12 15:46:19 Stupid Dog
theo mình code thì giữa các số có thể có nhiều khoảng trắng ' ' nên nhập 0 hoài rồi cứ 0 hoài
2015-03-15 05:56:35 Bee
20 miết ... ???
2015-03-10 17:24:13 Hacking to the Gate
eoln 10, seekeoln 100 điểm :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.