#include <assert.h>

#include <algorithm>
#include <array>
#include <iostream>
#include <optional>
#include <memory>
#include <vector>

// Indexed by level difference.
std::array<unsigned, 5> BaseRates = { 100, 50, 25, 10, 1 };
std::array<unsigned, 5> BonusRates = { 0, 16, 8, 3, 0 };

// How many 0* materials are required to go from level N to level N+1.
// For example, going from 0* to 1* requires exactly one 0* material.
std::array<double, 5> MatsRequired = { 1.0, -1.0, -1.0, -1.0, -1.0 };

// How many 0* items is an N* item equivalent to.  For example, a 0*
// item is equivalent to 1 0* items.  A 1* item is equivalent to 2
// 0* items (one for the base 0*, one to upgrade it).   This is easy
// to compute.  The "value" of an N* item is equal to the value of an
// (N-1)* item plus the number of materials required to go from N->N+1
std::array<double, 6> MatValue = { 1.0, -1.0, -1.0, -1.0, -1.0 };


struct MaterialNode;

struct OutcomeNode {
  explicit OutcomeNode(const MaterialNode &Parent, bool Success);

  double matsRequired() const;

  // How did we get here?
  const MaterialNode &Parent;

  const MaterialNode *cheapestMaterial() const;

  // Whether this node represents a successful attmept or a failed attempt.
  bool Success = false;

  // From this outcome, what materials did we try?  Empty if and only if
  // Success == true.
  std::vector<std::unique_ptr<MaterialNode>> MaterialsTried;
};

struct MaterialNode {
  explicit MaterialNode(unsigned BaseStars, unsigned InitialFailureBonus = 0);
  explicit MaterialNode(OutcomeNode &Parent, unsigned Stars, unsigned FailureBonus);

  const MaterialNode &root() const;

  unsigned maxMaterial() const;

  double matsRequired() const;

  unsigned successRate() const;
  unsigned accumulatedFailure() const;

  unsigned materialDifference() const;

  // How did we get here?
  OutcomeNode *Parent = nullptr;

  // The star value (0 - 5) of the material used in this attempt.
  unsigned Stars = 0;

  // The sequential number of the attempt this node represents.
  unsigned Attempt = 0;

  // The current failure bonus when this material was used.
  unsigned FailureBonus = 0;

  // The independent probability that we will succeed on this attempt.
  unsigned N_Succ = 0;

  std::optional<double> InfiniteIncrementalCost;

  std::unique_ptr<OutcomeNode> Success;
  std::unique_ptr<OutcomeNode> Failure;
};

OutcomeNode::OutcomeNode(const MaterialNode &Parent, bool Success)
  : Parent(Parent), Success(Success) {

  // If this was a success, we don't need to do anything.  There's no reason to
  // try any more materials.
  if (Success)
    return;

  const MaterialNode &Root = Parent.root();
  unsigned Diff = Root.Stars - Parent.Stars;
  unsigned MaxMaterial = Parent.maxMaterial();
  for (unsigned M = 0; M <= MaxMaterial; ++M) {
    unsigned B = BonusRates[Diff];
    unsigned NewFailureBonus = std::min(100U, Parent.FailureBonus + B);
    auto Mat = std::make_unique<MaterialNode>(*this, M, NewFailureBonus);
    MaterialsTried.push_back(std::move(Mat));
  }
}

const MaterialNode *OutcomeNode::cheapestMaterial() const {
  const MaterialNode *MC = nullptr;
  for (const auto &M : MaterialsTried) {
    if (!MC || M->matsRequired() < MC->matsRequired())
      MC = M.get();
  }

  return MC;
}


double OutcomeNode::matsRequired() const {
  if (MaterialsTried.empty())
    return 0.0;
  return cheapestMaterial()->matsRequired();
}


MaterialNode::MaterialNode(unsigned BaseStars, unsigned InitialFailureBonus)
  : Stars(BaseStars), Attempt(0), FailureBonus(InitialFailureBonus) {
  // This is just a dummy node to represent the root.  Consider this a "failure" node
  // so that it's consistent with only descending into failures.
  Failure = std::make_unique<OutcomeNode>(*this, false);
}

MaterialNode::MaterialNode(OutcomeNode &Parent, unsigned Stars, unsigned FailureBonus)
  : Parent(&Parent), Stars(Stars), Attempt(Parent.Parent.Attempt + 1), FailureBonus(FailureBonus) {
  assert(Stars <= Parent.Parent.maxMaterial());
  assert(Stars < root().Stars);
  unsigned Difference = root().Stars - Stars;
  N_Succ = BaseRates[Difference];
  N_Succ = std::min(100U, N_Succ + FailureBonus);

  if (Difference >= 4) {
    // When the difference is too large, there is no failure bonus, so we can't keep recursing
    // through branches of the decision tree because it would be infinite.  Instead, we have to
    // use some calculus this explicitly.  Specifically, we have the following variables:
    //
    //     N - the cost of materials we've used up until this point.
    //     P - The base success rate with this material + any accumulated failure bonus
    //
    // With these, we have an infinite set of attempts where the absolute chance of succeeding
    // on attempt k is P*(1-P)^k, where k=0 represents the first attempt where Difference >= 4
    // and ignores any attempts that came prior.
    //
    // Furthermore, if the k'th attempt is the attempt that succeeds, then we would have used
    // k additional materials, all 0* so a cost of 1, for a total cost of N+k, and since this
    // would happen with probability P*(1-P)^k the effective cost of this branch of the tree
    // would be:
    //
    //    (N+k)*P*(1-P)^k
    //
    // Thus, we can get the sum of all branches by computing the limit of this sum as K approaches
    // infinity.
    //
    //      ∑[k=0, ∞] (N+k)*P*(1-P)^k
    //
    // I leave it as an exercise to the reader that this is equal to N + 1/P - 1, which means
    // that the *incremental* cost from taking this branch is simply equal to 1/P - 1.

    double D_Succ = static_cast<double>(N_Succ) / 100.0;

    // Since we're mathematically solving the entire problem henceforth, just say it has a success
    // rate of 100%, and set a special variable indicating the solved answer.
    N_Succ = 100;
    InfiniteIncrementalCost = 1.0 / D_Succ - 1.0;
  } else {
    Success = std::make_unique<OutcomeNode>(*this, true);
    if (N_Succ < 100U) {
      Failure = std::make_unique<OutcomeNode>(*this, false);
    }
  }
}

const MaterialNode &MaterialNode::root() const {
  return (Parent) ? Parent->Parent.root() : *this;
}

unsigned MaterialNode::maxMaterial() const {
  return (Parent) ? Stars : Stars - 1;
}

double MaterialNode::matsRequired() const {
  double M = 0.0;
  if (Parent)
    M = MatValue[Stars];

  if (InfiniteIncrementalCost.has_value()) {
    // If this is an infinite branch, just add in the computed cost and
    // exit.
    return M + *InfiniteIncrementalCost;
  }

  double P_Succ = static_cast<double>(N_Succ) / 100.0;
  double P_Fail = 1.0 - P_Succ;
  if (Success)
    M += P_Succ * Success->matsRequired();
  if (Failure)
    M += P_Fail * Failure->matsRequired();
  return M;
}


unsigned MaterialNode::materialDifference() const {
  return root().Stars - Stars;
}

unsigned MaterialNode::successRate() const {
  return BaseRates[materialDifference()];
}

unsigned MaterialNode::accumulatedFailure() const {
  unsigned N = 0;
  if (Parent)
    N += Parent->Parent.FailureBonus;

  return N;
}


std::array<std::unique_ptr<MaterialNode>, 5> Roots;

int main()
{
  for (unsigned I = 0; I < 5; ++I) {
    double M = 1.0;
    if (I > 0) {
      Roots[I] = std::make_unique<MaterialNode>(I);
      M = Roots[I]->matsRequired();
    }
    std::cout << I << "* -> " << (I + 1) << "* : " << M << " 0* item required." << std::endl;
    MatsRequired[I] = M;
    MatValue[I + 1] = MatValue[I] + MatsRequired[I];
  }

  for (unsigned I = 2; I < 5; ++I) {
    for (unsigned FB = 0; FB < 100; ++FB) {
      Roots[I] = std::make_unique<MaterialNode>(I, FB);
      const MaterialNode *Cheapest = Roots[I]->Failure->cheapestMaterial();
      std::cout << I << "*, FB = " << FB << ":  Use " << Cheapest->Stars << "* material.\n";
    }
  }

  unsigned Base = 0;
  while (true) {
    std::cout << "Enter a base material star value: ";
    std::cin >> Base;
    if (Base < 5)
      break;

    std::cout << "Cannot upgrade any item which is 5* or higher" << std::endl;
  }

  const MaterialNode *R = Roots[Base].get();
  bool Finished = false;
  double Cost = 0.0;
  double Bonus = 0.0;
  unsigned F = 0;
  std::cout << "Upgrading " << R->Stars << "* base item" << std::endl;
  while (!Finished) {
    std::cout << "Analyzing choices..." << std::endl;
    for (const auto &X : R->Failure->MaterialsTried) {
      std::cout << X->Stars << "* material -> Cost = " << X->matsRequired() << std::endl;
    }
    R = R->Failure->cheapestMaterial();
    F += R->FailureBonus;
    std::cout << "Failure Bonus = " << F << "%" << std::endl;
    std::cout << "Selecting " << R->Stars << "* material" << std::endl;

    unsigned S = R->successRate();
    std::cout << "Attempt " << R->Attempt << "[" << (S + F) << "%]: " << S << "% + " << F << "%" << std::endl;
    std::cout << "Did this attempt (S)ucceed or (F)ail?  Or do you want to go (B)ack?";
    char CH;
    std::cin >> CH;
    CH = toupper(CH);
    assert(CH == 'S' || CH == 'F' || CH == 'B');
    if (CH == 'B') {
      F -= R->FailureBonus;
      R = &R->Parent->Parent;
      Cost -= MatsRequired[R->Stars];
      continue;
    }

    Cost += MatsRequired[R->Stars];
    Bonus += static_cast<double>(R->FailureBonus) / 100.0;

    if (CH == 'S') {
      std::cout << "Done!  Steps = " << R->Attempt << ", Total material cost = " << Cost << std::endl;
      break;
    }
  }
  return 0;
}