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.

sorti.cpp    1,263 b      izvorni kod rešenja
sorti.pas    1,947 b      izvorni kod rešenja
sorti.tests.7z    1,743,643 b      test primeri
sorti.checker.cpp    1,881 b      program za testiranje

zadatak: Sorti

Jedna prodavnica kompjuterske i slične opreme prodaje 10 različitih proizvoda: iPad, iPod, iPhone, iTunes, AAA alkalne baterije, LCD TV, crno-bele TV, kvalitetne NetCat tablet računare, jeftine mp4 plejere i sive boje za štampače. Ovi proizvodi se pakuju u identične kutije i na svakoj od njih stoji nalepnica sa celim brojem između 0 i 9 koja označava o kom proizvodu je reč.

Svakog jutra u stovarište prodavnice stiže n proizvoda upakovanih u kutije i one se raspoređuju u niz na jednoj jako dugačkoj polici (u redosledu dolaska). Gazdi prodavnice je jako bitno da te kutije budu sortirane po nalepnicama, od najmanje do najveće. Zato je angažovao robotića za sortiranje - Sortija. Sorti ima manu: sve što može da uradi u jednom potezu je da u nizu zameni bilo koje dve kutije koje su na rastojanju tačno d (rastojanje između dve kutije je broj kutija između njih plus 1). Gazda je uvideo ovaj nedostatak pa mu je dodao još jednu opciju: zamena nalepnica bilo koje dve kutije (nema veze što kupci neće dobiti korektan proizvod, bitno da su oni sortirani). Kada kutija dobije pogrešnu nalepnicu, ona postaje falična.

Pomozite Sortiju da sortira kutije ali tako da na kraju broj faličnih kutija bude najmanji moguć.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke sorti.in.) U prvom redu ulazne datoteke nalaze se 2 prirodna broja, n i d koji predstavljaju, redom, broj kutija sa proizvodima i konstantan raspon Sortijevih ruku (1 ≤ d < n ≤ 106).U sledećem redu nalazi se string dužine n sastavljen isključivo od cifara 0-9 koji predstavlja početni raspored kutija.

Izlaz:

(Izlazni podaci se ispisuju u datoteku sorti.out.) U prvom redu izlazne datoteke ispisati broj x - minimalan moguć broj faličnih kutija na kraju sorta. Zatim u sledećih x redova ispisati po dva broja indi i numi koji označavaju da kutija koja se na početku nalazila na poziciji indi sada ima (pogrešnu) nalepnicu numi (nije bitno od koje kutije je dobila tu nalepnicu). Ukoliko ima više rešenja, štampati bilo koje.

Primer 1.

sorti.in      sorti.out
8 5
07349622
        
3
3 9
4 3
5 4

Objašnjenje.

Moguće je sortirati tako da samo 3 kutije budu falične: kutiji na poziciji 3 (nalepnica 3) stavimo nalepnicu 9 sa kutije na poziciji 5, kutiji na poziciji 4 stavimo nalepnicu 3 sa kutije na poziciji 3 i kutiji na poziciji 5 - nalepnicu 4 sa kutije na poziciji 4. Zatim zamenimo kutije na pozicijama 2 i 7 i na pozicijama 3 i 8 (koje su na rastojanju d = 5). Nije moguće sortirati sa manje faličnih kutija.

Napomena.

Za tačno izračunat broj x (iz prvog reda) dobija se 50% poena na tom test primeru. Takođe, u 30% test primera na polici će biti samo iPad i iPod, tj. ulazni string će sadržati samo cifre 0 i 1.

fajl: sorti.cpp
#include <cstdlib>
#include <cstdio>
#include <memory.h>

const int MaxN = 1000100;
const int MaxD = 1000100;

int n, d, sol, pos;
char s[MaxN], p[MaxN];
int count[10];
int a[MaxD][10], ind[MaxN], num[MaxN];

int main() {

  FILE* inFile = fopen("sorti.in", "r");
  FILE* outFile = fopen("sorti.out", "w");
  
  fscanf(inFile, "%d%d", &n, &d);
  fscanf(inFile, "%s", s);

  memset(count, 0, sizeof(count));
  for (int i = 0; i < n; i++)
    count[s[i] - 48]++;
  pos = 0;
  for (int i = 0; i < 10; i++)
    for (int j = 0; j < count[i]; j++) 
      p[pos++] = (char)(i + 48);

  for (int i = 0; i < n; i++) {
    a[i % d][s[i] - 48]++;
    a[i % d][p[i] - 48]--;
  }

  sol = 0;
  for (int i = 0; i < d; i++)
    for (int j = 0; j < 10; j++)
      if (a[i][j] > 0) sol += a[i][j];
  fprintf(outFile, "%d\n", sol);

  int number = 0;
  for (int i = 0; i < d; i++) {
    pos = i;
    for (int j = 0; j < 10; j++) 
      while (a[i][j] < 0) {
        if (a[i][ s[pos] - 48 ] > 0) {
          ind[number] = pos + 1;
          num[number] = j;
          number++;
          a[i][j]++;
          a[i][ s[pos] - 48 ]--;
        }
        pos += d;
      }
  }

  for (int i = 0; i < sol; i++)
    fprintf(outFile, "%d %d\n", ind[i], num[i]);

  fclose(inFile);
  fclose(outFile);
  return 0;
}
fajl: sorti.pas
const
   MaxN = 1000100;
   MaxD = 1000100;


var
   inFile, outFile : Text;
   n, d, sol, pos : longint;
   s, p : array[0..MaxN] of longint;
   count : array[0..10] of longint;
   ind, num : array[0..MaxN] of longint;
   a : array[0..MaxD, 0..10] of longint;


procedure Input;
var
   i : longint;
   ch : char;

begin

   assign( inFile, 'sorti.in' );
   reset( inFile );
   readln( inFile, n, d );
   for i := 0 to n - 1 do begin
      read( inFile, ch );
      s[i] := ord( ch ) - 48;
   end;
   close( inFile );

end;


procedure Output;
var
  i : longint;

begin

   assign( outFile, 'sorti.out' );
   rewrite( outFile );
   writeln( outFile, sol );
   for i := 0 to sol - 1 do
      writeln( outFile, ind[ i ], ' ', num[ i ] );
   close( outFile );

end;


procedure Solve;
var
  i, j, number : longint;

begin

   fillchar(count, sizeof(count), 0);
   for i := 0 to n - 1 do
      count[ s[ i ] ] := count[ s[ i ] ] + 1;

   pos := 0;
   for i := 0 to 9 do
      for j := 1 to count[ i ] do begin
         p[ pos ] := i;
         pos := pos + 1;
      end;

   for i := 0 to n - 1 do begin
      a[ i MOD d ][ s[i] ] := a[ i MOD d ][ s[i] ] + 1;
      a[ i MOD d ][ p[i] ] := a[ i MOD d ][ p[i] ] - 1;
   end;

   sol := 0;
   for i := 0 to d - 1 do
      for j := 0 to 9 do
         if (a[i][j] > 0) then sol := sol + a[i][j];

   number := 0;
   for i := 0 to d - 1 do begin
      pos := i;
      for j := 0 to 9 do
         while ( a[i][j] < 0 ) do begin
            if ( a[i][ s[pos] ] > 0 ) then begin
                ind[ number ] := pos + 1;
                num[ number ] := j;
                number := number + 1;
                a[i][j] := a[i][j] + 1;
                a[i][ s[pos] ] := a[i][ s[pos] ] - 1;
            end;
            pos := pos + d;
         end;
   end;

end;


begin

   Input;
   Solve;
   Output;

end.