648 - Stamps (II)

[LittleJohn]

Can anybody explain the second sample input to me?
1 1 0
2 3 0
Why does the answer of 2 is 1 1, and the answer of 3 is tie.
thanx.

[cytse]

There are two types of stamps, let's call them A and B, both with value 1.

For the 1st case, there are three ways to allocate the stamps: (i) 2xA, (ii) 2xB, and (iii) 1A+1B. The first two only give 1 type of stamps, while the last one gives 2 different types of stamps, which is the 'best' combination, and it is unique. So the answer is 1 1.

For the 2nd case, there are 4 ways to allocate the stamps: (i) 3xA, (ii) 3xB, (iii) 2A+1B, and (iv) 1A+2B. The first two only gives one types of stamps, while the last two gives two different types of stamps. So the last two are better than the first two. Both (iii) and (iv) have the same total number of stamps (3), and the same highest single-value (1), so it is a tie.

[oulongbin]

i don't why i always get WA,could someone give some inputs and outputs?
thank!

Code: Select all

#include <iostream>
using namespace std;
#include <cstring>

int stamp[100];
int numOfType;
int customer;
int numOfStamp[100];
int stampUsed[100];
bool tie;
int stamp_list[5];
int now_stamp_list[5];
int now_type_sum;
int now_cnt;
int now_max;
bool ans;

void backtrack(int type,int sum,int type_sum,int cnt)
{
	if(sum==customer)
	{
		ans=true;
		int i;
		int m;
		if(now_type_sum<type_sum)
		{
			tie=false;
			now_type_sum=type_sum;
			now_cnt=cnt;
			m=0;
			for(i=0;i<cnt;i++)
			{
				now_stamp_list[i]=stamp_list[i];
				if(stamp_list[i]>m)
					m=stamp_list[i];
			}
			now_max=m;
		}
		else if(now_type_sum==type_sum)
		{
			if(cnt<now_cnt)
			{
				tie=false;
				now_type_sum=type_sum;
				now_cnt=cnt;
				m=0;
				for(i=0;i<cnt;i++)
				{
					now_stamp_list[i]=stamp_list[i];
					if(stamp_list[i]>m)
						m=stamp_list[i];
				}
				now_max=m;
			}
			else if(cnt==now_cnt)
			{
				m=0;
				tie=false;
				for(i=0;i<cnt;i++)
				{
					if(stamp_list[i]>m)
						m=stamp_list[i];
				}
				if(m>now_max)
				{
					now_max=m;
					now_cnt=cnt;
					for(i=0;i<cnt;i++)
					{
						now_stamp_list[i]=stamp_list[i];
					}
				}
				else if(m<now_max)
				{
				}
				else
				{
					tie=true;
				}
			}
		}
		return;
	}
	if(type==numOfType)
	{
		return;
	}
	if(cnt==4)
	{
		return;
	}

	stampUsed[type]++;
	sum+=stamp[type];
	stamp_list[cnt]=stamp[type];
	if(stampUsed[type]==1)
		backtrack(type,sum,type_sum+1,cnt+1);
	else
		backtrack(type,sum,type_sum,cnt+1);
	stampUsed[type]--;
	sum-=stamp[type];

	backtrack(type+1,sum,type_sum,cnt);
}

void output()
{
	int i;
	cout<<customer;
	if(!ans)
	{
		cout<<" ---- none"<<endl;
	}
	else
	{
		cout<<" ("<<now_type_sum<<"): ";
		if(tie)
			cout<<"tie"<<endl;
		else
		{
			for(i=0;i<now_cnt;i++)
				cout<<now_stamp_list[i]<<" ";
			cout<<endl;
		}
	}
}

int main() 
{ 
    int temp;
	while(cin>>temp)
	{
		stamp[0]=temp;
		numOfType=1;
		while(cin>>temp && temp)
		{
			stamp[numOfType++]=temp;
		}
		while(cin>>customer && customer)
		{
			memset(stampUsed,0,sizeof(stampUsed));
			tie=false;
			now_type_sum=0;
			now_cnt=0;
			now_max=0;
			ans=false;
			backtrack(0,0,0,0);
			output();
		}
	}
    return 0;
}

[Observer]

Hi everyone,

I'm getting WA for this problem. Well I think that the problem description is very badly written. The terms like "types", "values" etc. go without any explanation. And they are wrongly used. For instance in the sample input, it calls 1 1 0 "two of the same type", yet in the sample output, it gives the number of types sold as "2"!...... So what does it mean? And I still do not understand what the phrase "highest single-value stamp" means..........

By the way, can somebody give me the correct output for

Code: Select all

1 1 2 2 0
1 2 3 4 5 6 7 8 9 0

?

My WA code gives

Code: Select all

1 (1): tie
2 (2): 1 1
3 (2): tie
4 (3): tie
5 (3): tie
6 (4): 1 1 2 2
7 (3): tie
8 (2): tie
9 ---- none

Thanks.

[Observer]

Hi,

After a whole day and no reply... Seeing that the acceptance rate is so high for this problem, I must have misinterpreted the problem statement badly....

Please also try this input:

Code: Select all

3 2 2 0 
1 2 3 4 5 6 7 8 9 0
1 5 7 0
1 2 3 4 5 6 7 8 9 0
2 0
1 2 3 4 5 6 7 8 9 0

My WA code gives

Code: Select all

1 ---- none
2 (1): tie
3 (1): 3
4 (2): 2 2
5 (2): tie
6 (2): tie
7 (3): 2 2 3
8 (2): tie
9 (3): tie
1 (1): 1
2 (1): 1 1
3 (1): 1 1 1
4 (1): 1 1 1 1
5 (1): 5
6 (2): 1 5
7 (2): 1 1 5
8 (2): 1 7
9 (2): 1 1 7
1 ---- none
2 (1): 2
3 ---- none
4 (1): 2 2
5 ---- none
6 (1): 2 2 2
7 ---- none
8 (1): 2 2 2 2
9 ---- none

Thanks again.

[mf]

Both your outputs are correct.

"Highest single-value stamp" means just the largest value of stamp you've used (e.g. `1 2 5' is better than `1 3 4', because 5 > 4.)

Try this test case:

Code: Select all

4 2 1 3 0
6 0

The output should be "6 (3): 1 2 3"

[Observer]

Thanks for your case. However, my WA code gives correct answer for this case too.....

How about this case? What should be the correct output:

Code: Select all

1 2 2 4 8 0
1 2 3 4 5 6 7 8 9 10 0

[mf]

Code: Select all

1 (1): 1
2 (1): tie
3 (2): tie
4 (2): 2 2
5 (3): 1 2 2
6 (3): 1 1 2 2
7 (3): tie
8 (3): 2 2 4
9 (4): 1 2 2 4
10 (3): tie

[Observer]

Still output correctly.......

Should I just give up?

[mf]

Could you post here your code? I'll check it with random inputs.

[Observer]

Code: Select all

[mf]

Try this input:

Code: Select all

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0

Correct output:

Code: Select all

1 (1): 1
2 (1): 2
3 (2): 1 2
4 (2): 1 3
5 (2): 1 4
6 (3): 1 2 3
7 (3): 1 2 4
8 (3): 1 2 5
9 (3): 1 2 6
10 (4): 1 2 3 4
11 (4): 1 2 3 5
12 (4): 1 2 3 6
13 (4): 1 2 3 7
14 (4): 1 2 3 8
15 (4): 1 2 3 9
16 (4): 1 2 3 10
17 (4): 1 2 3 11
18 (4): 1 2 3 12
19 (4): 1 2 3 13
20 (4): 1 2 3 14
21 (4): 1 2 3 15
22 (4): 1 2 3 16
23 (4): 1 2 3 17
24 (4): 1 2 3 18
25 (4): 1 2 3 19

[Observer]

Thanks!!

Yes I've also just tried inputs like

Code: Select all

1 2 3 4 0
5 0

And at once I realize my mistake!!! (I just can't believe how careless I am..... Even a beginner won't get into mistakes as silly as this...... ) Got AC after modifying just ONE line..........

Thanks again for your help!!!!!!!! Now I can get some sleep

[metaphysis]

Test data generator.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    srand(time(NULL));
    for (int cs = 1; cs <= 100; cs++)
    {
        int n = rand() % 25 + 1;
        for (int i = 0; i < n; i++)
            cout << rand() % 100 + 1 << ' ';
        cout << "0\n";
        n = rand() % 25 + 1;
        for (int i = 0; i < n; i++)
            cout << rand() % 200 + 1 << ' ';
        cout << "0\n";
    }

    return 0;
}