Breaking Sticks:
You recently received a bag of chocolate sticks for Halloween. To prevent you from compulsively eating all the chocolate sticks in one go, your dietician devises the following fun game.
In each move, you choose one of the sticks from your bag. Then, you either eat it, or break it into some number of equally-sized parts and save the pieces for later. The lengths of all sticks must always be integers, so breaking a stick into d parts is possible only if d is a divisor of the stick's length, and d>1.
Note that this means that a stick of length 1 cannot be broken anymore, and can only be eaten.Given the chocolate sticks you received, determine the length of the longest sequence of moves you can perform.
Complete the function longestSequence which takes an integer array a, denoting the lengths of the chocolate sticks, as input. Return the maximum number of moves you can perform to consume the chocolate sticks according the game.
Input Format
The first line contains one integer n which is the number of chocolate sticks.
The second line contains n space-separated integers, a1, a2,a3...an..the lengths of the chocolate sticks.
Constraints
• 1<=n<=100
• 1<<=ai<=1012
Subtasks
• For 20% of the total score, ai<=106
Output Format
Print a single integer which is the maximum number of moves you can perform.
Sample Input O
1
6
Sample Output 0
10
Explanation O
You break a chocolate stick into three equal parts (1 move), then break each of them in half (3 moves), and then eat all six sticks (6 moves). This gives you 10 moves.
Sample Input 1
3
17 24
Sample Output 1
55
Explanation 1
You make 1 move using the stick of length 1, then 8 moves using the stick of length 7, and in the end 46 moves using the stick of length 24. This gives 55 moves in total.
Sample input
3
1 7 24
Sample output
55
Program:
#include<stdio.h>
#include<stdlib.h>
long long int mindiv(long long int n){
long long int i,x=n;
for(i=2;i*i<=n;i++){
if(n%i==0)
return i;
}
return x;
}
int main(){
long long int n,i,x,ans;
scanf("%lld",&n);
long long int a=(long long int)malloc(n*sizeof(long long int));
ans=0;
for(i=0;i<n;i++){
scanf("%lld",&a);
ans+=a;
x=a;
while(x!=1){
x/=mindiv(x);
ans+=x;
}
}
printf("%lld\n",ans);
}
Explanation:
1.The code includes standard header files stdio.h and stdlib.h for input/output and memory allocation functions, respectively.
2.The mindiv function takes an input integer n and finds its smallest divisor by checking all the integers i from 2 to the square root of n. If n is divisible by i, then i is the smallest divisor of n, and it is returned. If n is not divisible by any integer i from 2 to the square root of n, then n itself is the smallest divisor, and it is returned.
3.The main function takes an input integer n using scanf, allocates an array a of n integers using malloc, and initializes a variable ans to zero.
4.In a for loop that runs n times, each input integer is read into the array a using scanf. The variable ans is incremented by the sum of the divisors of each input integer. This is done by initializing a variable x to the input integer a, and then repeatedly dividing x by its smallest divisor (found using the mindiv function) until x becomes 1. Each time x is divided by its smallest divisor, the divisor is added to ans.
5.Finally, the value of ans is printed using printf.
0 Comments