## 990 - Diving for Gold

Moderator: Board moderators

RubenRamalho
New poster
Posts: 4
Joined: Fri Jun 25, 2010 8:33 pm

### 990 - Diving for Gold

I was getting WA all the time, suddenly without doing anything substantial it's ACC..
I guess I needed to stretch the limits a little bit..

Nevertheless thanks to anyone who at least read my plea..

Code Removed

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:

### 990 - Diving for Gold

Why WA!!! Please give me, some input & output.

Code: Select all

``````#include<stdio.h>
long A[1009],B[1009],C[1009];
long d[40],v[40],x[40],y[40];
long t,w,n,i,j,max,count,k,flag;

int main()
{

while(scanf("%ld %ld",&t,&w)==2)
{
scanf("%ld",&n);

for(i=0;i<n;i++)
{
scanf("%ld %ld",&d[i],&v[i]);
x[i] = w * d[i] * 3;
y[i]=0;
}

for(i=1;i<=t;i++)
A[i]=0;
A[0]=-1;
C[0]=0;

for(i=0;i<n;i++)
for(j=t-x[i];j>=0;j--)
if(A[j]!=0 && (A[j+x[i]]==0 || C[j+x[i]]<C[j]+v[i]))
{
A[j+x[i]]= i+1;
B[j+x[i]]= j;
C[j+x[i]]= C[j]+v[i];
}

max = 0;
k=0;
for(i=0;i<=t;i++)
if(A[i]!=0 && C[i]>max)
{
max = C[i];
k=i;
}
count = 0;

while(A[k]!=-1)
{
count++;
y[A[k]-1]=1;
k = B[k];
}

if(flag==1)
printf("\n");
flag=1;
printf("%ld\n%ld\n",max,count);
for(i=0;i<n;i++)
if(y[i]==1)
printf("%ld %ld\n",d[i],v[i]);

}

return 0;
}
``````
SHAKIL

Yousuf
New poster
Posts: 13
Joined: Thu Jun 09, 2011 8:22 am

I got wrong answer in this problem.
I need some critical input output. Help me Please....

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Check input and AC output for thousands of problems on uDebug!

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 990 - Diving for Gold

Can anyone provide me some critical test cases?

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 990 - Diving for Gold

i'm getting WA in this problem.
i used 0-1 knapsack algorithm.
can anyone find any bug in my code?
my code is here:

Code: Select all

``````removed after ac
``````

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

### Re: 990 - Diving for Gold

I always got WA. What's wrong with my code? Help!

Code: Select all

``````//Q990 Diving for gold,
#include <cstdio>
#include <stack>
#include <stdlib.h>
#define N 1005
using namespace std;
typedef struct node
{
int d,v;
} Treasure;
Treasure treasure[32];
int n,dp[N],from[N];
int main()
{
int t,i,j,k,testcase,w;
//freopen("in.txt","r",stdin);
for(testcase=1; scanf("%d %d",&t,&w)==2; testcase++)
{
if(testcase>1) printf("\n");
scanf("%d",&n);
for(i=0; i<n; i++) scanf("%d %d",&treasure[i].d,&treasure[i].v);

for(i=0; i<n; i++) if(treasure[i].d<=0 || treasure[i].v<=0) abort();
for(i=0; i<=t; i++) dp[i]=from[i]=-1;
dp[0]=from[0]=0;
for(i=0; i<n; i++)
for(j=t; j>=0; j--)
{
k=j-3*w*treasure[i].d;
if(k<0) break;
if(dp[k]==-1) continue;
if(dp[k]+treasure[i].v > dp[j])
{
//printf("kk=%d dpk=%d dpj=%d i=%d\n",k,dp[k],dp[j],i);
dp[j]=dp[k]+treasure[i].v;
from[j]=i;
}
}

int p=0;
for(i=1; i<=t; i++) if(dp[i]>dp[p]) p=i;
//for(i=0; i<=t; i++) if(dp[i]!=-1)printf("i=%d dp=%d from=%d\n",i,dp[i],from[i]);
//printf("p=%d\n",p);
printf("%d\n",dp[p]);
int count=0;
stack<int> s;

while(p!=0)
{
s.push(from[p]);
p-=3*w*treasure[from[p]].d;
count++;
}
printf("%d\n",count);
while(!s.empty())
{
k=s.top(); s.pop();
printf("%d %d\n",treasure[k].d,treasure[k].v);
}
}
return 0;
}
``````

yishiliu666
New poster
Posts: 4
Joined: Tue Mar 11, 2014 2:25 pm

### 990 Diving for Gold.

Please help me check, I get WA, but this code passed several critical sample test I've came across in this forum

Code: Select all

``````import java.util.Scanner;

public class Main {

/**
* @param args
*/
static int d[], v[];
static int trace[][];
static int dp[][];
static int count=0;

public static void trace(int n, int dcmax){
if(n<=0||dcmax<=0) {
System.out.println(count);
return;
}
if(trace[n][dcmax]==1){
count++;
trace(n-1, dcmax-d[n-1]);
System.out.println(d[n-1]+" "+v[n-1]);
}
else{
trace(n-1, dcmax);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int w, t;
int n;
int dcmax;

Scanner scan = new Scanner(System.in);
t=scan.nextInt();
w=scan.nextInt();
n=scan.nextInt();
d = new int[n];
v = new int[n];
dcmax = t/(3*w);

for(int i=0;i<n;i++){
d[i] = scan.nextInt();
v[i] = scan.nextInt();
}

dp = new int[n+1][dcmax+1];
trace = new int[n+1][dcmax+1];

for(int i=0;i<=n;i++)
for(int j=0;j<=dcmax;j++){
dp[i][j] = 0;
trace[i][j]=0;
}

for(int i=1;i<=n;i++){
for(int j=1; j<=dcmax;j++){
dp[i][j] = dp[i-1][j];
if(j>=d[i-1] && dp[i-1][j-d[i-1]]+v[i-1] > dp[i-1][j]){
dp[i][j] = dp[i-1][j-d[i-1]]+v[i-1];
trace[i][j] = 1;
}
}
}

System.out.println(dp[n][dcmax]);
trace(n, dcmax);
}

}
``````

For
210 4
3
10 5
10 1
7 2
i've got
7
2
10 5
7 2
for
604 3
29
32 11
15 83
78 61
45 56
87 3
14 57
52 64
10 45
14 99
55 6
89 11
64 79
7 73
78 86
73 62
73 1
85 5
19 88
97 15
18 16
74 84
0 32
29 26
77 10
68 95
58 84
16 57
83 22
8 23
I've got
420
6
15 83
10 45
14 99
7 73
19 88
0 32

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 990 Diving for Gold.

Input contains several test cases.
Try input:

Code: Select all

``````210 4
3
10 5
10 1
7 2

210 4
3
10 5
10 1
7 2``````
Output should be:

Code: Select all

``````7
2
10 5
7 2

7
2
10 5
7 2``````
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### WA...Pls Help.......

the procedures i use:
1.taking the depth and number of coin in a structure.
2.then i sort(high to low) the structure according to the number of coin.
3.then take the treasure if it fullfil the condition.that's it.
is my procedure wrong?
i check all the input from this thread and every AC output matches my output.pls check my code
my code:

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

struct t
{
int depth;
int num_coin;
int id;
};

bool acompare(t lhs, t rhs) { return lhs.num_coin > rhs.num_coin; }

int main()
{
int t_time,d_const,num_t;
int p=0;

while(scanf("%d %d",&t_time,&d_const)==2) {
if(p!=0) putchar('\n');
p=1;
cin>>num_t;
t arr[num_t];
vector<int>sol;
sol.clear();

for(int i=0;i<num_t;i++) {
cin>>arr[i].depth>>arr[i].num_coin;
arr[i].id=i;
}

std::sort(arr, arr+num_t, acompare);

//cout<<endl<<endl;
/*for(int i=0;i<num_t;i++) {
cout<<arr[i].depth<<" "<<arr[i].num_coin<<endl;
}*/

int curr_t=0;
int i=0,tym;
int maxi_g=0;
int cnt=0;
//cout<<endl<<endl;
for(int i=0;i<num_t;i++) {

tym=3*arr[i].depth*d_const;

if((curr_t+tym)<=t_time) {

maxi_g+=arr[i].num_coin;
sol.push_back(arr[i].id);
curr_t+=tym;
cnt++;
//cout<<"id= "<<arr[i].id<<endl;
}

}
sort(sol.begin(),sol.end());
//for(int i=0;i<cnt;i++) cout<<sol[i]<<endl;
cout<<maxi_g<<endl;
cout<<cnt<<endl;
for(int i=0;i<cnt;i++) {
for(int j=0;j<num_t;j++) {
if(sol[i]==arr[j].id) cout<<arr[j].depth<<" "<<arr[j].num_coin<<endl;
}
}
getchar();
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 990 - Diving for Gold

http://www.udebug.com/UVa/990
Click "Random Input", "Go!"
Check input and AC output for thousands of problems on uDebug!

saha2
New poster
Posts: 2
Joined: Fri Oct 07, 2016 10:10 pm

### Re: 990 - Diving for Gold

why WA??? i have tried inputs but find no solution..please anyone help
here is my code

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include<map>
#define inf 10000007
int dp[1000][1000];
int depth[1000];
int value[1000];
int track[1000][1000];
struct d{
int depth;
int value;
};
typedef struct d save;
save arr[1000];
using namespace std;
vector<save>v;
map<int,int>m;
int n,w;

int rec(int time,int now){
if(time<=0)return 0;
else if(time<=0 || now>=n){
return 0;
}
else{
if(dp[time][now]!=-1)return dp[time][now];
else{
if(time-3*w*depth[now]>=0){

int a=rec(time-3*w*depth[now],now+1)+value[now];
int b=rec(time,now+1);
if(a>b) {
track[time][now]=1;
return dp[time][now]=a;
}
else{
track[time][now]=0;
return dp[time][now]=b;}
}
else{
track[time][now]=0;
return dp[time][now]=rec(time,now+1);
}
}
}
}

void sol(int time,int now){
if(track[time][now]==1){
v.push_back(arr[now]);
sol(time-3*w*depth[now],now+1);
}
else if(track[time][now]==0){
sol(time,now+1);
}
}

int main(){
int a,b,c,d,t;
int chk=0;
while(cin>>t>>w){
if(chk!=0)cout<<endl;
v.clear();
memset(depth,0,sizeof(depth));
memset(value,0,sizeof(value));
memset(arr,0,sizeof(arr));
cin>>n;
for(c=0;c<n;c++){
cin>>a>>b;
save A;
A.depth=a;
A.value=b;
depth[c]=a;
value[c]=b;
arr[c]=A;
}
for(c=0;c<1000;c++){

for(d=0;d<1000;d++){
dp[c][d]=-1;
track[c][d]=-1;
}
}
int a=rec(t,0);
cout<<a<<endl;
sol(t,0);
cout<<v.size()<<endl;
for(c=0;c<v.size();c++){
cout<<v[c].depth<<" "<<v[c].value<<endl;
}
chk++;
getchar();

}
return 0;
}