Hi codeforces.
My coach gave me a problem the other day and I'm still stuck in it and I have no idea on how to solve it.
I was wondering if you could help me.
It goes like this:
You are in a candy workshop you have N candies , M boxes with the capacity of C units and each candy has it's own wight.
The candies are in a production line so you can't rearrange them you are standing in the front of the line and you have to bag as many candies as you can.
When a candy piece arrives to you , you have 3 choices
1) take the candy and subtract it's wight from the remaining wight of the box ( as long as it's wight is less or equal to the box's remaining wight)
2) discard the candy( NOTE : that you can not take the candy again )
3) close the box you have and open a new one ( if you have a box left )
What is the maximum number of candies you can bag in the boxes.
NOTE : that you stand in the left of the production line.
1 <= N <= 1000000 1 <= M,C <= 1000000
e.g:
N = 8
M = 2
C = 20
The candies are 12 8 5 10 13 15 4 7
The output is : 5
You can take 12 and 8 and put them in the first box and close it then you can take 5 and 10 and 4 and you're done.
e.g2:
N = 24
M = 1
C = 20
The candies are 13 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 13
The output is : 20
Auto comment: topic has been updated by M.A.H.M.O.O.D (previous revision, new revision, compare).
nice problem
need a deep thinking :)
it's an easy problom it's only 1% on the rate of IOI probloms it should be easy to you noooooooooooooooooooooooooooooooooooooooooooooob :)
Oh yeah...well post the solution.
include <bits/stdc++.h>
define forn(i, n) for (int i = 0; i < int(n); i++)
define ford(i, n) for (int i = int(n) — 1; i >= 0; i--)
define fore(i, l, r) for (int i = int(l); i < int(r); i++)
define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
define all(a) (a).begin(), (a).end()
define sz(a) int((a).size())
define pb(a) push_back(a)
define mp(x, y) make_pair((x), (y))
define x first
define y second
using namespace std;
typedef long long li; typedef long double ld; typedef pair<int, int> pt;
template inline X abs(const X& a) { return a < 0? -a: a; } template inline X sqr(const X& a) { return a * a; }
const int INF = int(1e9); const li INF64 = li(1e18); const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
int m, d; string a, b;
inline bool read() { if (!(cin >> m >> d)) return false; assert(cin >> a >> b); return true; }
const int mod = 1000 * 1000 * 1000 + 7;
inline int add(int a, int b) { return a + b >= mod ? a + b — mod : a + b; } inline void inc(int& a, int b) { a = add(a, b); } inline int sub(int a, int b) { return a — b < 0 ? a — b + mod : a — b; } inline void dec(int& a, int b) { a = sub(a, b); }
const int N = 2020;
int z[N][N][2];
int solve(string s) { int n = sz(s); forn(i, n + 1) forn(j, m) forn(k, 2) z[i][j][k] = 0; z[0][0][1] = 1; forn(i, n) forn(j, m) forn(k, 2) for (int p = 0; p <= (k ? int(s[i] — '0') : 9); p++) { if ((i & 1) && p != d) continue; if (!(i & 1) && p == d) continue; if (!i && !p) continue; int ni = i + 1; int nj = (j * 10 + p) % m; int nk = k && (p == int(s[i] — '0')); inc(z[ni][nj][nk], z[i][j][k]); } int ans = 0; forn(k, 2) inc(ans, z[n][0][k]); return ans; }
bool good(string s) { int rm = 0; forn(i, sz(s)) { int p = int(s[i] — '0'); if ((i & 1) && p != d) return false; if (!(i & 1) && p == d) return false; rm = (rm * 10 + p) % m; } return !rm; }
inline void solve() { int ans = 0; inc(ans, solve(b)); dec(ans, solve(a)); inc(ans, good(a)); cout << ans << endl; }
inline ld gett() { return ld(clock()) / CLOCKS_PER_SEC; }
int main() {
ifdef SU1
endif
}
How does that relate to the problem in anyway ???
Ask your coach to solve it...
Well I did and he didn't answer me I'm not even sure he knows the answer.
worst blog in the history of CF