USACO квалификационен кръг - октомври, SILVER Division, Задача nearfr
Уловието на задачата може да прочетете
тук.
Решение
Числителят на дроб със знаменател y, която е равна на дробта a/b,е x = a*y / b(равенството се получава след
привеждане под общ знаменател на a/b
= x/y).Следователно най-близката до a/b дроб за даден знаменател yс
числител цяло число, се получавакато вземем за числител:
·
най-голямото
цяло число x1, за което x1<xили
·
най-малкото
цяло число x2, за което x<x2.
Тeзи числа се намират с константна сложност O(1).
Търсената най-близка до дадената дроб има знаменател в
интервала [1;32767]. Този интервал е достатъчно малък,
за да се намерят x1 и x2за
всеки възможен знаменател.
И така, от намерените 2*32767
на брой дроби, избираме най-близката до дадената.Това се осъщесвява с константен брой
операции – c * 32767.
Забележка: Проверката започва от малките към големите
знаменатели. По този начин в случаите, в които има няколко равни една на друга
дроби, които са отговор на задачата – например 1/2, 2/4 и 3/6 – първо да бъде намерена съкратената
дроб (1/2) и след това несъкратената няма
да бъде взета предвид, защото не е по-близка. Така няма нужда от допълнително
съкращаване на най-близката дроб след намирането и.
Примерна реализация
#include <stdio.h>
#include <math.h>
#define MAX_DENOM 32767
int main()
{
int a,b; //Nominator and denominator
//of the input fraction
int x1,x2,y; //Nominators and denominator
//of the two possible nearest fractions
int X,Y; //Nominator and denominator
//ot the nearest fraction
double dif = 1; //The smallest difference between fractions
freopen("nearfr.in","r",stdin);
freopen("nearfr.out","w",stdout);
scanf("%d%d",&a,&b);
//For each possible denominator the
//two nearest fractions are checked
for(y=1; y <= MAX_DENOM; y++)
{
//x1 and x2 are determined
if((a*y)%b!=0)
{
x1 = (a*y)/b;
x2 = x1+1;
}
else
{
x1 = (a*y)/b-1;
x2 = x1+2;
}
//If x1/y is valid, it is compared
//to the nearest so far - X/Y
if(x1>0)
{
if(dif>fabs((double)a/b - (double)x1/y))
{
dif = fabs((double)a/b - (double)x1/y);
X = x1;
Y = y;
}
}
//If x2/y is valid, it is compared
//to the nearest fraction so far - X/Y
if(x2<=MAX_DENOM)
{
if(dif>fabs((double)a/b - (double)x2/y))
{
dif = fabs((double)a/b - (double)x2/y);
X = x2;
Y = y;
}
}
}
//The nearest fraction to a/b
printf("%d %d\n",X,Y);
return 0;
}
Автор: Орлин Тенчев
обратно към текущ брой
|