#include <stdlib.h>
#include <string.h>

typedef struct {
  long double hitChance;
  unsigned char maxDamage;
  unsigned char hitPoints;
} PlayerInfo;

typedef struct {
  long double win;
  long double lose;
  long double draw;
} Odds;

const Odds error = {0, 0, 0};

static void turnsOdds(unsigned char, long double *, long double **, unsigned *, long double);
static void hitsOdds(unsigned char, long double, long double *);
static void multiplyVector(long double *, long double *, long double);
static void addVector(long double *, long double *);
static long double totalOdds(long double *);
static long double currentError(long double *, unsigned char);
static void expand(long double **, unsigned, unsigned);
static Odds calculateFor(long double *, long double *, unsigned);

Odds calculateOdds (PlayerInfo p1, PlayerInfo p2, long double threshold) {
  unsigned t1, t2;
  long double * odds1;
  long double * odds2;
  long double hitodds1[12];
  long double hitodds2[12];
  unsigned turns;
  if ((p1.hitChance < 0) || (p1.hitChance > 1)) return error;
  if ((p2.hitChance < 0) || (p2.hitChance > 1)) return error;
  if ((!p1.maxDamage) || (p1.maxDamage > 11)) return error;
  if ((!p2.maxDamage) || (p2.maxDamage > 11)) return error;
  if (p1.hitPoints > 99) return error;
  if (p2.hitPoints > 99) return error;
  if ((threshold <= 0) || (threshold >= 1)) return error;
  hitsOdds(p1.maxDamage, p1.hitChance, hitodds1);
  hitsOdds(p2.maxDamage, p2.hitChance, hitodds2);
  turnsOdds(p2.hitPoints, hitodds1, &odds1, &t1, threshold);
  turnsOdds(p1.hitPoints, hitodds2, &odds2, &t2, threshold);
  if (t1 < t2) {
    expand(&odds1, t1, t2);
    turns = t2;
  } else if (t2 < t1) {
    expand(&odds2, t2, t1);
    turns = t1;
  } else
    turns = t1;
  Odds result = calculateFor(odds1, odds2, turns);
  free(odds1);
  free(odds2);
  long double totalError = 1;
  totalError -= result.win;
  totalError -= result.lose;
  totalError -= result.draw;
  if ((totalError * totalError) > (threshold * threshold * 10)) return calculateOdds(p1, p2, threshold / 10);
  result.draw += totalError;
  return result;
}

static void turnsOdds (unsigned char opponentHP, long double * hitOdds, long double ** result, unsigned * resultSize, long double threshold) {
  unsigned turns = 0;
  long double * turnOdds = malloc(sizeof(long double));
  *turnOdds = 1;
  long double damageDealtA[111];
  long double damageDealtB[111];
  unsigned char current = 0;
  long double * damageDealt;
  long double * damageDealtPrev;
  memset(damageDealtA, 0, 111 * sizeof(long double));
  *damageDealtA = 1;
  unsigned currentTurn;
  long double curDamage[12];
  unsigned char curHP;
  do {
    currentTurn = turns;
    turns += 20;
    turnOdds = realloc(turnOdds, sizeof(long double) * (turns + 1));
    for (currentTurn ++; currentTurn <= turns; currentTurn ++) {
      damageDealtPrev = current ? damageDealtB : damageDealtA;
      damageDealt = current ? damageDealtA : damageDealtB;
      memset(damageDealt, 0, 111 * sizeof(long double));
      for (curHP = 0; curHP < opponentHP; curHP ++) {
        multiplyVector(curDamage, hitOdds, damageDealtPrev[curHP]);
        addVector(damageDealt + curHP, curDamage);
      }
      turnOdds[currentTurn] = totalOdds(damageDealt + opponentHP);
      current = !current;
    }
    damageDealt = current ? damageDealtA : damageDealtB;
    *turnOdds = currentError(damageDealt, opponentHP);
  } while (*turnOdds >= threshold);
  *result = turnOdds;
  *resultSize = turns;
}

static void hitsOdds (unsigned char maxDamage, long double hitChance, long double * result) {
  *result = 1 - hitChance;
  long double x = hitChance / maxDamage;
  unsigned char pos;
  for (pos = 1; pos <= maxDamage; pos ++) result[pos] = x;
  for (; pos <= 11; pos ++) result[pos] = 0;
}

static void multiplyVector (long double * result, long double * src, long double value) {
  unsigned char pos;
  for (pos = 0; pos < 12; pos ++)
    result[pos] = src[pos] * value;
}

static void addVector (long double * dst, long double * src) {
  unsigned char pos;
  for (pos = 0; pos < 12; pos ++)
    dst[pos] += src[pos];
}

static long double totalOdds (long double * damageOdds) {
  long double total = 0;
  unsigned char pos;
  for (pos = 0; pos < 12; pos ++)
    total += damageOdds[pos];
  return total;
}

static long double currentError (long double * damageOdds, unsigned char maxDamage) {
  long double total = 0;
  unsigned char pos;
  for (pos = 0; pos < maxDamage; pos ++)
    total += damageOdds[pos];
  return total;
}

static void expand (long double ** turnOdds, unsigned from, unsigned to) {
  *turnOdds = realloc(*turnOdds, sizeof(long double) * (to + 1));
  unsigned pos;
  for (pos = from + 1; pos <= to; pos ++)
    (*turnOdds)[pos] = 0;
}

static Odds calculateFor (long double * turnOdds1, long double * turnOdds2, unsigned turns) {
  long double r0 = 0, r1 = 0, r2 = 0;
  unsigned turn1, turn2;
  for (turn1 = 1; turn1 <= turns; turn1 ++) {
    for (turn2 = 1; turn2 < turn1; turn2 ++)
      r2 += turnOdds1[turn1] * turnOdds2[turn2];
    r0 += turnOdds1[turn1] * turnOdds2[turn1];
    for (turn2 = turn1 + 1; turn2 <= turns; turn2 ++)
      r1 += turnOdds1[turn1] * turnOdds2[turn2];
    r1 += turnOdds1[turn1] * (*turnOdds2);
  }
  for (turn2 = 1; turn2 <= turns; turn2 ++)
    r2 += turnOdds2[turn2] * (*turnOdds1);
  r0 += (*turnOdds1) * (*turnOdds2);
  return (Odds) {.win = r1, .lose = r2, .draw = r0};
}