|
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: 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.
|
|
|