Привет, расскажите, пожалуйста, задачи A, B, H.

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

Привет, расскажите, пожалуйста, задачи A, B, H.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 21:01:40 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Div.2 easier string problems

N4 [C--] andO4 [Allo] using Perl as higher-level language (C--, Allo).It seems that problemset from CERC 2014 was used today, but with renamed and shuffled problems.

Here you may find standings from original contest; i guess that mapping between problems is following:

Announcement at CERC site says that

the contest data (problems, tests, and model solutions) will be posted at Sunday, November 23.— i guess Opencup was a reason for such a delay:) And we'll see solutions published soon.How to solve

E4Exress As The Sum: faster than O(t * N ^ 3/4) ?, N = 10^9, t — unknown amount of tests. TL.We can represent our segment as [

x+ 1, ...,x+k]. The sum equals to , so now it's clear that . Now we can iterate over all possiblek.We can also show that the smallest

ksatisfying the equation is either a prime or a power of two. So it is sufficient to iterate over all primes and all powers of 2 less than or equal to The primes can be precomputed using Eratosthenes sieve. This gives total complexity ofπ(

N) (the number of primes less than N) can be approximated asN/log(N).The approximation gives total complexity which is a little better than .

Actually my solution in received time limit exceeded and the optimization above helped to get it accepted. Maybe this is because I am using slow Ejudge server and it makes even the simplest problem more interesting:)

Accepted code (a little ugly, I call 2^n a prime:): http://pastie.org/9739170

I haven't realized that we need no only primes, but primes**2 also. So I used all numbers from 2 to sqrt(N), but now I've written with primes, but still getting TL on tc 2. Can't understand why. (code). Ideone says, that such primes are generated in 0.1 sec (and there are 4.7k of them). And I can't understand what can be the biggest interval of numbers?

1) We do not need

primes^{2}, we need powers of two; i.e., 2^{1}, 2^{2}, 2^{3}, ..., . Your code gives incorrect result for 999990008. The answer should be(2

^{4}= 16 elements)2) I don't know Perl, but I couldn't get my Java solution working. 1 second time limit seems rather strict. Probably you should try C/C++.

.

hello,where is the place to see and submitt the problem

hello,could some friend share the statements of the open cup gp of europe div2,thanks very much,my email is [email protected]