Есенен турнир 2004, Задача А2. ПРОЧИТ НА ГЕН
Уловието на задачата може да прочетете тук.
Решение
Първо,
ще преобразуваме входните данни в по- удобен вид. Всеки кодон е съставен от 3 бази,
за всяка база има по 4 възможности – A, C,
G, T. Следователно имаме 43=64 различни кодона. Ще
представим всеки един кодон с едно от числата в интервала 0..63. Така опростихме
условието “Да се намери броят на
разлчините белтъци (последователности от кодони), които са подпоследователности
на дадената ни редица” до следното: “Дадена
е редица от числа, да се намери броят на различните редици от числа, подредици
на дадената”. Така получихме задача
от теорията на информатиката и за нейното решаване ще приложим познатите
информатически методи, а именно ще решим така поставената задача по метода на
динамичното оптимиране.
Нека
дадената ни в началото редица да отбележим с a1, a2,
…, an. Нека си поставим
задача да намерим колко на брой различни подредици има до даден елемент t, за всяко t ≤ n и нека
бележим това число със S[t]. Очевидно
S[n] е отговора на задачата. Сега
нека, типично за принципа на динамичното оптимиране, да решим задачата за
дадено t, като изпозваме решенията за
всички по-малки задачи (за всяко i <
t). Нека се запитаме какъв може да е
видът на редицата спрямо елемента който седи на текущата позиция t. Вариантите са два:
1. Eлементът at се среща за първи път в редицата
на позиция t.
В този
случай можем към всички редици, които сме имали до елементът t-1 да
добавим елемента at в края
и освен това да конструираме нова редица с дължина 1, съставена само от елемента at.
Така със сигурност няма да повторим елемент, понеже до моментът няма редици
завършващи на елеменът at.
В този случай получаваме, че ако вариантите до предишния елемент са били S[t-1], то броят на редиците до
елементът t са:
S[t] =
2*S[t-1]+1.
2. Елементът
at се среща по-рано в
редицата.
Сега разсъждаваме
аналогично и към всяка от редиците, преброени до позиция t-1 прибавимяме
елемента at в края. Ще
получим S[t-1] нови редици.
Обаче ще имаме повторения, а именно това ще са всички редици, които са били
“завършени” от предишното срещане на елемента at в редицата. Нека то
е било на позиция r. Тогава за всяка
редица, чиито край е бил преди позиция r
ние сме добавили at в края
и ако го направим отново с елемента на позиция t ще повторим редици. Затова от броя трябва да извадим S[r-1], което е точно броят на тези
редици. Очевидно редиците, които завършват на позиции между r и t-1
включително няма как да бъдат повторени. Така получаваме зависимостта:
S[t] =
2*S[t-1] – S[r-1].
По този
начин изчерпахме възможните случаи (т.е. всеки елемент или е бил срещан преди,
или не). Получихме, че:
S[0] = 0,
инициализация, до нулевия елемент имаме нула редици
За t > 0:
S[t] =
2*S[t-1] + 1, ако числото на позиция t се появява за първи път,
или
S[t] =
2*S[t-1] – S[r-1], ако числото
на позиция t не се появява за първи
път и r е позицията на последното, преди позиция t
появяване на това число в редицата.
Тъй като всеки елемент бива изчислен точно един път, а за пресмятането му
използваме константен брой елементарни операции (едно умножение и едно събиране),
сложността на това решение е O(N), където N е броят на числата в началната редица.
Примерна реализация:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 4000002
char s[3*MAX]; // posledowatelnostta ot azotni bazi
int n,t[MAX]; // vhodnia masiw, preobrazuwan w chisla
int last[64]; // last[i] = poslednata pozicia, na koiato se sreshta
// ili 0, ako oshte ne e sreshtan
int dp[MAX]; // masiwa za realizacia na dinamichnoto
int main () {
int i,j,st2;
// chetem whoda
fgets(s,3*MAX,stdin);
n = (strlen(s)-1)/3;
// i go preobrazuwame ot posledowatelnost i ot stringowe w chisla
// AAA = 0, AAC = 1, AAG = 2, AAT = 3, ACA = 4,... TTT = 63
for (i=0;i<n;i++) {
t[i+1] = 0;
st2 = 16;
for (j=0;j<3;j++) {
if (s[3*i+j]=='C')
t[i+1]+=1*st2;
if (s[3*i+j]=='G')
t[i+1]+=2*st2;
if (s[3*i+j]=='T')
t[i+1]+=3*st2;
st2/=4;
}
}
dp[0] = 0; // inicializirame
for (i=1;i<=n;i++) {
if (last[t[i]]) {
dp[i] = 2*dp[i-1] - dp[last[t[i]] - 1];
} else {
dp[i] = 2*dp[i-1] + 1;
}
while (dp[i]<0) // wajno!
dp[i]+=(1<<20);
dp[i]%=(1<<20);
last[t[i]] = i;
}
printf("%d\n",dp[n]); // dp[n] - reshenieto
return 0;
}
Автор: Слави Маринов
обратно към брой 26
|