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

tetuya
New poster
Posts: 14
Joined: Thu May 27, 2004 2:31 pm
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 !
sorry for my poor English.
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### limits differ ( they are not as in the problem statement )

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
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

### problem limits

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
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
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
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.
polluel
New poster
Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm

### 574 in Java. Why WA???

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 {

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];
//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;}}
for(i=0;i<n;i++){
if(b){
matriu[imat][jmat]=v;jmat++;}
}
imat++;jmat=0;}
}

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)
{
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
New poster
Posts: 4
Joined: Thu Dec 29, 2005 5:41 am

### 574 W.A

ACCEPT
Last edited by tOd on Fri May 12, 2006 5:35 am, edited 1 time in total.
neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Search for '574' on the board and you will get enough threads about this problem...
kodder
New poster
Posts: 6
Joined: Mon Apr 10, 2006 6:19 am
Location: china
Contact:

### 574

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
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm

### Help On 574

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.
Love programmers,help programmers.
Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Contact:

### Re: Help On 574

sohel_acm wrote: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....
From 0 to 0
altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Contact:

### 574(sum it up) wA

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");
}
}
``````
altaf_sust_82@yahoo.com
http://www.sust.edu
altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Contact:

### getting wa in 574

removed after got acc
Last edited by altaf hussain(sust_2002) on Sat Sep 02, 2006 8:59 am, edited 1 time in total.
DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
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)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Contact:
thak u dp,
i got the problem,and got ac.
bye
altaf
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
There is no input with xi<=0, but there is Xi with value 999.
Beware.
Impossible is Nothing.