codeforces-scrape

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

822.md (10301B)


      1 Source: https://codeforces.com/blog/entry/53068
      2 
      3 Tutorial is loading...
      4 
      5 First accepted Div1: 00:00:58 [kriii](/profile/kriii "Grandmaster kriii")
      6 
      7 First accepted Div2: 00:00:59 [Baneling3](/profile/Baneling3 "Expert Baneling3")
      8 
      9 **Author's solution**
     10 
     11 ```
     12     int a, b;
     13     scanf ( "%d%d", &a, &b );
     14     int ans = 1;
     15     for ( int j = 1; j <= min( a, b ); j++ )
     16     	ans *= j;
     17     printf ( "%d\n", ans );
     18 ```
     19 
     20 Tutorial is loading...
     21 
     22 First accepted Div1: 00:03:30 [kiyotaka](/profile/kiyotaka "Master kiyotaka")
     23 
     24 First accepted Div2: 00:04:43 [Baneling3](/profile/Baneling3 "Expert Baneling3")
     25 
     26 **Author's solution**
     27 
     28 ```
     29     const int maxn = 1050;
     30 
     31     vector < int > ans;
     32     vector < int > newAns;
     33 
     34     char t1[maxn];
     35     char t2[maxn];
     36 
     37     int n, m;
     38     scanf ( "%d%d\n", &n, &m );
     39     gets( t1 );
     40     gets( t2 );
     41 
     42     for ( int j = 0; j < n; j++ )
     43     	ans.pb( j );
     44 
     45     for ( int j = 0; j < m - n + 1; j++ ) {
     46     	newAns.clear();
     47     	for ( int i = 0; i < n; i++ )
     48     		if ( t1[i] != t2[i + j] )
     49     			newAns.pb( i );
     50     	if ( newAns.size() < ans.size() )
     51     		ans = newAns;
     52     }
     53     int sz = ans.size();
     54     printf( "%d\n", sz );
     55     for ( int j = 0; j < sz; j++ ) 
     56     	printf( "%d ", ans[j] + 1 );
     57 ```
     58 
     59 Tutorial is loading...
     60 
     61 First accepted Div1: 00:08:30 [nuip](/profile/nuip "International Master nuip")
     62 
     63 First accepted Div2: 00:10:19 [ColdSu](/profile/ColdSu "Expert ColdSu")
     64 
     65 **Author's solution**
     66 
     67 ```
     68 const int maxn = 200500;
     69 const int inf = ( 2e9 ) + 2;
     70 
     71 vector < pair < pair < int, int >, pair < int, int > > > queries;
     72 int bestCost[maxn];
     73 
     74 int l[maxn];
     75 int r[maxn];
     76 int cost[maxn];
     77 
     78 int solution( int n, int needLen ) {
     79     queries.clear();
     80     for ( int j = 0; j < n; j++ ) {
     81         queries.pb( mp( mp( l[j], -1 ), mp( r[j], cost[j] ) ) );
     82         queries.pb( mp( mp( r[j], 1 ), mp( l[j], cost[j] ) ) );
     83     }
     84     for ( int j = 0; j < maxn; j++ )
     85         bestCost[j] = inf;
     86     ll ans = 2LL * inf;
     87     sort( queries.begin(), queries.end() );
     88     int sz = queries.size();
     89     for ( int j = 0; j < sz; j++ ) {
     90         int type = queries[j].f.s;
     91         if ( type == -1 ) {
     92             int curLen = queries[j].s.f - queries[j].f.f + 1;
     93             if ( curLen <= needLen )
     94                 ans = min( ans, 1LL * queries[j].s.s + 1LL * bestCost[needLen - curLen] );
     95         }
     96         if ( type == 1 ) {
     97             int curLen = queries[j].f.f - queries[j].s.f + 1;
     98             bestCost[curLen] = min( bestCost[curLen], queries[j].s.s );
     99         }
    100     }
    101     return ans >= inf ? -1 : ans;
    102 }
    103 ```
    104 
    105 Tutorial is loading...
    106 
    107 First accepted Div1: 00:15:47 [arsijo](/profile/arsijo "Grandmaster arsijo")
    108 
    109 First accepted Div2: 00:18:01 [ColdSu](/profile/ColdSu "Expert ColdSu")
    110 
    111 **Author's solution**
    112 
    113 ```
    114 const int maxn = 5000500;
    115 
    116 int isPrime[maxn];
    117 ll dp[maxn];
    118 
    119 int main()
    120 {
    121     int t, l, r;
    122     scanf ( "%d%d%d", &t, &l, &r );
    123     for ( int j = 2; j < maxn; j++ )
    124         isPrime[j] = j;
    125     for ( int j = 2; j * j < maxn; j++ )
    126         if ( isPrime[j] == j )
    127             for ( int i = j * j; i < maxn; i += j )
    128                 isPrime[i] = min( j, isPrime[i] );
    129 
    130     dp[1] = 0;
    131     for ( int j = 2; j < maxn; j++ ) {
    132         dp[j] = 1LL * inf * inf;
    133         for ( int x = j; x != 1; x /= isPrime[x] )
    134             dp[j] = min( dp[j], 1LL * dp[j / isPrime[x]] + 1LL * j * ( isPrime[x] - 1 ) / 2LL );
    135     }
    136 
    137     int ans = 0;
    138     int cnt = 1;
    139     for ( int j = l; j <= r; j++ ) {
    140         dp[j] %= base;
    141         ans = ( 1LL * ans + 1LL * cnt * dp[j] ) % base;
    142         cnt = ( 1LL * cnt * t ) % base;
    143     }
    144     printf ( "%d\n", ans );
    145 }
    146 ```
    147 
    148 Tutorial is loading...
    149 
    150 First accepted Div1: 00:43:18 [Pepe.Chess](/profile/Pepe.Chess "Master Pepe.Chess")
    151 
    152 First accepted Div2: 01:05:21 [CountOlaf](/profile/CountOlaf "Candidate Master CountOlaf")
    153 
    154 **Author's solution**
    155 
    156 ```
    157 import java.io.*;
    158 import java.util.*;
    159 
    160 public class Main implements Runnable {
    161     static class InputReader {
    162         BufferedReader reader;
    163         StringTokenizer tokenizer;
    164 
    165         InputReader(InputStream in) {
    166             reader = new BufferedReader(new InputStreamReader(in), 1 << 20);
    167             tokenizer = null;
    168         }
    169 
    170         String next() {
    171             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    172                 try {
    173                     tokenizer = new StringTokenizer(reader.readLine());
    174                 } catch (IOException e) {
    175                     e.printStackTrace();
    176                     throw new RuntimeException(e);
    177                 }
    178             }
    179             return tokenizer.nextToken();
    180         }
    181 
    182         int nextInt() {
    183             return Integer.parseInt(next());
    184         }
    185 
    186         long nextLong() {
    187             return Long.parseLong(next());
    188         }
    189 
    190         double nextDouble() {
    191             return Double.parseDouble(next());
    192         }
    193     }
    194 
    195     static long[] unique(long[] arr) {
    196         Arrays.sort(arr);
    197         int newLen = 0;
    198         for (int i = 0; i < arr.length; i++) {
    199             if (i + 1 == arr.length || arr[i] != arr[i + 1]) {
    200                 arr[newLen++] = arr[i];
    201             }
    202         }
    203         return Arrays.copyOf(arr, newLen);
    204     }
    205 
    206     static class SuffixArray {
    207          int[][] classes;
    208          String s;
    209          int maxH;
    210          SuffixArray(String s) {
    211              this.s = s;
    212              maxH = 0;
    213              while ((1 << maxH) <= s.length()) maxH++;
    214              classes = new int[maxH][];
    215              for (int h = 0; h < maxH; h++) {
    216                  classes[h] = new int[s.length()];
    217              }
    218              for (int i = 0; i < s.length(); i++) {
    219                  classes[0][i] = s.charAt(i) - 'a';
    220              }
    221              for (int h = 1; h < maxH; h++) {
    222                  long[] values = new long[s.length() - (1 << h) + 1];
    223                  int valuesLen = 0;
    224                  for (int i = 0; i + (1 << h) <= s.length(); i++) {
    225                      int leftPart = classes[h - 1][i];
    226                      int rightPart = classes[h - 1][i + (1 << (h - 1))];
    227                      long curValue = ((long)leftPart << 30) ^ rightPart;
    228                      values[valuesLen++] = curValue;
    229                  }
    230                  values = unique(values);
    231                  for (int i = 0; i + (1 << h) <= s.length(); i++) {
    232                      int leftPart = classes[h - 1][i];
    233                      int rightPart = classes[h - 1][i + (1 << (h - 1))];
    234                      long curValue = ((long)leftPart << 30) ^ rightPart;
    235                      classes[h][i] = Arrays.binarySearch(values, curValue);
    236                  }
    237              }
    238          }
    239          int getLCP(int i, int j) {
    240              int res = 0;
    241              for (int h = maxH - 1; h >= 0; h--) {
    242                  if (i + (1 << h) <= s.length() && j + (1 << h) <= s.length() && classes[h][i] == classes[h][j]) {
    243                      res += (1 << h);
    244                      i += (1 << h);
    245                      j += (1 << h);
    246                  }
    247              }
    248              return res;
    249          }
    250     }
    251 
    252     @Override
    253     public void run() {
    254 
    255         InputReader in = new InputReader(System.in);
    256         PrintWriter out = new PrintWriter(System.out);
    257 
    258         int n = in.nextInt();
    259         String s = in.next();
    260         int m = in.nextInt();
    261         String t = in.next();
    262 
    263         int x = in.nextInt();
    264 
    265         int[][] dp = new int[x + 1][n + 1];
    266 
    267         for (int i = 0; i <= x; i++) {
    268             for (int j = 0; j <= n; j++) {
    269                 dp[i][j] = Integer.MIN_VALUE;
    270             }
    271         }
    272 
    273         String q = s + "#" + t;
    274 
    275         SuffixArray sarr = new SuffixArray(q);
    276 
    277         dp[0][0] = 0;
    278 
    279         for (int cnt = 0; cnt <= x; cnt++) {
    280             for (int prefS = 0; prefS <= n; prefS++) {
    281                 if (dp[cnt][prefS] == Integer.MIN_VALUE) continue;
    282                 //System.err.println("cnt = " + cnt + ", prefS = " + prefS + ", value = " + dp[cnt][prefS]);
    283                 if (prefS + 1 <= n && dp[cnt][prefS + 1] < dp[cnt][prefS]) {
    284                     dp[cnt][prefS + 1] = dp[cnt][prefS];
    285                 }
    286                 if (cnt + 1 <= x) {
    287                     int prefT = dp[cnt][prefS];
    288                     int lcp = sarr.getLCP(prefS, prefT + n + 1);
    289                     if (dp[cnt + 1][prefS + lcp] < prefT + lcp) {
    290                         dp[cnt + 1][prefS + lcp] = prefT + lcp;
    291                     }
    292                 }
    293             }
    294         }
    295 
    296         boolean ok = false;
    297 
    298         for (int cnt = 0; cnt <= x; cnt++) {
    299             if (dp[cnt][n] == m) {
    300                 ok = true;
    301             }
    302         }
    303 
    304         out.println(ok ? "YES" : "NO");
    305 
    306         out.close();
    307     }
    308 
    309     public static void main(String[] args) {
    310         new Thread(null, new Main(), "1", 1L << 28).run();
    311     }
    312 }
    313 ```
    314 
    315 Tutorial is loading...
    316 
    317 First accepted Div1: 00:16:33 [webmaster](/profile/webmaster "International Master webmaster")
    318 
    319 First accepted Div2: 01:12:52 [Nisiyama_Suzune](/profile/Nisiyama_Suzune "Candidate Master Nisiyama_Suzune")
    320 
    321 **Author's solution**
    322 
    323 ```
    324 const int maxn = 105;
    325 
    326 vector < pair < int, int > > edge[maxn];
    327 int used[maxn];
    328 int from[maxn];
    329 int where[maxn];
    330 ld dist[maxn];
    331 
    332 void dfs( int v, ld prevTime ) {
    333     used[v] = true;
    334     int sz = edge[v].size();
    335     ld bestTime = 2.0L / sz;
    336     ld nextTime = prevTime + bestTime;
    337     if ( nextTime >= 2.0L )
    338         nextTime -= 2.0L;
    339     for ( int j = 0; j < sz; j++ ) {
    340         int id = edge[v][j].f;
    341         int to = edge[v][j].s;
    342         if ( used[to] )
    343             continue;
    344 
    345         ld toTime;
    346         if ( nextTime <= 1.0L ) {
    347             from[id] = to;
    348             where[id] = v;
    349             dist[id] = 1.0L - nextTime;
    350             toTime = nextTime + 1.0L;
    351         } else {
    352             from[id] = v;
    353             where[id] = to;
    354             dist[id] = 2.0L - nextTime;
    355             toTime = nextTime - 1.0L;
    356         }
    357 
    358         dfs( to, toTime );
    359 
    360         nextTime = nextTime + bestTime;
    361         if ( nextTime >= 2.0L )
    362             nextTime -= 2.0L;
    363     }
    364 }
    365 
    366 int main()
    367 {
    368     int n;
    369     scanf ( "%d", &n );
    370     for ( int j = 1; j < n; j++ ) {
    371         int u, v;
    372         scanf ( "%d%d", &u, &v );
    373         edge[u].pb( mp( j, v ) );
    374         edge[v].pb( mp( j, u ) );
    375     }
    376     dfs( 1, 0 );
    377     printf( "%d\n", n - 1 );
    378     for ( int j = 1; j < n; j++ ) {
    379         printf( "%d %d %d %d ", 1, j, from[j], where[j] );
    380         cout << fixed << setprecision( 10 ) << dist[j] << endl;
    381     }
    382 }
    383 ```