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 ```