fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <limits>
  5.  
  6. class ApartmentHunting {
  7. private:
  8.     std::vector<std::vector<int>> populateBlocks() {
  9.         std::vector<std::vector<int>> blocks = {
  10.             {0, 1, 0},
  11.             {1, 0, 0},
  12.             {1, 1, 0},
  13.             {0, 1, 0},
  14.             {0, 1, 1}
  15.         };
  16.         return blocks;
  17.     }
  18.  
  19.     std::vector<std::vector<int>> initiateDp(int blocksCount, int reqsCount) {
  20.         std::vector<std::vector<int>> dp(blocksCount, std::vector<int>(reqsCount + 1, std::numeric_limits<int>::max()));
  21.         return dp;
  22.     }
  23.  
  24. public:
  25.     int huntAndGetResult(std::vector<int>& requirements) {
  26.         std::vector<std::vector<int>> blocks = populateBlocks();
  27.         int blocksCount = blocks.size();
  28.         int reqsCount = requirements.size();
  29.         int result = std::numeric_limits<int>::max();
  30.         std::vector<std::vector<int>> dp = initiateDp(blocksCount, reqsCount);
  31.         int AMENITY_UNAVAILABLE = std::numeric_limits<int>::max();
  32.         int AMENITY_AVAILABLE = 0;
  33.  
  34.         for (int j = 0; j < reqsCount; j++) {
  35.             if (blocks[0][requirements[j]] == 1) {
  36.                 dp[0][j] = AMENITY_AVAILABLE;
  37.             }
  38.         }
  39.  
  40.         for (int i = 1; i < blocksCount; i++) {
  41.             dp[i][reqsCount] = 0;
  42.             for (int j = 0; j < reqsCount; j++) {
  43.                 if (blocks[i][requirements[j]] == 1) {
  44.                     dp[i][j] = AMENITY_AVAILABLE;
  45.                 } else {
  46.                     if (dp[i - 1][j] != AMENITY_UNAVAILABLE)
  47.                         dp[i][j] = std::min(dp[i][j], dp[i - 1][j] + 1);
  48.                 }
  49.                 dp[i][reqsCount] = std::max(dp[i][reqsCount], dp[i][j]);
  50.             }
  51.         }
  52.  
  53.         for (int i = blocksCount - 2; i >= 0; i--) {
  54.             dp[i][reqsCount] = 0;
  55.             for (int j = 0; j < reqsCount; j++) {
  56.                 if (blocks[i][requirements[j]] == 1) {
  57.                     dp[i][j] = 0;
  58.                 } else {
  59.                     if (dp[i + 1][j] != AMENITY_UNAVAILABLE)
  60.                         dp[i][j] = std::min(dp[i][j], dp[i + 1][j] + 1);
  61.                 }
  62.                 dp[i][reqsCount] = std::max(dp[i][reqsCount], dp[i][j]);
  63.             }
  64.             result = (dp[i][reqsCount] <= result) ? i : result;
  65.         }
  66.         return (result + 1);
  67.     }
  68. };
  69.  
  70. int main() {
  71.     ApartmentHunting apartmentHunting;
  72.     std::vector<int> requirements = {0, 1, 2};
  73.     int result = apartmentHunting.huntAndGetResult(requirements);
  74.     std::cout << "Block: " << result << " is the answer." << std::endl;
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Block: 3 is the answer.
https://ideone.com/wIbUco
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

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!