codeforces-scrape

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

1451.md (16144B)


      1 Source: https://codeforces.com/blog/entry/84885
      2 
      3 [1451A - Subtract or Divide](/contest/1451/problem/A "Codeforces Round 685 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Code (C++)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 int32_t main() {
     16     ios::sync_with_stdio(0); cin.tie(0);
     17     int t, n;
     18     cin >> t;
     19     while(t--) {
     20         cin >> n;
     21         cout << (n <= 3? n-1 : 2 + (n&1)) << '\n';
     22     }
     23     return 0;
     24 }
     25 ```
     26 
     27 **Code (Java)**
     28 
     29 ```
     30 import java.util.*;
     31 import java.util.ArrayList;
     32 public class Main {
     33     public static void main(String args[])
     34     {
     35         Scanner sc = new Scanner(System.in);
     36         int t = sc.nextInt();
     37         for(int i = 0; i < t; i++)
     38         {
     39             int n = sc.nextInt();
     40             System.out.println(Math.min(2 + (n & 1), n - 1));
     41         }
     42     }
     43 }
     44 ```
     45 
     46 Idea by [ridbit10](/profile/ridbit10 "Expert ridbit10")
     47 
     48 [1451B - Non-Substring Subsequence](/contest/1451/problem/B "Codeforces Round 685 (Div. 2)")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Code (C++)**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 using namespace std;
     59 
     60 int32_t main() {
     61     ios::sync_with_stdio(0); cin.tie(0);
     62     int t;
     63     cin >> t;
     64     while(t--) {
     65         int i, n, Q; string s;
     66         cin >> n >> Q >> s;
     67         while(Q--) {
     68             int l, r; cin >> l >> r; --l; --r;
     69             bool bad = true;
     70             for(i = 0; i < l and bad; i++)
     71                 if(s[i] == s[l]) bad = false;
     72             for(i = r+1; i < n and bad; i++)
     73                 if(s[i] == s[r]) bad = false;
     74             cout << (bad? "NO" : "YES") << '\n';
     75         }
     76     }
     77     return 0;
     78 }
     79 ```
     80 
     81 **Code (Java)**
     82 
     83 ```
     84 import java.io.*;
     85 import java.util.*;
     86 public class Main {
     87     public static void main(String args[]) throws IOException
     88     {
     89         BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     90         int t = Integer.parseInt(br.readLine());
     91         for(int cases = 0; cases < t; cases++)
     92         {
     93             StringTokenizer st = new StringTokenizer(br.readLine());
     94             int n = Integer.parseInt(st.nextToken());
     95             int q = Integer.parseInt(st.nextToken());
     96             String s = br.readLine();
     97             int fi[] = new int[2];
     98             int la[] = new int[2];
     99             for(int j = 0; j < 2; j++)
    100             {
    101                 fi[j] = 2000000000;
    102                 la[j] = -1;
    103             }
    104             for(int i = 0; i < s.length(); i++)
    105             {
    106                 int cur = (s.charAt(i) - '0');
    107                 fi[cur] = Math.min(fi[cur], i);
    108                 la[cur] = i;
    109             }
    110             for(int i = 0; i < q; i++)
    111             {
    112                 st = new StringTokenizer(br.readLine());
    113                 int l = Integer.parseInt(st.nextToken()) - 1;
    114                 int r = Integer.parseInt(st.nextToken()) - 1;
    115                 int curl = (s.charAt(l) - '0');
    116                 int curr = (s.charAt(r) - '0');
    117                 if(fi[curl] < l || la[curr] > r)
    118                     System.out.println("YES\n");
    119                 else
    120                     System.out.println("NO\n");
    121             }
    122         }
    123     }
    124 }
    125 ```
    126 
    127 Idea by [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Candidate Master the_hyp0cr1t3")
    128 
    129 [1451C - String Equality](/contest/1451/problem/C "Codeforces Round 685 (Div. 2)")
    130 
    131 **Tutorial**
    132 
    133 Tutorial is loading...
    134 
    135 **Code (C++)**
    136 
    137 ```
    138 #include <bits/stdc++.h>
    139 using namespace std;
    140 
    141 int32_t main() {
    142     ios::sync_with_stdio(0); cin.tie(0);
    143     int t;
    144     cin >> t;
    145     while(t--) {
    146         int i, n, k; string a, b;
    147         cin >> n >> k >> a >> b;
    148         array<int, 27> have{}, need{};
    149         for(auto& c: a)
    150             have[c-'a']++;
    151         for(auto& c: b)
    152             need[c-'a']++;
    153      
    154         bool bad = false;
    155         for(i = 0; i < 26; i++) {
    156             if(have[i] < need[i] || (have[i] -= need[i]) % k)
    157                 bad = true;
    158             have[i+1] += have[i];
    159         }
    160         cout << (bad? "No" : "Yes") << '\n';
    161     }
    162     return 0;
    163 }
    164 ```
    165 
    166 **Code (Java)**
    167 
    168 ```
    169 import java.util.*;
    170 import java.util.ArrayList;
    171 public class Main {
    172     public static void main(String args[])
    173     {
    174         Scanner sc = new Scanner(System.in);
    175         int t = sc.nextInt();
    176         for(int cases = 0; cases < t; cases++)
    177         {
    178             int n = sc.nextInt();
    179             int k = sc.nextInt();
    180             sc.nextLine();
    181             String a = sc.nextLine();
    182             String b = sc.nextLine();
    183             int have[] = new int[27];
    184             int need[] = new int[27];
    185             for(int i = 0; i < n; i++)
    186             {
    187                 have[a.charAt(i) - 'a']++;
    188                 need[b.charAt(i) - 'a']++;
    189             }
    190             boolean bad = false;
    191             for(int j = 25; j >= 0; j--)
    192             {
    193                 have[j] += have[j + 1];
    194                 need[j] += need[j + 1];
    195                 if(have[j] > need[j] || (need[j] - have[j]) % k != 0)
    196                     bad = true;
    197             }
    198             if(bad)
    199                 System.out.println("No");
    200             else
    201                 System.out.println("Yes");
    202         }
    203     }
    204 }
    205 ```
    206 
    207 Idea by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup")
    208 
    209 [1451D - Circle Game](/contest/1451/problem/D "Codeforces Round 685 (Div. 2)")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Code (C++)**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 using namespace std;
    220 
    221 int32_t main() {
    222     ios::sync_with_stdio(0); cin.tie(0);
    223     int t;
    224     cin >> t;
    225     while(t--) {
    226         int64_t d, k;
    227         cin >> d >> k;
    228         int64_t x = 0, y = 0;
    229         while(true) {
    230             if(x <= y && (x + k) * (x + k) + y * y <= d * d)
    231                 x += k;
    232             else if(x > y && (y + k) * (y + k) + x * x <= d * d)
    233                 y += k;
    234             else
    235                 break;
    236         }
    237         if(x == y)
    238             cout << "Utkarsh" << endl;
    239         else
    240             cout << "Ashish" << endl;
    241     }
    242     return 0;
    243 }
    244 ```
    245 
    246 **Code (Java)**
    247 
    248 ```
    249 import java.util.*;
    250 import java.util.ArrayList;
    251 public class Main {
    252     public static boolean is_within(long x, long y, long dsq, long k)
    253     {
    254         return dsq - k * k * x * x - k * k * y * y >= 0;
    255     }
    256     public static void main(String args[])
    257     {
    258         Scanner sc = new Scanner(System.in);
    259         int t = sc.nextInt();
    260         for(int cases = 0; cases < t; cases++)
    261         {
    262             int d = sc.nextInt();
    263             long dsq = ((long) d) * d;
    264             int k = sc.nextInt();
    265             int cur = 0;
    266             while(is_within(cur + 1, cur + 1, dsq, k))
    267                 cur++;
    268             if(is_within(cur + 1, cur, dsq, k))
    269                 System.out.println("Ashish");
    270             else
    271                 System.out.println("Utkarsh");
    272         }
    273     }
    274 }
    275 ```
    276 
    277 Idea by [Utkarsh.25dec](/profile/Utkarsh.25dec "Master Utkarsh.25dec")
    278 
    279 [1451E1 - Bitwise Queries (Easy Version)](/contest/1451/problem/E1 "Codeforces Round 685 (Div. 2)")
    280 
    281 **Tutorial**
    282 
    283 Tutorial is loading...
    284 
    285 **Code (C++)**
    286 
    287 ```
    288 #include <bits/stdc++.h>
    289 #define int long long
    290 using pii=std::pair<int,int>;
    291 using namespace std;
    292  
    293 const int maxn = (1ll << 16) + 5, minn = 4, maxncheck = (1ll << 16);
    294  
    295 int n, xorvals[maxn], ans[maxn];
    296  
    297 void andqueries(string s, int& dest)
    298 {
    299     cout << s << endl;
    300     cout.flush();
    301     cin >> dest;
    302     if(dest == -1)
    303         exit(0);
    304     return;
    305 }
    306  
    307 int32_t main()
    308 {
    309     cin >> n;
    310     assert(n >= minn && n <= maxncheck && __builtin_popcount(n) == 1);
    311     for(int i = 2; i <= n; i++)
    312     {
    313         cout << "XOR 1 " << i << endl;
    314         cout.flush();
    315         cin >> xorvals[i];
    316         if(xorvals[i] == -1)
    317             return 0;
    318     }
    319     int xor12 = xorvals[2], xor13 = xorvals[3], xor23 = xorvals[2] ^ xorvals[3];
    320     int and12, and13, and23;
    321     andqueries("AND 1 2", and12);
    322     andqueries("AND 1 3", and13);
    323     andqueries("AND 2 3", and23);
    324     int x = xor12 + 2 * and12;
    325     int y = xor13 + 2 * and13;
    326     int z = xor23 + 2 * and23;
    327     assert((x + y - z) % 2 == 0);
    328     ans[1] = (x + y - z) / 2;
    329     for(int i = 2; i <= n; i++)
    330         ans[i] = (xorvals[i] ^ ans[1]);
    331     cout << "! ";
    332     for(int i = 1; i <= n; i++)
    333         cout << ans[i] << " ";
    334     cout << endl;
    335     cout.flush();
    336     return 0;
    337 }
    338 ```
    339 
    340 **Code (Java)**
    341 
    342 ```
    343 import java.util.Scanner;
    344  
    345 public class Main {
    346     public static int queries(String s, Scanner sc)
    347     {
    348         System.out.println(s);
    349         System.out.flush();
    350         int x = sc.nextInt();
    351         if(x == -1)
    352             System.exit(0);
    353         return x;
    354     }
    355     public static void main(String args[])
    356     {
    357         Scanner sc = new Scanner(System.in);
    358         int n = sc.nextInt();
    359         int xorvals[] = new int[n + 1];
    360         int ans[] = new int[n + 1];
    361         for(int i = 2; i <= n; i++)
    362             xorvals[i] = queries("XOR 1 " + i, sc);
    363         int xor12 = xorvals[2], xor13 = xorvals[3], xor23 = xorvals[2] ^ xorvals[3];
    364         int and12, and13, and23;
    365         and12 = queries("AND 1 2", sc);
    366         and13 = queries("AND 1 3", sc);
    367         and23 = queries("AND 2 3", sc);
    368         int x = xor12 + 2 * and12;
    369         int y = xor13 + 2 * and13;
    370         int z = xor23 + 2 * and23;
    371         assert((x + y - z) % 2 == 0);
    372         ans[1] = (x + y - z) / 2;
    373         for(int i = 2; i <= n; i++)
    374             ans[i] = (xorvals[i] ^ ans[1]);
    375         System.out.print("! ");
    376         for(int i = 1; i <= n; i++)
    377             System.out.print(ans[i] + " ");
    378         System.out.println();
    379         System.out.flush();
    380     }
    381 }
    382 ```
    383 
    384 Idea by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10")
    385 
    386 [1451E2 - Bitwise Queries (Hard Version)](/contest/1451/problem/E2 "Codeforces Round 685 (Div. 2)")
    387 
    388 **Tutorial**
    389 
    390 Tutorial is loading...
    391 
    392 **Code (C++)**
    393 
    394 ```
    395 #include <bits/stdc++.h>
    396 #define int long long
    397 using pii=std::pair<int,int>;
    398 using namespace std;
    399  
    400 const int maxn = (1ll << 16) + 5, minn = 4, maxncheck = (1ll << 16);
    401  
    402 int n, xorvals[maxn], ans[maxn];
    403 vector<int> pos[maxn];
    404  
    405 int queries(string s, int i, int j)
    406 {
    407     cout << s << " " << i << " " << j << endl;
    408     cout.flush();
    409     int dest;
    410     cin >> dest;
    411     if(dest == -1)
    412         exit(0);
    413     return dest;
    414 }
    415  
    416 int32_t main()
    417 {
    418     cin >> n;
    419     assert(n >= minn && n <= maxncheck && __builtin_popcount(n) == 1);
    420     xorvals[1] = 0;
    421     pos[0].push_back(1);
    422     for(int i = 2; i <= n; i++)
    423     {
    424         xorvals[i] = queries("XOR", 1, i);
    425         pos[xorvals[i]].push_back(i);
    426     }
    427     int a = 1, b = -1, c = -1;
    428     int same = -1;
    429     for(int i = 0; i < n; i++)
    430         if(pos[i].size() > 1)
    431         {
    432             b = pos[i][0];
    433             c = pos[i][1];
    434             same = i;
    435         }
    436     if(same == -1)
    437     {
    438         // If a_b ^ a_c == n - 1, then a_b & a_c = 0 
    439         for(int i = 2; i <= 3; i++)
    440             for(int j = i + 1; j <= n; j++)
    441                 if((xorvals[i] ^ xorvals[j]) == n - 1)
    442                 {
    443                     b = i;
    444                     c = j;
    445                 }
    446         int xorab = xorvals[a] ^ xorvals[b], xorac = xorvals[a] ^ xorvals[c], xorbc = xorvals[b] ^ xorvals[c];
    447         int andab = queries("AND", a, b);
    448         int andac = queries("AND", a, c);
    449         int andbc = 0;
    450         int x = xorab + 2 * andab;
    451         int y = xorac + 2 * andac;
    452         int z = xorbc + 2 * andbc;
    453         assert((x + y - z) % 2 == 0);
    454         ans[a] = (x + y - z) / 2;
    455     }
    456     else
    457     {
    458         // if a_1 ^ a_b == a_1 ^ a_c, then a_b = a_c = (a_b & a_c)
    459         ans[b] = queries("AND", b, c);
    460         ans[1] = xorvals[b] ^ ans[b];
    461     }
    462     for(int i = 2; i <= n; i++)
    463         ans[i] = (xorvals[i] ^ ans[1]);
    464     cout << "! ";
    465     for(int i = 1; i <= n; i++)
    466         cout << ans[i] << " ";
    467     cout << endl;
    468     cout.flush();
    469     return 0;
    470 }
    471 ```
    472 
    473 **Code (Java)**
    474 
    475 ```
    476 import java.util.*;
    477 import java.util.ArrayList;
    478 public class Main {
    479     public static int queries(String s, int i, int j, Scanner sc)
    480     {
    481         System.out.println(s + " " + i + " " + j);
    482         System.out.flush();
    483         int x = sc.nextInt();
    484         if(x == -1)
    485             System.exit(0);
    486         return x;
    487     }
    488     public static void main(String args[])
    489     {
    490         Scanner sc = new Scanner(System.in);
    491         int n = sc.nextInt();
    492         ArrayList<Integer> pos[] = new ArrayList[n + 1];
    493         for(int i = 0; i <= n; i++)
    494             pos[i] = new ArrayList<Integer>();
    495         int xorvals[] = new int[n + 1];
    496         int ans[] = new int[n + 1];
    497         xorvals[1] = 0;
    498         pos[0].add(1);
    499         for(int i = 2; i <= n; i++)
    500         {
    501             xorvals[i] = queries("XOR", 1, i, sc);
    502             pos[xorvals[i]].add(i);
    503         }
    504         int a = 1, b = -1, c = -1;
    505         int same = -1;
    506         for(int i = 0; i < n; i++)
    507         if(pos[i].size() > 1)
    508             {
    509                 b = pos[i].get(0);
    510                 c = pos[i].get(1);
    511                 same = i;
    512             }
    513         if(same == -1)
    514         {
    515             // If a_b ^ a_c == n - 1, then a_b & a_c = 0 
    516             for(int i = 2; i <= 3; i++)
    517                 for(int j = i + 1; j <= n; j++)
    518                     if((xorvals[i] ^ xorvals[j]) == n - 1)
    519                     {
    520                         b = i;
    521                         c = j;
    522                     }
    523             assert(b != -1 && c != -1);
    524             int xorab = xorvals[a] ^ xorvals[b], xorac = xorvals[a] ^ xorvals[c], xorbc = xorvals[b] ^ xorvals[c];
    525             int andab = queries("AND", a, b, sc);
    526             int andac = queries("AND", a, c, sc);
    527             int andbc = 0;
    528             int x = xorab + 2 * andab;
    529             int y = xorac + 2 * andac;
    530             int z = xorbc + 2 * andbc;
    531             assert((x + y - z) % 2 == 0);
    532             ans[a] = (x + y - z) / 2;
    533         }
    534         else
    535         {
    536             // if a_1 ^ a_b == a_1 ^ a_c, then a_b = a_c = (a_b & a_c)
    537             ans[b] = queries("AND", b, c, sc);
    538             ans[1] = xorvals[b] ^ ans[b];
    539         }
    540         for(int i = 2; i <= n; i++)
    541             ans[i] = (xorvals[i] ^ ans[1]);
    542         System.out.print("! ");
    543         for(int i = 1; i <= n; i++)
    544             System.out.print(ans[i] + " ");
    545         System.out.println();
    546         System.out.flush();
    547     }
    548 }
    549 ```
    550 
    551 Idea by [FastestFinger](/profile/FastestFinger "Master FastestFinger"), [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10")
    552 
    553 [1451F - Nullify The Matrix](/contest/1451/problem/F "Codeforces Round 685 (Div. 2)")
    554 
    555 **Tutorial**
    556 
    557 Tutorial is loading...
    558 
    559 **Code (C++)**
    560 
    561 ```
    562 #include <bits/stdc++.h>
    563 using namespace std;
    564  
    565 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    566 #define endl "\n"
    567 #define int long long
    568  
    569 const int N = 105;
    570  
    571 int n, m;
    572 int a[N][N], xorsum[2 * N];
    573  
    574 int32_t main()
    575 {
    576     IOS;
    577     int t;
    578     cin >> t;
    579     while(t--)
    580     {
    581         memset(xorsum, 0, sizeof(xorsum));
    582         cin >> n >> m;
    583         for(int i = 1; i <= n; i++)
    584         {
    585             for(int j = 1; j <= m; j++)
    586             {
    587                 cin >> a[i][j];
    588                 xorsum[i + j] ^= a[i][j];
    589             }
    590         }
    591         int flag = 1;
    592         for(int i = 1; i <= n + m; i++)
    593             flag &= (xorsum[i] == 0);
    594         if(!flag)
    595             cout << "Ashish" << endl;
    596         else
    597             cout << "Jeel" << endl;
    598     }
    599     return 0;
    600 }
    601 ```
    602 
    603 **Code (Java)**
    604 
    605 ```
    606 import java.util.*;
    607  
    608 public class NullifyTheMatrix {
    609     public static void main(String[] args) {
    610         Scanner sc = new Scanner(System.in);
    611         int t = sc.nextInt();
    612  
    613         for(int x = 0; x < t; ++x) {
    614             int n = sc.nextInt();
    615             int m = sc.nextInt();
    616  
    617             int mat[][] = new int[n][m];
    618             for(int i = 0; i < n; ++i) {
    619                 for(int j = 0; j < m; ++j)
    620                     mat[i][j] = sc.nextInt();
    621             }
    622  
    623             int xors[] = new int[n + m - 1];
    624             for(int i = 0; i < n; ++i) {
    625                 for(int j = 0; j < m; ++j)
    626                     xors[i + j] ^= mat[i][j];
    627             }
    628  
    629             int flag = 0;
    630             for(int xor : xors) {
    631                 flag |= xor != 0 ? 1 : 0;
    632             }
    633  
    634             if(flag == 1)
    635                 System.out.println("Ashish");
    636             else
    637                 System.out.println("Jeel");
    638         }
    639     }
    640 }
    641 ```
    642 
    643 Idea by [Jeel_Vaishnav](/profile/Jeel_Vaishnav "Grandmaster Jeel_Vaishnav")