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
-
rij
- New poster
- Posts: 5
- Joined: Mon Nov 03, 2008 3:59 am
- Location: BD
-
Contact:
Post
by rij »
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;
}
-
dhanesh_09
- New poster
- Posts: 1
- Joined: Sat Jan 30, 2016 9:37 pm
Post
by dhanesh_09 »
I tried some of the udebug inputs and they worked well, but whenever I submit my code in UVa, I am getting WA.
Please help.
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();
}
}
public void addToSet(){
ArrayList<Integer> cArr = new ArrayList<Integer>();
int calcSum = 0;
for(int i = 0; i < this.size;i++){
if(flag[i] == true){
cArr.add(this.arr[i]);
calcSum += this.arr[i];
}
}
if(!set.contains(cArr) && calcSum == this.sum){
set.add(cArr);
}
}
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;
this.addToSet();
}
else {
flag[i] = true;
val = this.sum - this.arr[i];
for(int j=i+1;j<this.size;j++){
if(checkSum(j, val)){
this.addToSet();
}
}
}
}
}
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.addValToArr(i, val);
}
obj.calculateSum();
obj.printSet();
}while(size != 0 && sum != 0);
kb.close();
}
}