574 - Sum It Up

[titid_gede]

reading the problem description, i'm sure this is not a difficult (the soft word of easy ) problem. but now i'm look stupid coz of WA. are there special cases? can anyone help me?

[c]
--- cut GOT AC---
[/c]

[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-

[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
i'll fixed my code. Hope we can meet in Kampus Anggrek

[titid_gede]

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

[c]

--- cut --- GOT AC
[/c]

[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

[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

[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...

[deddy one]

*sigh*

I failed in your third case ,

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

btw, thx evan for your third case.

[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

[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.

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.

bye......

[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();
	}
}

[watershed]

Code: Select all

INPUT:
999 1 999

CORRECT OUTPUT:
NONE

YOUR OUTPUT:
-25

[tetuya]

Thank you for your reply

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]

Thank you for your reply

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]

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

Thank you for your reply

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