|
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ć
|
Sponzori
|
|
|
zadatak: Rečnik
|
Mali Dekica je odlučio da napravi svoj prvi rečnik. U njega će da smešta sve reči kojih se dokopa.
Naravno kao što je u svakom rečniku pravilo, reči su poslagane po leksikografskom poretku od najmanje do najveće.
Vremenom rečnik raste, pa bi mali Dekica voleo da zna za neku reč, koliko manjih reči od nje ima u rečniku.
Ulaz.
U prvome redu standardnog ulaza nalazi se jedan ceo broj, N (1 ≤ N ≤ 100000) koji predstavlja broj komandi.
Usledećih N redova, nalaze se neka od komandi
ADD reč
LESS reč
Reči će biti sastavljene od slova engleske abecede, bilo malih bilo velikih,
pri čemu se smatra da su reči "PoPoKaTaPeTL" i "POPOkataPETl" iste. Nijedna reč neće biti duža od 100 znakova a
kompletan rečnik neće imati više od 2 000 000 slova.
Izlaz.
Na standardni izlaz treba za svaku komandu koja počinje sa LESS ispisati po jedan ceo broj koji predstavlja broj reči
leksikografski manjih od reči koja sledi iza komande LESS. Svaki Broj u novom redu.
Ako tražene reči nema u rečniku ispisati "no such word".
Napomena.
U 50% primera N će biti ≤ 1000.
Primer 1.
Ulaz:
|
|
Izlaz:
|
14
ADD Petronije
ADD PeTrONIJE
ADD Jovan
ADD STEVAN
LESS Stevan
ADD ISTVAn
LESS pajVan
ADD maja
LESS istvan
ADD KlipaN
ADD Milica
LESS stevan
ADD Milica
ADD MiliCA
|
|
2
no such word
0
6
|
|
|
fajl: recnik.BIT.cpp
|
// Stošić Ivan, Niš
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long Reci[100005][8],meee,JosReci[100005][8];
int N,Dole,Gore,i,j,k,l,r,icmp,ucitaji,ucitajj;
int Perm[100005]; //Perm[i] mi govori gde stvarno treba da se nadje koja je i-ta po velicini
int Ct[100005];
char St[105],Malo[6];
bool AddUpit[100005],Ubacen[100005];
inline char cmpreci(long long *r1,long long *r2){
for (icmp=0; icmp<8; icmp++){
if (r1[icmp] > r2[icmp]) return 3; else
if (r1[icmp] < r2[icmp]) return 1;
}
return 2;
}
void inkrementuj(int p){
while (p<100005){
Ct[p]++;
p+=p&(-p);
}
}
int izvadi(int p){
int r=0;
while (p>0){
r+=Ct[p];
p-=p&(-p);
}
return r;
}
void qsort(int b,int c){
int l,r,m,t;
l=b;
r=c;
m=Perm[(7*l+9*r)>>4];
while (l<=r){
while (cmpreci(Reci[Perm[l]],Reci[m])==1) l++;
while (cmpreci(Reci[m],Reci[Perm[r]])==1) r--;
if (l<=r){
t=Perm[l];
Perm[l]=Perm[r];
Perm[r]=t;
l++;
r--;
}
}
if (b<r) qsort(b,r);
if (l<c) qsort(l,c);
}
inline void ucitajrecistavije(long long *gde){
memset(St,0,sizeof(St));
scanf("%s",St);
for (ucitaji=0; ucitaji<8; ucitaji++){
meee=0;
for (ucitajj=0; ucitajj<13; ucitajj++){
meee*=27;
meee+=St[13*ucitaji+ucitajj] % 32;
}
gde[ucitaji]=meee;
}
}
int pronadji(long long *sta){
char z;
l=1;
r=Dole;
while (l<=r){
k=(l+r)/2;
z=cmpreci(sta,Reci[Perm[k]]);
if (z==1) r=k-1;
if (z==3) l=k+1;
if (z==2) return k;
}
return 0;
//k mi govori gde se STVARNO nalazi trazeni string
}
int main(){
scanf("%d",&N);
for (i=1; i<=N; i++){
scanf("%s",Malo);
if (Malo[0]=='A'){
Dole++;
Perm[Dole]=Dole;
ucitajrecistavije(Reci[Dole]);
memcpy(JosReci[i],Reci[Dole],64);
AddUpit[i]=true;
} else {
ucitajrecistavije(JosReci[i]);
}
}
qsort(1,Dole);
for (i=1; i<=N; i++){
if (AddUpit[i]){
j=pronadji(JosReci[i]);
if (!Ubacen[j]){
inkrementuj(j);
Ubacen[j]=true;
}
} else {
j=pronadji(JosReci[i]);
if (j==0 || !Ubacen[j]) printf("no such word\n"); else printf("%d\n",izvadi(j-1));
}
}
return 0;
}
|
|
fajl: recnik.TRIE.cpp
|
// Demjan Grubić, Novi Sad
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MaxN 110
class Trie {
public:
class List {
public:
List *next;
Trie *pointer;
List() {
next = NULL;
pointer = NULL;
}
};
int abs( char a ) { return a>0?a:-a; }
Trie *Find( List **list2, char _ch ) {
List *prev = NULL;
List *list = *list2;
while ( list != NULL ) {
if ( abs( list->pointer->ch ) == _ch ) return list->pointer;
prev = list;
list = list->next;
}
list = new List;
list->pointer = new Trie;
list->pointer->list = NULL;
list->pointer->d = 0;
list->pointer->ch = _ch;
if ( prev != NULL ) prev->next = list;
else *list2 = list;
return list->pointer;
}
Trie *Exist( List *list, char _ch ) {
while ( list != NULL ) {
if ( abs( list->pointer->ch ) == _ch ) return list->pointer;
list = list->next;
}
return NULL;
}
int Sum( List *list, char _ch ) {
int ret = 0;
while ( list != NULL ) {
if ( abs( list->pointer->ch ) < _ch ) ret += list->pointer->d;
list = list->next;
}
return ret;
}
int d;
char ch;
List *list;
void Init()
{
list = NULL;
}
bool Add( char *s, int pos, int len ) {
if ( pos == len ) {
if ( ch > 0 ) {
ch = -ch;
d++;
return 1;
}
return 0;
}
Trie *tmp = Find( &list, s[pos] );
int pom = tmp->Add( s, pos+1, len );
if ( pom == 0 ) return 0;
d++;
return 1;
}
int Result( char *s, int pos, int len ) {
if ( pos == len ) {
if ( ch > 0 ) return -1;
return 0;
}
Trie *tmp = Exist( list, s[pos] );
if ( tmp == NULL ) return -1;
int ret = tmp->Result( s, pos+1, len );
if ( ret == -1 ) return -1;
ret += Sum( list, s[pos] );
if ( ch < 0 ) ret++;
return ret;
}
};
int n;
char s[MaxN];
int len;
char kom[10];
Trie trie;
void UmanjiSlova( char *s, int len )
{
for (int i = 0; i < len; ++i) {
if ( s[i] >= 'A' && s[i] <= 'Z' ) s[i] += - 'A' + 'a';
}
}
int main()
{
trie.Init();
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
scanf("%s %s",kom,s);
len = strlen(s);
UmanjiSlova(s, len);
if ( kom[0] == 'A' ) {
trie.Add( s, 0, len );
}
else {
int tmp = trie.Result( s, 0, len );
if ( tmp == -1 ) printf("no such word\n");
else printf("%d\n",tmp);
}
}
return 0;
}
|
|
fajl: recnik.BIT.pas
|
// Dusko Obradovic, Sombor
Uses SysUtils;
Type Slog = Record
Rec: String[100];
kom: char;
rb, Sort : LongInt;
end;
var s : String;
i, j, k, N, x, hf, brojac, BrojReci : LongInt;
ima : Boolean;
Recnik, kopija : array[1..100001] of Slog;
KT : Array[1..100001] of LongInt;
Procedure QSort(Left, Right : LongInt);
Var x, i, j, Pivot2 : LongInt;
Pivot : String[100];
Pom : Slog;
Begin
x := Left + random(Right - Left + 1);
i := Left;
j := Right;
Pivot := Kopija[x].Rec;
Pivot2 := Kopija[x].Rb;
Repeat
While (Kopija[i].Rec < Pivot) or
(Kopija[i].Rec = Pivot) and (Kopija[i].Rb < Pivot2)
Do i := i + 1;
While (Kopija[j].Rec > Pivot) or
(Kopija[j].Rec = Pivot) and (Kopija[j].Rb > Pivot2)
Do j := j - 1;
If i <= j Then
Begin
Pom := Kopija[i];
Kopija[i] := Kopija[j];
Kopija[j] := Pom;
i := i + 1;
j := j - 1;
End;
Until i > j;
If Left < j Then QSort(Left, j);
If i < Right Then QSort(i, Right);
End;
procedure add(x :longint); { BIT }
begin
while (x <= N) do
begin
KT[x] := KT[x] + 1;
x := x + x and (-x);
end;
end;
Function sum(x:longint):LongInt; { BIT }
var PomSum:LongInt;
begin
PomSum := 0;
while x > 0 do
begin
PomSum := PomSum + KT[x];
x := x - x and (-x);
end;
Sum := PomSum;
end;
Begin
Readln(N);
For i := 1 to N do
Begin
Readln(S);
Recnik[i].kom := S[1];
if s[1] = 'A'
then Delete(S, 1, 4)
else Delete(S, 1, 5);
S := UpperCase(s);
Recnik[i].Rec := S;
Recnik[i].Rb := i;
end;
Kopija := Recnik;
QSort(1, n);
For i := 1 to n do Kopija[i].sort := i;
For i := 2 to n do
if Kopija[i].rec = Kopija[i-1].rec
then Kopija[i].Sort := Kopija[i-1].Sort;
For i := 1 to n do Recnik[Kopija[i].rb].sort := Kopija[i].sort;
For i := 1 to N do
if Recnik[i].kom = 'A'
then if Sum(Recnik[i].Sort) - Sum(Recnik[i].Sort-1) = 0
then add(Recnik[i].Sort)
else
else if Sum(Recnik[i].Sort) - Sum(Recnik[i].Sort-1) = 0
then Writeln('no such word')
else writeln(Sum(Recnik[i].Sort-1));
end.
|
|
|