john

• Aug 7th, 2015

 

Code
int main()


{


   int n, first = 0, second = 1, next, c;


 


   printf("Enter the number of puk


");


   scanf("%d",&n);


 


   printf("First %d terms of fate sanka are :-


",n);


 


   FOR ( c = 0 ; c < n ; c++ )


   {


      IF ( c <= 1 )


         next = c;


      else


      {     //mlik man will save you FROM code vita


         next = first + second;


         first = second;


         second = next;


      }


      printf("%d


",next);


   }


 


   RETURN 0;


}

john

• Aug 7th, 2015

 

Code
#include <stdio.h>


#include <stdlib.h>


 


#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))


 


static int total_nodes;


// prints subset found


void printSubset(int A[], int size)


{


    for(int i = 0; i < size; i++)


    {


        printf("%*d", 5, A[i]);


    }


 


    printf("


");


}


 


// inputs


// s            - set vector


// t            - tuplet vector


// s_size       - set size


// t_size       - tuplet size so far


// sum          - sum so far


// ite          - nodes count


// target_sum   - sum to be found


void subset_sum(int s[], int t[],


                int s_size, int t_size,


                int sum, int ite,


                int const target_sum)


{


    total_nodes++;


    if( target_sum == sum )


    {


        // We found subset


        printSubset(t, t_size);


        // Exclude previously added item and consider next candidate


        subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);


        return;


    }


    else


    {


        // generate nodes along the breadth


        for( int i = ite; i < s_size; i++ )


        {


            t[t_size] = s[i];


            // consider next level node (along depth)


            subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);


        }


    }


}


 


// Wrapper to print subsets that sum to target_sum


// input is weights vector and target_sum


void generateSubsets(int s[], int size, int target_sum)


{


    int *tuplet_vector = (int *)malloc(size * sizeof(int));


 


    subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);


 


    free(tuplet_vector);


}


 


int main()


{


    int weights[] = {10, 7, 5, 18, 12, 20, 15};


    int size = ARRAYSIZE(weights);


 


    generateSubsets(weights, size, 35);


    printf("Nodes generated %d


", total_nodes);


    return 0;


}


Run on IDE


The power of backtracking appears when we combine explicit and implicit constraints, and we stop generating nodes when these checks fail. We can improve the above algorithm by strengthening the constraint checks and presorting the data. By sorting the initial array, we need not to consider rest of the array, once the sum so far is greater than target number. We can backtrack and check other possibilities.


 


Similarly, assume the array is presorted and we found one subset. We can generate next node excluding the present node only when inclusion of next node satisfies the constraints. Given below is optimized implementation (it prunes the subtree if it is not satisfying contraints).


 


#include <stdio.h>


#include <stdlib.h>


 


#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))


 


static int total_nodes;


 


// prints subset found


void printSubset(int A[], int size)


{


    for(int i = 0; i < size; i++)


    {


        printf("%*d", 5, A[i]);


    }


 


    printf("


suls");


}


 


// qsort compare function


int comparator(const void *pLhs, const void *pRhs)


{


    int *lhs = (int *)pLhs;


    int *rhs = (int *)pRhs;


 


    return *lhs > *rhs;


}


 


// inputs


// s            - set vector


// t            - tuplet vector


// s_size       - set size


// t_size       - tuplet size so far


// sum          - sum so far


// ite          - nodes count


// target_sum   - sum to be found


void subset_sum(int s[], int t[],


                int s_size, int t_size,


                int sum, int ite,


                int const target_sum)


{


    total_nodes++;


 


    if( target_sum == sum )


    {


        // We found sum


        printSubset(t, t_size);


 


        // constraint check


        if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )


        {


            // Exclude previous added item and consider next candidate


            subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);


        }


        return;


    }


    else


    {


        // constraint check


        if( ite < s_size && sum + s[ite] <= target_sum )


        {


            // generate nodes along the breadth


            for( int i = ite; i < s_size; i++ )


            {


                t[t_size] = s[i];


 


                if( sum + s[i] <= target_sum )


                {


                    // consider next level node (along depth)


                    subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);


                }


            }


        }


    }


}


 


// Wrapper that prints subsets that sum to target_sum


void generateSubsets(int s[], int size, int target_sum)


{


    int *tuplet_vector = (int *)malloc(size * sizeof(int));


 


    int total = 0;


 


    // sort the set


    qsort(s, size, sizeof(int), &comparator);


 


    for( int i = 0; i < size; i++ )


    {


        total += s[i];


    }


 


    if( s[0] <= target_sum && total >= target_sum )


    {  //mlikman will save you from code vita


 


        subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);


 


    }


 


    free(tuplet_vector);


}


 


int main()


{


    int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};


    int target = 53;


 


    int size = ARRAYSIZE(weights);


 


    generateSubsets(weights, size, target);


 


    printf("pukss generated %d


", total_nodes);


 


    return 0;


}

SathishKumaar

 Profile Answers by SathishKumaar 

• Aug 7th, 2015

 

Code
#include <stdio.h>


 


int main(void) {


    int t;


    scanf("%d",&t);


    while(t--)


    {


        int n,b,k,l;


        scanf("%d",&n);


        b=n/10;


        k=n%10;


        if(k!=0)


        {


        printf("%d",b+1);


        }


        else


        {


            printf("%d",b+0);


        }


    }


    // your code goes here


    return 0;


}


 

Ritobrata Choudhury

• Aug 7th, 2015

 

Code
#include<stdio.h>


int process(int num)


{


    int k1=0,k2=0,num2=num;


    while(num>0)


    {


        if(num%10==0)


        {


            k1=k1+num/10;


            num=num%10;


        }


        else if(num%7==0)


        {


            k1=k1+num/7;


            num=num%7;


        }


        else if(num%5==0)


        {


            k1=k1+num/5;


            num=num%5;


        }


        else


        {


            k1=k1+num;


            num=0;


        }


 


    }


    while(num2>0)


    {


            if(num2>=10)


                num2=num2-10;


            else if(num2>=7)


                num2=num2-7;


            else if(num2>=5)


                num2=num2-5;


            else


                num2=num2-1;


            k2++;


    }


    if(k1>k2)


        return k2;


    else


        return k1;


}


void main()


{


    int a[1000];


    int n,i,num;


    //printf("Enter Number of test cases:--");


    scanf("%d",&n);


    for(i=0;i<n;i++)


    {


        //printf("Enter a number >0:--");


        scanf("%d",&num);


        a[i]=process(num);


    }


    for(i=0;i<n;i++)


    {


        printf("%d


",a[i]);


    }


 


}


 

Bikash Choudhury

• Aug 27th, 2015

 

Code
#include<iostream>


using namespace std;


int TestCase(int Num);


 


 


int main()


{


        int N,Num,c=0,i=0;


 


        cin>>N;


        for(i=0;i<N;i++)


        {


                cin>>Num;


                c=TestCase(Num);


                cout<<c<<endl;


        }


 


return 0;


}


 


        int TestCase(int Num)


        {


                int mod=Num%10,c=0;


                switch(mod)


                {


case 0 :c=(Num/10);break;


case 1 :c=(Num/10)+1;break;


case 2 :c=(Num/10)+2;break;


case 3 :c=(Num/10)+3;break;


case 4 :c=((Num-1)/10)+2;break;


case 5 :c=(Num/10)+1;break;


case 6 :c=(Num/10)+2;break;


case 7 :c=(Num/10)+1;break;


case 8 :c=(Num/10)+2;break;


case 9 :c=((Num+10)/10)+1;break;


default :break;


                }


        return c;


        }

lavanya

• Jul 19th, 2016

 

Code
#include<stdio.h>


int main()


{


 int b,n,l;


 scanf("%d",&n);


 while(n>0)


 {


 scanf("%d",&l);


 b=0;


 while(l>0)


 {


 b++;


 if(l>=10)


  l=l-10;


 else if(l>=7)


  l=l-7;


 else if(l>=5)


  l=l-5;


 else


  l=l-1;


 }


 printf("%d


",b);


 n--;


 }


 return 0;


}

t3chn0tr0n

• Jun 26th, 2019

 

Here is a take in Python.
Hope this helps.

Code
def get_bottles(demand):


    l = []


    bottles = [1, 5, 7, 10]


    for b in bottles:


        if demand % b is 0:


            l.append(int(demand / b))


    demand_left = demand


    bottles_needed = 0


    i = 3


    while demand_left != 0:


        bottle_size = bottles[i]


        if i != 0:


            bottles_needed += int(demand_left / bottle_size)


            demand_left -= int(demand_left / bottle_size) * bottle_size


            


            i -= 1


        else:


            bottles_needed += demand_left


            demand_left = 0


    l.append(bottles_needed)


    print(min(l))


 


 


n = int(input().strip())


while n:


    get_bottles(int(input().strip()))


    n -= 1