MarioYC's blog

By MarioYC, 13 years ago, In English
Hi, I found this contest http://judge.mipt.ru/cgi-bin/new-client?contest_id=201112 announced in the russian interface, however I'm having troubles understanding some statements. I would appreciate if someone could help me understand them.

-------

Problem count-Считалочка

Считалочка

Time limit = 1

Игра "Считалочка" заключается в следующем. N человек (мы пронумеруем их числами 1, 2, ... N) встают в круг и начинают считать с первого по кругу. Каждый M-ый выходит из круга. Один человек, который останется, считается победителем. Если N = 6, а M = 5, то будут выходить 5, 4, 6, 2, 3 и останется игрок с номером 1.

У нас N человек разбиты на две команды по K человек. Первые K принадлежат первой команде, следующие K — второй команде. Вам нужно найти такое минимальное M, что в игре "Считалочка" сначала выйдут все игроки второй команды, прежде, чем какой-либо игрок первой команды

I understand in the second paragraph that N = 2K, but I don't understand what is the condition these two groups of K people must fulfill when I choose M.

-------

Problem graph-game

Алиса и Боб играют в игру со следующими правилами. В начале есть граф без ребер на N вершинах. Каждым ходом игроки соединяют ребром две вершины, которые до сих не были соединены (т.е. кратных ребер не бывает). Игрок, после чьего хода граф становится связным проигрывает. Первым ходит Боб.

Here I don't understand if we can connect two vertices only when they are not on the same connected component or when there is not an edge between them.
-------
  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Second problem: we can connect two vertices only when there is no edge between them.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
First problem: find minimum M such that every player of the second team (which consists of players with indices K + 1 to N) is eliminated before any player of the first team (which consists of players with indices 1 to K).