Getting a wrong answer !!!

[Maggi Iggam]

Here's question :-

As we all know caterpillars love to eat leaves. Usually, a caterpillar sits on leaf, eats as much of it as it can (or wants), then stretches out to its full length to reach a new leaf with its front end, and finally "hops" to it by contracting its back end to that leaf.
We have with us a very long, straight branch of a tree with leaves distributed uniformly along its length, and a set of caterpillars sitting on the first leaf. (Well, our leaves are big enough to accommodate upto 20 caterpillars!). As time progresses our caterpillars eat and hop repeatedly, thereby damaging many leaves. Not all caterpillars are of the same length, so different caterpillars may eat different sets of leaves. We would like to find out the number of leaves that will be undamaged at the end of this eating spree. We assume that adjacent leaves are a unit distance apart and the length of the caterpillars is also given in the same unit.
For example suppose our branch had 20 leaves (placed 1 unit apart) and 3 caterpillars of length 3, 2 and 5 units respectively. Then, first caterpillar would first eat leaf 1, then hop to leaf 4 and eat it and then hop to leaf 7 and eat it and so on. So the first caterpillar would end up eating the leaves at positions 1,4,7,10,13,16 and 19. The second caterpillar would eat the leaves at positions 1,3,5,7,9,11,13,15,17 and 19. The third caterpillar would eat the leaves at positions 1,6,11 and 16. Thus we would have undamaged leaves at positions 2,8,12,14,18 and 20. So the answer to this example is 6.
Input format
The first line of the input contains two integers N and K, where N is the number of leaves and K is the number of caterpillars. Lines 2,3,...,K+1 describe the lengths of the K caterpillars. Line i+1 (1 ≤ i ≤ K) contains a single integer representing the length of the ith caterpillar.
You may assume that 1 ≤ N ≤ 1000000000 and 1 ≤ K≤ 20. The length of the caterpillars lie between 1 and N.
Output format
A line containing a single integer, which is the number of leaves left on the branch after all the caterpillars have finished their eating spree.
Test Data:
The range of input values over which your pragram is to be tested is described above. In addition, 50% of the test-cases will also satisfy 1 ≤ N≤ 10000000 and K ≤ 16.
Example:
We now illustrate the input and output formats using the example described above.
Sample Input:
20 3
3
2
5
Sample Output:
6
Hint:
You may use 64-bit integers (long long int in C/C++) to avoid errors while multiplying large integers. The maximum value you can store in a 32-bit integer is 2^31-1, which is approximately 2 * 10^9. 64-bit integers can store values greater than 10^18.

Here's my solution using Inclusion Exclusion Principle :-

#include <cstdio>
#include <numeric>

int gcd(int a, int b)
{
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
}

int lcm(int a, int b)
{
    int temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
}

int main() {
int i,j,n,l[20],leng,count=0;
scanf("%d %d",&leng,&n);
for (i=0;i<n;i++) {scanf("%d",&l[i]);count+=((n-1)/l[i])-1;}
for (i=0;i<(n-1);i++) {
for (j=i+1;j<n;j++) {
count=count - lcm(l[i],l[j]);
}}
count+=std::accumulate(l, l + 4, 1, lcm);
printf("%d",leng-count);
}

Can anybody please correct the code and thnx to this community i am really indebted to it ! :)

[Moschops]

I'm not going to even read your code, because it's just like all the rest of your code; horrific.

Please, please, for the love of God(s), start using meaningful variable names. Start commenting your code. Stop using scanf and printf. Use braces in a way that actually makes the code easier to understand, rather than harder. Stop jamming the entire contents of a block on a single line. Space things out around operators and commas and semi-colons.

Help yourself by helping us to help you.

[Maggi Iggam]

LOL !!!
Nvr mind , here's the edited and better looking code :P :-

#include <cstdio>
#include <numeric>

int gcd(int a, int b)                         //function for calculatig Greatest Common Divisor , to be used for calculating LCM actually
{
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
}

int lcm(int a, int b)                             //For calculating LCM
{
    int temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
}

int main() {
int i,j,n,l[20],leng,count=0;                         //i & j are counter variables , n is number of caterpillars , l[20] is array for storing length of each caterpillar , leng is for length of leafs and count is for counting number of leaves eaten
scanf("%d %d",&leng,&n);
for (i=0;i<n;i++) {
scanf("%d",&l[i]);                       //Storing length of each caterpillar in array
count+=((n-1)/l[i])-1;                 //Calculating number of leafs the entered length of caterpillar will be eating mathematically 
}
for (i=0;i<(n-1);i++) {               //Subtracting number of leafs eaten by both ith and jth caterpillar , since we have overcounted them previously accordingly to Inclusion Exclusion Principle
for (j=i+1;j<n;j++) {
count=count - lcm(l[i],l[j]);
}
}
count+=std::accumulate(l, l + 4, 1, lcm);           //Adding LCM of length of caterpillar 
printf("%d",leng-count);                  //Count was having number of leaves eaten but number of leaves uneaten is asked so substracting from total 
}

Hope this helps you to help me @Moschops :P !!!

[Moschops]

count=count - lcm(l[i],l[j]);

I think there is a mistake here.

For example, let's say there are 100 leaves, and caterpillars of size one and size two.

THe first will eat 100 leaves. The second will eat 50 leaves. So count is 150.

Now, we apply this:

for (i=0;i<(n-1);i++) {               //Subtracting number of leafs eaten by both ith and jth caterpillar , since we have overcounted them previously accordingly to Inclusion Exclusion Principle
  for (j=i+1;j<n;j++) {
    count=count - lcm(l[i],l[j]);
  }
}

n is two, so we go through this loop only twice, and we set count to be count minus the lcm of (1,2), twice. So now count is 148. That's more than the number of leaves; there must be a mistake in this part of your algorithm.

Before you added comments, there was no way to know what you were trying to do, so helping you was pretty much impossible.

[coder777]

Hm, you seems to have some mathematical knowledge.

Your problem is that trying to avoid the development. I tried to introduce this step by step approch, but you immediately gave up/shut down.

debugging is also an important part of the development. if you'd done this you'd found that this

count+=((n-1)/l[i])-1;

is blatant nonsense.


what you mean is not n, instead it's leng. (I heard somewhere that naming the variables is important, but this is just a rumor...)

But nonetheless the formula above is just wrong. Look at this:

count += ((leng + l[i] - 1) / l[i]);

Are you able to figure out what it means?