Tävlingsprogrammering/Uppgifter/Samla mat

Samla mat

En seriös strategispelare vet hur viktigt det är att samla tillräckligt med mat till en armé innan en invation ska genomföras. Därför har du bestämt dig för att samla ihop en viss mängd mat till dina trupper.

Från början har du ett visst antal bönder. I varje rond kan varje bonde samla ihop en enhet mat. Efter varje rond kan du sälja en viss mängd mat och köpa en ny bonde. Du kan köpa så många bönder du vill, så länge du har tillräckligt med mat att betala med. Skriv ett program som beräknar det minsta antalet ronder du måste samla mat för att nå upp till den mängd mat du behöver. Alla värden i indatat kommer vara mellan 1 och 1000.

Körningsexempel:

Mängd mat du behöver ? 10 
Antal bönder från början ? 2 
Kostnad för att köpa bonde ? 1 
Det tar 4 ronder. 

Kommentar: Notera att det skulle ta 5 ronder om du inte köpte några bönder. En bättre strategi är att köpa en bonde efter rond 1. Efter rond 1 kommer du då att ha 1 enhet mat, därefter 4 enheter, sedan 7 och slutligen 10.

Lösning

Att testa alla kombinationer av bondköp är omöjligt för de större testfallen, men man kan använda sig av dynamisk programmering. För varje rond sparar man hur mycket mat man maximalt kan ha för varje möjligt antal bönder man har köpt. I nästa rond räknar man enkelt ut hur mycket mat som genereras för varje antal bönder. Därefter testar man att köpa nya bönder. Problemet underlättas av att det alltid är bra att köpa bönderna så tidigt som möjligt (eftersom de då hinner generera mer). Det är alltså bara om man redan har maximalt antal bönder som det kan vara aktuellt att köpa nya bönder.

#include <stdio.h>

int main() {
  int goal,start,f[10000],mb,t,i,cost;
  scanf("%d %d %d", &goal, &start,&cost);
  mb=0;   //Max antal bönder man kan ha köpt
  f[0]=0;  //f[x]: maximal mängd mat om man köpt x bönder
  t=0;
  while(1){
    t++;
    for(i=0;i<=mb;i++) f[i]+=i+start;  //Varje bonde genererar en enhet mat
    for(i=1;i<=f[mb]/cost;i++) f[mb+i]=f[mb]-i*cost;   //Köp bönder, upp till så många det går
    mb+=f[mb]/cost;    //Öka maxantalet bönder
    for(i=0;i<=mb;i++) if(f[i]>=goal) {     //Kolla om vi uppnått målet för något antal bönder
        printf("Det tar %d ronder\n", t);
        return 0;
      }
  }  
}

Lösning i Java som bygger på idén att det alltid är smart att köpa maximalt antal bönder om antalet rundor det kommer att ta för att uppnå målet med nuvarande antal bönder är strikt större än kostnaden för en bonde.

import java.util.*;

public class Bonde
{
	static int cost = 1; //Kostnaden för en bonde.
	static int min = 0; //Minimala antalet rundor/ronder.
	static int mat = 10; //Mat att uppnå.
	static int have = 0; //Mat jag har för tillfället.
	static int pes = 0; //Bönder. Pes = Peasant.

	//Retunerar hur många rundor det kommer att ta för
	// att uppnå målet med nuvarande antal bönder.
	public static int turnsLeft()
	{
		int foodLeft = mat - have;
		float turnsLeft = (float)foodLeft/pes;

		//3.33 (10/3) t.ex. tar ju 4 ronder.
		return (int)Math.ceil(turnsLeft);
	}

	//Metod för att köpa en bonde.
	public static void buyPes()
	{
			have -= cost;
			pes++;
	}

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

		System.out.print("Mängd mat du behöver: ");
		mat = scan.nextInt();

		System.out.print("Antal bönder från början: ");
		pes = scan.nextInt();

		System.out.print("Kostnad för att köpa bonde: ");
		cost = scan.nextInt();

		//Håller på tills vi uppnått målet.
		while(have<mat)
		{
			have += pes; //Vi får mat.

			if(turnsLeft()>cost)
			{
				//Köper max antal bönder.
				while(have>=cost) buyPes();
			}

			min++;
		}

		//Skriver ut svaret.
		System.out.println("Det tar " + min + " ronder.");
	}
}