574 - Sum It Up

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

Moderator: Board moderators

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

574 - Sum It Up

Post by titid_gede » Thu Apr 10, 2003 5:11 am

reading the problem description, i'm sure this is not a difficult (the soft word of easy :wink: ) problem. but now i'm look stupid coz of WA. are there special cases? can anyone help me?
:evil: :evil: :evil: :evil: :evil:
[c]
--- cut GOT AC---
[/c]
Last edited by titid_gede on Tue Apr 15, 2003 5:55 am, edited 2 times in total.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Apr 10, 2003 6:50 am

Hiya titid, my friend ...

Your same() function won't help you that much. It's not enough to compare just with the last result you got. Try this:

Code: Select all

12 6 4 4 4 4 3 1
0 0
Oh yes, there are 2 more things:
1. The input terminates on jumdata == 0, not sum == 0.
2. You don't need mark[] ... probably removing it from your code won't change your algorithm.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Apr 10, 2003 7:59 am

How stupid i am... Thank you very much Pak Haryanto... muach muach...
yes i found my mark variable wont change my algo since i always start searching from the last term + 1. i really didn't realize that i should check to all result not only last result until i found case you've given. And also i have to read the problem more carefully. once again thank you very much :D :D :D :D :D :D :D :D
i'll fixed my code. Hope we can meet in Kampus Anggrek :D :D :D

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Mon Apr 14, 2003 10:28 am

still got wrong answerr. now i'm looks like evillll :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil:
here is my code :

[c]

--- cut --- GOT AC
[/c]
Last edited by titid_gede on Tue Apr 15, 2003 5:52 am, edited 1 time in total.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Mon Apr 14, 2003 2:08 pm

hello titid, I try to compile your program with bc 3.1 and I got your program too much global variable, and if I reduce your allresult[500] to allresult [200], you cannot pass with first sample I/O. but I don't know, if at gcc compiler you pass or not.

but I think, your program cannot handle input like this:

Code: Select all

4 1 4
4 3 4 1 1
your output is blank line

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Mon Apr 14, 2003 5:46 pm

I have problem with 574 too

I use brute force to search for the answer
and compare it to the previous answer
so there will be no duplicate answer,
but somehow it didn't work.

pls give me more sample input
for this problem,
I didn't find my mistake although it
already gives me 3 WA's.

I already tried several test case
and it gives correct answer in my
pc.

ow and yes I agreed with titid that this
problem looked simple and easy to solve,
therefore I feel stupid too because
couldn't get this one accepted

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Mon Apr 14, 2003 6:39 pm

hai, this is sample I/O:
input:

Code: Select all

6 1 2
7 1 7
131 12 99 80 70 60 50 40 30 20 10 10 10 2
18 12 3 3 3 3 3 3 3 3 3 3 3 3
24 12 2 2 2 2 2 2 2 2 2 2 2 2
11 4 4 3 2 1
999 1 999
output:

Code: Select all

Sums of 6:
NONE
Sums of 7:
7
Sums of 131:
99+30+2
99+20+10+2
99+10+10+10+2
Sums of 18:
3+3+3+3+3+3
Sums of 24:
2+2+2+2+2+2+2+2+2+2+2+2
Sums of 11:
NONE
Sums of 999:
999
Good luck... :wink:

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Mon Apr 14, 2003 8:17 pm

*sigh*

I failed in your third case ,

Ok now already fixed that
but still couldn't get accepted :oops:

btw, thx evan for your third case.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Tue Apr 15, 2003 6:03 am

I've got AC. there are small bugs in my last code, it cannot handle if there is only one result, and also in outputing results. thank you very much brother evan and brother hary.
btw how is your kpkbm03 result? after good start in semifinal, i was kicked down to 11th place, no money :( :(

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Tue Apr 15, 2003 12:06 pm

to deddy: I don't know where is your mistake, because I don't know your code, but it maybe only a small mistake. :wink:

to titid: I'm failed at semifinal, because a small mistake in file he..he..he.. because that I solve problem 3 at 2 hour, and I cannot solve another problem because I very angry with myself. I hope I can try for KPKB next year. :D

bye...... :wink:

User avatar
tetuya
New poster
Posts: 14
Joined: Thu May 27, 2004 2:31 pm

574 Sum It Up. WA can you tell me some inputs?

Post by tetuya » Mon Aug 09, 2004 3:45 pm

I got Wrong Answer.I tried some inputs made by me.but i could found no any wrong.Could you tell me some inputs ,and my mistake?

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <functional>
#include <algorithm>
using namespace std;
int t,n;
int data[200];
vector<string> result;

void init() {
	result.clear();
}
void input() {
	int i;
	for(i=0;i<n;i++)
		cin >> data[i];
}

int sum;
int num;
string buff;
void recursion(int i,int r) {
	int j;
	if(sum>t) return;
	
	buff += data[i];
	sum += data[i];
	num++;
	if(sum==t) result.push_back(buff);
		
	if(num<r) {
		for(j=i+1;j<n;j++) {
			recursion(j,r);
		}
	}
	
	num--;
	buff.erase(buff.begin()+buff.size()-1);
	sum -= data[i];
}
void print_a_line(string str) {
	cout << (int)str[0];
	int i;
	for(i=1;i<str.size();i++)
		cout << "+"<< ((int)str[i]);
	cout << endl;
}
void output() {
	int i,j;
	printf("Sums of %d:\n",t);
	if(result.size()==0) {
		cout << "NONE" << endl;
		return;
	}
		
	for(i=0;i<result.size();i++)
		print_a_line(result[i]);
			
}
void func() {
	sort(data,data+n,greater<int>());
	int i,j;
	for(i=0;i<n;i++) {
		for(j=1;j<=n;j++) {
			num=0;
			sum=0;
			recursion(i,j);
		}
	}
	sort(result.begin(),result.end(),greater<string>());
	result.erase(unique(result.begin(),result.end()),result.end());
	output();
}
int main()  {
	
	while(true) {
		cin >> t >> n;
		if(n==0) return 0;
		init();
		input();
		func();
	}
}
Last edited by tetuya on Tue Jun 14, 2005 5:14 pm, edited 1 time in total.

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am

Re: 574 Sum It Up. WA can you tell me some inputs?

Post by watershed » Mon Aug 09, 2004 5:57 pm

Code: Select all

INPUT:
999 1 999

CORRECT OUTPUT:
NONE

YOUR OUTPUT:
-25

User avatar
tetuya
New poster
Posts: 14
Joined: Thu May 27, 2004 2:31 pm

574 Sum It Up. WA can you tell me some inputs?

Post by tetuya » Mon Aug 09, 2004 6:04 pm

Thank you for your reply :D :D

I read this following passage.
and X1,...,Xn will be positive integers less than 100.
and , 999 1 999 is invalid input,isnt it?

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am

Re: 574 Sum It Up. WA can you tell me some inputs?

Post by watershed » Tue Aug 10, 2004 8:47 am

tetuya wrote:Thank you for your reply :D :D

I read this following passage.
and X1,...,Xn will be positive integers less than 100.
and , 999 1 999 is invalid input,isnt it?
maybe you can try in this test data

hiloshi
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan

Re: 574 Sum It Up. WA can you tell me some inputs?

Post by hiloshi » Tue Aug 31, 2004 2:49 pm

hi.

I got accept after some WA, but I think this problem is easy and simple.
Cause of your WA might a very little bug.

And...
tetuya wrote:Thank you for your reply :D :D

I read this following passage.
and X1,...,Xn will be positive integers less than 100.
and , 999 1 999 is invalid input,isnt it?
Yes, you are right.
Ignore watershed's replay, and think where is wrong.
So you will get accept.
Keep it up :D
I hope you can understand my poor English.

Post Reply

Return to “Volume 5 (500-599)”