CareerCup

bool is_sum_possible(int num_items)
{
bool * temp;
int i;

if(num_items<18)
{
if((num_items==6)||(num_items==9)||(num_items==17)||(num_items==12)||
(num_items==15))
		return true;
}

temp=(bool *)malloc(sizeof(bool)*(num_items+1));
for(i=0;i<num_items;i++)
temp[i]=false;

temp[6]=temp[9]= temp[17]=temp[12]=temp[15]=true;

for(i=18;i<num_items;i++)
{
		if(temp[i-6]|temp[i-9]|temp[i-17])
				temp[i]=true;
}

return temp[num_items];

}

1 #include <stdio.h>
  2 int f(int input) {
  3         if(!input) return 1;
  4         if(input < 6) return 0;
  5         return f(input-6) || f(input-9) ||f(input-17);
  6 }
  7 
  8 int main() {
  9         int iNum;
 10         while(scanf("%d\n",&iNum) > 0) {
 11                 if(f(iNum)) {
 12                         printf("true!\n");
 13                 } else {
 14                         printf("false!\n");
 15                 }
 16         }
 17         return 0;
 18 }

take LCM of three number if the N is divisible by LCM (6,9,17) then it is possible otherwise not...

Use the knapsack technique to do it.

#include <iostream>
using namespace std;

//Function to calculate posssibility
bool IsPossible(int numItems)
{
     int tempItems;
     if (numItems < 6) return false;
     if (numItems < 9) return false;
     if (numItems < 17 && (numItems != 9 || numItems != 15)) return false;
        
     if ((tempItems = numItems % 17) > 0)
        {           
            if ((tempItems = ((tempItems != 9 && tempItems != 6) ? tempItems + 17 :tempItems ) % 9) > 0 )
            {    
                 if((tempItems=(tempItems != 6 ? tempItems + 9:tempItems) % 6) > 0)
                 {
                     return false;
                 }
                 return true;
            }
            return true;
        }  
     return true;                
}

//Driver Function
int main()
{
    int amount;
    do{
    cout<<"Enter amount here: ";
    cin>>amount;  
    bool result =IsPossible(amount);
    if(result)
        cout<< "Yes, Can be "<<endl;
    else
        cout<< "No, Cant be "<<endl;  
    }while(amount != -1);           
    
    return 0;    
}

great solution... :))

bool IsSalePossible(int number)
{
if(number % 6 == 0)
return true;
if(number % 9 == 0)
return true;
if(number % 17 == 0)
return true;
if(number %3 == 0 && number % 6 == 3 && number > 6)
return true;
number = number - 17;
while(number > 0)
{
if(number % 6 == 0)
return true;
if(number % 9 == 0)
return true;
number = number - 17;
}
return false;
}

It may work like: (only algorithm, not coding)
[input:x]
if((x%6 and x%9 and x%17)==0) return true;
k=x/17;
kr = x%17;
if(k>=kr) return true;
if(k>=1 && (kr==10 || kr==7 || kr==13)) return true;
if(k%2==0 && (kr==2 || kr==4 || kr==11) return true;

// Many more cases can be there...

The problem is the same as finding if there exists a non-negative solution to a linear diophantine equation in 3 variables.

The problem is the same as finding if there exists a non-negative solution to a linear diophantine equation in 3 variables.

/* Here a = 6, b = 8 & c = 17 as per the question */
	public static boolean canGivePacks(int noOfItems, int a, int b, int c) {
		int[] combinations = {a, b, c, a + b, a + c, b + c, a + b + c};
		
		for (int comb: combinations) {
			if(noOfItems % comb == 0) 
				return true;
		}
		return false;
	}
	
	public static void main(String[] args) {
		for( int i = 0; i < 100; i++) {
		System.out.println("No. of Apples (" + i + ") supports packing?:" + ApplePacks.canGivePacks(i, 6, 9, 17));;
		}
	}

A simple DP will do.

s[0] = true
s[i] = true if either s[i-6], s[i-9] or s[i-17] is true

N = 9a + 6b => N = 3q => q = 3a + 2b, given N, find a and b: q mod 3 = 2 => b=1,a=q/3, q mod 3 = 1 => b=2,a=q/3-1, else a=q/3, this means that for every N(3) > 5 there exists pair of a and b to satisfy requirements.

Let number of apple to be writtable as M = 17q + t, and M mod 3 != 0 and t mod 3 != 0 - as it has been checked in previous para, moving forward: q - t = d > 0 =>
M could be written as 17(q-t) + t + (18-1)t=17d + 18t.
So it's simple! Any objections?

You guys are making this way too complicated.

public boolean canPurchase(int num)
{
    num %= 17;
    num %= 9;
    num %= 6;
    return num == 0;

}

You guys are making this way too complicated.

public static boolean canPurchase(int num)
{
    num %= 17;
    num %= 9;
    num %= 6;
    return num == 0;

}

Very simple answer:

public static boolean canPurchase(int num)
{
    num %= 17;
    num %= 9;
    num %= 6;
    return num == 0;

}

number = gets.to_i

p (number % 6 == 0  || number % 9 == 0 || number % 17 == 0)