codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1695.md (6309B)


      1 Source: https://codeforces.com/blog/entry/103996
      2 
      3 Tutorial is loading...
      4 
      5 **Solution**
      6 
      7 ```
      8 #include <bits/stdc++.h>
      9 using namespace std;
     10 
     11 int grid[45][45];
     12 
     13 int main() {
     14     int num_tests;
     15     cin >> num_tests;
     16 
     17     for (int test = 0; test < num_tests; ++test) {
     18         int n, m;
     19         cin >> n >> m;
     20 
     21         int max_i = 0, max_j = 0;
     22         
     23         for (int i = 0; i < n; ++i)
     24             for (int j = 0; j < m; ++j) {
     25                 cin >> grid[i][j];
     26                 if (grid[i][j] > grid[max_i][max_j])
     27                     max_i = i, max_j = j;
     28             }
     29 
     30         int h = max(max_i+1, n-max_i);
     31         int w = max(max_j+1, m-max_j);
     32         cout << h * w << '\n';
     33     }
     34 }
     35 ```
     36 
     37 Tutorial is loading...
     38 
     39 **Solution**
     40 
     41 ```
     42 #include <bits/stdc++.h>
     43 using namespace std;
     44 
     45 int main() {
     46     int num_tests;
     47     cin >> num_tests;
     48 
     49     for (int test = 0; test < num_tests; ++test) {
     50 
     51         int n; cin >> n;
     52         vector<int> a(n);
     53         for (int i = 0; i < n; ++i)
     54             cin >> a[i];
     55 
     56         if (n % 2 == 1) {
     57             cout << "Mike\n";
     58             continue;
     59         }
     60 
     61         int smallest = 0;
     62         for (int i = 0; i < n; ++i)
     63             if (a[i] < a[smallest])
     64                 smallest = i;
     65 
     66         if (smallest % 2 == 0) cout << "Joe\n";
     67         else cout << "Mike\n";
     68     }
     69 }
     70 ```
     71 
     72 Tutorial is loading...
     73 
     74 **Solution**
     75 
     76 ```
     77 #include <bits/stdc++.h>
     78 using namespace std;
     79 
     80 #define N 1010
     81 
     82 int grid[N][N], mn[N][N], mx[N][N];
     83 
     84 int main() {
     85     int num_tests;
     86     cin >> num_tests;
     87 
     88     for (int test = 0; test < num_tests; ++test) {
     89         int n, m;
     90         cin >> n >> m;
     91         
     92         for(int i = 0; i < n; ++i)
     93             for(int j = 0; j < m; ++j)
     94                 cin >> grid[i][j];
     95         
     96         mn[0][0] = mx[0][0] = grid[0][0];
     97         
     98         for(int i = 1; i < n; ++i)
     99             mx[i][0] = mn[i][0] = mx[i - 1][0] + grid[i][0];
    100         
    101         for(int j = 1; j < m; ++j)
    102             mx[0][j] = mn[0][j] = mx[0][j - 1] + grid[0][j];
    103         
    104         for(int i = 1; i < n; ++i)
    105             for(int j = 1; j < m; ++j) {
    106                 mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + grid[i][j];
    107                 mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + grid[i][j];
    108             }
    109         
    110         if(mx[n - 1][m - 1] % 2 || mn[n - 1][m - 1] > 0 || mx[n - 1][m - 1] < 0)
    111             cout << "NO\n";
    112         else
    113             cout << "YES\n";
    114     }
    115 }
    116 ```
    117 
    118 Tutorial is loading...
    119 
    120 **Solution**
    121 
    122 ```
    123 #include <bits/stdc++.h>
    124 using namespace std;
    125 
    126 #define N 2010
    127 
    128 vector<int> tree[N];
    129 
    130 int dfs(int i, int p) {
    131     int sm = 0, z = 0;
    132     
    133     for (int j : tree[i]) if (j != p) {
    134         int x = dfs(j, i);
    135         sm += x;
    136         if (x == 0)
    137             z++;
    138     }
    139     
    140     return sm + max(0, z - 1);
    141 }
    142 
    143 int main() {
    144     int num_tests;
    145     cin >> num_tests;
    146 
    147     for (int test = 0; test < num_tests; ++test) {
    148         int n;
    149         cin >> n;
    150         
    151         for (int i = 1; i < n; ++i) {
    152             int u, v;
    153             cin >> u >> v;
    154             tree[u].push_back(v);
    155             tree[v].push_back(u);
    156         }
    157         
    158         if (n == 1)
    159             cout << "0\n";
    160         else {
    161             int ans = n;
    162 
    163             for (int i = 1; i <= n; ++i)
    164                 ans = min(ans, 1 + dfs(i, i));
    165             
    166             cout << ans << '\n';
    167         }
    168         
    169         for (int i = 1; i <= n; ++i)
    170             tree[i].clear();
    171     }
    172 }
    173 ```
    174 
    175 Tutorial is loading...
    176 
    177 **Solution**
    178 
    179 ```
    180 #include <bits/stdc++.h>
    181 using namespace std;
    182 
    183 #define N 200010
    184 
    185 vector<int> tree[N];
    186 
    187 int dfs(int i, int p) {
    188     int sm = 0, z = 0;
    189     
    190     for (int j : tree[i]) if (j != p) {
    191         int x = dfs(j, i);
    192         sm += x;
    193         if (x == 0)
    194             z++;
    195     }
    196     
    197     return sm + max(0, z - 1);
    198 }
    199 
    200 int main() {
    201     int num_tests;
    202     cin >> num_tests;
    203 
    204     for (int test = 0; test < num_tests; ++test) {
    205         int n;
    206         cin >> n;
    207         
    208         for (int i = 1; i < n; ++i) {
    209             int u, v;
    210             cin >> u >> v;
    211             tree[u].push_back(v);
    212             tree[v].push_back(u);
    213         }
    214 
    215         int max_deg = 0;
    216         for (int i = 1; i <= n; ++i)
    217             max_deg = max(max_deg, (int)tree[i].size());
    218         
    219         if (max_deg == 0)
    220             cout << "0\n";
    221         else if (max_deg < 3)
    222             cout << "1\n";
    223         else {
    224             for (int i = 1; i <= n; ++i)
    225                 if (tree[i].size() >= 3) {
    226                     cout << dfs(i, i) << '\n';
    227                     break;
    228                 }
    229         }
    230         
    231         for (int i = 1; i <= n; ++i)
    232             tree[i].clear();
    233     }
    234 }
    235 ```
    236 
    237 Tutorial is loading...
    238 
    239 **Solution**
    240 
    241 ```
    242 #include <bits/stdc++.h>
    243 using namespace std;
    244 
    245 #define N 600010
    246 
    247 vector<pair<int, int>> graph[N];
    248 vector<int> lst;
    249 
    250 int ans[2][N];
    251 
    252 bool used[N], usedEdges[N];
    253 
    254 void dfs(int i) {
    255     lst.push_back(i);
    256 
    257     if (!used[i]) {
    258         used[i] = true;
    259         
    260         for (pair<int, int> p : graph[i])
    261             if (!usedEdges[p.second]) {
    262                 usedEdges[p.second] = true;
    263                 dfs(p.first);
    264                 lst.push_back(i);
    265             }
    266     }
    267 }
    268 
    269 int main() {
    270 
    271     int n; cin >> n;
    272     string ptop(n, 'U'), pbot(n, 'D');
    273     string mtop(n, 'U'), mbot(n, 'D');
    274 
    275     for (int i = 0; i < n; ++i) {
    276         int u, v;
    277         cin >> u >> v;
    278         graph[u].emplace_back(v, i);
    279         graph[v].emplace_back(u, i);
    280     }
    281 
    282     int idx = 0;
    283     for (int i = 1; i <= 2 * n; ++i) if (!used[i]) {
    284 
    285         dfs(i);
    286         lst.pop_back();
    287         int k = lst.size() / 2;
    288         
    289         if (k == 1) {
    290             cout << "-1\n";
    291             exit(0);
    292         }
    293 
    294         for (int j = 0; j < k; ++j) {
    295             ans[0][j + idx] = lst[j];
    296             ans[1][j + idx] = lst[2 * k - 1 - j];
    297         }
    298 
    299         for (int j = 0; j < k - 1; j += 2)
    300             ptop[j + idx] = pbot[j + idx] = 'L', ptop[j + 1 + idx] = pbot[j + 1 + idx] = 'R';
    301         for (int j = 1; j < k - 1; j += 2)
    302             mtop[j + idx] = mbot[j + idx] = 'L', mtop[j + 1 + idx] = mbot[j + 1 + idx] = 'R';
    303         lst.clear();
    304 
    305         idx += k;
    306     }
    307 
    308     cout << "2 " << n << '\n';
    309     
    310     for (int i = 0; i < 2; ++i) {
    311         for (int j = 0; j < n; ++j)
    312             cout << ans[i][j] << ' ';
    313         cout << '\n';
    314     }
    315 
    316     cout << ptop << '\n' << pbot << '\n';
    317     cout << mtop << '\n' << mbot << '\n';
    318 }
    319 ```