Page 2 of 4
Posted: Tue Aug 31, 2004 7:08 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 !

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

Posted: Tue Jun 14, 2005 3:02 pm
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.

### problem limits

Posted: Sat Jul 09, 2005 4:43 pm
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.

Posted: Tue Jul 26, 2005 5:48 pm
hello all...
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

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

Posted: Tue Feb 28, 2006 4:22 pm
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 {

//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));
}

}

### 574 W.A

Posted: Tue May 09, 2006 2:14 pm
ACCEPT

Posted: Thu May 11, 2006 5:41 am

### 574

Posted: Sat May 20, 2006 7:19 am
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;
}

``````

### Help On 574

Posted: Mon May 22, 2006 10:09 pm
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.

### Re: Help On 574

Posted: Sat Aug 19, 2006 2:56 pm
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....

### 574(sum it up) wA

Posted: Sun Aug 27, 2006 12:23 pm
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

### getting wa in 574

Posted: Sun Aug 27, 2006 12:31 pm
removed after got acc

Posted: Wed Aug 30, 2006 8:22 pm
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
``````

Code: Select all

``````Within each test case, all sums must be distinct; the same sum cannot appear twice.
``````
-----------------------------------------------
http://www.third-eye-creative.com

Posted: Sat Sep 02, 2006 8:54 am
thak u dp,
i got the problem,and got ac.
bye
altaf

Posted: Sat Nov 04, 2006 8:20 pm
There is no input with xi<=0, but there is Xi with value 999.
Beware.