|
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: Progsice
|
Cica je vođa grupe progsica - čirlidersica koje su se specijalizovale za zabavljanje
publike na Državnom takmičenju iz programiranja. Tokom poluvremena ove prestižne manifestacije
progsice izvode svoj performans.
Svaka progsica obučena je u kostim određene boje. Cica i ekipa zamislile su da se, kao
vrhunac nastupa, poređaju u liniju duž pravca sever-jug, a da potom neke od njih napuste
arenu (moguće je i da nijedna ne ode) i to tako da publika sa istočne tribine, gledajući
preostale progsice, vidi isti redosled boja kakav vidi i publika sa zapadne tribine. Tim
povodom vas mole za pomoć: pitaju na koliko načina mogu ostvariti svoju zamisao.
Ulaz.
(Ulazni podaci se učitavaju iz datoteke progsice.in.) U prvom redu ulazne datoteke
nalazi se broj progsica, n (1 ≤ n ≤ 5.000). U drugom redu dat je poredak progsica, onako
kako ih vidi publika s istočne tribine, u momentu kada neke od njih treba da napuste
arenu. Poredak je dat u formi stringa dužine n, pri čemu i-ti karakter u stringu označava
boju kostima i-te progsice (naravno, isti karakteri uvek označavaju istu boju, a različiti
karakteri različitu).
Izlaz.
(Izlazne podatke upisati u datoteku progsice.out) U prvi i jedini red izlazne
datoteke upisati ostatak pri deljenju broja načina da progsice ostvare svoju zamisao brojem
1.000.000.007.
Primer 1.
progsice.in
|
|
progsice.out
|
5
patka
|
|
8
|
Objašnjenje.
Na slici su prikazane sve mogućnosti (prekrižene su one progsice koje treba
da napuste arenu). Slika prikazuje pogled s istočne tribine, a uočava se da i publika sa
zapadne vidi isti redosled boja. Primetiti da se ne ubraja mogućnost kada sve progsice
napuste teren (tj., mora ostati bar jedna da nastavi zabavljanje publike).
|
|
fajl: progsice.cpp
|
/*
Autor: Slobodan Mitrovic
*/
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <cmath>
#include <time.h>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
using namespace std;
const int MAXN = 5000, MOD = 1000000007;
char str[MAXN + 10];
int fastMod(int val){
// return val % MOD;
if (val > MOD)
return val - MOD;
return val;
}
int fastestDP[MAXN + 1][MAXN + 1];
int fastestSolution(int n){
SET(fastestDP, 0);
int *cur;
for (int i = n - 1; i > -1; i--){
fastestDP[i][i] = 1;
for (int j = i + 1; j < n; j++){
cur = &fastestDP[i][j];
*cur = fastMod(fastestDP[i][j - 1] + fastestDP[i + 1][j]);
*cur = fastMod((*cur) - fastestDP[i + 1][j - 1] + MOD);
if (str[i] == str[j])
*cur = fastMod((*cur) + 1 + fastestDP[i + 1][j - 1]);
}
}
return fastMod(fastestDP[0][n - 1]);
}
int main(){
FILE *fin;
FILE *fout;
fin = fopen("progsice.in", "r");
fout = fopen("progsice.sol", "w");
int n;
fscanf(fin, "%d\n", &n);
FOR (i, n)
fscanf(fin, "%c", &str[i]);
fprintf(fout, "%d\n", fastestSolution(n));
fclose(fin);
fclose(fout);
return 0;
}
|
|
fajl: progsice.pas
|
var i,n,k:integer;
a:ansistring;
palin:array[1..5000,1..5000] of longint;
f:text;
begin
assign(f,'progsice.in');
reset(f);
readln(f,n);
readln(f,a);
close(f);
for i:=1 to n-1 do
begin
palin[i,i]:=1;
if a[i]=a[i+1] then palin[i,i+1]:=3
else palin[i,i+1]:=2;
end;
palin[n,n]:=1;
for k:=1 to n-1 do
for i:=1 to n-k do
begin
if a[i]=a[i+k] then palin[i,i+k]:=palin[i,i+k-1]+palin[i+1,i+k]+1
else palin[i,i+k]:=palin[i,i+k-1]+palin[i+1,i+k]-palin[i+1,i+k-1];
if palin[i,i+k]>1000000007 then palin[i,i+k]:=palin[i,i+k]-1000000007
else if palin[i,i+k]<0 then palin[i,i+k]:=palin[i,i+k]+1000000007;
end;
assign(f,'progsice.out');
rewrite(f);
writeln(f,palin[1,n]);
close(f);
end.
|
|
|