codeforces-scrape

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

1487.md (8728B)


      1 Source: https://codeforces.com/blog/entry/87873
      2 
      3 [1487A - Arena](/contest/1487/problem/A "Educational Codeforces Round 104 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     int n;
     23     cin >> n;
     24     vector<int> a(n);
     25     for (int& x : a) cin >> x;
     26     cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl;
     27   }
     28 }
     29 ```
     30 
     31 [1487B - Cat Cycle](/contest/1487/problem/B "Educational Codeforces Round 104 (Rated for Div. 2)")
     32 
     33 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution (adedalic)**
     40 
     41 ```
     42 fun main() {
     43     repeat(readLine()!!.toInt()) {
     44         var (n, k) = readLine()!!.split(' ').map { it.toInt() }
     45         k--
     46         val floor = n / 2
     47         println((k + (n % 2) * k / floor) % n + 1)
     48     }
     49 }
     50 ```
     51 
     52 [1487C - Minimum Ties](/contest/1487/problem/C "Educational Codeforces Round 104 (Rated for Div. 2)")
     53 
     54 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     55 
     56 **Tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Solution (BledDest)**
     61 
     62 ```
     63 #include<bits/stdc++.h>
     64 
     65 using namespace std;
     66 
     67 int main()
     68 {
     69     int t;
     70     cin >> t;
     71     for(int i = 0; i < t; i++)
     72     {
     73         int n;
     74         cin >> n;
     75         if(n % 2 == 1)
     76         {
     77             for(int i = 0; i < n; i++)
     78                 for(int j = i + 1; j < n; j++)
     79                     if(j - i <= n / 2)
     80                         cout << 1 << " ";
     81                     else
     82                         cout << -1 << " ";
     83             cout << endl;
     84         }
     85         else
     86         {
     87             for(int i = 0; i < n; i++)
     88                 for(int j = i + 1; j < n; j++)
     89                     if(j - i < n / 2)
     90                         cout << 1 << " ";
     91                     else if(j - i == n / 2)
     92                         cout << 0 << " ";
     93                     else
     94                         cout << -1 << " ";
     95             cout << endl;
     96         }
     97     }
     98 }
     99 ```
    100 
    101 [1487D - Pythagorean Triples](/contest/1487/problem/D "Educational Codeforces Round 104 (Rated for Div. 2)")
    102 
    103 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    104 
    105 **Tutorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution (Neon)**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 
    114 using namespace std;
    115 
    116 int main() {
    117   int t;
    118   cin >> t;
    119   while (t--) {
    120     int n;
    121     cin >> n;
    122     int ans = 0;
    123     for (int i = 3; i * i <= 2 * n - 1; i += 2)
    124       ++ans;
    125     cout << ans << '\n';
    126   }
    127 }
    128 ```
    129 
    130 [1487E - Cheap Dinner](/contest/1487/problem/E "Educational Codeforces Round 104 (Rated for Div. 2)")
    131 
    132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution (BledDest)**
    139 
    140 ```
    141 #include<bits/stdc++.h>
    142 
    143 using namespace std;
    144 
    145 int main()
    146 {   
    147     vector<int> ns(4);
    148     for(int i = 0; i < 4; i++)
    149         scanf("%d", &ns[i]);
    150     vector<vector<int>> cs(4);
    151     for(int i = 0; i < 4; i++)
    152     {
    153         cs[i].resize(ns[i]);
    154         for(int j = 0; j < ns[i]; j++)
    155             scanf("%d", &cs[i][j]);
    156     }
    157     vector<vector<vector<int>>> bad(3);
    158     for(int i = 0; i < 3; i++)
    159     {
    160         bad[i].resize(ns[i + 1]);
    161         int m;
    162         scanf("%d", &m);
    163         for(int j = 0; j < m; j++)
    164         {
    165             int x, y;
    166             scanf("%d %d", &x, &y);
    167             x--;
    168             y--;
    169             bad[i][y].push_back(x);
    170         }
    171     }                   
    172     vector<vector<int>> dp(4);
    173     dp[0] = cs[0];
    174     for(int i = 0; i < 3; i++)
    175     {
    176         dp[i + 1].resize(ns[i + 1]);                
    177         multiset<int> s;
    178         for(int j = 0; j < ns[i]; j++)
    179             s.insert(dp[i][j]);
    180         for(int j = 0; j < ns[i + 1]; j++)
    181         {
    182             for(auto k : bad[i][j])
    183                 s.erase(s.find(dp[i][k]));
    184             if(s.empty())
    185                 dp[i + 1][j] = int(4e8 + 43);
    186             else
    187                 dp[i + 1][j] = *s.begin() + cs[i + 1][j];
    188             for(auto k : bad[i][j])
    189                 s.insert(dp[i][k]);       
    190         }
    191     }
    192     int ans = *min_element(dp[3].begin(), dp[3].end());
    193     if(ans > int(4e8))
    194         ans = -1;
    195     cout << ans << endl;
    196 }
    197 ```
    198 
    199 [1487F - Ones](/contest/1487/problem/F "Educational Codeforces Round 104 (Rated for Div. 2)")
    200 
    201 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    202 
    203 **Tutorial**
    204 
    205 Tutorial is loading...
    206 
    207 **Solution (Neon)**
    208 
    209 ```
    210 #include <bits/stdc++.h>
    211 
    212 using namespace std;
    213 
    214 #define sz(a) int((a).size())
    215 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    216 
    217 const int N = 250;
    218 const int M = 28;
    219 const int INF = 1e9;
    220 
    221 int dp[2][M * 2 + 1][N][N];
    222 
    223 int main() {
    224   string s;
    225   cin >> s;
    226   reverse(s.begin(), s.end());
    227   s += "0";
    228   
    229   forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[0][carry][cp][cn] = INF;
    230   dp[0][M][N - 1][N - 1] = 0;
    231   
    232   forn(i, sz(s)) {
    233     forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[1][carry][cp][cn] = INF;
    234     forn(carry, M * 2 + 1) for (int cp = N - 1; cp >= 0; --cp) for (int cn = N - 1; cn >= 0; --cn) if (dp[0][carry][cp][cn] != INF) {
    235       if (cp > 0) dp[0][carry][cp - 1][cn] = min(dp[0][carry][cp - 1][cn], dp[0][carry][cp][cn]);
    236       if (cn > 0) dp[0][carry][cp][cn - 1] = min(dp[0][carry][cp][cn - 1], dp[0][carry][cp][cn]);
    237       int rcarry = carry - M;
    238       int val = rcarry + cp - cn;
    239       int digit = val % 10;
    240       if (digit < 0) digit += 10;
    241       int ncarry = val / 10;
    242       if (val < 0 && digit != 0) --ncarry;
    243       if (digit == s[i] - '0') dp[1][ncarry + M][cp][cn] = min(dp[1][ncarry + M][cp][cn], dp[0][carry][cp][cn] + cp + cn);
    244     }
    245     swap(dp[0], dp[1]);
    246   }
    247   
    248   int ans = INF;
    249   forn(i, N) forn(j, N) ans = min(ans, dp[0][M][i][j]);
    250   cout << ans << endl;
    251 }
    252 ```
    253 
    254 [1487G - String Counting](/contest/1487/problem/G "Educational Codeforces Round 104 (Rated for Div. 2)")
    255 
    256 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    257 
    258 **Tutorial**
    259 
    260 Tutorial is loading...
    261 
    262 **Solution (BledDest)**
    263 
    264 ```
    265 #include<bits/stdc++.h>
    266 
    267 using namespace std;
    268 
    269 const int MOD = 998244353;
    270 const int N = 402;
    271 
    272 int add(int x, int y)
    273 {
    274     x += y;
    275     while(x >= MOD) x -= MOD;
    276     while(x < 0) x += MOD;
    277     return x;
    278 }
    279 
    280 int sub(int x, int y)
    281 {
    282     return add(x, -y);
    283 }
    284 
    285 int mul(int x, int y)
    286 {
    287     return (x * 1ll * y) % MOD;
    288 }
    289 
    290 int c[26];
    291 int dp[2][N][N][3][3];
    292 int sumDp[N][N];
    293 int p1[N][N];
    294 int p2[N][N];
    295 int n;
    296 
    297 int main()
    298 {
    299     cin >> n;
    300     for(int i = 0; i < 26; i++)
    301         cin >> c[i];
    302     for(int i = 0; i < 26; i++)
    303         for(int j = 0; j < 26; j++)
    304             for(int k = 0; k < 26; k++)
    305                 if(i != k)
    306                 {                                                                    
    307                     multiset<int> s = {i, j, k};
    308                     dp[1][s.count(0)][s.count(1)][min(2, j)][min(2, k)]++;
    309                 }
    310     for(int i = 4; i <= n; i++)
    311     {
    312         for(int j = 0; j < N; j++)
    313             for(int k = 0; k < N; k++)
    314                 for(int x = 0; x < 3; x++)
    315                     for(int y = 0; y < 3; y++)
    316                     {
    317                         dp[0][j][k][x][y] = dp[1][j][k][x][y];
    318                         dp[1][j][k][x][y] = 0;
    319                     }
    320         for(int j = 0; j < N; j++)
    321             for(int k = 0; k < N; k++)
    322                 for(int x = 0; x < 3; x++)
    323                     for(int y = 0; y < 3; y++)
    324                     {
    325                         int cur = dp[0][j][k][x][y];
    326                         if(cur == 0) continue;
    327                         for(int z = 0; z < 3; z++)
    328                         {                      
    329                             int& nw = dp[1][j + (z == 0 ? 1 : 0)][k + (z == 1 ? 1 : 0)][y][z];
    330                             nw = add(nw, mul(cur, (z == 2 ? 24 : 1) - (z == x ? 1 : 0)));
    331                         }
    332                     }
    333     }
    334     for(int i = 0; i < N; i++)
    335         for(int j = 0; j < N; j++)
    336             for(int k = 0; k < 3; k++)
    337                 for(int l = 0; l < 3; l++)
    338                     sumDp[i][j] = add(sumDp[i][j], dp[1][i][j][k][l]);
    339     for(int i = 0; i < N; i++)
    340     {
    341         p1[i][N - 1] = sumDp[i][N - 1];
    342         for(int j = N - 2; j >= 0; j--)
    343             p1[i][j] = add(sumDp[i][j], p1[i][j + 1]);
    344     }
    345     for(int j = 0; j < N; j++)
    346     {
    347         p2[N - 1][j] = p1[N - 1][j];
    348         for(int i = N - 2; i >= 0; i--)
    349             p2[i][j] = add(p1[i][j], p2[i + 1][j]);
    350     }
    351     int ans = p2[0][0]; 
    352     for(int i = 0; i < 26; i++)
    353     {
    354         for(int j = 0; j < N; j++)
    355             for(int k = c[i] + 1; k < N; k++)
    356                 ans = sub(ans, sumDp[k][j]);
    357     }
    358     for(int i = 0; i < 26; i++)
    359         for(int j = 0; j < i; j++)
    360             ans = add(ans, p2[c[i] + 1][c[j] + 1]);
    361     cout << ans << endl;    
    362 }
    363 ```