Lüks Sepeti
'A' ve 'B' tedarikçileri, lüks sepet piyasası için aşağıda belirtilen sayıda ürün sağlamışlardır:
Ürün 'A' 'B'
Beluga Havyarı 5248 640
Noel Keki 1312 1888
Jambon 2624 3776
Porto Şarabı 5760 3776
Şampanya 3936 5664
Tedarikçiler mallarını kusursuz durumda göndermeye çalışsa da kaçınılmaz olarak bazı bozulmalar oldu - yani ürünler kötüleşti.
Tedarikçiler, iki istatistik türünü kullanarak performanslarını karşılaştırırlar:
- Her bir tedarikçi için ürün başına beş bozulma oranı, beş ürünün sırasıyla her biri için tedarik edilen ürün sayısıyla bölünen kötü ürün sayısına eşittir.
- Her bir tedarikçi için genel bozulma oranı, kötüleşmiş toplam ürün sayısının bu tedarikçinin sağladığı toplam ürün sayısına bölünmesiyle elde edilen değere eşittir.
Bu şaşırtıcı sonucun oluşabileceği otuz beş m > 1 değeri vardır, en küçük olanı ise 1476/1475 dir.
m'nin mümkün olan en büyük değeri nedir?
Cevabınızı en sade halinde verilmiş u/v kesri şeklinde veriniz.
Cevap: 123/59
C++:
#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
int n[5][2]={{1312,1888},{5248,640},{2624,3776},{5760,3776},{3936,5664}};
int gcd(int a,int b)
{
if (a==0 || b==0) return a+b;
if (a>b) {return gcd(b,a%b);} else return gcd(a,b%a);
}
int main ()
{
int s1a,s1b,pm,qm,dm,k,a2,a3,a4,a5,siga=0,sigb=0,spoila,spoilb;
int f[5][2];
bool go_on;
int pmax=1,qmax=1;
for (k=0;k<=5;k++) {siga+=n[k][0];sigb+=n[k][1];};
for (s1b=36;s1b<=n[0][1];s1b++)
{
for (s1a=36;s1a<(qmax*s1b*n[0][0])/(n[0][1]*pmax);s1a++)
{
pm=s1b*n[0][0];
qm=s1a*n[0][1];
dm=gcd(pm,qm);
pm/=dm;
qm/=dm;
go_on=true;
for (k=1;k<=4;k++)
{
dm=gcd(pm*n[k][1],qm*n[k][0]);
f[k][0]=pm*n[k][1]/dm;
f[k][1]=qm*n[k][0]/dm;
};
for (a2=0;go_on && a2<=min(n[2][0]/f[1][1],n[2][1]/f[1][0]);a2++)
{
for (a3=0;go_on && a3<=min(n[3][0]/f[2][1],n[3][1]/f[2][0]);a3++)
{
for (a4=0;go_on && a4<=min(n[4][0]/f[3][1],n[4][1]/f[3][0]);a4++)
{
for (a5=0;go_on && a5<=min(n[5][0]/f[4][1],n[5][1]/f[4][0]);a5++)
{
spoila=s1a+a2*f[1][1]+a3*f[2][1]+a4*f[3][1]+a5*f[4][1];
spoilb=s1b+a2*f[1][0]+a3*f[2][0]+a4*f[3][0]+a5*f[4][0];
if (spoila*qm*sigb==spoilb*pm*siga)
{
cout <<pm << "/"<< qm << endl;
pmax=pm;qmax=qm;
go_on=false;
}
};
};
};
};
};
};
cout << "Max=" << pmax << "/" << qmax << endl;
return 0;
}Haskell:
problem236 = head [ m |
sumB' <- [5..sumB],
let minSumA' = ceiling $ (sumA*sumB')%sumB,
sumA' <- [sumA,sumA-1..minSumA'],
let m = (sumA'*sumB)%(sumA*sumB');
search pb b ba (a':a's) =
let b' = m*(fromInteger a')*ba
in if (b' <= (fromInteger (min b (sumB'-pb)))) then
if (denominator b' == 1) then Just (a',numerator b')
else search pb b ba a's
else Nothing;
search _ _ _ [] = Nothing
ab1' = search 0 b1 ba1 [1..min sumA' a1], isJust ab1',
let (a1',b1') = fromJust ab1';
ab2' = search b1' b2 ba2 [1..min (sumA'-a1') a2 ],isJust ab2',
let (a2',b2') = fromJust ab2';
ab3' = search (b1'+b2') b3 ba3 [1..min (sumA'-a1'-a2') a3], isJust ab3',
let (a3',b3') = fromJust ab3';
ab4' = search (b1'+b2'+b3') b4 ba4 [1..min (sumA'-a1'-a2'-a3') a4 ], isJust ab4'
]
where
a1 = 5248; a2 = 1312; a3 = 2624; a4 = 5760; a5 = 3936
b1 = 640; b2 = 1888; b3 = 3776; b4 = 3776; b5 = 5664
ba1 = b1%a1; ba2 = b2%a2; ba3 = b3%a3; ba4 = b4%a4; ba5 = b5%a5;
sumA = a1 + a2 + a3 + a4 + a5
sumB = b1 + b2 + b3 + b4 + b5ML:
module FracSet = Set.Make (
struct
type t = int * int
let compare (a,b) (c,d) = a * d - b * c
end)
let ( -- ) = Int64.sub
let ( ** ) = Int64.mul
let ( // ) = Int64.div
let ( %% ) = Int64.rem
let ( !< ) = Int64.of_int
let ( !> ) = Int64.to_int
let rec gcd a b = if b = 0 then a else gcd b (a mod b)
let main () =
let rec loop_b4 set b1 a1 step4 b4 =
if b4 > 3776 then set else
let a4 = !> (450L ** !< (a1 * b4) // !< (2419 * b1)) in
let asum, bsum = a1 + a4, b1 + b4 in
let t5 = !< (6 * a1 * asum - 59 * b1 * bsum) ** !< (b1 * 59) in
let t6 = !< (b1 * b1) ** 3481L -- !< (a1 * a1) ** 30L in
if t5 %% t6 = 0L &&
let b2 = !> (t5 // t6) in
let a2 = 5 * a1 * b2 / (59 * b1) in
b2 > 0 && b2 <= 11328 && a2 > 0 && a2 <= 7872 then
let u = 41 * b1 in
let v = 5 * a1 in
let w = gcd u v in
FracSet.add (u / w, v / w) set
else loop_b4 set b1 a1 step4 (b4 + step4) in
let rec loop_a1 set b1 a1 =
if 5 * a1 >= 41 * b1 then set else
let btmp = 2419 * b1 in
let step4 = btmp / gcd btmp (450 * a1) in
let set = loop_b4 set b1 a1 step4 step4 in
loop_a1 set b1 (a1 + 1) in
let rec loop_b1 set b1 =
if b1 = 0 then set else
loop_b1 (loop_a1 set b1 1) (b1 - 1) in
loop_b1 FracSet.empty 640
let _ =
FracSet.iter (fun (a, b) -> Printf.printf "%d/%d\n" a b) (main ())Python:
import math, fractions
s = set()
for x in range(0, 200):
for y in range(0, 200):
for z in range(0, 200):
if x or y or z:
p1 = 181548*(x+y+z)
q1 = 59*(450*x+5310*y+2419*z)
g = fractions.gcd(p1, q1)
p1, q1 = p1 // g, q1 // g
p = int(math.sqrt(p1))
q = int(math.sqrt(q1))
if p ** 2 == p1 and q ** 2 == q1 and p > q:
g1 = fractions.gcd(p * x * 5, q * 41)
g2 = fractions.gcd(p * y * 59, q * 41)
g3 = fractions.gcd(p * z * 59, q * 90)
xp = p * x * 5 // g1
yp = p * y * 59 // g2
zp = p * z * 59 // g3
xq = q * 41 // g1
yq = q * 41 // g2
zq = q * 90 // g3
g = xq * yq // fractions.gcd(xq, yq)
g = g * zq // fractions.gcd(g, zq)
xp = xp * g // xq
yp = yp * g // yq
zp = zp * g // zq
if x * g <= 5248 and y * g <= 1312 + 2624 + 3936 and \
z * g <= 5760 and xp <= 640 and yp <= 1888 + 3776 + 5664 and \
zp <= 3776:
s.add((p, q))
print(len(s), max(s, key=lambda p: p[0] / p[1])) public class Problem236 {
private static int[] A_236={1312,5248,5760,2624,3936};
private static int[] B_236={1888,640,3776,3776,5664};
private static int A;
private static int B;
private static long nBest;
private static long dBest;
private static double xBest=0;
static
{
for (int i=0; i<A_236.length; i++)
{
A+=A_236[i];
}
for (int i=0; i<B_236.length; i++)
{
B+=B_236[i];
}
}
public static void problem236() //called by Main.main
{
for (int a1=1; a1<A_236[0]; a1++)
{
System.out.println("a1 "+a1);
for (int b1=1; b1<B_236[0]; b1++)
{
if (b1*A_236[0]>a1*B_236[0])
{
long gcd=Main.gcd(b1*A_236[0],a1*B_236[0]);
search(1,b1*A_236[0]/gcd,a1*B_236[0]/gcd, a1,b1);
}
}
}
System.out.println("BEST "+nBest+"/"+dBest);
}
public static void search(int pos, long num, long den, long suma, long sumb)
{
if ((double)num/den <=xBest)
{
return;
}
if (pos==A_236.length)
{
if (suma*B*den==sumb*A*num)
{
double x=(double)num/den;
if (x>xBest)
{
xBest=x;
nBest=num;
dBest=den;
System.out.print("RUNNING BEST ");
}
System.out.println("solution "+num+"/"+den+" ("+x+")");
}
}
else
{
long aBase=A_236[pos]*den;
long bBase=B_236[pos]*num;
long gcd=Main.gcd(aBase,bBase);
aBase/=gcd;
bBase/=gcd;
for (long aa=aBase, bb=bBase; aa<A_236[pos] && bb<B_236[pos]; aa+=aBase,bb+=bBase)
{
search(pos+1,num,den,suma+aa,sumb+bb);
}
}
}
}