Tävlingsprogrammering/Uppgifter/Börsen

Börsen

Evelina vill bli rik och tänker börja spekulera på börsen. Egentligen är hon dock rätt ointresserad av ekonomi och orkar aldrig läsa mer än den första aktiekursen i tidningen. Men, tänker hon, det är ni andra som krånglar till det. Om man bara köper och säljer i rätt lägen kan man ju lika väl tjäna pengar på detta enda företag, som vi kan kalla A. Genom att ständigt fråga sina vänner hur mycket fiskbullar de äter lär hon sig att förutsäga exakt hur A:s aktiekurs kommer att variera under N dagar framåt. Skriv ett program som beräknar hur mycket pengar hon har i slutet av denna period om hon hade 100 kronor från början och investerar optimalt. Hon kan aldrig låna pengar utan endast använda sina egna.

Aktiekursen uppdateras en gång om dagen och är densamma för köp och försäljning. Varje dag kan Evelina antingen köpa valfri mängd aktier, sälja valfri mängd aktier eller inte göra någonting. Mängden hon köper eller säljer behöver inte vara ett heltal. För varje transaktion hon gör måste hon betala en fast avgift. Avgiften betalas med kontanter, d.v.s. innan hon köper aktier måste hon först betala avgiften, och efter att hon har sålt aktier måste hon betala avgiften.

Indata

På första raden står ett heltal N (2 ≤ N ≤ 100000), antalet dagar. På andra raden står ett flyttal Q (0 ≤ Q ≤ 100), avgiften i kronor per transaktion. Därefter följer N rader med vardera ett flyttal, aktiekursen för dag 1, dag 2, o.s.v., t.o.m. dag N. Kursen ligger alltid mellan 1 och 1000 kr per aktie.

Utdata

En rad med ett flyttal X som anger hur mycket kontanter (inte aktier) Evelina maximalt kan ha efter N dagar. Svaret kan anges med godtyckligt antal decimaler, men ska ha ett relativt fel (felet dividerat med det rätta svaret) som är mindre än 10^-5. Observera att hon inte är tvungen att handla några aktier (alltså gäller X ≥ 100). I samtliga testfall kommer X vara under en miljon.

Exempel: Indata

6 2.3 75.6 86.2 83.1 91.3 72.5 95.7

Exempel: Utdata

147.3742

Exempel: Förklaring

Dag 1 köper hon 1.29233 aktier för alla sina pengar. Dag 4 säljer hon alltihop och får tillbaka 115.689 kr. Dag 5 köper hon på nytt aktier för alla sina pengar och får 1.56399 stycken, som hon slutligen säljer dag 6.

Lösning

Här gäller det att inse att det aldrig kan vara fördelaktigt att ha både aktier och pengar. Antingen går börsen upp och då vill hon ju givetvis ha allt i aktier, eller så går börsen ner och då vill hon ha allt i pengar. Enda anledningen att ibland inte följa dessa "greedy"-regler är att undvika kostnaden för en extra transaktion, och att i det läget göra en deltransaktion som kostar lika mycket är givetvis vansinnigt.

Sålunda kan vi för varje dag hålla reda på det största beloppet hon kan ha om hon för tillfället har aktier, samt det största beloppet hon kan ha om hon för tillfället har pengar. För varje dag prövar du att göra transaktioner i båda riktningarna och jämför med det belopp hon har om hon inte gör någonting. Detta är en mycket enkelt exempel på den algoritm som kallas Dynamisk programmering. Du är inte intresserad av vad som hänt innan, utan du kan sammanfatta hela situationen med hjälp av optimalvärden för ett begränsat antal "states", i det här fallet bara två stycken: "hon har aktier" och "hon har pengar".

Lösning i C:

#include <stdio.h>

double max(double p, double q) {return p>q?p:q;}

int main() {
  int N,i;
  double z[100000],money,stock,m,s,fee;
  scanf("%d %lf", &N, &fee);
  for(i=0;i<N;i++) scanf("%lf", &z[i]);
  money=100.0;
  stock=0.0;
  for(i=0;i<N;i++) {
    s=max(stock, (money-fee)/z[i]);
    m=max(money, stock*z[i]-fee);
    stock=s;
    money=m;
  }
  printf("%f\n", money);
  return 0;
}