Finding perimeter of a recursively modified square

user4115692 Published at Dev

user4115692

I have a square of side length 1 . Now, after each second, each square of side L will break into four squares each of side L/2.

enter image description here

I need the compute the total perimeter of the resulting figure, where total perimeter is defined as the sum of lengths of all line segments in the resulting figure. For example, the total perimeter of the image on the left is 4L while that on the right is 6L - 4L from the regular square edges and 2L from the internal line segments.

My code:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod 1000000007

int main() {



        int s;
        cin>>s;
       long long  int ans=4;

        for(int i=1;i<=s;i++)
            ans+=1<<i;
            ans=ans%mod;

        cout<<ans<<endl;


    return 0;
}

Since the final answer might not fit in a 64-bit signed integer, I am required to compute the answer modulo 1000000007.

For example, after 0 seconds, the length is 4. After 1 second, the length is 6. I am not getting the correct output. PLease help

Pradhan

Solve it recursively - let P(L, n) be the "perimeter" of the figure obtained after n iterations, starting with an LxL square. So, P(L, n+1) = 4*P(L/2,n) - 2*L. Also, since the perimeter is linear, P(L/2, n) = P(L, n)/2, giving you P(L,n) = 2*P(L,n-1) - 2*L. Substitute L=1 and run your loop.

   int s;
   cin>>s;
   long long  int ans=4;

   for(int i=1;i<=s;i++)
   {
        ans = 2*(ans-1);
        ans=ans%mod;
   }

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at2021-02-13

Comments

0 comments

From Dev

Related Related

Article