Привет, расскажите, пожалуйста, задачи A, B, H.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
Привет, расскажите, пожалуйста, задачи A, B, H.
Name |
---|
Div.2 easier string problems N4 [C--] and O4 [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 E4 Exress 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 possible k.
We can also show that the smallest k satisfying 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 as N / 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 primes2, we need powers of two; i.e., 21, 22, 23, ..., . Your code gives incorrect result for 999990008. The answer should be
(24 = 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 zgjx0802@sina.com