Tävlingsprogrammering/Uppgifter/Olikheter

Mall:Proguppgift

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} ⟺ a d < b c$

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} ⟺ \frac{A_{1} B}{A_{2}} < b$

$\frac{b}{B} < \frac{c}{C} ⟺ \frac{b C}{B} < c$

$\frac{c}{C} < \frac{d}{D} ⟺ \frac{c D}{C} < d$

$\frac{d}{D} < \frac{E_{1}}{E_{2}} ⟺ 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]]

Tävlingsprogrammering/Uppgifter/Olikheter

Lösning

Navigeringsmeny

Sök