#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define y0 isdnfviu
#define y1 asinhiv
#define fst first
#define snd second
#define count sdifnsugh
int s(int n)
{
return (n * (n + 1)) / 2;
}
const int maxn = 200003, MOD = 1000000007;
int f[maxn];
int main()
{
int r, g;
cin >> r >> g;
if (r > g)
swap(r, g);
int n;
for (int i = 1; i <= 1000; i++)
if (s(i) <= r + g && s(i + 1) > r + g)
{
n = i;
break;
}
int kol = s(n);
f[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = r; j >= i; j--)
{
f[j] += f[j-i];
if (f[j] >= MOD)
f[j] -= MOD;
}
int ans = 0;
for (int i = r; i >= 0; i--)
if (i + g >= kol)
ans = (ans + f[i]) % MOD;
cout << ans << "\n";
cin >> n;
return 0;
}
If you come to post just to downvote then please do downvote + help .
Please somebody help I really tried hard to get this ;(
Think of problem recursively. First find the max height that you can get using r red and g greens, you can use binary search for it.
Now suppose you are at i_th level, you can fill this level either with red balls or green balls. suppose you say level 1 = top of tower, level 2 as 2nd top and so on. so when you are at i_th level you know how much ball you need to fill in this level, that is i.
Now when we are at level i we can fill it with either red balls or green balls, we check recursively for each case and recur for next one. the problem is a simple knapsack problem but the problem is it will give you Memory limit exceeded.
To avoid MLE, you have to solve it iteratively. observe that current ith level depend on i-1 th level.
so convert the above recusive approach to iterative one of state dp[2][N]. Now fill each level with red and green balls, but beware it doesn't become <0.
Link to understandable code.
Thank You so much .
Ok it's quite simple.
First step: Determine $$$h$$$. You can derive $$$h$$$ from the following inequality $$$ \frac{h\times (h+1)}{2} \le r+g$$$. You can see that $$$h \le \sqrt{2\times(r+ g)}$$$, so you can bruteforce $$$h$$$.
Second step: Now you see the problem mimics the traditional DP problem: You have $$$h$$$ sacks, the sack $$$i$$$ contains $$$i$$$ blocks, so how many ways can you form $$$X (X\le r)$$$ red blocks using $$$h$$$ sacks.
You can solve like this: $$$f_{X, i}$$$ is the number of way to form $$$X$$$ red blcoks using sacks from $$$1 \rightarrow i$$$. Then $$$f_{X, i} = f_{X-i, i-1} + f_{X, i-1}$$$.
The overall complexity of both time and memory is $$$(r+g)\sqrt{r+g}$$$. Actually the solution code is the optimization of DP, but you can ignore it.
Hope this helps!
Thank You so much . I got it now .