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.

spisak.cpp    1,144 b      izvorni kod rešenja
spisak.tests.rar    37,188 b      test primeri

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;
}