Page 1 of 4

574 - Sum It Up

Posted: Thu Apr 10, 2003 5:11 am
by titid_gede
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]

Posted: Thu Apr 10, 2003 6:50 am
by turuthok
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-

Posted: Thu Apr 10, 2003 7:59 am
by titid_gede
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

Posted: Mon Apr 14, 2003 10:28 am
by titid_gede
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]

Posted: Mon Apr 14, 2003 2:08 pm
by Hisoka
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

Posted: Mon Apr 14, 2003 5:46 pm
by deddy one
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

Posted: Mon Apr 14, 2003 6:39 pm
by Hisoka
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:

Posted: Mon Apr 14, 2003 8:17 pm
by deddy one
*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.

Posted: Tue Apr 15, 2003 6:03 am
by titid_gede
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 :( :(

Posted: Tue Apr 15, 2003 12:06 pm
by Hisoka
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:

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

Posted: Mon Aug 09, 2004 3:45 pm
by tetuya
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();
	}
}

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

Posted: Mon Aug 09, 2004 5:57 pm
by watershed

Code: Select all

INPUT:
999 1 999

CORRECT OUTPUT:
NONE

YOUR OUTPUT:
-25

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

Posted: Mon Aug 09, 2004 6:04 pm
by tetuya
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?

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

Posted: Tue Aug 10, 2004 8:47 am
by watershed
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

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

Posted: Tue Aug 31, 2004 2:49 pm
by hiloshi
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