TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

sifra.cpp    3,176 b      izvorni kod rešenja
sifra.tests.rar    54,439 b      test primeri

zadatak: Sifra

Svi smo nekada imali problema pri pamćenju brojeva telefona, datuma rođenja, šifri... Sličan problem ima i najbogatiji patak na svetu, stari Baja. Naime, Baja je za svoj rođendan od Proke pronalazača dobio sef najnovije generacije. Kako je Proka primetio da Baji polako popušta pamćenje, šifru mu je zapisao na papiru. Međutim, svestan stalnih napada opake braće Buldog i opasnosti koja vreba ukoliko se oni domognu tog papira, Baja je malo kodirao šifru. Vaš zadatak je da pomognete Baji da što pre nađe dužinu njegove šifre kao i broj mogućih kombinacija.

Šifra predstavlja najduži uzastopni podniz koji čini permutaciju brojeva nekog segmenta [a, b] (uzastopni elementi niza koji čine permutaciju).

Ulaz:

(Ulazni podaci se nalaze u datoteci sifra.in) U prvom redu nalazi se broj n, koji predstavlja broj elemenenata niza. U svakom od sledećih n redova, nalazi se po jedan broj. Dati niz predstavlja brojeve ispisane na Bajinom papiru.

Izlaz:

(Izlazne podatke upisati u datoteku sifra.out) U prvim i jedini red ispisati dva broja odvojena razmakom: dužinu najdužeg uzastopnog podžniza koji je permutacija i broj mogućnosti.

Ograničenja:

  • 1 ≤ n ≤ 5000
  • elementi niza su pozitivni celi brojevi manji od 230
  • vremensko ograničenja za izvršavanje programa je 1 s
  • memorijsko ograničenje za izvršavanje programa je 32 MB

Primer 1:

sifra.in      sifra.out
6
2
8
6
7
5
1
        
4 1

Primer 2:

sifra.in      sifra.out
6
1
3
2
1
2
3
        
3 3

Na slici su prikazana rešenja primera 1 i 2.

U prvom primeru uslov permutacije zadovoljavaju podnizovi (2), (8), (8,6,7), (6), (6,7), (6,7,5), (7), (5) i (1), ali oni nemaju maksimalnu dužinu (koja je u tom primeru 4).

U drugom primeru, tri podniza čine moguća rešenja.

fajl: sifra.cpp
/*
ZADATAK: sifra
JEZIK: c++
*/
#include <stdio.h>
#define MaxN 6005

int a [MaxN], pom [MaxN], p [MaxN], n, num, d, m;
FILE *in, *out;

         void QSort (int l, int r)
         {
                    int i, j, pivot, tmp;
                    if (l < r)
                    {
                             pivot = pom [(l + r) / 2];
                             i = l; j = r;
                             do
                             {
                                 while (pom [i] < pivot) i++;
                                 while (pom [j] > pivot) j--;
                                     if (i <= j)
                                     {
                                            tmp = pom [i]; pom [i] = pom [j]; pom [j] = tmp;
                                            i++; j--;
                                     }
                         }
                         while (i <= j);
                         QSort (i, r);
                         QSort (l, j);
                    }
         }

         int main ()
         {
                 int i, j, min, max;

                 in = fopen ("sifra.in", "r");
                 out = fopen ("sifra.out", "w");
                 fscanf (in, "%d", &n);
                 for (i = 1; i <= n; i++)
                 {
                         fscanf (in, "%d", &a [i]);
                         pom [i] = a [i];
                 }
                 QSort (1, n);
                 i = 1; m = 0;
                 while (i <= n)
                 {
                            m++;
                            pom [m] = pom [i];
                            while ((i <= n) && (pom [m] == pom [i]))
                                        i++;
                 }
                 for (i = 1; i <= n; i++)
                 {
                         p [i] = 1;
                         while (pom [p [i]] != a [i])
                                     p [i]++;
                 }
                 num = d = 0;
                 for (i = 1; i <= n; i++)
                 {
                         for (j = 1; j <= n; j++)
                                 pom [j] = 0;
                       max = -1; min = 2000000000;
                         for (j = i; j >= 1; j--)
                         {
                                 pom [p [j]]++;
                                 if (pom [p [j]] == 2) break;
                                 if (a [j] > max) max = a [j];
                                 if (a [j] < min) min = a [j];
                                 if (max - min + 1 == i - j + 1)
                                 {
                                        if (i - j + 1 == d) num++;
                                        if (i - j + 1 > d)
                                        {
                                             num = 1;
                                             d = i - j + 1;
                                        }
                                    }
                     }
                 }

                 fprintf (out, "%d %d\n", d, num);

                 return 0;
         }