Page 2 of 4

Posted: Tue Aug 31, 2004 7:08 pm
by tetuya
Hi hiloshi , watershed.

I got Accepted ! Thank you :wink:

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

problem limits

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

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

574 in Java. Why WA???

Posted: Tue Feb 28, 2006 4:22 pm
by 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));
}

}

574 W.A

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

Posted: Thu May 11, 2006 5:41 am
by neno_uci
Search for '574' on the board and you will get enough threads about this problem...

574

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


Help On 574

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

Re: Help On 574

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

getting wa in 574

Posted: Sun Aug 27, 2006 12:31 pm
by altaf hussain(sust_2002)
removed after got acc

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

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

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