Submission #337354

#	Time	Username	Problem	Language	Result	Execution time	Memory
337354		chenwz	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	77 ms	1388 KiB

biscuits

#include "biscuits.h"
#include <vector>
#include <map>
typedef long long LL;
using namespace std;
typedef vector<LL> VL;
map<LL, LL> m;

// S(i) = ∑a(k)*(2^i)
LL f(const VL& s, LL x, LL n) {
  if (n <= 0) return 0;
  if (n == 1) return 1;
  if (m.count(n)) return m[n];
  LL i = __lg(n - 1), p2 = 1LL << i; // 2^i<n≤2^(i+1)
  return m[n] = f(s, x, p2) + f(s, x, min(n, 1 + s[i] / x) - p2);
}
LL count_tastiness(LL x, VL a) {
  m.clear();
  for (size_t i = 1; i < a.size(); i++) a[i] = a[i - 1] + (a[i] << i);
  while (a.size() <= 60) a.push_back(a.back());
  return f(a, x, 1 + a.back());
}
/*
OK(y) : 可以装出x袋y
S(i) = ∑a(j)·2^j, j=0...i
对于2^i≤y<2^(i+1), y可用↔s(i)≥x·y且OK(y-2^i) (1)
式子1的→是显然的，下面考虑←:
定义r=y-2^i,因为OK(r)，考虑剩下的x·(y-r)=x·2^i
因为S(i)≥x·y=x·2^i+x·r。
定义T=S(i)-x·r ≥ x·2^i。
注意T是一堆2^j之和，对于任意两个2^j，其中j<i，将其替换成一个2^(j+1)。 |TODO: 演算
最终T=x_0·2^0+ x_1·2^1+.... + x_i·2^i≥x·2^i，其中x_j <= 1,
则 x·2^i ≤T ≤2^i - 1 + x_i·x^i=(x_i+1)2^i-1则x_i+1 > x
所以(y-r)也可以包装出x个2^i来
定义Ai={y|OK(y),y≤2^i}。则A_(i+1)=A_i∪{y|y-2^i∈A_i, S(i)≥x·y, 2^i≤y<2^(i+1)}
定义g(n)=|{y|OK(y),y≤n}|
S(i)≥n·x, 则g(n) = g(2^i) + g(n-2^i) 
S(i)<n·x,   g(n) = g(2^i) + g(S(i)/x+1-2^i)
g(0)=0,g(1)=1
*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23