Tävlingsprogrammering/Uppgifter/Tårtrester
Tårtrester
Festen är över. På bordet finns ett antal tallrikar. En del är fulla med tårta, andra är halvfulla eller tomma. De tre värdarna ska till att börja diska efter festen. De ska diska lika många tallrikar var och dessutom vill de ha lika mycket av den överblivna tårtan utan att för den skull flytta tårta mellan tallrikarna.
Om vi till exempel antar att det finns 3 tomma, 6 halvfulla och 9 fulla tallrikar kan de delas upp så här:
| Tomma | Halvfulla | Fulla | |
| Värd 1 | 0 | 4 | 2 |
| Värd 2 | 1 | 2 | 3 |
| Värd 3 | 2 | 0 | 4 |
Som vi ser får alla 6 tallrikar var att diska. Totalt får de också 4 fulla tallrikar tårta var. Ett annat godkänt sätt vore att alla fick 1 tom, 2 halvfulla och 3 fulla tallrikar.
Skriv ett program som frågar efter antalet tallrikar av varje typ och som presenterar en lösning på hur de ska fördelas. Du kan utgå ifrån att det finns minst en lösning. Om det finns flera lösningar räcker det med att ditt program ger en av dessa. Antalet tallrikar av varje typ kommer att vara mellan 0 och 1000.
Körningsexempel:
Antal tomma ? 1 Antal halvfulla ? 7 Antal fulla ? 7 Värd1 -> T:0 H:3 F:2 Värd2 -> T:0 H:3 F:2 Värd3 -> T:1 H:1 F:3
Lösning
redigeraHär ser vi ett typiskt problem som går ut på att pröva de möjliga kombinationerna. För stora indata ser vi snabbt att detta naiva första angrepp skulle leda till exekveringstiden O(2^N). Lyckligtvis så kan vi begränsa antalet kombinationer genom att inse att för att det ska finnas en lösning:
1. Att antalet tallrikar måste vara delbart med tre.
2. Att antalet tårthalvor måste vara delbart med tre.
Tårthalvor är ett begrepp som vi inför för att förenkla problemet så att vi slipper decimaltal.
Nedan följer en lösning i C++ som skriver ut lösningen på brödsmulesätt:
#include <cstdio>
bool Search(const int& nDepth, const int& nEmpty, const int& nHalf
, const int& nFull, const int& nSumPlates, const int& nSumCake) {
if (nDepth == 2) {
if (nEmpty + nHalf + nFull == nSumPlates && nHalf + 2*nFull == nSumCake) {
printf("Värd %d. -> T:%d H:%d F:%d\n", 3-nDepth, nEmpty, nHalf, nFull);
return true;
} else {
return false;
}
}
for (int i = 0; i < nHalf; ++i) {
for (int j = 0; j < nFull; ++j) {
int k = nSumPlates - i -j;
if (k >= 0 && k <= nEmpty && i + j*2 == nSumCake) {
if (Search(nDepth+1, nEmpty-k, nHalf-i, nFull-j, nSumPlates, nSumCake)){
printf("Värd %d. -> T:%d H:%d F:%d\n", 3-nDepth, k, i, j);
return true;
}
}
}
}
}
int main() {
int nEmpty, nHalf, nFull;
scanf("%d %d %d", &nEmpty, &nHalf, &nFull);
Search(0, nEmpty, nHalf, nFull, (nEmpty+nHalf+nFull)/3, (nHalf + nFull*2)/3);
return 0;
}
En iterativ lösning i Java, som utnyttjar det faktum att det alltid finns en lösning. Lösningen går till på så sätt att man börjar med att plocka så många fulla tallrikar man kan (vi kan se det som att en värd är girig och tar de bästa tallrikarna först), sedan när man upptäcker att man har rätt mängd tårta (en tredjedel av det totala), men inte rätt antal tallrikar (en tredjedel av alla tallrikar) så kommer bakslaget och den giriga värden får börja plocka tomma tallrikar.
Om det skulle vara så att det inte finns några tomma tallrikar (och här kommer utnyttjandet av att en lösning finns) kvar, så får värden kasta bort en full tallrik och ta två halva istället (de andra två värdarna stirrar ilsket på honom, så han känner sig tvingad). Nu kan man kanske tänka sig att det är möjligt att de halva tallrikarna är slut, men om det finns en lösning och den föregående värden försökte plocka så många fulla tallrikar som möjligt, ja då måste det finnas halva tallrikar kvar.
Jag antar att lösningen kan sammanfattas i följande tre punkter:
- Om det finns en lösning, så kan värd 1 plocka rätt antal tallrikar och rätt mängd tårta.
- Om värd 1 har plockat rätt antal tallrikar och rätt mängd tårta, så kan värd 2 plocka rätt antal tallrikar och rätt mängd tårta.
- Om värd 2 har plockat rätt antal tallrikar och rätt mängd tårta, så måste det som blir över också vara rätt antal tallrikar och rätt mängd tårta.
import java.util.*;
public class Cake
{
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal tomma: ");
int tomma = scan.nextInt();
System.out.print("Antal halvfulla: ");
int halva = scan.nextInt();
System.out.print("Antal fulla: ");
int fulla = scan.nextInt();
//Antalet tallrikar varje värd ska ha.
int antal = (tomma+halva+fulla)/3;
//Hur mycket tårta (mätt i tårthalvor) varje värd ska ha.
int cake = (halva+fulla*2)/3;
//De tre värdarna.
//[i][0] = Hur mycket tårta värden har för tillfället.
//[i][1] = Hur många tomma tallrikar värden har.
//[i][2] = Hur många halvfulla tallrikar värden har.
//[i][3] = Hur många fulla tallrikar värden har.
int [][] host = new int [3][4];
//För varje värd.
for(int i = 0; i<3; i++)
{
//Håller på tills vi har rätt antal tallrikar och mängd tårta.
//Egentligen behövs inte den andra kollen eftersom vi aldrig
// kommer att uppnå rätt antal tallrikar innan rätt mängd tårta.
while(host[i][1]+host[i][2]+host[i][3]!=antal || host[i][0]!=cake)
{
//Om vi har rätt mängd tårta.
if(host[i][0]==cake)
{
//Och kan ta en tom tallrik.
if(tomma>0)
{
//Ja då tar vi en tom tallrik.
host[i][1]++;
tomma--;
}
else //Om de tomma tallrikarna är slut.
{
//Ja då finns det inget annat sätt än att försaka en
// full tallrik och ta två halva för att behålla rätt
// mängd tårta och öka antalet tallrikar.
//Ger bort en full tallrik.
host[i][3]--;
fulla++;
//Tar två halva. Detta kan kännas farligt, men om det finns
// en lösning, så måste denna handling vara tillåten.
host[i][2] += 2;
halva -= 2;
}
} //Om vi får och kan ta en full tallrik, så bör vi göra det.
else if(host[i][0]<cake-1 && fulla>0)
{
//En full tallrik ökar antalet halvor med 2.
host[i][0] += 2;
host[i][3]++;
fulla--;
}
else if(halva>0) //Om vi inte kunde ta en full, så får vi ta en halv.
{
//Och nej vi kommer inte hamna i ett dödläge med för många halva
// tallrikar, eftersom vi alltid försöker ta fulla först.
host[i][0]++;
host[i][2]++;
halva--;
}
}
}
//Sparar svaren.
String host1 = "Värd1 -> T:" + host[0][1] + " H:" + host[0][2] + " F:" + host[0][3];
String host2 = "Värd2 -> T:" + host[1][1] + " H:" + host[1][2] + " F:" + host[1][3];
String host3 = "Värd3 -> T:" + host[2][1] + " H:" + host[2][2] + " F:" + host[2][3];
//Skriver ut svaret.
System.out.println("\n" + host1 + "\n" + host2 + "\n" + host3);
}
}