Codeforces Beta Round #70 (Div. 2)

13 лет назад, # |

+28

Так и не рассказали о себе :)

→ Ответить

eog	13 лет назад, # ^ \| -7 привет мозырю :D → Ответить

13 лет назад, # ^ |

Здравствуйте, а откуда вы будете =) ?

→ Ответить

eog	13 лет назад, # ^ \| 0 гомель, областной лицей) → Ответить

13 лет назад, # ^ |

а кто вы именно?

→ Ответить

eog	13 лет назад, # ^ \| +3 Миняйлова Елена Леонидовна :DDD → Ответить

agul	13 лет назад, # ^ \| +11 Нашли место обсуждать. → Ответить

eog	13 лет назад, # ^ \| -6 ладно, умываю руки :D → Ответить

Gassa

13 лет назад, # ^ |

Имя и фамилию же можно написать в профиле.

→ Ответить

13 лет назад, # ^ |

и город

→ Ответить

waiter_pvl

13 лет назад, # |

good luck and have fun=)

→ Ответить

philolo1

13 лет назад, # |

-13

I do not like this contest, problem statement two is not clear. And C is to difficult.

→ Ответить

agul	13 лет назад, # ^ \| 0 Stop complaining please. The statements on both languages are OK. And C is not very difficuilt I think. → Ответить

t.gogniashvili

13 лет назад, # ^ |

Yeah that's why you have solved it ?

→ Ответить

golovozhop

13 лет назад, # |

задача E печальна=(

→ Ответить

philolo1

13 лет назад, # |

-18

I did get an answer after one hour, i think it should not be rated.

→ Ответить

philolo1

13 лет назад, # ^ |

maybe there was a problem with my browser

→ Ответить

agul	13 лет назад, # \| 0 Do not you think that downtime in the last quarter of contest could cause some problems for participants? May be you should make this contest longer. → Ответить

ahm.kam_92

13 лет назад, # |

← Rev. 2 →

+22

The problems are nice but I think these problems should have been put into a division 1 contest (Especially: C, D and E). What do you think?

→ Ответить

hogeover30

13 лет назад, # ^ |

I think so too.

→ Ответить

yeputons

13 лет назад, # ^ |

+10

Well, last contest problems C-E for Div.2 was A-C for Div.1
May be you are right, I think that problems are quiet harder that usual.

→ Ответить

dalex

13 лет назад, # ^ |

I agree with you, the problems are quite hard today.

But I'm on 19th place, on the first page! *YAHOO*

→ Ответить

hogeover30

13 лет назад, # ^ |

congrats!

→ Ответить

13 лет назад, # ^ |

I think C,D is not so hard.

E maybe hard for div2 but it is E :)

→ Ответить

Tranvick

13 лет назад, # |

← Rev. 2 →

Можно получить 5ый претест задачи С(div 2)? У меня на нем почему-то валились 3 разных решения.

→ Ответить

NKolotey

13 лет назад, # ^ |

Они жеж после окончания тестирования становятся доступны, когда в разделе "Мои посылки" кликаешь на номер "посылки".

→ Ответить

Tranvick

13 лет назад, # ^ |

Блин, точно =)

→ Ответить

ballon

13 лет назад, # |

E:
Почему в первом тесте ответ-2
Разве они втроём не успеют залесть в капсулы?

→ Ответить

Kandyman

13 лет назад, # ^ |

Последний не успевает добежать из-за взрыва

→ Ответить

ifsmirnov

13 лет назад, # ^ |

Через три единицы времени все взрывается, и верхний не успевает добежать.

→ Ответить

13 лет назад, # ^ |

Ученому из левого верхнего угла бежать 4 хода. А время 3.

Видимо поэтому

→ Ответить

ballon

13 лет назад, # ^ |

← Rev. 2 →

Сказано же что жидкость не проходит через правильно работающие реакторы
Тоисть есть что, жидкость вообще не пройдёт к людям ... или как ?

→ Ответить

13 лет назад, # ^ |

Но в любом случае ВСЯ карта жахнется через t ед. времени

→ Ответить

ballon

13 лет назад, # ^ |

А! Понятно! Спасибо !

→ Ответить

13 лет назад, # |

+11

Сегодня alert'a с кларом, разосланным всем не было.

При том, что обычно рассылается. это ожидаемое поведение?

→ Ответить

Gassa

13 лет назад, # ^ |

Может, это для внеконкурсных участников он не разослался?

→ Ответить

13 лет назад, # ^ |

Может быть.

→ Ответить

ifsmirnov

13 лет назад, # ^ |

А что должен был быть за клар?

→ Ответить

13 лет назад, # ^ |

На странице соревнования есть вопрос, с Отметкой "да" в поле "рассылка"

→ Ответить

witua

13 лет назад, # ^ |

Для учасников в конкурсе (меня) тоже не пришол.

→ Ответить

logic_max

13 лет назад, # |

Problems c,d,e were tough. Problem a,b didn't have any special tests (or pretests were good) so no hack :(.

→ Ответить

13 лет назад, # |

← Rev. 2 →

When I tried to hack problem A, I got an invalid input error said "FAIL Expected EOLN (stdin)", what does this mean?

Missing eol at the last line?

→ Ответить

13 лет назад, # ^ |

Yes, last line should have EOLN too

→ Ответить

13 лет назад, # ^ |

Thanks.

→ Ответить

yarrr

13 лет назад, # |

Не терпится увидеть претест №6 к D.

→ Ответить

hydrastuff

13 лет назад, # |

Спасибо за контест, жаль не успел дописать E.

→ Ответить

DULGUUNBATMUNKH

13 лет назад, # |

how u guys hackin? Teach me PLS :D i'm newbie

→ Ответить

13 лет назад, # ^ |

1)Solve any problem

2)Open problemlist

3)Click "Lock"-icon

4)Open your room

5)Ctrl+Click to any cell(problem you lock only) and see others solution.

6)Write test or generator and submit hack

→ Ответить

wRabbits_AlMag

13 лет назад, # ^ |

-7

Yeah, very usefull) He ment the process of generating tests for hacking, i think

→ Ответить

13 лет назад, # ^ |

maybe maybe.

But I think, It's unreal to teach)

→ Ответить

DULGUUNBATMUNKH

13 лет назад, # ^ |

Tnx. I meant this. Very helpful :)

→ Ответить

RetiredLoser

13 лет назад, # |

+19

Fast System test :)

→ Ответить

unprost

13 лет назад, # ^ |

It's because problems were harder, and nothing to test :)

→ Ответить

RetiredLoser

13 лет назад, # ^ |

LOL :D .. Yeah :)

→ Ответить

13 лет назад, # |

Хорошо хоть претестами по A зацепило. надо же так лажануть

→ Ответить

-dp-	13 лет назад, # \| ← Rev. 2 → +1 Очень понравились задачки. A-D пишутся легко и изящно если чутка подумать. До Е я не добрался =( → Ответить

Artishok

13 лет назад, # ^ |

Задачи так-же понравились. Долго и безрезультатно думал над Д, затем глянул Е, но легко и изящно написать уже не успел (минут на 5 раньше-бы посмотрел) :)

→ Ответить

t.gogniashvili

13 лет назад, # |

Can anybody explain me how to solve Problem C?

→ Ответить

_jte_

13 лет назад, # ^ |

Let's find divisors of m.

We can notice, that if m / mindivisor < k - therefore u can not split any log, so Marsel wins.

Ok, let m / mindivisor be >= k.

Then, optimal strategy for both players is to split every log into mindivisor logs.

And now we can find the answer - if n is odd, the last log will be splitted by Timur, and Timur wins.

Otherwise - Marsel wins.

→ Ответить

logic_max

13 лет назад, # ^ |

"Then, optimal strategy for both players is to split every log into mindivisor logs." Can you please explain/proof this?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

If N is even Marsel win anyway because he can repeat Timur's turns.

else if Timur can split one log to mindivisors logs, He win as Second witn even N

→ Ответить

naagi

13 лет назад, # ^ |

"Then, optimal strategy for both players is to split every log into mindivisor logs."
It gives the correct result, but it's not obvious, and, I suppose, not true.

One of possible winning strategies here is symmetric strategy. If n is even, Marcel has symmetric strategy, so he wins. Otherwise, if Timur can make a turn (m / mindivisor >= k), then he splits one log, so that it parts can't be splited again, and so he gets symmetric strategy for remaining logs.

→ Ответить

logic_max

13 лет назад, # ^ |

Thanks :)

→ Ответить

amit.codename13

13 лет назад, # |

What was the main idea for C ?

→ Ответить

Hackson

13 лет назад, # ^ |

Consider the situation where N is even. Pair up the logs. Then the opponent can always copy your move for another pair, so you always lose. What if N is odd? You can deduce from the even case that it is equivalent to play on a single log with length M.

Now the rule goes as follows. When you play on a single log with length L, you always try to split it into logs with length L' ≥ K such that $\text{[math]}$ is even. By the above argument opponent always loses. If none of the allowed divisions leads your opponent into even case, try to recur on each possible splitting and see if you can win. It runs pretty fast.

Be careful to handle the case when N = K = 1.

→ Ответить

13 лет назад, # ^ |

Recursion is not necessary. (See this branch)

→ Ответить

Hackson

13 лет назад, # ^ |

Yes you are right. :-)

→ Ответить

khanhptnk

13 лет назад, # ^ |

If Timur can't move at first, then Marsel will obviously win.

Otherwise, we have two cases:

- N is even, Marsel will win by imitating Timur's actions since at that time, logs are paired up.

- N is odd, Timur simply destroys a log of length M and puts Marsel into the an even position, at which who moves second will win (it is Timur then!). You can see there is always a way to divide the log so that you can not make any move on the newly formed logs (repeatedly divide M by its divisors while this does not make M less than K).

→ Ответить

ddldyj237

13 лет назад, # |

it used Sprague-Grundy function.

→ Ответить

13 лет назад, # |

+15

Контесты от Ripatti как всегда на высоте!

→ Ответить

quangpham

13 лет назад, # |

Nice problem set! Even a little bit harder than usual :D
And I love the fast system test :x

→ Ответить

13 лет назад, # |

← Rev. 6 →

I kind of doubt if test 23 for problem A is a valid input(I can't see the whole data because of ellipsis at the last line). According to the input constraint, every line contains 100 characters at most, so I used char str[3][101]; during the contest and failed unexpectedly, but char str[3][102]; got AC.

So how to explain this?

→ Ответить

13 лет назад, # ^ |

May you say your position in standigs .

It helps to see your code

→ Ответить

13 лет назад, # ^ |

Code in Rev. 5.

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

Input
aaa
aa

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main () {
    freopen("input","r",stdin);
    char a[2][4];
    for(int j=0;j<2;++j)
        fgets(a[j], 4, stdin);
//a[0] is "aaa\0"
//a[1] is "\n\0[trash]"

//so strlen(a[1]=1)
//and your loop is uncorrect

//tested with g++
    return 0;
}

→ Ответить

13 лет назад, # ^ |

← Rev. 4 →

Update:

It turned out I didn't grasp fgets until now. Your code snippet helps, thanks.

The testcases for problem A are OK.

→ Ответить