990 - Diving for Gold

[RubenRamalho]

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]

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;    
}

[Yousuf]

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

[brianfry713]

This thread has one:
http://acm.uva.es/board/viewtopic.php?t=12839

You can also generate some here:
http://www.uvatoolkit.com/problemssolve.php

[mostafiz93]

Can anyone provide me some critical test cases?

[mostafiz93]

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]

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]

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]

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

[LazyTym]

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;
}

thanks in advanced

[brianfry713]

http://www.udebug.com/UVa/990
Click "Random Input", "Go!"

[saha2]

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

Code: Select all

#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;
}