29ος ΠΔΠ Γ' Φάση
Ακολουθίες DNA (dnaseq)

Οι βιολόγοι συσχετίζουν ακολουθίες DNA για να βγάλουν συμπεράσματα για κοινά χαρακτηριστικά. Σε ένα εργαστήριο πιστεύουν ότι ακολουθίες DNA με τα παρακάτω χαρακτηριστικά αναφέρονται σε άτομα με κοινά χαρακτηριστικά προσώπου. Κάθε ακολουθία αποτελείται από \(N\) κεφαλαία γράμματα του λατινικού αλφάβητου. Τα στοιχεία των ακολουθιών είναι αριθμημένα από \(1\) έως και \(N\). Λέμε ότι δυο ακολουθίες \(A\) και \(B\) σχετίζονται αν ισχύουν τα παρακάτω: υπάρχουν δυο ακέραιοι \(L\) και \(M\) (\(1 \leq L \leq M \leq N\)) έτσι ώστε:

• \(A[i] = B[i]\) για κάθε \(i < L\)
• \(A[i] = B[i]\) για κάθε \(i > M\)
• \(A[i] = B[M+L-i]\) για κάθε \(L \leq i \leq M\)

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (Pascal, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα \(N\), \(A[i]\) και \(B[i]\) και θα βρίσκει αν αυτές οι ακολουθίες σχετίζονται ή όχι.

Αρχεία εισόδου

Το αρχείο εισόδου με όνομα dnaseq.in είναι αρχείο κειμένου που περιέχει τρεις γραμμές. Η πρώτη γραμμή περιέχει έναν μόνο ακέραιο αριθμό \(N\), το πλήθος των στοιχείων των ακολουθιών. Η δεύτερη γραμμή περιέχει τους \(N\) χαρακτήρες \(A[i]\) (όπου \(1 \leq i \leq N\)) της πρώτης ακολουθίας. Ομοίως, η τρίτη γραμμή περιέχει τους \(N\) χαρακτήρες \(B[i]\) της δεύτερης ακολουθίας

Αρχείο εξόδου

Το αρχείο εξόδου με όνομα dnaseq.out είναι αρχείο κειμένου αποτελούμενο από μία μόνο γραμμή. Αν οι ακολουθίες σχετίζονται, αυτή η γραμμή πρέπει να περιέχει μόνο έναν ακέραιο, την τιμή της διαφοράς \(M−L\). Αν υπάρχουν περισσότερες τιμές των \(L\) και \(M\) που επαληθεύουν τα παραπάνω, πρέπει να βρίσκετε την ελάχιστη δυνατή διαφορά \(M−L\). Αν οι ακολουθίες δεν σχετίζονται, η γραμμή της εξόδου θα πρέπει να περιέχει τη λέξη «no».

Παραδείγματα αρχείων εισόδου – εξόδου

1^o

dnaseq.in	dnaseq.out
12 BCBADABMAADA BCBAAAMBADDA	5

Εξήγηση: Οι τιμές \(L=5\) και \(M=10\) επαληθεύουν τα παραπάνω και δίνουν την ελάχιστη δυνατή τιμή της διαφοράς \(M−L = 10−5 = 5\).

2^o

dnaseq.in	dnaseq.out
5 ABACA ABACA	0

Εξήγηση: Οι τιμές \(L=1\) και \(M=1\) (και εν γένει κάθε \(L=M\)) επαληθεύουν τα παραπάνω.

3^o

dnaseq.in	dnaseq.out
7 ABABCAA DAABBBA	no

Περιορισμοί

• Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι:

  \[1 \leq N \leq 10.000\]

• Για περιπτώσεις ελέγχου συνολικής αξίας 100%, θα είναι:

  \[1 \leq N \leq 1.000.000\]

Προσοχή! Φροντίστε να διαβάζετε και να επεξεργάζεστε τις ακολουθίες αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

• Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
  
• Μέγιστος χρόνος εκτέλεσης: 1 sec.
  
• Μέγιστη διαθέσιμη μνήμη: \(64\) MB.