codeforces-scrape

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

1670.md (16688B)


      1 Source: https://codeforces.com/blog/entry/102579
      2 
      3 Here is the editorial. Please provide your feedback on each problem so that we can improve upon them the next time.
      4 
      5 ### [1670A - Профессор Слим](/contest/1670/problem/A "Codeforces Round 788 (Div. 2)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 import java.io.*;
     15 import java.util.StringTokenizer;
     16  
     17 public class A {
     18     public static void main(String[] args) throws IOException {
     19         Scanner sc = new Scanner(System.in);
     20         PrintWriter pw = new PrintWriter(System.out);
     21         int tc = sc.nextInt();
     22         for (int test = 1; test <= tc; test++) {
     23             int n = sc.nextInt();
     24             int[] arr = new int[n];
     25             for (int i = 0; i < n; i++)
     26                 arr[i] = sc.nextInt();
     27             int i = 0, j = 0;
     28             while (i < n) {
     29                 if (arr[i] < 0) {
     30                     arr[j++] *= -1;
     31                     arr[i] *= -1;
     32                 }
     33                 i++;
     34             }
     35             if (isSorted(arr)) {
     36                 pw.println("YES");
     37             } else
     38                 pw.println("NO");
     39         }
     40         pw.flush();
     41     }
     42  
     43     private static boolean isSorted(int[] arr) {
     44         for (int i = 1; i < arr.length; i++)
     45             if (arr[i] < arr[i - 1])
     46                 return false;
     47         return true;
     48     }
     49  
     50     static class Scanner {
     51         BufferedReader br;
     52         StringTokenizer st;
     53  
     54         public Scanner(InputStream s) {
     55             br = new BufferedReader(new InputStreamReader(s));
     56         }
     57  
     58         public Scanner(FileReader f) {
     59             br = new BufferedReader(f);
     60         }
     61  
     62         public String next() throws IOException {
     63             while (st == null || !st.hasMoreTokens())
     64                 st = new StringTokenizer(br.readLine());
     65             return st.nextToken();
     66         }
     67  
     68         public int nextInt() throws IOException {
     69             return Integer.parseInt(next());
     70         }
     71  
     72         public long nextLong() throws IOException {
     73             return Long.parseLong(next());
     74         }
     75  
     76         public double nextDouble() throws IOException {
     77             return Double.parseDouble(next());
     78         }
     79  
     80         public int[] nextIntArr(int n) throws IOException {
     81             int[] arr = new int[n];
     82             for (int i = 0; i < n; i++) {
     83                 arr[i] = Integer.parseInt(next());
     84             }
     85             return arr;
     86         }
     87  
     88     }
     89 }
     90 ```
     91 
     92 ### [1670B - Общажные войны](/contest/1670/problem/B "Codeforces Round 788 (Div. 2)")
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **Solution**
     99 
    100 ```
    101 import java.io.*;
    102 import java.util.StringTokenizer;
    103  
    104 public class B{
    105  
    106  
    107     public static void main(String[] args) throws IOException {
    108         Scanner sc = new Scanner(System.in);
    109         PrintWriter pw = new PrintWriter(System.out);
    110         int tests = sc.nextInt();
    111         for (int test = 0; test < tests; test++) {
    112             int n = sc.nextInt();
    113             char[] arr = sc.next().toCharArray();
    114             int k = sc.nextInt();
    115             boolean[] special = new boolean[26];
    116             for (int i = 0; i < k; i++)
    117                 special[sc.next().charAt(0) - 'a'] = true;
    118             int idx = -1;
    119             for (int i = 0; i < n; i++)
    120                 if (special[arr[i] - 'a'])
    121                     idx = i;
    122             int max=0;
    123             for(int i=idx-1;i>=0;i--){
    124                 int j=i;
    125                 while (j>0&&!special[arr[j]-'a'])
    126                     j--;
    127                 max=Math.max(max,i+1-j);
    128                 i=j;
    129             }
    130             pw.println(max);
    131         }
    132         pw.flush();
    133     }
    134  
    135  
    136     public static class Scanner {
    137         StringTokenizer st;
    138         BufferedReader br;
    139  
    140         public Scanner(InputStream s) {
    141             br = new BufferedReader(new InputStreamReader(s));
    142         }
    143  
    144         public Scanner(String s) throws FileNotFoundException {
    145             br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
    146         }
    147  
    148         public String next() throws IOException {
    149             while (st == null || !st.hasMoreTokens())
    150                 st = new StringTokenizer(br.readLine());
    151             return st.nextToken();
    152         }
    153  
    154         public int nextInt() throws IOException {
    155             return Integer.parseInt(next());
    156         }
    157  
    158         public long nextLong() throws IOException {
    159             return Long.parseLong(next());
    160         }
    161     }
    162 }
    163 ```
    164 
    165 ### [1670C - Где пицца?](/contest/1670/problem/C "Codeforces Round 788 (Div. 2)")
    166 
    167 **Tutorial**
    168 
    169 Tutorial is loading...
    170 
    171 **Solution**
    172 
    173 ```
    174 import java.io.*;
    175 import java.util.HashSet;
    176 import java.util.StringTokenizer;
    177  
    178 public class C{
    179  
    180     static int mod = (int) 1e9 + 7;
    181  
    182     public static void main(String[] args) throws IOException {
    183         Scanner sc = new Scanner(System.in);
    184         PrintWriter pw = new PrintWriter(System.out);
    185         int tests = sc.nextInt();
    186         for (int test = 0; test < tests; test++) {
    187             int n = sc.nextInt();
    188             int[] first = new int[n];
    189             int[] second = new int[n];
    190             int[] third=new int[n];
    191             for (int i = 0; i < n; i++)
    192                 first[i] = sc.nextInt() - 1;
    193             for (int i = 0; i < n; i++)
    194                 second[i] = sc.nextInt() - 1;
    195             for(int i=0;i<n;i++)
    196                 third[i]= sc.nextInt()-1;
    197             UnionFind uf = new UnionFind(n);
    198             for (int i = 0; i < n; i++)
    199                 uf.unionSet(first[i], second[i]);
    200             HashSet<Integer> set = new HashSet<>();
    201             for (int i = 0; i < n; i++)
    202                 set.add(uf.findSet(i));
    203             for(int i=0;i<n;i++){
    204                 if(third[i]==-1)
    205                     continue;
    206                 set.remove(uf.findSet(third[i]));
    207             }
    208             int pow = 0;
    209             for (int x : set)
    210                 if (uf.sizeOfSet(x) > 1)
    211                     pow++;
    212             int ans = 1;
    213             for (int i = 0; i < pow; i++)
    214                 ans = (int) ((2L * ans) % mod);
    215             pw.println(ans);
    216         }
    217         pw.flush();
    218     }
    219     
    220     
    221     
    222      public static class UnionFind {
    223         int[] p, rank, setSize;
    224         int numSets;
    225  
    226         public UnionFind(int N) {
    227             p = new int[numSets = N];
    228             rank = new int[N];
    229             setSize = new int[N];
    230             for (int i = 0; i < N; i++) {
    231                 p[i] = i;
    232                 setSize[i] = 1;
    233             }
    234         }
    235  
    236         public int findSet(int i) {
    237             return p[i] == i ? i : (p[i] = findSet(p[i]));
    238         }
    239  
    240         public boolean isSameSet(int i, int j) {
    241             return findSet(i) == findSet(j);
    242         }
    243  
    244         public void unionSet(int i, int j) {
    245             if (isSameSet(i, j))
    246                 return;
    247             numSets--;
    248             int x = findSet(i), y = findSet(j);
    249             if (rank[x] > rank[y]) {
    250                 p[y] = x;
    251                 setSize[x] += setSize[y];
    252             } else {
    253                 p[x] = y;
    254                 setSize[y] += setSize[x];
    255                 if (rank[x] == rank[y]) rank[y]++;
    256             }
    257         }
    258  
    259         public int numDisjointSets() {
    260             return numSets;
    261         }
    262  
    263         public int sizeOfSet(int i) {
    264             return setSize[findSet(i)];
    265         }
    266     }
    267  
    268  
    269     public static class Scanner {
    270         StringTokenizer st;
    271         BufferedReader br;
    272  
    273         public Scanner(InputStream s) {
    274             br = new BufferedReader(new InputStreamReader(s));
    275         }
    276  
    277         public Scanner(String s) throws FileNotFoundException {
    278             br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
    279         }
    280  
    281         public String next() throws IOException {
    282             while (st == null || !st.hasMoreTokens())
    283                 st = new StringTokenizer(br.readLine());
    284             return st.nextToken();
    285         }
    286  
    287         public int nextInt() throws IOException {
    288             return Integer.parseInt(next());
    289         }
    290  
    291         public long nextLong() throws IOException {
    292             return Long.parseLong(next());
    293         }
    294     }
    295 }
    296 ```
    297 
    298 ### [1670D - Очень подозрительно](/contest/1670/problem/D "Codeforces Round 788 (Div. 2)")
    299 
    300 **Tutorial**
    301 
    302 Tutorial is loading...
    303 
    304 **Solution**
    305 
    306 ```
    307 import java.util.*;
    308 import java.io.*;
    309  
    310 public class D{
    311 	public static void main(String[] args) throws Exception {
    312 		int t=sc.nextInt();
    313 		while(t-->0) {
    314 			pw.println(sol(sc.nextInt()));
    315 		}
    316 		pw.close();
    317 	}
    318 	
    319 	public static int sol(int n) {
    320 		int low=0;
    321 		int high=(int)1e9;
    322 		int mid=(low+high)/2;
    323 		while(low<=high) {
    324 			if(calc(mid)<n) {
    325 				low=mid+1;
    326 			}else {
    327 				high=mid-1;
    328 			}
    329 			mid=(low+high)/2;
    330 		}
    331 		return low;
    332 	}
    333 	
    334 	public static long calc(long n) {
    335 		n--;
    336 		long ans=0;
    337 		ans=(n/3)*(n/3)*3;
    338 		for (int i = 0; i <= n % 3; i++)
    339 			ans += (n / 3) * 2 + i;
    340 		return ans*2;
    341 	}
    342  
    343 	static class Scanner {
    344 		StringTokenizer st;
    345 		BufferedReader br;
    346  
    347 		public Scanner(InputStream s) {
    348 			br = new BufferedReader(new InputStreamReader(s));
    349 		}
    350  
    351 		public Scanner(FileReader r) {
    352 			br = new BufferedReader(r);
    353 		}
    354  
    355 		public String next() throws IOException {
    356 			while (st == null || !st.hasMoreTokens())
    357 				st = new StringTokenizer(br.readLine());
    358 			return st.nextToken();
    359 		}
    360  
    361 		public int nextInt() throws IOException {
    362 			return Integer.parseInt(next());
    363 		}
    364  
    365 		public long nextLong() throws IOException {
    366 			return Long.parseLong(next());
    367 		}
    368  
    369 		public String nextLine() throws IOException {
    370 			return br.readLine();
    371 		}
    372  
    373 		public double nextDouble() throws IOException {
    374 			String x = next();
    375 			StringBuilder sb = new StringBuilder("0");
    376 			double res = 0, f = 1;
    377 			boolean dec = false, neg = false;
    378 			int start = 0;
    379 			if (x.charAt(0) == '-') {
    380 				neg = true;
    381 				start++;
    382 			}
    383 			for (int i = start; i < x.length(); i++)
    384 				if (x.charAt(i) == '.') {
    385 					res = Long.parseLong(sb.toString());
    386 					sb = new StringBuilder("0");
    387 					dec = true;
    388 				} else {
    389 					sb.append(x.charAt(i));
    390 					if (dec)
    391 						f *= 10;
    392 				}
    393 			res += Long.parseLong(sb.toString()) / f;
    394 			return res * (neg ? -1 : 1);
    395 		}
    396  
    397 		public long[] nextlongArray(int n) throws IOException {
    398 			long[] a = new long[n];
    399 			for (int i = 0; i < n; i++)
    400 				a[i] = nextLong();
    401 			return a;
    402 		}
    403  
    404 		public Long[] nextLongArray(int n) throws IOException {
    405 			Long[] a = new Long[n];
    406 			for (int i = 0; i < n; i++)
    407 				a[i] = nextLong();
    408 			return a;
    409 		}
    410  
    411 		public int[] nextIntArray(int n) throws IOException {
    412 			int[] a = new int[n];
    413 			for (int i = 0; i < n; i++)
    414 				a[i] = nextInt();
    415 			return a;
    416 		}
    417  
    418 		public Integer[] nextIntegerArray(int n) throws IOException {
    419 			Integer[] a = new Integer[n];
    420 			for (int i = 0; i < n; i++)
    421 				a[i] = nextInt();
    422 			return a;
    423 		}
    424  
    425 		public boolean ready() throws IOException {
    426 			return br.ready();
    427 		}
    428  
    429 	}
    430  
    431 	static Scanner sc = new Scanner(System.in);
    432 	static PrintWriter pw = new PrintWriter(System.out);
    433 }
    434 ```
    435 
    436 ### [1670E - Хемос на дереве](/contest/1670/problem/E "Codeforces Round 788 (Div. 2)")
    437 
    438 **Tutorial**
    439 
    440 Tutorial is loading...
    441 
    442 **Solution**
    443 
    444 ```
    445 import java.util.*;
    446 import java.io.*;
    447  
    448 public class E{
    449     static ArrayList<int[]>[] adj;
    450     static int[] nodeval, edgeval;
    451     static int count, N;
    452  
    453     public static void main(String[] args) throws IOException {
    454         Scanner sc = new Scanner(System.in);
    455         PrintWriter pw = new PrintWriter(System.out);
    456         int t = sc.nextInt();
    457         while(t-->0){
    458         
    459             int n = sc.nextInt();
    460             N = 1 << n;
    461             adj = new ArrayList[N];
    462             for (int i = 0; i < N; i++)
    463                 adj[i] = new ArrayList<>();
    464     
    465             for (int i = 0; i < N - 1; i++) {
    466                 int u = sc.nextInt() - 1;
    467                 int v = sc.nextInt() - 1;
    468     
    469                 adj[u].add(new int[]{v, i});
    470                 adj[v].add(new int[]{u, i});
    471             }
    472             nodeval = new int[N];
    473             edgeval = new int[N];
    474             nodeval[0] = N;
    475             count =0;
    476             dfs(0, -1);
    477     
    478             pw.println(1);
    479             for (int i = 0; i < N; i++)
    480                 pw.print(nodeval[i] + " ");
    481             pw.println();
    482             for (int i = 0; i < N - 1; i++)
    483                 pw.print(edgeval[i] + " ");
    484             pw.println();    
    485         }
    486         pw.close();
    487  
    488     }
    489  
    490     private static void dfs(int u, int p) {
    491  
    492         for (int[] nxt : adj[u]) {
    493             int v = nxt[0];
    494             int idx = nxt[1];
    495             if (v == p)
    496                 continue;
    497             count++;
    498             edgeval[idx] = count + ((nodeval[u] & N) != 0 ? N : 0);
    499             nodeval[v] = count + ((nodeval[u] & N) != 0 ? 0 : N);
    500             dfs(v, u);
    501         }
    502     }
    503  
    504  
    505     static class Scanner {
    506         BufferedReader br;
    507         StringTokenizer st;
    508  
    509         public Scanner(InputStream s) {
    510             br = new BufferedReader(new InputStreamReader(s));
    511         }
    512  
    513         public Scanner(FileReader f) {
    514             br = new BufferedReader(f);
    515         }
    516  
    517         public String next() throws IOException {
    518             while (st == null || !st.hasMoreTokens())
    519                 st = new StringTokenizer(br.readLine());
    520             return st.nextToken();
    521         }
    522  
    523         public int nextInt() throws IOException {
    524             return Integer.parseInt(next());
    525         }
    526  
    527         public long nextLong() throws IOException {
    528             return Long.parseLong(next());
    529         }
    530  
    531         public double nextDouble() throws IOException {
    532             return Double.parseDouble(next());
    533         }
    534  
    535         public int[] nextIntArr(int n) throws IOException {
    536             int[] arr = new int[n];
    537             for (int i = 0; i < n; i++) {
    538                 arr[i] = Integer.parseInt(next());
    539             }
    540             return arr;
    541         }
    542  
    543     }
    544  
    545 }
    546 ```
    547 
    548 ### [1670F - Джи, видишь?](/contest/1670/problem/F "Codeforces Round 788 (Div. 2)")
    549 
    550 **Tutorial**
    551 
    552 Tutorial is loading...
    553 
    554 **Solution**
    555 
    556 ```
    557 import java.io.*;
    558 import java.util.Arrays;
    559 import java.util.StringTokenizer;
    560  
    561 public class F {
    562     static final int mod = (int) 1e9 + 7;
    563     static int n;
    564     static long l, r, z;
    565     static long[][] memo;
    566     static long[][] memo2;
    567  
    568     public static long nCr(int n, int r) {
    569         if (r == 0)
    570             return 1;
    571         if (n == 0)
    572             return 0;
    573         if (memo[n][r] != -1)
    574             return memo[n][r];
    575         return memo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1)) % mod;
    576     }
    577  
    578     public static void main(String[] args) throws IOException {
    579         Scanner sc = new Scanner(System.in);
    580         PrintWriter pw = new PrintWriter(System.out);
    581         int tests = 1;
    582         memo = new long[1001][1001];
    583         for (long[] x : memo)
    584             Arrays.fill(x, -1);
    585         for (int test = 0; test < tests; test++) {
    586             n = sc.nextInt();
    587             l = sc.nextLong();
    588             r = sc.nextLong();
    589             z = sc.nextLong();
    590             long ans = (compute(r) - compute(l - 1) + mod) % mod;
    591             pw.println(ans);
    592         }
    593         pw.flush();
    594     }
    595  
    596     private static long compute(long val) {
    597         memo2 = new long[61][2001];
    598         for (long[] x : memo2)
    599             Arrays.fill(x, -1);
    600         return dp(60, 0, val);
    601     }
    602  
    603     private static long dp(int idx, int rem, long val) {
    604         if (rem > 2000)
    605             rem = 2000;
    606         if (rem < 0)
    607             return 0;
    608         if (idx == -1)
    609             return 1;
    610         if (memo2[idx][rem] != -1)
    611             return memo2[idx][rem];
    612         long ans = 0;
    613         int currentBitXor = (z & 1L << idx)== 0 ? 0 : 1;
    614         for (int i = currentBitXor == 1 ? 1 : 0; i <= n; i += 2) {
    615             int currentBitSum = (val & 1L << idx) == 0 ? 0 : 1;
    616             int nextRem = 2 * (rem + currentBitSum - i);
    617             long toAdd = (nCr(n, i) * dp(idx - 1, nextRem, val)) % mod;
    618             ans = (ans + toAdd) % mod;
    619         }
    620         return memo2[idx][rem] = ans;
    621     }
    622  
    623  
    624     public static class Scanner {
    625         StringTokenizer st;
    626         BufferedReader br;
    627  
    628         public Scanner(InputStream s) {
    629             br = new BufferedReader(new InputStreamReader(s));
    630         }
    631  
    632         public Scanner(String s) throws FileNotFoundException {
    633             br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
    634         }
    635  
    636         public String next() throws IOException {
    637             while (st == null || !st.hasMoreTokens())
    638                 st = new StringTokenizer(br.readLine());
    639             return st.nextToken();
    640         }
    641  
    642         public int nextInt() throws IOException {
    643             return Integer.parseInt(next());
    644         }
    645  
    646         public long nextLong() throws IOException {
    647             return Long.parseLong(next());
    648         }
    649     }
    650 }
    651 ```