|
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: Operacije
|
Duletu je bilo jako dosadno na času matematike (ne zato što ga gradivo ne interesuje
već zato što je većinu prešao kada se pripremao za takmičenje) tako da je rešio da se
malo poigra. Naime, rekao je svom drugu da napiše veliki prirodni broj n na papiru i
tvrdio da može samo uz pomoć operacija: dodavanja broja 1 datom broju, oduzimanja broja
1 od datog broja i njegovim deljenjem sa 2 (ukoliko je paran) - dobiti broj 0. Kako njegovo
rešenje mora stati na jednom papiru, Dule mora da nađe najmanji broj operacija koje dovode
broj n na 0.
Kako je Dule uvideo da ovo nije toliko jednostavan problem, zamolio vas je da napišete
program koji nalazi traženi minimalni broj operacija.
Ulaz.
(Ulazni podaci se učitavaju iz datoteke mino.in.) U prvom i jednom redu ulazne
datoteke nalazi se prirodni broj n. Broj n neće imati više od 1000 cifara. Broj neće
imati vodećih nula.
Izlaz.
(Izlazne podatke upisati u datoteku mino.out) U prvi i jedini red izlazne
datoteke upisati minimalni broj operacija potrebnih da se prirodni broj n svede na nulu.
Operacije su dodavanje ili oduzimanje jedinice i deljenje sa dva, ukoliko je broj paran.
Primer 1.
Objašnjenje.
Minimalni broj operacija potrebnih da se broj 5 dovede na nulu je 4. Jedini
algoritam koji sadrži 4 operacija je:
5 → 4 → 2 → 1 → 0
Primer 2.
|
|
fajl: mino.cpp
|
/*
Author: Andreja Ilic, PMF Nis
e-mail: ilic_andrejko@yahoo.com
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_N 1005
// d - broj pamtimo u nizu d po ciframa u obrnutom redosledu
// n - broj trenutnih cifara u broj
int n, d[MAX_N], sol;
// Unos podataka
void input()
{
FILE *in = fopen ("mino.in", "r");
char tmp [MAX_N];
fscanf (in, "%s", &tmp);
n = strlen(tmp);
for (int i = 0; i < n; i++)
d [n - i] = (int)(tmp [i] - '0');
fclose(in);
}
void output()
{
FILE *out = fopen ("mino.out", "w");
fprintf (out, "%d\n", sol);
printf ("%d\n", sol);
fclose(out);
}
// Funckija koja deli trenurni broj sa 2
void divide(int c)
{
int tmp = 0;
for (int i = n; i >= 1; i--)
{
tmp = tmp * 10 + d [i];
d [i] = tmp / c;
tmp = tmp % c;
}
if (d [n] == 0)
n--;
}
// Metoda koja trenutnom broju dodaje 1
void add()
{
d [1] = d [1] + 1;
int index = 1;
while (d [index] == 10)
{
d [index] = 0;
d [++index]++;
}
}
// Metoda koja trenutnom broju oduzima 1
void sub()
{
d [1] = d [1] - 1;
int index = 1;
while ((d [index] == -1) && (index < n))
{
d [index] == 9;
d [++index]--;
}
if (d [n] == 0)
n--;
}
void printN()
{
printf ("%d: ", sol);
for (int i = n; i >= 1; i--)
printf("%d", d [i]);
printf ("\n");
}
int solve()
{
//printN();
// [1] Ispitivanje kraja rekurzije
if (n == 1)
{
switch (d [1])
{
case 0:
return 0;
case 1:
return 1;
case 3:
return 3;
default:
break;
}
}
int tmp = d [2] * 10 + d [1];
// [2] Ukoliko je broj deljiv sa 2, delimo ga
if (tmp % 4 == 2)
{
divide(2);
return (1 + solve());
}
if (tmp % 4 == 0)
{
divide(4);
return (2 + solve());
}
// [3] Ispitujemo da li treba dodati 1 ili oduzeti 1
if ((tmp + 1) % 4 == 0)
add();
else
sub();
return (1 + solve());
}
int main()
{
input();
d [n + 1] = 0;
sol = solve();
output();
return 0;
}
|
|
|