Tävlingsprogrammering/Uppgifter/Olikheter

Olikheter

På hur många sätt kan följande olikhet satisfieras?

${\frac {A_{1}}{A_{2}}}<{\frac {?}{B}}<{\frac {?}{C}}<{\frac {?}{D}}<{\frac {E_{1}}{E_{2}}}$

där A₁, A₂, B, C, D, E₁, E₂ alla är givna heltal mellan 1 och 1000 och ? ska ersättas med heltal. Svaret ryms alltid i ett 64-bitars heltal.

Exempel 1

A1 ? 14
A2 ? 5
B ? 1
C ? 9
D ? 7
E1 ? 10
E2 ? 3

Svar

Antal lösningar: 3

Förklaring: Här är lösningarna utskrivna:

${\frac {14}{5}}<{\frac {3}{1}}<{\frac {28}{9}}<{\frac {22}{7}}<{\frac {10}{3}}$

${\frac {14}{5}}<{\frac {3}{1}}<{\frac {28}{9}}<{\frac {23}{7}}<{\frac {10}{3}}$

${\frac {14}{5}}<{\frac {3}{1}}<{\frac {29}{9}}<{\frac {23}{7}}<{\frac {10}{3}}$

Exempel 2

A1 ? 1
A2 ? 5
B ? 4
C ? 3
D ? 2
E1 ? 5
E2 ? 1

Svar

Antal lösningar: 369

Exempel 3

A1 ? 900
A2 ? 950
B ? 900
C ? 950
D ? 980
E1 ? 950
E2 ? 900

Svar

Antal lösningar: 177631

Lösning

Här gäller det att känna till det elfte budordet "Du skall icke jämföra flyttal", samt hur man bör jämföra bråk. D.v.s:

${\frac {a}{b}}<{\frac {c}{d}}\iff ad<bc$

förutsatt att samtliga tal är positiva.

Kalla de okända talen för b, c och d.

${\frac {A_{1}}{A_{2}}}<{\frac {b}{B}}<{\frac {c}{C}}<{\frac {d}{D}}<{\frac {E_{1}}{E_{2}}}$

${\frac {A_{1}}{A_{2}}}<{\frac {b}{B}}\iff {\frac {A_{1}B}{A_{2}}}<b$

${\frac {b}{B}}<{\frac {c}{C}}\iff {\frac {bC}{B}}<c$

${\frac {c}{C}}<{\frac {d}{D}}\iff {\frac {cD}{C}}<d$

${\frac {d}{D}}<{\frac {E_{1}}{E_{2}}}\iff d<{\frac {E_{1}D}{E_{2}}}$

Vilket genererar följande kodsnutt.

long sum = 0;

for(int b = A1*B/A2 + 1; b*E2<B*E1; b++)
for(int c = b*C/B + 1; c*E2<C*E1; c++)
for(int d = c*D/C + 1; d*E2<D*E1; d++)
sum++;

Man inser ganska snabbt att den kan förenklas till följande:

long sum = 0;

int tod = D*E1/E2;
//Om divisionen går jämnt ut måste termen justeras.
if(D*E1%E2==0) tod--;

for(int b = A1*B/A2 + 1; b*E2<B*E1; b++)
for(int c = b*C/B + 1; c*E2<C*E1; c++)
sum += tod - c*D/C;

Här skulle man kunna tro att man kan ersätta den inre loopen med någon form av aritmetisk summa, men det kommer inte ge samma resultat då avrundningen kommer att bli annorlunda. Men vi kan konstatera att vi beräknar stora delar av den inte loopen flera gånger om och om igen. Så varför komplicera till det? Vi kör lite dynamisk programmering och beräknar summan från respektive värde mellan 0 och C*E1/E2 upp till C*E1/E2.

Slutligen landar vi i följande program.

import java.util.*;

public class Olikheter
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("A1 ? ");
		int A1 = scan.nextInt();

		System.out.print("A2 ? ");
		int A2 = scan.nextInt();

		System.out.print("B ? ");
		int B = scan.nextInt();

		System.out.print("C ? ");
		int C = scan.nextInt();

		System.out.print("D ? ");
		int D = scan.nextInt();

		System.out.print("E1 ? ");
		int E1 = scan.nextInt();

		System.out.print("E2 ? ");
		int E2 = scan.nextInt();

		long sum = 0;

		final int tod = D*E1%E2==0 ? D*E1/E2-1 : D*E1/E2;
		final int toc = C*E1%E2==0 ? C*E1/E2-1 : C*E1/E2;

		long [] cp = new long [toc+2];

		for(int c = toc; c>=0; c--) cp[c] = cp[c+1] + tod - c*D/C;

		for(int b = A1*B/A2 + 1; b*E2<B*E1; b++)
		{
			sum += cp[b*C/B + 1];
		}

		System.out.println("\nAntal lösningar: " + sum);
	}
}

En elegant lösning i Haskell (av Anton Fors Hurdén):

l a b c = quot (a * b) c + 1

u a b c = q - if r == 0 then 1 else 0
	where (q, r) = quotRem (a * b) c

main = do
	a1 <- readLn
	a2 <- readLn
	b <- readLn
	c <- readLn
	d <- readLn
	e1 <- readLn
	e2 <- readLn
	print $ sum [1 | x <- [l a1 b a2..u e1 b e2], y <- [l x c b..u e1 c e2], z <- [l y d c..u e1 d e2]]