Ripatti's blog

Codeforces Round #139 (div2)
By Ripatti, 12 years ago, translation, In English

Hello everyone!

That is Codeforces Round 139 for the second division only. Members of the first division can participate out of competition.

Round is prepared by Ripatti , Gerald , Delinur.

We will use dynamic score system. Problems will be ordered in order of expected increasing difficulty.

Good luck!

UPD. For technical reasons round delays in 15 minutes.

UPD2. Testing is complete. Winners:
1. wccy
2. ttl
3. shubhanshu
4. Atarashi_Ako
5. dvylfz921

2 members solved all 5 problems.

English editorial will be tomorrow. You can try to understand russian editorial.

UPD3. English editorial.

  • Vote: I like it
  • +88
  • Vote: I do not like it

Comments Comments (29)
| Write comment?
»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Time for the contest is 23:30 in China. It's toooo late

→ Reply
»
12 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Missed the registration. Didn't know contest was today. Quite quick back to back to contests.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder what is the solution of E. Anybody write in short please.

→ Reply
»
12 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I finished Div.2 C problem just 5s late... Bad luck...

→ Reply
»
12 years ago, # |
  Vote: I like it +27 Vote: I do not like it

"It started like a Cheetah , but now is as slow as a snail "- yes , the system testing

→ Reply
»
12 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Solutions to A and E of wccy and wzc1995 are ditto same.

→ Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

So slow.. =/

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Although my program of problem C is passed by the system test, my total scores in the scoreboard does NOT add the score of the problem C as well as my new rating. Please recalculate my score and new rating.

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

For this 139 competition, I receive notification on E-mail 4 hour after contest!

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

225D - Snake In the problem was said that the snake's head is "1", the second segment is "2", and so on to k. But in the sixth test the snake starts from 5 to 9. Where is the first part from 1 to 4?

I saw it — http://mirror.codeforces.com/blog/entry/5322#comment-105121

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Because some large test case may be not display completely

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm having some troubles generating the K-bonacci numbers on problem B. I tried to just implement the recurrences describe in the problem statement, but I suppose I have a bug somewhere. Can anyone help? Thanks.

typedef long long i64;
i64 K;
i64 S;

i64 F(i64 n) {
  if (n >=1 && n < K)
    return 0;
  if (n==K)
    return 1;
  i64 ans = 0;
  while(n > K) {
    ans += F(n-1);
    --n;
  }
  return ans;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("139_B.in","r", stdin);
#endif

  cin>>S>>K;
  for(int i = 1; i <= 15; ++i) {
    cout<<F(i)<<endl;
  }

  return 0;
}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    while(n > K) is wrong. You should add every F(x) for x in [n — K — 1, n — 1].

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for the help. I changed the loop to be like this, but I never get 3 as one of the K-bonacci numbers when using K=2. However, according to example 1, 3 is supposed to be one of the numbers.

        FOR(x,n-K-1,n-1) {
    if (x < 0)
      break;
    ans += F(x);
  }

      At any rate, I don't want to waste anyone's time here, so I will try to study some other solutions to see if I can use them as a reference. Thanks very much again for your help, I really appreciate it.

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is the relation between Mersenne primes and the answer of Problem E???? I mean what is the proof that (2^(Mp-1)-1) don't have an answer to the equation??? I will appreciate a proof or a reference to be read! ;)

→ Reply