fork download
copy 
  1. //Pratik Dayama - TRIDIM
  2. #include <stdio.h>
  3. #define MOD 1000000007
  4. #define access(i,j) ((i)*(i+1))/2+j //macro to access 1D array with 2D indexing
  5.  
  6. long long pow2[1001];   //2^x storage
  7. long long tri[1000001]; //to store input triangle
  8. int compute[1000001];   //aux array to store path
  9.  
  10. //compute and store 2^0 to 2^(n-1) modulo MOD
  11. void power(int n)
  12. {
  13.     long long a = 1;
  14.     int i;
  15.     for(i = 0; i < n; i++)
  16.     {
  17.         pow2[i] = a;
  18.         a = (a*2) % MOD;
  19.     }
  20. }
  21.  
  22. int main()
  23. {
  24.     int n, i, j;
  25.     scanf("%d", &n);
  26.     power(n);
  27.     for(i = 0; i < (n*(n+1))/2; i++)
  28.         scanf("%lld", &tri[i]);
  29.  
  30.     for(i = n-1; i > 0; i--) //starting from the bottom row
  31.     {
  32.         for(j = 0; j < i; j++)
  33.         {
  34.             //compare adjacent pairs, add the larger one to the value above
  35.             if(tri[access(i, j)] < tri[access(i, j+1)])
  36.             {
  37.                 tri[access(i-1, j)] = tri[access(i-1, j)] + tri[access(i, j+1)];
  38.                 compute[access(i-1, j)] = 1; //indicates right turn
  39.             }
  40.             else
  41.             {
  42.                 tri[access(i-1, j)] = tri[access(i-1, j)] + tri[access(i, j)];
  43.                 compute[access(i-1, j)] = 0; //indicates left turn
  44.             }
  45.         }
  46.     }
  47.  
  48.     long long sum = 1; //1 for the max path itself
  49.     i = 0;
  50.     j = 0;
  51.     while(1) //calculate number of paths before max path
  52.     {
  53.         while(compute[access(i, j)] == 0 && i < n) //left path
  54.             i++;
  55.         if(i > n) //reached end
  56.             break;
  57.         //right path
  58.         i++;
  59.         j++;
  60.         sum = (sum + pow2[n-i-1]) % MOD; //add number of paths on the left
  61.     }
  62.     printf("%lld", sum);
  63. 	return 0;
  64. }
Success #stdin #stdout 0s 13736KB
comments (?)
stdin
copy 
4
3
7 4
2 3 5
8 5 9 3
stdout
copy 
4
https://ideone.com/KTJLv6
language:
C (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!