ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 06.11.2019 21:25:26

ამოცანა: ვირუსები

მომხმარებელი: Vato

ვერდიქტი: ნაწილობრივი ამოხსნა

შეფასება: 90.0 ქულა







#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

int main()
{
// initialize table to false, no viruses in the beginning
    bool table[501][501] = {false};
// stores coordinates of viruses, first row is for x
// second row is for y
    static int coordinates[2][250000] = {0};

    int n, m;
    std::cin >> n >> m; // work on n x n table with m initial virus(es)
    int x, y; // coordinates of initial virus(es)

    for (int i = 1; i <= m; ++i){ // enter coordinates m times
        std::cin >> x >> y;
        table[y][x] = true; // make virus on corresponding point
        coordinates[0][i] = x; // store x coordinate of virus
        coordinates[1][i] = y; // store y coordinate of virus
    }

// initial index of coordinates of new virus is m+1,m+2...
    int index_cNewVirus = m+1; // (incrementing by 1 as next virus appears)
    int nVirus = m; // total number of all viruses
    int countMoves = 0; // moves needed to fill the table with viruses

// make new viruses until the table is full
    while (nVirus != n*n){
    // start from virus 1 and on above, below, left and right
    // cells make a new virus (every virus makes 4 new viruses)
        for (int i = 1; i <= m; ++i){
            x = coordinates[0][i]; // get x coordinate of virus N
            y = coordinates[1][i]; // get y coordinate of virus N

        // if above cell is in range and there is no virus in it
            if (y+1 <= n && table[y+1][x] == false){
                table[y+1][x] = true; // make virus
                coordinates[0][index_cNewVirus] = x; // store new viruses x coordinate
                coordinates[1][index_cNewVirus] = y+1; // store new viruses y coordinate
                ++index_cNewVirus; // move to the index of coordinates of next virus
                ++nVirus; // increment number of total viruses
            }
        // repeat same steps as above, but for below cell
            if (y-1 >= 1 && table[y-1][x] == false){
                table[y-1][x] = true;
                coordinates[0][index_cNewVirus] = x;
                coordinates[1][index_cNewVirus] = y-1;
                ++index_cNewVirus;
                ++nVirus;
            }
        // repeat same steps as above, but for right cell
            if (x+1 <= n && table[y][x+1] == false){
                table[y][x+1] = true;
                coordinates[0][index_cNewVirus] = x+1;
                coordinates[1][index_cNewVirus] = y;
                ++index_cNewVirus;
                ++nVirus;
            }
        // repeat same steps as above, but for left cell
            if (x-1 >= 1 && table[y][x-1] == false){
                table[y][x-1] = true;
                coordinates[0][index_cNewVirus] = x-1;
                coordinates[1][index_cNewVirus] = y;
                ++index_cNewVirus;
                ++nVirus;
            }
        }
        m = nVirus; // on the next cycle test new viruses
        ++countMoves; // increment number of moves needed to fill the table
    }

    std::cout << countMoves;

}

ტესტები

შემავალი მონაცემები
5 1
2 3
გამომავალი მონაცემები
5
თქვენი პასუხი
5
ჩეკერის პასუხი
YES
შემავალი მონაცემები
5 2
1 3
5 5
გამომავალი მონაცემები
5
თქვენი პასუხი
5
ჩეკერის პასუხი
YES
შემავალი მონაცემები
6 3
1 2
1 4
1 6
გამომავალი მონაცემები
6
თქვენი პასუხი
6
ჩეკერის პასუხი
YES
შემავალი მონაცემები
6 5
2 2
2 5
4 4
6 2
6 5
გამომავალი მონაცემები
3
თქვენი პასუხი
3
ჩეკერის პასუხი
YES
შემავალი მონაცემები
7 7
1 1
2 2
3 3
4 4
5 5
6 6
7 7
გამომავალი მონაცემები
6
თქვენი პასუხი
6
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50 1
3 5
გამომავალი მონაცემები
92
თქვენი პასუხი
92
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100 2
7 8
80 56
გამომავალი მონაცემები
104
თქვენი პასუხი
104
ჩეკერის პასუხი
YES
შემავალი მონაცემები
200 6
12 11
26 37
55 183
125 48
186 189
39 199
გამომავალი მონაცემები
122
თქვენი პასუხი
122
ჩეკერის პასუხი
YES
შემავალი მონაცემები
500 1
22 458
გამომავალი მონაცემები
935
თქვენი პასუხი

                    
ჩეკერის პასუხი
NO
შემავალი მონაცემები
500 10
250 260
45 307
49 485
397 8
163 20
5 10
308 59
308 60
122 486
199 283
გამომავალი მონაცემები
427
თქვენი პასუხი
427
ჩეკერის პასუხი
YES