Zadanie SPOJ, rozpisanie zadania

Szykuję się do olimpiady i potrzebuje pomocy z zadaniem oraz uzyskaniem pewnych wskazówek

Zadanie:
http://pl.spoj.com/problems/BFN4/

To co rozpisałem:

1. DANE OGÓLNE:
   a) Klucz składa się z "n" liter ponumerowanych 0-25
   b) x - zaszyfrowana wiadomosc
   c) y - niezaszyfrowana wiadomość
   d) k - klucz składający się z liczb 0 - 25
   e) wzór klucza y_i = ( x_i+k_{1 + (i-1) mod n} ) mod 26

2. WEJŚCIE:
   a) Liczba testów (liczba <= 200)
   b) Zestaw
   Linia 1:

• Liczba "m"
• ogranicza długość klucza 1 <= n <= m <= 100000
  Linia 2:
• wiadomość x
  nie wiem jaką długość ma wiadomość x
  Linia 3:
• wiadomość y
  nie wiem jaką długość ma wiadomość y

Czego nie dopatrzyłem w zadaniu? Na razie stanąłem na długościach łańcuchów:

 
#include <iostream>
using namespace std;

struct TEST
{
    int dlugosc_klucza;
    char niezaszyfrowany[...];
    char zaszyfrowany[...]
};

void konwertuj_na_liczby(char *tab);
void konwertuj_na_litery(char *tab);

int main()
{
    int ILOSC_ZESTAWOW;
    cin >> ILOSC_ZESTAWOW;
    
    struct TEST *wsk = new TEST[ILOSC_ZESTAWOW];
    
    
}

Wziąłem do siebie to ostrzeżenie:

Uwaga: duże rozmiary plików wejścia/wyjścia, należy starannie przemyśleć wybór języka. Limit czasu działania programu jest dobrany restrykcyjnie.

Zastanawiam się, czy zamiast zbierać wszystkie informacje i dopiero rozwiązywać problem nie lepiej byłoby zrobić w sposób:

• alokujemy pamięć na pierwszy test.

• Zapisujemy rozwiązanie do zmiennej

• Zwalniamy pamięć

• Alokujemy pamięć na drugi test i tak dalej

• Na końcu wyświetlamy wszystkie rozwiązania

Co Wy na to? To mogłoby zmniejszyć zużycie pamięci?

#include <iostream>
using namespace std;

void konwertuj_na_liczby(char *tab);
void konwertuj_na_litery(char *tab);

int main()
{
    int ILOSC_ZESTAWOW;
    cin >> ILOSC_ZESTAWOW;
    
    int *dlugosc_klucza = NULL;
    char *wiadomosc_x = NULL;
    char *wiadomosc_y = NULL;
    char* rozwiazania[ILOSC_ZESTAWOW];
    
    
} 

#include <cstdio>
using namespace std;

int main()
  {
   unsigned t;
   scanf("%u ",&t);
   while(t--)
     {
      unsigned m;
      scanf("%u ",&m);
      static char X[1000001],Y[1000001]; // max 2 MB
      getline(X,sizeof(X),'\n');
      getline(Y,sizeof(Y),'\n');
      // tu rozwiązujesz jedno zadanie i wyświetlasz wynik.
     }
   return 0;
  }

@_13th_Dragon powstaje błąd spowodowany tą linijką.

static char X[1000000001],Y[1000000001]; // max 2 MB 

Process returned 1969616009 (0x7565F489) execution time : 0.039 s
Press any key to continue.

(program sie kompiluje i uruchamia, lecz od razu wyskakuje mi to).

Co powiedziałbyś o tym?

 
#include <iostream>
using namespace std;

void konwertuj_na_liczby(char *tab);
void konwertuj_na_litery(char *tab);
char* rozwiazanie(char* x, char* y, int max_rozmiar_klucza);

void konwertuj_na_liczby(char *tab, int rozmiar){
    for(int i=0; i<rozmiar; i++)
     if(tab[i] != '*')
      tab[i] -= 65;
     else
      tab[i] = 100;
}
void konwertuj_na_litery(char *tab, int rozmiar){
    for(int i=0; i<rozmiar; i++)
     if(tab[i] != 100)
      tab[i] += 65;
     else
      tab[i] = '*';
}
char* rozwiazanie(char* x, char* y, int max_rozmiar_klucza){
    char* OUT = new char[max_rozmiar_klucza];


}

int main()
{
    int ILOSC_ZESTAWOW;
    cin >> ILOSC_ZESTAWOW;

    int max_dlugosc_klucza = 0;
    char * wiadomosc_x = NULL;
    char * wiadomosc_y = NULL;
    char * rozwiazania[ILOSC_ZESTAWOW];

    for(int i=0; i<ILOSC_ZESTAWOW; i++)
    {
        cin >> max_dlugosc_klucza;
        wiadomosc_x = new char[max_dlugosc_klucza];
        wiadomosc_y = new char[max_dlugosc_klucza];
        cin >> wiadomosc_x >> wiadomosc_y;

        rozwiazania[i] = rozwiazanie(wiadomosc_x, wiadomosc_y, max_dlugosc_klucza);

        delete wiadomosc_x;
        delete wiadomosc_y;
    }

    for(int i=0; i<ILOSC_ZESTAWOW; i++)
    {
        cout << rozwiazania[i] << endl;
        delete rozwiazania[i];
    }

}

================

Ale znowu długość klucza może być mniejsza od długości tekstów i wtedy mam wysypanie się programu...
Nie da rady sprawdzić długości tekstu wpisanego w konsolę, zanim go się nie zapisze?

zamieniłem na 2 x 1MB (faktycznie tam gigabajty były, niedopatrzyłem)

static char X[1000001],Y[1000001]; 

mam pytanko, czy funkcja strlen() jest dozwolona na olimpiadach?

To w takim razie problemy się rozwiązały :)

To, co na razie mam jest dobrze?

#include <iostream>
#include <cstring>

using namespace std;

void konwertuj_na_liczby(char *tab);
void konwertuj_na_litery(char *tab);
char* rozwiazanie(char* x, char* y, int max_rozmiar_klucza);
int pobierz_tekst(char* wsk);

void konwertuj_na_liczby(char *tab, int rozmiar){
    for(int i=0; i<rozmiar; i++)
     if(tab[i] != '*')
      tab[i] -= 65;
     else
      tab[i] = 100;
}
void konwertuj_na_litery(char *tab, int rozmiar){
    for(int i=0; i<rozmiar; i++)
     if(tab[i] != 100)
      tab[i] += 65;
     else
      tab[i] = '*';
}
char* rozwiazanie(char* x, char* y, int max_rozmiar_klucza, int rozmiar_xy){
    char* OUT = new char[rozmiar_xy];

    
}

int main()
{

    int ILOSC_ZESTAWOW;
    cin >> ILOSC_ZESTAWOW;

    int max_dlugosc_klucza = 0;
    char * rozwiazania[ILOSC_ZESTAWOW];

    static char X[1000001],Y[1000001];
    for(int i=0; i<ILOSC_ZESTAWOW; i++)
    {
        cin >> max_dlugosc_klucza;
        cin >> X >> Y;

        rozwiazania[i] = rozwiazanie(X, Y, max_dlugosc_klucza, strlen(X));
    }

    for(int i=0; i<ILOSC_ZESTAWOW; i++)
    {
        cout << rozwiazania[i] << endl;
        delete rozwiazania[i];
    }

}
 

ps. Dziękuję za cierpliwość

Nie musisz gromadzić wyników, wypisuj je natychmiast po obliczeniu.
Na rozwiązanie przygotuj kolejną tablicę: ,Z[1000001]; (może warto w kwadratowych dać 10241024+1)
Nie musisz konwertować na litery, różnice liczysz tak: signed char r=(signed)Y[i]-X[i];, dodajesz tak: Z[i]=(X[i]+r-'A')%26+'A';
Generalna zasada: "Nie krzątaj się pod klientem" - czyli jeżeli nie powiedziano ci wyraźnie że masz coś zrobić to nie rób tego.

• • Stara prostytutka uczy młodszą koleżankę: "Nie krzątaj się pod klientem, klient się poci i zjeżdża."