|
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.
|
logo by Igor Antolović
|
|
|
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;
}
|
|
|