648 - Stamps (II)

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

648 - Stamps (II)

Post by LittleJohn » Fri Aug 16, 2002 7:14 pm

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.

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Fri Oct 11, 2002 6:35 pm

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
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

648 help me!

Post by oulongbin » Fri Aug 26, 2005 2:28 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Sep 06, 2005 7:51 pm

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.......... :cry:

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Sep 07, 2005 5:26 pm

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Sep 07, 2005 6:02 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Sep 07, 2005 6:06 pm

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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Sep 07, 2005 6:11 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Sep 07, 2005 6:12 pm

Still output correctly.......

Should I just give up? :(
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Sep 07, 2005 6:15 pm

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Sep 07, 2005 6:20 pm

Last edited by Observer on Wed Sep 07, 2005 6:42 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Sep 07, 2005 6:39 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Sep 07, 2005 6:43 pm

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 :-)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

metaphysis
Experienced poster
Posts: 138
Joined: Wed May 18, 2011 3:04 pm

Re: 648 - Stamps (II)

Post by metaphysis » Sat Dec 29, 2018 5:51 pm

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

Post Reply

Return to “Volume 6 (600-699)”