SHARE
TWEET

Untitled

a guest Nov 19th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Author: Tulba-Lecu Theodor Gabriel
  2. // Student at Politehnica Universiy of Bucharest, group 311CA
  3. // Email: gabi_tulba_lecu@yahoo.com
  4. // Task: star_dust
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <ctype.h>
  9.  
  10. // free a dinamically allocated 2D array
  11. void free_matrix(int rows, int **mat) {
  12.     for (int i = 0; i < rows; i++) {
  13.         free(mat[i]);
  14.     }
  15.  
  16.     free(mat);
  17. }
  18.  
  19. // swap the values of two bytes
  20. void swap_bytes(char *a, char *b) {
  21.     *a = *a ^ *b;
  22.     *b = *a ^ *b;
  23.     *a = *a ^ *b;
  24. }
  25.  
  26. // read until a letter is found
  27. void read_alpha(char *a) {
  28.     *a = 0;
  29.  
  30.     while (!isalpha(*a)) {
  31.         scanf("%c", a);
  32.     }
  33. }
  34.  
  35. // check if a coordinate is inside the matrix
  36. int in_bounds(int x, int y, int x_max, int *v) {
  37.     if (x < 0 || x >= x_max)
  38.         return 0;
  39.     if (y < 0 || y >= 4 * v[x])
  40.         return 0;
  41.  
  42.     return 1;
  43. }
  44.  
  45. // allocate and read the initial matrix
  46. void read(int *n_addr, int **v_addr, int ***mat_addr) {
  47.     int n;
  48.     int *v = NULL;
  49.     int **mat = NULL;
  50.  
  51.     // read the number of rows
  52.     scanf("%d", &n);
  53.  
  54.     // allocate the row length array
  55.     v = (int *) malloc(n * sizeof(int));
  56.     if (v == NULL) {
  57.         printf("Error! Unable to allocate memory.\n");
  58.         exit(1);
  59.     }
  60.  
  61.     // allocate the matrix's rows
  62.     mat = (int **) malloc(n * sizeof(int *));
  63.     if (mat == NULL) {
  64.         free(v);
  65.  
  66.         printf("Error! Unable to allocate memory.\n");
  67.  
  68.         exit(1);
  69.     }
  70.  
  71.     for (int i = 0; i < n; i++) {
  72.         // read the length of the i-th row
  73.         scanf("%d", &v[i]);
  74.  
  75.         // allocate the matrix's i-th row
  76.         mat[i] = (int *) malloc(v[i] * sizeof(int));
  77.         if (mat[i] == NULL) {
  78.             printf("Error! Unable to allocate memory.\n");
  79.             free_matrix(i, mat);
  80.             free(v);
  81.  
  82.             exit(1);
  83.         }
  84.  
  85.         // read the i-th row
  86.         for (int j = 0; j < v[i]; j++) {
  87.             scanf("%x", &mat[i][j]);
  88.         }
  89.     }
  90.  
  91.     // pass the read input
  92.     *n_addr = n;
  93.     *v_addr = v;
  94.     *mat_addr = mat;
  95. }
  96.  
  97. // solve the first task
  98. void solve_task1(int n, int *v, int **mat) {
  99.     printf("task 1\n");
  100.  
  101.     int total = 0;
  102.     int score = 0;
  103.     double mean = 0.0;
  104.  
  105.     // add the bytes on the frist row
  106.     for (int i = 0; i < 4 * v[0]; i++) {
  107.             score += ((char *) mat[0])[i];
  108.             total++;
  109.     }
  110.  
  111.     // add the first and last bytes of each row from 1 to n-1
  112.     for (int i = 1; i < n - 1; i++) {
  113.         if (v[i] > 0) {
  114.             score += ((char *) mat[i])[0];
  115.             score += ((char *) mat[i])[4 * v[i] - 1];
  116.             total += 2;
  117.         }
  118.     }
  119.  
  120.     // add the bytes on the last row
  121.     for (int i = 0; i < 4 * v[n - 1]; i++) {
  122.             score += ((char *) mat[n - 1])[i];
  123.             total++;
  124.     }
  125.  
  126.     // calculate the arithmetic mean
  127.     mean = (double) score / (double) total;
  128.  
  129.     printf("%.10f\n", mean);
  130. }
  131.  
  132. // read an update for the second task
  133. void read_update(char *op, char *type, int *row, int *index, int *value) {
  134.     *value = 0;
  135.  
  136.     read_alpha(op);
  137.     read_alpha(type);
  138.  
  139.     scanf("%d", row);
  140.     scanf("%d", index);
  141.  
  142.     if (*op == 'M') {
  143.         scanf("%x", value);
  144.     }
  145. }
  146.  
  147. // apply a modify update on the matrix
  148. void modify(int n, int *v, int **mat, int row, char type, int idx, int val) {
  149.     int int_block_index;
  150.  
  151.     // get the int block in which the modification will take place
  152.     switch (type) {
  153.         case 'I':
  154.             int_block_index = idx;
  155.             break;
  156.  
  157.         case 'S':
  158.             int_block_index = idx / 2;
  159.             break;
  160.  
  161.         case 'C':
  162.             int_block_index = idx / 4;
  163.             break;
  164.     }
  165.  
  166.     // if the block is outside the allocated memory of the row, extend the row
  167.     if (int_block_index >= v[row]) {
  168.         int *p = realloc(mat[row], (int_block_index + 1) * sizeof(int));
  169.         if (p == NULL) {
  170.             printf("Error! Unable to reallocate memory.\n");
  171.  
  172.             free_matrix(n, mat);
  173.             free(v);
  174.  
  175.             exit(1);
  176.         }
  177.  
  178.         mat[row] = p;
  179.         // set the newly allocated memory to 0
  180.         for (int i = v[row]; i <= int_block_index; i++) {
  181.             mat[row][i] = 0;
  182.         }
  183.  
  184.         // remember the new length of the array
  185.         v[row] = int_block_index + 1;
  186.     }
  187.  
  188.     // based on the type of modification, set the memory to new value
  189.     // for simplicty for the 'S' and 'C' types the row is casted to
  190.     // short int and char respectively
  191.     switch (type) {
  192.         case 'I':
  193.             mat[row][idx] = val;
  194.             break;
  195.  
  196.         case 'S':
  197.             ((short int *)mat[row])[idx] = (short int) val;
  198.             break;
  199.  
  200.         case 'C':
  201.             ((char *)mat[row])[idx] = (char) val;
  202.             break;
  203.     }
  204. }
  205.  
  206. // swap the order of the bytes of a int/short int
  207. void swap_order(int *v, char type, int index) {
  208.     short int *v_short = (short int *) v;
  209.     char *byte_arr = NULL;
  210.  
  211.     switch (type) {
  212.         case 'I':
  213.             byte_arr = (char *) &v[index];
  214.             swap_bytes(&byte_arr[0], &byte_arr[3]);
  215.             swap_bytes(&byte_arr[1], &byte_arr[2]);
  216.  
  217.             break;
  218.  
  219.         case 'S':
  220.             byte_arr = (char *) &v_short[index];
  221.             swap_bytes(&byte_arr[0], &byte_arr[1]);
  222.  
  223.             break;
  224.     }
  225. }
  226.  
  227. // solve the second task
  228. void solve_task2(int n, int *v, int **mat) {
  229.     int k, row, index, value;
  230.     char op, type;
  231.  
  232.     printf("task 2\n");
  233.  
  234.     // read the number of updates
  235.     scanf("%d", &k);
  236.  
  237.     for (int i = 0; i < k; i++) {
  238.         read_update(&op, &type, &row, &index, &value);
  239.  
  240.         switch (op) {
  241.             case 'M':
  242.                 modify(n, v, mat, row, type, index - 1, value);
  243.                 break;
  244.  
  245.             case 'D':
  246.                 // the delete operation is equivalent to modify with value = 0
  247.                 modify(n, v, mat, row, type, index - 1, 0);
  248.                 break;
  249.  
  250.             case 'S':
  251.                 swap_order(mat[row], type, index);
  252.                 break;
  253.         }
  254.     }
  255.  
  256.     // print the matrix after all the updates
  257.     for (int i = 0; i < n; i++) {
  258.         for (int j = 0; j < v[i]; j++) {
  259.             printf("%08X ", mat[i][j]);
  260.         }
  261.         printf("\n");
  262.     }
  263. }
  264.  
  265. // do a depth first search on the matrix to get the size of the component
  266. int dfs(int n, int *v, char **mat, int x, int y, int **found) {
  267.     int size = 0, next_x, next_y;
  268.     // direction arrays
  269.     int dx[4] = {1, 0, -1, 0};
  270.     int dy[4] = {0, 1, 0, -1};
  271.  
  272.     // set this cell as visited
  273.     found[x][y] = 1;
  274.  
  275.     for (int i = 0; i < 4; i++) {
  276.         next_x = x + dx[i];
  277.         next_y = y + dy[i];
  278.         // if the neighbour cell is inside the matrix and it wasn't
  279.         // previously visited and the cell is 0, do a dfs on that cell
  280.         if (in_bounds(next_x, next_y, n, v)) {
  281.             if (!found[next_x][next_y] && mat[next_x][next_y] == 0) {
  282.                     size += dfs(n, v, mat, next_x, next_y, found);
  283.             }
  284.         }
  285.     }
  286.  
  287.     return size + 1;
  288. }
  289.  
  290. // solve the third task
  291. void solve_task3(int n, int *v, int **mat) {
  292.     int max = 0, max_pos_x = -1, max_pos_y = -1;
  293.     int **found = NULL;
  294.  
  295.     // allocate the visited cells matrix
  296.     found = (int **) calloc(n, sizeof(int *));
  297.     if (found == NULL) {
  298.         printf("Error! Unable to allocate memory.\n");
  299.         free_matrix(n, mat);
  300.         free(v);
  301.  
  302.         exit(1);
  303.     }
  304.  
  305.     for (int i = 0; i < n; i++) {
  306.         found[i] = (int *) calloc(4 * v[i], sizeof(int));
  307.         if (found[i] == NULL) {
  308.             printf("Error! Unable to allocate memory.\n");
  309.             free_matrix(i, found);
  310.             free_matrix(n, mat);
  311.             free(v);
  312.  
  313.             exit(1);
  314.         }
  315.     }
  316.  
  317.     for (int i = 0; i < n; i++) {
  318.        for (int j = 0; j < 4 * v[i]; j++) {
  319.            // if a new unvisited 0 cell is found get it's component size
  320.            if (!found[i][j] && ((char *) mat[i])[j] == 0) {
  321.                int size = dfs(n, v, (char **) mat, i, j, found);
  322.                // it the current component size is bigger than the biggest
  323.                // component, remember it as the best answer yet
  324.                if (size > max) {
  325.                    max = size;
  326.                    max_pos_x = i;
  327.                    max_pos_y = j;
  328.                }
  329.            }
  330.        }
  331.     }
  332.  
  333.     printf("task 3\n%d %d %d\n", max_pos_x, max_pos_y, max);
  334.  
  335.     // free allocated memory
  336.     free_matrix(n, found);
  337. }
  338.  
  339. int main() {
  340.     int n; // number of rows
  341.     int *row_width = NULL; // the array of row lengths
  342.     int **map = NULL; // the matrix
  343.  
  344.     // read initial matrix
  345.     read(&n, &row_width, &map);
  346.  
  347.     // solve tasks
  348.     solve_task1(n, row_width, map);
  349.     solve_task2(n, row_width, map);
  350.     solve_task3(n, row_width, map);
  351.  
  352.     // free allocated memory
  353.     free_matrix(n, map);
  354.     free(row_width);
  355.  
  356.     return 0;
  357. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top