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

User avatar
tetuya
New poster
Posts: 14
Joined: Thu May 27, 2004 2:31 pm

Post by tetuya » Tue Aug 31, 2004 7:08 pm

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 ! :)
sorry for my poor English.

User avatar
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 )

Post by Sedefcho » 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.

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

problem limits

Post by jdmetz » 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.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » Tue Jul 26, 2005 5:48 pm

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

Post by polluel » 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 {

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

574 W.A

Post by tOd » Tue May 09, 2006 2:14 pm

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

Post by neno_uci » Thu May 11, 2006 5:41 am

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

Post by kodder » 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;
}


sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm
Location: Bangladesh

Help On 574

Post by sohel_acm » 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.
Love programmers,help programmers.

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Re: Help On 574

Post by Towhid » 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.... :)
From 0 to 0

altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Location: bangladesh
Contact:

574(sum it up) wA

Post by altaf hussain(sust_2002) » 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");
	}
}
thanks in advance;
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
Location: bangladesh
Contact:

getting wa in 574

Post by altaf hussain(sust_2002) » Sun Aug 27, 2006 12:31 pm

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
Location: Bangladesh
Contact:

Post by DP » 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
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
Location: bangladesh
Contact:

Post by altaf hussain(sust_2002) » Sat Sep 02, 2006 8:54 am

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

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sat Nov 04, 2006 8:20 pm

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

Post Reply

Return to “Volume 5 (500-599)”