|
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: Birački spisak
|
Izborna komisije opštine Bajtograd je dobila dopis od Republičke Izborne Komisije
o novom načinu rasporedivanja birača, po kome birači dobijaju svoj broj koji odredjuje
biračko mesto na osnovu njihove pozicije u sortiranom biračkom spisku za celu opštinu.
Nažalost, ovaj dopis im je stigao nedelju dana pre izbora nakon što su oni već poslali
pozive na glasanje sa brojevima dodeljenim po starom spisku koji nije bio sortiran već su
birači dopisivani i brisani onim redom kojim su dobijali i gubili biračko pravo. Da bi
uštedeli, članovi OIK/a su se setili da ne moraju svima da pošalju nove pozive već samo
onim biračima čiji se broj u starom i novom spisku razlikuje. Pomozite im da izračunaju
koliko poziva treba da pošalju.
Ulaz:
(Ulazni podaci se nalaze u datoteci spisak.in) Ulaz predstavlja stari spisak
birača. U prvom redu se nalazi broj birača n, a u sledećih n redova se nalaze imena
i prezimena birača, po jedno u svakom redu. Biraču u i/tom redu dodeljen je broj i. Imena
i prezimena su sastavljena od malih slova engleskog alfabeta i razdvojeni tačno jednim
razmakom.
Izlaz:
(Izlazne podatke upisati u datoteku spisak.out) U prvom redu izlazne datoteke
ispisati broj birača kojima treba poslati nove pozive.
Ograničenja:
- broj birača je manji od 1000,
- dužina imena i prezimena je manja od 25 slova,
- vremensko ograničenje za izvršavanje programa je 1 s.
Napomena:
Novi spisak je sortiran leksikografski, prvo po imenima pa po prezimenima.
Ako su A i B neke dve osobe sa spiska onda se odredjuje prvo mesto na kome se razlikuju
njihova imena (odnosno prvo mesto na kome se razlikuju prezimena, ako su imena ista). Ako
su sA i sB slova koja se nalaze na tim mestima u rečima A i B, redom, onda se proveri koje
je od ta dva slova pre u engleskom alfabetu. Za onu reč u kojoj se nalazi slovo koje je pre u
alfabetu, kažemo da je manja i stoji pre druge (veće) reči u sortiranom spisku. Dozvoljeno
je postojanje više osoba sa istim imenom i prezimenom.
Primer 1:
spisak.in
|
|
spisak.out
|
4
ana popovic
nikola peric
nemanja tomic
marko djordjevic
|
|
2
|
Primer 2:
spisak.in
|
|
spisak.out
|
9
ana popovic
nemanja tomic
marko djordjevic
nikola peric
marko djordjevic
ana popovic
nikola peric
sanja popovic
marko djordjevic
|
|
5
|
Objašnjenje:
Birači kojima se ne šalju novi pozivi su: ana popovic (broj 1), marko djordjevic
(broj 3), marko djordjevic (broj 5) i nikola peric (broj 7). Primetimo da bi ovaj spisak
nakon leksikografskog uređivanja imao sledeći izgled: ana popovic , ana popovic , marko
djordjevic , marko dordjevic , marko djordjevic , nemanja tomic , nikola peric , nikola peric ,
sanja popovic .
|
|
fajl: spisak.cpp
|
#include <stdio.h>
#include <string.h>
bool less(char *a,char *b)
{
int i=0;
while ((a[i]!=0) && (b[i]!=0) && (a[i]==b[i]))
i++;
return a[i]<b[i];
}
void sort(char **a, int n)
{
int i;
char temp[30];
bool ok = false;
while (!ok)
{
ok=true;
for (i=0;i<n-1;i++)
if (less(a[i+1],a[i]))
{
ok=false;
strcpy(temp,a[i]);
strcpy(a[i],a[i+1]);
strcpy(a[i+1],temp);
}
}
}
bool equal(char *a,char *b)
{
int i=0;
while ((a[i]!=0) && (b[i]!=0) && (a[i]==b[i]))
i++;
return a[i]==b[i];
}
int count(char **a,char **b,int n)
{
int k=0,i;
for (i=0;i<n;i++)
if (equal(a[i],b[i]))
k++;
return k;
}
int main()
{
FILE *f;
char **a,**b;
a = new char*[1000];
for (int i=0;i<1000;i++) a[i] = new char[30];
b = new char*[1000];
for (int i=0;i<1000;i++) b[i] = new char[30];
int i,n;
f = fopen("spisak.in","r");
fscanf(f,"%d",&n);
fgets(a[0],30,f);
for (i=0;i<n;i++)
fgets(a[i],30,f);
fclose(f);
for (i=0;i<n;i++)
strcpy(b[i],a[i]);
sort(b,n);
f = fopen("spisak.out","w");
fprintf(f,"%d\n",n-count(a,b,n));
fclose(f);
return 0;
}
|
|
|