Table of contents

• Problem
  • Input
  • Output
• Explanation
• Time complexity
• Solution

# Problem

https://atcoder.jp/contests/abc104/tasks/abc104_c

# Input

$D G$
$p_1 c_1$
...
$p_D c_D$

• D - The number of ranks
• G - total score
• p_1 - The number of problems of rank i
• c_1 - The bonus score of rank i

The score of problem of rank i is $100 \times i$.

# Output

The minimum number of problems to solve to arhieve a total score G or more.

# Explanation

This problem can be solved by DFS about ranks in $O(2^D)$ as D is enough small.

Possible choice for each rank is either

• 1. Solve all the problems of the rank (with bonus)
• 2. Don't solve any problem of the rank
• 3. Solve problems of the rank partially (without bonus)

# Time complexity

$O(2^D)$

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_D 11

struct Rank {
  Int numProblems, score, bonus;

  Rank(): numProblems(0), score(0), bonus(0) {}

  Rank(Int n, Int s, Int b): numProblems(n), score(s), bonus(b) {
  }
};

Int D, G, c, p;
Rank ranks[MAX_D];

struct State {
  Int index = 0, numTaken = 0, score = 0, partialIndex = 0;

  State() {
  }

  bool success() {
    return score >= G;
  }

  bool end() {
    return index >= D;
  }

  State takePart() {
    State copy = *this;
    Int need = (G - score) / ranks[index].score;
    if (need > ranks[index].numProblems) return copy;
    copy.score += ranks[index].score * need;
    copy.numTaken += need;
    return copy;
  }

  State take() {
    State copy = *this;
    copy.score += ranks[index].score * ranks[index].numProblems + ranks[index].bonus;
    copy.numTaken += ranks[index].numProblems;
    return copy;
  }

  State inc() {
    State copy = *this;
    copy.index++;
    return copy;
  }
};

void input() {
  cin >> D >> G;
  loop(d,1,D+1) {
    cin >> p >> c;
    ranks[d-1] = Rank(p, 100*d, c);
  }
  reverse(ranks, ranks+D);
}

State dfs(State state) {
  if (state.success() || state.end()) return state;
  if (state.takePart().success()) return state.takePart();

  State not_take = dfs(state.inc());
  State take = dfs(state.take().inc());
  if (not_take.success() && take.success())
    return (not_take.numTaken < take.numTaken) ? not_take : take;
  if (take.success()) return take;
  else return not_take;
}

void solve() {
  State init;
  State result = dfs(init);
  cout << result.numTaken << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}