Задача 6525. Источник: Поляков. Задание КИМ 24
(А. Богданов) Текстовый файл 24-258.txt содержит геном коронавируса SARS-CoV-2 в виде последовательности из четырех типов нуклеотидов, обозначенных буквами A, T, G, C. Известно, что код S-белка, «отвечающего» за проникновение вируса в клетку, состоит из троек нуклеотидов (кодонов). Этот код начинается с ATGTTT, заканчивается на ACATAA и не содержит внутри себя кодонов TAA, TGA, TAG. Найдите количество кодонов, из которых строится код S-белка, включая стартовые и конечные кодоны.
Решение
Найдем в строке стартовую комбинацию, а после нее найдем такую конечную комбинацию, чтобы количество символов между ними было кратно трем. Если строка не содержит недопустимых троек, то она является решением. Выводим длину всей комбинации в кодонах. Если решение не найдено, ищем следующую стартовую комбинацию.
Python
f = open('24-258.txt')
s = f.readline()
n1 = s.find('ATGTTT')
while n1 != -1:
n2 = s.find('ACATAA', n1 + 6)
while n2 != -1:
if (n2 - n1) % 3 == 0:
valid = True
for i in range(n1 + 6, n2, 3):
if s[i:i + 3] in ['TAA', 'TGA', 'TAG']:
valid = False
break
if valid:
print((n2 - n1 + 6) // 3)
exit()
break
n2 = s.find('ACATAA', n2 + 6)
n1 = s.find('ATGTTT', n1 + 6)
PascalABC
var
n1, n2, i: Integer;
s, s1: String;
valid: Boolean;
f: TEXT;
begin
Assign(f, '24-258.txt');
Reset(f);
Readln(f, s);
n1 := s.IndexOf('ATGTTT');
while n1 <> -1 do
begin
n2 := s.IndexOf('ACATAA', n1 + 6);
while n2 <> -1 do
begin
if (n2 - n1) mod 3 = 0 then
begin
valid := True;
i := n1 + 7;
while i < n2 do
begin
s1 := s[i:i + 3];
if (s1 = 'TAA') or (s1 = 'TGA') or (s1 = 'TAG') then
begin
valid := False;
break;
end;
i := i + 3;
end;
if valid then
begin
Writeln((n2 - n1 + 6) div 3);
Exit;
end;
break;
end;
n2 := s.IndexOf('ACATAA', n2 + 6);
end;
n1 := s.IndexOf('ATGTTT', n1 + 6);
end;
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("24-258.txt");
string s;
f >> s;
int n1 = s.find("ATGTTT");
while (n1 != -1)
{
int n2 = s.find("ACATAA", n1 + 6);
while (n2 != -1)
{
if ((n2 - n1) % 3 == 0)
{
bool valid = true;
for (int i = n1 + 6; i < n2; i += 3)
{
string s1 = s.substr(i, 3);
if (s1 == "TAA" || s1 == "TGA" || s1 == "TAG")
{
valid = false;
break;
}
}
if (valid)
{
cout << (n2 - n1 + 6) / 3 << endl;
return 0;
}
break;
}
n2 = s.find("ACATAA", n2 + 6);
}
n1 = s.find("ATGTTT", n1 + 6);
}
}
Можно сохранить в два массива все индексы символов после стартовой комбинации и индексы конечных комбинаций. Перебирая все пары начальных и конечных комбинаций, находим подстроку, длина которой кратна трем и которая не содержит недопустимых троек.
Python
f = open('24-258.txt')
s = f.readline()
a1 =[]
i = s.find("ATGTTT")
while i != -1:
a1.append(i + 6)
i = s.find("ATGTTT", i + 6)
a2 =[]
i = s.find("ACATAA")
while i != -1:
a2.append(i)
i = s.find("ACATAA", i + 6)
for i in a1:
for j in a2:
if i < j and (j - i) % 3 == 0:
valid = True
for n in range(i, j, 3):
if s[n:n + 3] in ['TAA', 'TGA', 'TAG']:
valid = False
break
if valid:
print((j - i + 12) // 3)
exit()
PascalABC
var
na1, na2, i, j, n: Integer;
a1, a2: array [1..50] of Integer;
s, s1: String;
valid: Boolean;
f: TEXT;
begin
Assign(f, '24-258.txt');
Reset(f);
Readln(f, s);
na1 := 0;
i := s.IndexOf('ATGTTT');
while i <> -1 do
begin
na1 := na1 + 1;
a1[na1] := i + 7;
i := s.IndexOf('ATGTTT', i + 7);
end;
na2 := 0;
i := s.IndexOf('ACATAA');
while i <> -1 do
begin
na2 := na2 + 1;
a2[na2] := i + 1;
i := s.IndexOf('ACATAA', i + 1);
end;
for i := 1 to na1 do
for j := 1 to na2 do
if (a1[i] < a2[j]) and ((a2[j] - a1[i]) mod 3 = 0) then
begin
valid := True;
n := a1[i];
while n < a2[j] do
begin
s1 := s[n:n + 3];
if (s1 = 'TAA') or (s1 = 'TGA') or (s1 = 'TAG') then
begin
valid := False;
break;
end;
n := n + 3;
end;
if valid then
begin
Writeln((a2[j] - a1[i] + 12) div 3);
Exit;
end;
break;
end;
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("24-258.txt");
string s;
f >> s;
int a1[50], a2[50];
int na1 = 0, na2 = 0;
int i = s.find("ATGTTT");
while (i != -1)
{
a1[na1++] = i + 6;
i = s.find("ATGTTT", i + 6);
}
i = s.find("ACATAA");
while (i != -1)
{
a2[na2++] = i;
i = s.find("ACATAA", i + 6);
}
for (int i = 0; i < na1; i++)
for (int j = 0; j <na2; j++)
if (a1[i] < a2[j] && (a2[j] - a1[i]) % 3 == 0)
{
bool valid = true;
for (int n = a1[i]; n < a2[j]; n += 3)
{
string s1 = s.substr(n, 3);
if (s1 == "TAA" || s1 == "TGA" || s1 == "TAG")
{
valid = false;
break;
}
}
if (valid)
{
cout << (a2[j] - a1[i] + 12) / 3 << endl;
return 0;
}
}
}
Ответ
1274