encho253

Untitled

Nov 25th, 2016
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 4.71 KB | None | 0 0
  1. using System;
  2. using System.Linq;
  3. using System.Numerics;
  4.  
  5. /// <summary>
  6. /// You are given rectangular matrix. The matrix is filled with numbers that are power of 2, as follows:
  7. ///  The bottom left corner holds the value 1
  8. ///  The next cell above holds value of 2, the next cell above holds of 4, etc…
  9. ///  The second cell the bottom row holds a value of 2, the cell next to it holds a value of 4
  10. /// You have a pawn on the field.The pawn can only move to the cells that directly above, below it or right/left of it.
  11. /// We have four directions UP, DOWN, LEFT, RIGHT.
  12. /// Given that initially the pawn starts at the bottom left corner and a list of cells that the pawn must reach calculate the s
  13. /// um of the cells that the pawn has to go through.
  14. /// The value of each cell is calculated only once, i.e. if the pawn visits the same cell more than once,
  15. /// its value is added to the result only the first time (the value is collected).
  16. /// The top row is at position 0, the bottommost row is at position ROWS – 1.
  17. /// The pawn goes from one cell to the other, following the rules:
  18. ///  First go to the target column
  19. ///  Second go to the target row
  20. /// </summary>
  21. class BitShiftMatrix
  22. {
  23.     /// <summary>
  24.     /// Defines the entry point of the application.
  25.     /// </summary>
  26.     static void Main()
  27.     {
  28.         int r = int.Parse(Console.ReadLine());
  29.         int c = int.Parse(Console.ReadLine());
  30.         BigInteger[,] matrix = GenerateMatrix(r,c);
  31.         BigInteger sum = CalculateSumOfPawn(r,c,matrix);
  32.         Console.WriteLine(sum);          
  33.     }
  34.     /// <summary>
  35.     /// Generates the matrix.
  36.     /// </summary>
  37.     /// <param name="r">The r.</param>
  38.     /// <param name="c">The c.</param>
  39.     /// <returns></returns>
  40.     static BigInteger[,] GenerateMatrix(int r,int c)
  41.     {
  42.         BigInteger[,] matrix = new BigInteger[r,c];      
  43.         BigInteger counterCol = 1;
  44.         BigInteger counterRow = 1;
  45.  
  46.         for (int i = matrix.GetLength(0) - 1; i >= 0; i--)
  47.         {
  48.             for (int j = 0; j < matrix.GetLength(1) ; j++)
  49.             {
  50.                 matrix[i, j] = counterRow;
  51.                 matrix[i, j] *= counterCol;
  52.                 counterCol *= 2;
  53.             }
  54.             counterRow *= 2;
  55.             counterCol = 1;
  56.         }
  57.         return matrix;
  58.     }
  59.     /// <summary>
  60.     /// Calculates the sum of pawn.
  61.     /// </summary>
  62.     /// <param name="r">The r.</param>
  63.     /// <param name="c">The c.</param>
  64.     /// <param name="matrix">The matrix.</param>
  65.     /// <returns></returns>
  66.     static BigInteger CalculateSumOfPawn(int r ,int c,BigInteger[,] matrix)
  67.     {
  68.         int n = int.Parse(Console.ReadLine());
  69.         int[] numbers = new int[n];
  70.         numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
  71.         BigInteger sum = 0;
  72.         int lastCol = 0;
  73.         int lastRow = r - 1;
  74.         bool[,] boolMatrix = new bool[r,c];
  75.  
  76.         for (int i = 0; i < n; i++)
  77.         {          
  78.             int coef = Math.Max(r, c);
  79.             int row = numbers[i] / coef;
  80.             int col = numbers[i] % coef;
  81.  
  82.             if (lastCol <= col)
  83.             {
  84.                 for (int k = lastCol; k <= col; k++)
  85.                 {
  86.                     if (boolMatrix[lastRow,k] == false)
  87.                     {
  88.                         sum += matrix[lastRow,k];
  89.                         boolMatrix[lastRow, k] = true;
  90.                     }
  91.                     lastCol = k;
  92.                 }
  93.             }
  94.             else if (lastCol >= col)
  95.             {
  96.                 for (int j = lastCol; j >= col; j--)
  97.                 {
  98.                     if (boolMatrix[lastRow, j] == false)
  99.                     {
  100.                         sum += matrix[lastRow, j];
  101.                         boolMatrix[lastRow, j] = true;
  102.                     }
  103.                     lastCol = j;
  104.                 }
  105.             }
  106.             if (lastRow <= row)
  107.             {
  108.                 for (int k = lastRow; k <= row; k++)
  109.                 {
  110.                     if (boolMatrix[k, lastCol] == false)
  111.                     {
  112.                         sum += matrix[k,lastCol];
  113.                         boolMatrix[k,lastCol] = true;
  114.                     }
  115.                     lastRow = k;
  116.                 }
  117.             }
  118.             else if (lastRow >= row)
  119.             {
  120.                 for (int j = lastRow; j >= row; j--)
  121.                 {
  122.                     if (boolMatrix[j,lastCol] == false)
  123.                     {
  124.                         sum += matrix[j, lastCol];
  125.                         boolMatrix[j, lastCol] = true;
  126.                     }
  127.                     lastRow = j;
  128.                 }
  129.             }
  130.         }
  131.         return sum;
  132.     }
  133. }
Advertisement
Add Comment
Please, Sign In to add comment