|
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: Najmanji
|
Dat je niz brojeva a1, a2, ..., an. Pod konkatenacijom dva
broja x i y podrazumevamo broj xy, koji je dobijen
nadovezivanjem cifara broja y posle broja x (npr.
konkatenacijom brojeva 123 i 45 dobijamo broj 12345). Veliki
broj dobijamo kada dopisujemo brojeve jedan iza drugog u nekom
redosledu. Odrediti najmanji broj koji se dobija konkatenacijom
svih brojeva a1, a2, ..., an.
Ulaz:
(Ulazni podaci se nalaze u datoteci najmanji.in)
U prvom redu ulazne datoteke nalazi se ceo broj
n (2 ≤ n ≤ 5000). U sledećih n redova se
nalaze prirodni brojevi a1,
a2, ..., an (1 ≤ ai
≤ 2000000000). Brojevi su zadati bez početnih
(nevažećih) nula.
Izlaz:
(Izlazne podatke upisati u datoteku najmanji.out) U prvom redu izlazne datoteke ispisati
najmanji broj koji se dobija konkatenacijom učitanih brojeva.
Ograničenja:
- Maksimalno vreme izvršavanja programa je 1 sekunda.
Primer 1:
najmanji.in
|
|
najmanji.out
|
2
91919
919191
|
|
91919191919
|
Primer 2:
najmanji.in
|
|
najmanji.out
|
5
32
11
987
12
3
|
|
1112323987
|
Objašnjenje:
Najmanji broj dobijamo konkatenacijom redom 11, 12, 32, 3, 987.
|
|
fajl: najmanji.cpp
|
/*
DRZAVNO TAKMICENJE 2008
ZADATAK: najmanji
AUTOR: Aleksandar i Andreja Ilic, Nis
Treba odrediti permutaciju unetih brojeva a [1], a [2], ..., a [n]
tako da je konkatenirani veliki broj najmanji moguc. Vrsimo zamenu
dva susedna broja x i y ako je broj xy veci od yx.
Zbog ogranicenja u zadatku, brojeve je najbolje posmatrati kao
stringove ili 64-bitne brojeve.
Vremenska slozenost je O (n log n), a prostorna O (n).
*/
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
#define MAXN 5001
using namespace std;
int n, length;
long a [MAXN];
// Fja uporedjivanja dva broja
int compare (const void * a, const void * b)
{
__int64 x = *(long*) a;
__int64 y = *(long*) b;
long tmp = (long) y;
__int64 xy = x;
while (tmp > 0)
{
xy = xy * 10;
tmp = tmp / 10;
}
xy = xy + y;
tmp = (long) x;
__int64 yx = y;
while (tmp > 0)
{
yx = yx * 10;
tmp = tmp / 10;
}
yx = yx + x;
if (xy < yx)
return -1;
else if (xy > yx)
return 1;
else
return 0;
}
int main ()
{
/* Ucitavanje podataka */
ifstream in ("najmanji.in");
in >> n;
for (int i = 0; i < n; i++)
in >> a [i];
in.close();
/* Sortiranje */
qsort (a, n, sizeof (long), compare);
/* Stampa rezultata */
ofstream out ("najmanji.out");
for (int i = 0; i < n; i++)
out << a [i];
out << endl;
out.close();
return 0;
}
|
|
|