I got WA for this. I use memoization to solve. But WA
![:cry:](./images/smilies/icon_cry.gif)
anyone got test cases? and what the answer for this?
Input
5
12 23 42 14
12 53 75 23
56 23 34 2
23 55 72 25
124 86 173 84
Output
166 14
728 23
0 0
23 23
1012 77
Moderator: Board moderators
Code: Select all
#include <stdio.h>
#include <string.h>
const int MAX = 10000000000000000;
int f[210][210][210], qA[9000000], qB[9000000], qC[9000000];
char used[210][210][210];
int i, j, k, t, a, b, c, d, MAXD, MINS, nxt, lst;
void check(int D, long long SUM) {
if (D <= d)
if (D > MAXD || (D == MAXD && SUM < MINS) ) {
MAXD = D;
MINS = SUM;
}
}
void add(int I, int J, int K, int poured) {
if (!used[I][J][K]) {
used[I][J][K] = 1;
f[I][J][K] = f[i][j][k] + poured;
qA[lst] = I;
qB[lst] = J;
qC[lst++] = K;
check(I, f[I][J][K]);
check(J, f[I][J][K]);
check(K, f[I][J][K]);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
scanf("%d", &t);
while(t--) {
scanf("%d %d %d %d", &a, &b, &c, &d);
memset(used, 0, sizeof(used));
qA[0] = 0;
qB[0] = 0;
qC[0] = c;
f[0][0][c] = 0;
used[0][0][c] = 1;
MAXD = MINS = 0;
for (nxt = 0, lst = 1; nxt < lst; nxt++) {
i = qA[nxt];
j = qB[nxt];
k = qC[nxt];
if (i) {
if (i + j > b) add(i + j - b, b, k, b - j);
else add(0, i + j, k, i);
if (i + k > c) add(i + k - c, j, c, c - k);
else add(0, j, i + k, i);
}
if (j) {
if (j + k > c) add(i, j + k - c, c, c - k);
else add(i, 0, j + k, j);
if (j + i > a) add(a, j + i - a, k, a - i);
else add(j + i, 0, k, j);
}
if (k) {
if (k + i > a) add(a, j, k + i - a, a - i);
else add(k + i, j, 0, k);
if (k + j > b) add(i, b, k + j - b, b - j);
else add(i, k + j, 0, k);
}
}
printf("%lld %d\n", MINS, MAXD);
}
return 0;
}
If we come to a visited state and we have less poured water, in my opinion we should change old value to the new better value. But in this case this problem cannot be solved by BFS. It becomes a DP problem which must be solved using Deikstra algo. Am i right?I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.
At last i removed the lineChange line 101 to:
printf("%d %d\n", MINS, MAXD);
Try changing line 8 to:
char used[201][201][201];
You're not using line 4 but you shouldn't try to declare an int with a value greater than 2147483647.
I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.
You could try making your functions inline.
Code: Select all
memset(used, 0, sizeof(used));
Code: Select all
for (i = 0; i <= a; i++)
for (j = 0; j <= b; j++)
for (k = 0; k <= c; k++) used[i][j][k] = 0;
Code: Select all
for (i = 0; i <= a && i <= C; i++)
for (j = 0; j <= b && i + j <= C; j++)
used[i][j][C - i - j] = INT_MAX;
Code: Select all
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;
struct state
{
int water[3];
int amt;
bool operator < (const state& s) const
{
for (int i = 0 ; i < 2 ; ++i)
{
if (water[i] != s.water[i])
{
return water[i] < s.water[i];
}
}
return water[2] < s.water[2];
}
};
int cap[3];
int d;
set<state> ss;
int r_d;
int r_cnt;
bool is_visited(state& s)
{
set<state>::iterator it = ss.find(s);
if (it != ss.end())
{
if (it->amt > s.amt)
{
ss.erase(it);
return false;
}
return true;
}
return false;
}
void set_visit(state& s)
{
ss.insert(s);
}
void bfs()
{
queue<state> q;
state tmp;
tmp.water[0] = tmp.water[1] = tmp.amt = 0;
tmp.water[2] = cap[2];
q.push(tmp);
while (!q.empty())
{
state tmp = q.front();
q.pop();
set_visit(tmp);
int max_liter;
for (int k = 0 ; k < 3 ; ++k)
{
if (k == 0)
{
max_liter = tmp.water[k];
}
else if (tmp.water[k] <= d && tmp.water[k] > max_liter)
{
max_liter = tmp.water[k];
}
}
if (max_liter <= d)
{
if (max_liter > r_d)
{
r_d = max_liter;
r_cnt = tmp.amt;
}
if (max_liter == r_d && r_cnt > tmp.amt)
{
r_cnt = tmp.amt;
}
}
for (int i = 0 ; i < 3 ; ++i)
{
if (tmp.water[i] == 0)
{
continue;
}
for (int j = 0 ; j < 3 ; ++j)
{
if (i == j)
{
continue;
}
if (tmp.water[j] < cap[j])
{
state next;
memcpy(&next,&tmp,sizeof(next));
int cnt = next.water[i] < (cap[j] - next.water[j]) ? next.water[i] : (cap[j] - next.water[j]);
next.water[i] -= cnt;
next.water[j] += cnt;
next.amt += cnt;
if (!is_visited(next))
{
q.push(next);
}
}
}
}
}
}
void read_input()
{
scanf("%d%d%d%d",&cap[0],&cap[1],&cap[2],&d);
r_d = r_cnt = 0;
}
int main()
{
#ifdef shichun
freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
#endif
int n;
scanf("%d",&n);
while (n--)
{
read_input();
bfs();
printf("%d %d\n",r_cnt,r_d);
}
return 0;
}
Try to use existing threads and continue it.If there is a thread about your problem, please use it.
Code: Select all
2
93 157 199 67
96 97 199 62
Code: Select all
343 64
3468 12
Code: Select all
250 64
9859 62
Code: Select all
2
96 97 199 62
93 157 199 67
Code: Select all
9859 62
343 64