| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P142SUMF - ROUND 2F - So sánh DNA |
Các thuật toán về xâu được ứng dụng rất nhiều trong sinh học, cụ thể là bài toán kiểm tra 2 chuỗi gen (DNA) có giống nhau hay không?
2 Nucleotit X và Y trong 2 chuỗi DNA được coi là giống nhau nếu như |X – Y| ≤ 1. Hai chuỗi gen được gọi là “khả giống” nếu như nó tồn tại một chuỗi các Nucleotit liên tiếp giống nhau và có chiều dài ít nhất bằng một nửa của hai chuỗi DNA đang xét. 2 chuỗi con này có thể nằm ở 2 vị trí khác nhau trên 2 chuỗi gen ban đầu.
Nhiệm vụ của bạn là hãy xác định xem 2 chuỗi gen cho trước có “khả giống” hay không?
Input
Dòng đầu tiên là số lượng bộ test T (T <= 1000).
Mỗi bộ test gồm số nguyên dương n (n <= 1000) là độ dài chung của 2 chuỗi gen cần kiểm tra. Hai dòng tiếp theo, mỗi dòng gồm n kí tự chữ cái thường miêu tả chuỗi gen thứ nhất và chuỗi gen thứ hai.
Output
Với mỗi test, in ra “POSITIVE” nếu 2 chuỗi gen “khả giống” nhau. In ra “NEGATIVE” trong trường hợp ngược lại.
Example
Input:3
Output:
4
aaaa
bbcc
8
iacdefgh
abeaaaaa
8
iacdefgh
abeafaaaPOSITIVE
NEGATIVE
NEGATIVE
| Được gửi lên bởi: | adm |
| Ngày: | 2014-07-01 |
| Thời gian chạy: | 5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2018-09-08 11:13:15
Last edit: 2018-10-23 09:37:18 |
|
|
2015-05-06 15:09:15 Ngát Taro
Ko hiểu đề lắm :( ai gt hộ e với. Tks |
