Tävlingsprogrammering/Uppgifter/Kortblandare
Kortblandare
En kortblandare är en maskin som blandar en kortlek slumpmässigt. En dålig (men tyvärr vanlig) design av en sådan maskin fungerar som följer: Maskinen slumpar fram ett heltal M mellan 1 och MAX. Därefter utförs M stycken identiska blandoperationer (“rifflingar”). En blandoperation innebär att korten permuteras (kastas om) på ett visst sätt. Permutationen är kodad i maskinen och kan inte ändras. Efter att de M blandoperationerna utförts delas korten ut till spelarna. Varje spelare får K stycken kort.
En ohederlig spelare har lyckats ta reda på hur maskinen fungerar, och känner således till blandpermutationen och talet MAX. Han har dessutom identifierat vilka K kort han helst vill ha. Innan kortleken läggs in i blandaren kan han ordna korten som han vill. Bestäm hur han bäst ska ordna korten för att få så många av de K korten han vill ha. Programmet ska skriva ut det antal kort han kan förvänta sig att få, i snitt, om han ordnar dem på bästa sätt.
Första raden i filen kort.dat innehåller tre heltal: N (antal kort i kortleken, mellan 10 och 52), talet MAX (mellan 1 och 1000) och K (mellan 1 och N). Därefter följer en rad med N heltal (mellan 1 och N) som anger maskinens blandpermutation. Det i:te talet i denna rad anger var kortet på plats i kommer att hamna efter att en blandoperation utförts. Därefter följer en rad med K heltal som anger vilka kort spelaren kommer att få, där 1 innebär att han kommer få det första kortet i leken efter att den blandats o.s.v.
Programmet ska skriva ut det förväntade antalet önskade kort som spelaren kan få om han preparerar leken på bästa sätt. Svaret ska vara korrekt med minst 3 decimalers noggrannhet.
Körningsexempel: Filen kort.dat med innehållet
10 3 4 2 3 4 5 6 7 8 9 10 1 1 3 5 6
ska ge svaret
Förväntat antal kort: 2.667
Förklaring: Varje blandning förskjuter korten ett steg bakåt i leken (det sista kortet placeras överst). Genom att preparera leken så att de fyra önskade korten initialt befinner sig på position 2, 3, 4 och 10 uppnås det bästa resultatet. Beroende på hur talet M väljs av maskinen kommer de önskade korten antingen hamna på position (3, 4, 5, 1), (4, 5, 6, 2) eller (5, 6, 7, 3). I snitt fås därför (3 + 2 + 3) / 3 av de önskade korten.
Lösning
[redigera]Allt vi behöver veta är att förväntade antalet önskade kort på en delning är summan av de gånger de K korten som kommer upp mest av alla permutationer av händer man kan få, genom antalet permutationer av händer.
Algoritmen:
Sätt upp en tabell och skriv ut alla permutationer från 1 till MAX.
2 3 4 5 6 7 8 9 10 1
3 4 5 6 7 8 9 10 1 2
4 5 6 7 8 9 10 1 2 3
Vi behöver bara bry oss om de kort vi får; dessa är första, tredje, femte och sjätte:
2 4 6 7
3 5 7 8
4 6 8 9
Det är dessa kort vi alltid kommer att få om vi spelar med denna sorteringsalgoritm. Därför är det klokast och i vårt intresse att de mest frekventa av dessa är de kort vi vill ha.
Vi ställer upp en frekvenstabell.
2: 1
3: 1
4: 2
5: 1
6: 2
7: 2
8: 2
9: 1
Vi har fyra kortpositioner att manipulera. Vi ser direkt att 4, 6, 7 och 8 är de kortpositioner vi vill ha. De uppkommer alltså 2+2+2+2 = 8 gånger totalt på alla permutationer.
Alltså blir antalet förväntade kort på en slumpmässig permutation (2+2+2+2)/MAX = 1.666... där MAX är antalet permutationer.
En lösning i C++ som nyttjar map och pair:
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
int main() {
int N, MAX, K;
std::cin >> N >> MAX >> K;
int p[N];
int a[N][2];
for (int i = 0; i < N; ++i) {
a[i][0] = 0;
a[i][1] = i+1;
std::cin >> p[i];
--p[i];
}
int Kort[K];
for (int i = 0; i < K; ++i) {
std::cin >> Kort[i];
--Kort[i];
}
std::map<int, int> bst;
int iOne = 0;
for (int i = 0; i < MAX; ++i) {
int iTwo = (iOne+1)%2;
for (int j = 0; j < N; ++j) {
a[j][iOne] = a[p[j]][iTwo];
}
for (int i = 0; i < K; ++i) {
++bst[a[Kort[i]][iOne]];
}
iOne = iTwo;
}
std::vector<std::pair<int, int> > vpTemp(N);
int index = 0;
for (std::map<int, int>::iterator it = bst.begin(); it != bst.end(); ++it) {
vpTemp[index].first = it->second;
vpTemp[index].second = it->first;
++index;
}
std::sort(vpTemp.begin(), vpTemp.end());
double nSum = 0;
std::vector<std::pair<int, int> >::reverse_iterator it = vpTemp.rbegin();
for (int i = 0; i < K; ++i) {
nSum += (it->first);
++it;
++index;
}
std::cout << (nSum) / double (MAX) << '\n';
return 0;
}
Lösningsexempel i Java. Istället för att gå från start till mål, så går vi från mål till start. Vi börjar med att markera de positioner som vi vill att korten ska sluta på. Sedan utför vi inverterade rifflingar (i exemplet i uppgiftstexten hade det varit att flytta alla kort ett steg åt vänster). Efter det att vi har utfört en inverterad riffling, så har vi flyttat de markerade positionerna så att de nu markerar de optimala startpositionerna om kortblandaren skulle besluta sig för att utföra bara en (vanlig) riffling. Sedan utför vi en till inverterad riffling och då har vi markerat de startpositioner som är optimala om kortblandaren skulle besluta sig för att utföra två (vanliga) rifflingar. Sedan fortsätter vi att utföra inverterade rifflingar upp till MAX gånger och så behöver vi bara spara hur många gånger en viss startposition varit optimal/gynnsam (vilket görs efter en inverterad riffling).
Nu behöver vi bara leta upp de K startpositioner som har varit optimala flest gånger. Och det fiffiga är att vi redan vet hur många gånger vardera position kommer att generera ett önskat kort (det har vi ju redan tagit reda på och sparat), så vi behöver bara sortera positionerna och välja de K bakersta korten, addera ihop hur många önskade kort de kommer att generera och slutligen dela summan med MAX (då kommer vi att få genomsnittstalet).
import java.util.*;
import java.io.*;
public class Kortblandare
{
//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 kort.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\kort.dat"));
//Antalet kort.
int N = scan.nextInt();
//Max antal rifflingar man får utföra.
int max = scan.nextInt();
//Antalet kort spelaren ska få.
int K = scan.nextInt();
//Hur blandpermutationen ser ut.
int [] permutation = new int [N];
//Den inverterade blandpermutationen.
int [] inverted = new int [N];
//Läser in permutationen.
for(int i = 0; i<N; i++)
{
//Kort 3 svarar t.ex. mot index 2 (därav -1).
//Kort i ska flyttas till?
permutation[i] = scan.nextInt()-1;
//För den inverterade är det tvärtom.
inverted[permutation[i]] = i;
}
//Array i vilken vi markerar vilka kort vi
// kommer att få, alltså där vi vill att våra
// önskade kort ska hamna efter alla blandningar.
boolean [] desired = new boolean [N];
//Läser in vilka kort vi kommer att få/vill ha.
for(int i = 0; i<K; i++)
{
desired[scan.nextInt()-1] = true;
}
//Array i vilken vi markerar hur många gånger en
// viss startposition slutar på en önskad plats.
int [] count = new int [N];
//Vi startar på slutpositionen och utför därfirån
// max antal inverterade rifflingar.
for(int i = 0; i<max; i++)
{
//Att flytta över korten till en ny array är lättast.
boolean [] tmp = new boolean [N];
//Utför en inverterad riffling.
for(int j = 0; j<N; j++)
{
//Kortet på plats j befann sig tidigare på platsen
// inverted[j] innan rifflingen.
tmp[inverted[j]] = desired[j];
}
//Såhär såg kortleken ut innan riffling nummer (max-i).
desired = tmp;
//Om detta var antalet rifflingar som kortblandaren
// skulle utföra, då har vi markerat de startpositioner
// som ger oss de önskade korten i slutändan för detta antal.
for(int j = 0; j<N; j++)
{
//Denna position gav oss ett av våra önskade kort för
// detta antal (i+1) rifflingar.
if(desired[j]) count[j]++;
}
}
//Sorterar de markerade positionerna (de bästa/största hamnar längst bak).
Arrays.sort(count);
//Summan av antalet gynnsamma kort positionerna kan generera för
// alla olika antal rifflingar.
float sum = 0;
//Vi är intresserade av de K sista positionerna.
// (De positioner som gav flest gynnsamma kort i slutändan.)
for(int i = N-1; i>N-1-K; i--)
{
sum += count[i];
}
//Skriver ut svaret.
System.out.println("Förväntat antal kort: " + (sum/max));
}
}