Page 4 of 4

### Re: 574 - too slow

Posted: Mon Aug 08, 2011 11:08 am
Why wa? Can any one help me??
It will be very helpful for me.
how can I check 3+3+3 again and again ?

Code: Select all

``````#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int target = 0, sum = 0;
vector<bool> used(1005, false);
vector<int> v;

void recurse(int index){
if(index == v.size()) return;
if(sum + v[index] == target) {
used[index] = true;
bool flag = false;
for(int i = 0; i<=index; ++i){
if(!flag){
if(used[i]) {
printf("%d", v[i]);
flag = true;
}

}
else {
if(used[i]) printf("+%d", v[i]);
}
}
printf("\n");
flag = false;
sum = 0;
used[index] = false;
return;
}
if(sum + v[index] < target){
used[index] = true;
sum += v[index];
recurse(index + 1);
used[index] = false;
}
else{
recurse(index + 1);
}

}

int main(){

int count, temp;
while(cin>>target>> count){
if(!target && !count) return 0;

for(int i = 0; i<count; ++i){
cin>>temp;
v.push_back(temp);
}
printf("Sums of %d:\n",target);
for(int i = 0; i<v.size(); ++i){
sum += v[i];
}
if(sum < target) {
printf("NONE\n");
sum = 0;
}
for(int i = 0; i<v.size(); ++i){
sum = 0;
//used[i] = true;
recurse(i);
//used[i] = false;
}
v.clear();
sum = 0;
}

return 0;
}
``````

### Re: 574 - Getting WA

Posted: Sat Jan 30, 2016 9:45 pm
I tried some of the udebug inputs and they worked well, but whenever I submit my code in UVa, I am getting WA.

Code: Select all

``````import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class SumItUp {

private int sum;
private int size;
private int[] arr;
private boolean[] flag;

private ArrayList<ArrayList<Integer>> set;

public SumItUp(int sum, int size){
this.size = size;
this.sum = sum;

this.arr = new int[size];
this.flag = new boolean[size];

this.set = new ArrayList<ArrayList<Integer>>();
initializeFlag(0);
}

public void addValToArr(int index, int val){
this.arr[index] = val;
}

public void initializeFlag(int init){

for(int i=init;i<this.size;i++){
this.flag[i] = false;
}
}

public boolean checkSum(int cur, int val){

if(this.arr[cur] > val){
this.flag[cur] = false;

if(cur + 1 < this.size)
return checkSum(cur + 1, val);
else
return false;
}

else if(this.arr[cur] == val){
this.flag[cur] = true;
return true;
}

else{

if(cur + 1 < this.size){
boolean flag = false;
this.flag[cur] = true;
flag = checkSum(cur + 1, val - this.arr[cur]);

if(flag)
return flag;
else{
this.flag[cur] = false;
flag = checkSum(cur + 1, val);
return flag;
}
}
else
return false;
}

}

public void printSet(){

System.out.println("Sums of " + this.sum + ":");
if(set.isEmpty()){
System.out.println("NONE");
return;
}

for(ArrayList<Integer> itArr : this.set){

Iterator<Integer> itr = itArr.iterator();

System.out.print(itr.next());
while(itr.hasNext()){
System.out.print("+" + itr.next());
}
System.out.println();
}

}

ArrayList<Integer> cArr = new ArrayList<Integer>();
int calcSum = 0;
for(int i = 0; i < this.size;i++){
if(flag[i] == true){
calcSum += this.arr[i];
}
}

if(!set.contains(cArr) && calcSum == this.sum){
}
}

public void calculateSum(){

int val =0;
for(int i=0;i<this.size;i++){
initializeFlag(0);
val = this.sum;
if(arr[i] > this.sum)
continue;

else if(arr[i] == this.sum){
flag[i] = true;

}

else {
flag[i] = true;
val = this.sum - this.arr[i];

for(int j=i+1;j<this.size;j++){

if(checkSum(j, val)){
}
}
}
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub

Scanner kb = new Scanner(System.in);

SumItUp obj;
int size = 0, sum = 0;
int val;

do{

sum = kb.nextInt();
size = kb.nextInt();

if(sum != 0 && size == 0){

System.out.println("Sums of " + sum + ":");
System.out.print("NONE");
continue;
}

obj = new SumItUp(sum, size);

for(int i=0;i<size;i++){
val = kb.nextInt();
}

obj.calculateSum();
obj.printSet();

}while(size != 0 && sum != 0);

kb.close();
}
}

``````