Gnalcats

I ricercatori hanno scoperto una nuova forma di vita, che hanno chiamato Gnalcats. I Gnalcats hanno una struttura del DNA e delle proteine molto insolita, tuttavia i ricercatori sono riusciti a capire come funzionano. Ora stanno cercando di classificare le specie di Gnalcats confrontando il loro DNA.

Un gene del loro DNA è una sequenza di basi. Questi geni agiscono su proteine, che sono catene estremamente lunghe di amminoacidi \big(a - b - c - \ldots\big). Gli amminoacidi possono essere semplici o complessi (composti da altri due amminoacidi). Le proteine contengono sempre diversi miliardi di amminoacidi.

I geni agiscono sulle proteine nel modo seguente: a sette diverse basi (C, D, L, P, R, S, U) corrispondono diverse trasformazioni della proteina. Il risultato dell'applicazione di un gene a una proteina si ottiene applicando successivamente le trasformazioni corrispondenti alle singole basi del gene: la prima base del gene trasforma la proteina originale, poi alla proteina ottenuta viene applicata la trasformazione corrispondente alla seconda base del gene, e così via. La vita non è perfetta, quindi una di queste trasformazioni può fallire, nel qual caso l'intera trasformazione è considerata fallita. Se in una qualsiasi fase della trasformazione la proteina si riduce a una catena di tre o meno amminoacidi (semplici o complessi), anche la trasformazione fallisce.

L'azione di ciascuna base è descritta nella seguente tabella, dove $X$ indica la coda della proteina, e $a,b$ e $c$ sono amminoacidi (semplici o complessi):

Ad esempio, il gene PSDSPCRPSDUL trasforma la proteina nel modo seguente:

• la proteina originale ha la forma a - b - c - d - e - f - \ldots

• applicando la regola per la prima $P$ si ottiene: <a, b> - c - d - e - f - \ldots

• applicando la regola per $S$ si ottiene: c - <a, b> - d - e - f - \ldots

• $D$ dà: <a, b> - d - e - f - \ldots

• $S$ dà: d - <a, b> - e - f - \ldots

• $P$ dà: <d, <a, b>> - e - f - \ldots

• $C$ dà: <d, <a, b>> - <d, <a, b>> - e - f - \ldots

• $R$ dà: <a, b> - <d, <a, b>> - e - f - \ldots

• $P$ dà: <<a, b>, <d, <a, b>>> - e - f - \ldots

• $S$ dà: e - <<a, b>, <d, <a, b>>> - f - \ldots

• $D$ dà: <<a, b>, <d, <a, b>>> - f - \ldots

• $U$ dà: <a, b> - <d, <a, b>> - f - \ldots

• infine, $L$ dà: a - <d, <a, b>> - f - \ldots

Vi vengono dati due geni. Dovete determinare se sono equivalenti. Due geni si dicono equivalenti se per ogni proteina in ingresso composta da almeno un miliardo di amminoacidi semplici, si verifica una delle due condizioni seguenti: o l'applicazione di entrambi i geni produce la stessa proteina in uscita, oppure entrambe le applicazioni falliscono.