574 - Sum It Up

[tetuya]

Hi hiloshi , watershed.

I got Accepted ! Thank you

I used int array.

considerations are below.

1. string operation is not proper for using string which is substituted for int.
2. uva put my program into invalid input.
3. other.

anyway,I expected that string is suspect.
It's by grace of two !
Thanks !

[Sedefcho]

That's right !
The limits are different, they are not as described
in the problem statement.

If we assume the limits are
1) max value for n -> 12
2) max number in sum ( additive ) -> 100
we get WA

If we assume
1) max value for n -> 100
2) max number in sum ( additive ) -> 1000
we get ACC

Hope this will help someone who is wondering why he/she gets
WA although the algorithm implemented is OK.

[jdmetz]

n is always <= 12
t is always < 1000

These are as the problem statement says.

But, one of the xi is 999 (not < 100 as the problem says).

I tested using my AC solution.

It passes with exit conditions on n > 12, t >= 1000, and xi >= 1000. But, it fails with exit on n > 12, t >= 1000, and xi >= 999.

[I LIKE GN]

hello all...
please give me some I/O
i know it's stupid mistake!!!!
one thing
for t=0 i print
0
0+0
0+0+0
...
depending on number of zeros in X1 up to Xn

[polluel]

import java.io.*;
import java.util.*;



class Main{

static int imat=0;
static int jmat=0;
static int XLLEG=50;
static int FILES=50;
static int[][] matriu = new int[FILES][12];

public static void main (String args []) throws Exception {

//BufferedReader entrada = new BufferedReader(new InputStreamReader(System.in));
String linea = ReadLn(XLLEG);
//System.out.println(linea);
java.util.StringTokenizer st = new java.util.StringTokenizer(linea," ");
String tstring=st.nextToken();
String nstring=st.nextToken();
String aux;
int t,n,i;
t=Integer.parseInt(tstring);
n=Integer.parseInt(nstring);
int[] v= new int[12];
boolean[] b = new boolean[12];
while (n!=0){
System.out.print("Sums of ");
System.out.print(t);
System.out.println(":");
for(i=0;i<n;i++){
aux=st.nextToken();
v=Integer.parseInt(aux);}
b[0]=true;
backtracking(v,b,t,n,0);
b[0]=false;
backtracking(v,b,t,n,0);
filesd(matriu);
if (matriu[0][0]==0){System.out.println("NONE");}
else {escmat(matriu);}
imat=0;
jmat=0;
matriu = new int[FILES][12];
linea = ReadLn(XLLEG);
//System.out.println(linea);
st=new java.util.StringTokenizer(linea," ");
t=Integer.parseInt(st.nextToken());
n=Integer.parseInt(st.nextToken());
}
}

static void backtracking(int[] v,boolean[] b,int t, int n, int contador){
int x=0;
int i;
for(i=0;i<n;i++){
if(b){x=x+v;}}
if(x==t && contador==(n-1)){
for(i=0;i<n;i++){
if(b){
matriu[imat][jmat]=v;jmat++;}
}
imat++;jmat=0;}
if (contador<n-1) {
contador++;
b[contador]=true;
backtracking(v,b,t,n,contador);
b[contador]=false;
backtracking(v,b,t,n,contador);}
}

static void filesd(int[][] mat){
int a,b;
for (a=0;a<FILES;a++){
for (b=a+1;b<FILES;b++){
if (dosfiles(mat[a],mat)){mat[0]=0;}
}
}
}

static boolean dosfiles(int[] v, int[] w){
int a=0;
boolean b=true;
while(a<v.length && b){
if(v[a]!=w[a]){b=false;}
a++;}
return b;
}

static void escmat(int[][] mat) throws Exception{
int a,b;
for (a=0;a<FILES;a++){
if (mat[a][0]!=0){
for(b=0;b<FILES;b++){
System.out.print(mat[a]);
if (mat[a][b+1]==0){System.out.println("");b=FILES;}
else{System.out.print("+");}}
}
}

}

static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int x,lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
//System.out.println("lg:"+lg);
//System.out.println("lin[lg-1]:"+lin[lg-1]);
//System.out.println("lin[lg]:"+lin[lg]);
//System.out.println("lin[lg+1]:"+lin[lg+1]);
if(lin[lg-1]!='0')lg--;

}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

}

[tOd]

ACCEPT

[neno_uci]

Search for '574' on the board and you will get enough threads about this problem...

[kodder]

can any one help me i can pass all the data set find in
this board, but still cannot ac !!! any one help me or
send the source code to me...
my mail is kodderster@gmail.com thank you

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX	130

int	n, total, data[MAX], flag[MAX];
int	mark, alen, ans[MAX], prev[MAX], plen;

void output(void)
{
	int	i;

	if (alen < plen) return;
	if (alen == plen) {
		for (i = 0; i < alen; i++) 
			if (ans[i] != prev[i])
				goto out;
		return;
	}
out:	printf("%d", ans[0]);
	for (i = 1; i < alen; i++) printf("+%d", ans[i]);
	printf("\n");
	mark = 0;
	plen = alen;
	for (i = 0; i < alen; i++) prev[i] = ans[i];
}
void dfs(int floor)
{
	int	i, sum;

	if (floor >= n) return;
	flag[floor] = 1;
	for (i = 0, sum = 0, alen = 0; i < n; i++) {
		if (flag[i]) {
			sum += data[i];
			ans[alen++] = data[i];
		}
	}
	if (sum == total) {
		output();
		flag[floor] = 0;
		//for (j = floor + 1; data[j] == data[floor] && j < n; j++);
		//dfs(j);
		dfs(floor + 1);
	} else if (sum > total) {
		flag[floor] = 0;
		//for (j = floor + 1; data[j] == data[floor] && j < n; j++);
		//dfs(j);
		dfs(floor + 1);
	} else {
		dfs(floor + 1);
		flag[floor] = 0;
		dfs(floor + 1);
	}
}
int invalid(void)
{
	int	i;

	for (i = 0; i < n; i++) 
		if (data[i] < 1 || data[i] >= 100) return 1;
	for (i = 1; i < n; i++) 
		if (data[i] > data[i - 1]) return 1;
	return 0;
}
int main(void)
{
	int	i;

	while (scanf("%d %d", &total, &n) && n) {
		for (i = 0; i < n; i++) scanf("%d", &data[i]);
		memset(flag, 0, sizeof(flag));
		plen = 0;
		mark = 1;
		printf("Sums of %d:\n", total);
		if (!invalid()) {
			dfs(0);
			if (mark) printf("NONE\n");
		} else printf("NONE\n");
	}
	return 0;
}

[sohel_acm]

Hi kodder
I have found your problem.Your code fails to give the correct output to the following input.
Input:

4 0
6 0

Your program terminates here while the correct output is:

Sums of 4:
NONE
Sums of 6:
NONE

Best Of Luck.

[Towhid]

Hi kodder
I have found your problem.Your code fails to give the correct output to the following input.
Input:

4 0
6 0

Your program terminates here while the correct output is:

Sums of 4:
NONE
Sums of 6:
NONE

I don't think that is the case. Because when n==0 the program should terminate:

If n = 0 it signals the end of the input;

But there are cases for which your program doesn't work:

Input:
0 2 0 0
2 5 2 1 1 0 0

Output:
Sums of 0:
0
0+0
Sums of 2:
2
2+0
2+0+0
1+1
1+1+0
1+1+0+0

Try for these. Good luck....

[altaf hussain(sust_2002)]

hi, i am getting wa in 574. plz help me :::
here my code:

Code: Select all

:

#include<stdio.h>
#include<math.h>
#define max_sz 100

int in[max_sz],pre_sol[max_sz],none,pre_k;

void construct_candidates(int a[],int k,int n,int c[],int *ncandidates){
	int i;
	*ncandidates=0;
	for(i=a[k-1]+1;i<=n;i++)
		c[(*ncandidates)++]=i;
}

int same_sol(int a[],int k,int n)
{
	int flag=0,i;
	
	if(k>pre_k)
	{
		for(i=1;i<=k;i++)
			pre_sol[i]=in[a[i]];
		pre_k=k;
		return 1;
	}

	if(k<=pre_k)
	{		
		for(i=1;i<=k;i++)
			if(pre_sol[i]!=in[a[i]])
				flag=1;
				pre_sol[i]=in[a[i]];
		if(k<pre_k)
		{
			for(i=1;i<pre_k;i++)
			if(pre_sol[i]==in[a[i]])
				flag=0;
			if(flag==1)
				return 1;
			else 
				return 0;
		}
	}
	pre_k=k;
	if(flag==1)
		return 1;
	else
		return 0;
}

void process_solution(int a[],int k,int n,int total)
{
	int i,sum=0;
	for(i=1;i<=k;i++)
		sum+=in[a[i]];
	if((sum==total)&& same_sol( a,k,n ) )
	{
		none=1;
		for(i=1;i<k;i++)
			printf("%d+",in[a[i]]);
		if(k>0)
			printf("%d",in[a[k]]);
		printf("\n");
	}
}

void backtrack(int a[],int k,int n,int total)
{
	int i,c[max_sz],ncandidates;
	process_solution(a,k,n,total);
	k++;
	construct_candidates(a,k,n,c, &ncandidates);
	for(i=0;i<ncandidates;i++)
	{
		a[k]=c[i];
		backtrack(a,k,n,total);

	}
}

void main()
{
	int a[max_sz],n,i,total;
	a[0]=0;
	while(scanf("%d %d",&total,&n)==2 && n)
	{
		none=pre_k=0;
		printf("Sums of %d:\n",total);
		for(i=1;i<=n;i++)
			scanf("%d",&in[i]);	
		for(i=0;i<max_sz;i++)
			pre_sol[i]=-1;
		backtrack(a,0,n,total);
		if(none == 0)
			printf("NONE\n");
	}
}

thanks in advance;
altaf_sust_82@yahoo.com
http://www.sust.edu

[altaf hussain(sust_2002)]

removed after got acc

[DP]

Hey, try with this test case:

Code: Select all

4 6 4 3 2 2 1 4

Code: Select all

Output:
4
3+1
2+2

But your output.....what ????
Read the problem Statement carefully:

Code: Select all

Within each test case, all sums must be distinct; the same sum cannot appear twice.

-----------------------------------------------
http://www.third-eye-creative.com

[altaf hussain(sust_2002)]

thak u dp,
i got the problem,and got ac.
bye
altaf

[cytmike]

There is no input with xi<=0, but there is Xi with value 999.
Beware.