Tävlingsprogrammering/Uppgifter/Valutaväxling

Valutaväxling

Den välkända banken Dumbank har nyligen öppnat en ny tjänst för sina kunder. Tjänsten är en valutaväxlingstjänst där kunden stoppar in sina pengar i kronor, och därefter växlar sina insatta pengar mot andra valutor. Välkänt är att det sällan är lönt att växla sina pengar fram och tillbaka mellan två valutor, men det Dumbank förbisåg är att man kan, om man är listig, växla runt sina pengar mellan flera olika valutor och till sist tillbaka till kronor och sluta med mer pengar än man hade från början.

Efter att ha haft sin tjänst i drift ett tag har Dumbank börjat inse att det går att fiffla med deras system och har därför valt att stänga ner tjänsten om D dagar. Dessutom införde de begränsningen att man bara kan växla pengar en gång per dag.

Du har precis hört talas om denna banktjänst och bestämmer dig för att utnyttja den. Tjänsten tillåter växling mellan N olika valutor numrerade från 1 till N där svenska kronor är nummer 1. Du känner till växlingskurserna mellan alla par av valutor, som dessutom är oförändrade under de D dagar som tjänsten har öppet. Växlingskursen K[i][j] är ett reellt tal som anger hur mycket du kommer ha i valuta j om du växlar in en enhet av valuta i. Om vi exempelvis antar att valuta 2 är amerikanska dollar, så skulle K[2][1] vara cirka 7 med dagens penningvärde.

Skriv ett program som beräknar vad du som mest kan tjäna om du sätter in dina besparingar (i svenska kronor) dag 1. Du hinner därmed som mest göra D växlingar. Efter den sista växlingen måste dina pengar vara i svenska kronor igen.

Indata

Första raden i filen dumbank.dat innehåller två heltal, N (2 ≤ N ≤ 100) och D (2 ≤ D ≤ 100). Därefter följer N rader med N tal som anger växlingkurserna, där tal j på rad i motsvarar K[i][j]. Växlingkurserna är reella tal med en noggrannhet på som mest 4 decimaler. Talen i diagonalen, K[i][i], kommer alltid vara 1.

Utdata

Skriv ut den faktor med vilket du som mest kan växla upp dina insatta pengar, med minst fyra decimaler. Små avrundningsfel är tillåtna.

Exempel

4 6
1 1.2 0.001 0.001
0.001 1 1.2 0.001
0.001 0.001 1 1.2
1.2 0.001 0.001 1

Svar

2.0736

Extra exempel

7 13
1.0000 4.3515 0.4617 0.5947 0.7079 0.6761 1.1220
0.2368 1.0000 0.1082 0.1408 0.1676 0.1617 0.2630
2.2096 9.4259 1.0000 1.3011 1.5488 1.5088 2.4793
1.7497 7.3168 0.7998 1.0000 1.2023 1.1829 1.9055
1.4553 6.0256 0.6457 0.8318 1.0000 0.9645 1.6007
1.5392 6.3096 0.6828 0.8797 1.0682 1.0000 1.6762
0.9002 3.8019 0.4115 0.5301 0.6373 0.6026 1.0000

Svar

1.41715

Lösning

Förklaring kommer snart.

Lösning i Java.

import java.util.*;
import java.io.*;

public class Dumbank
{
	//Orka fånga exceptions. Vi är lata och säkra på vår sak.
	public static void main(String [] klein) throws FileNotFoundException
	{
		//Vi ska läsa av filen dumbank.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\dumbank.dat"));

		//Antalet valutor.
		int N = scan.nextInt();

		//Antalet dagar.
		int D = scan.nextInt();

		//Sparar växlingskurserna.
		float [][] change = new float [N][N];

		//Läser in växlingskurserna.
		for(int i = 0; i<N; i++)
		{
			for(int j = 0; j<N; j++)
			{
				//Vi läser in på det här lite alternativa sättet ifall
				//det skulle råka stå 1 istället för 1.0.
				change[i][j] = Float.parseFloat(scan.next());
			}
		}

		//Lagrar den bästa ration för en valuta "so far".
		//Dvs den bästa vägen från en valuta i till valutan 0 (kronor).
		float [] ratio = new float [N];

		//På den sista dagen måste vi hoppa tillbaka till kronor
		//och eftersom vi vandrar baklänges så är det där vi börjar.
		for(int i = 0; i<N; i++)
		{
			ratio[i] = change[i][0];
		}

		//Då har vi använt oss av en dag.
		int dag = D - 1;

		//Så länge vi har dagar kvar.
		while(dag>0)
		{
			//Mellanlagrar den bästa ration för en valuta.
			float [] copy = new float [N];

			//Räknar ut den bästa vägen vi kan ta från en valuta i.
			for(int i = 0; i<N; i++)
			{
				//Sparar det hittills bästa resultatet.
				float best = 0f;

				//Testar att gå från denna valuta i till en valuta j.
				for(int j = 0; j<N; j++)
				{
					//Går från valuta i till j.
					float tmp = ratio[j]*change[i][j];

					//Om denna väg var bättre än tidigare bästa så...
					if(tmp>best) best = tmp;
				}

				//Sparar den bästa vägen för valuta i.
				copy[i] = best;
			}

			//Nu har vi en ny bästa väg för respektive valuta.
			ratio = copy;

			//En dag har gått.
			dag--;
		}

		//Skriver ut svaret. (Dvs den bästa vägen från valuta 0 till valuta 0.)
		System.out.println("Bästa ratio: " + ratio[0]);
	}
}