Разбор задач КРОК 2016 — Квалификация

Правка ru1, от fcspartakm, 2016-04-18 18:40:56

644A - Parliament of Berland

Из условия задачи следует, что либо демократов и республиканцев поровну (если n чётно), либо демократов на одного больше (если n нечётно). Так как представители одной и той же партии не должны сидеть на соседних креслах, представим парламентский зал в виде шахматной доски, где левая верхняя клетка будет белой. Затем начнем перебирать ряды клеток сверху вниз, а клетки в каждом ряду слева направо и будем по очереди сажать парламентариев — демократов в белые клетки, а республиканцев в черные.

Таким образом, если n > a·b, ответом будет  - 1. В противном случае рассадка всегда найдется.

Для определения того, какого цвета клетка (и, соответственно, кого нужно в нее посадить), находящаяся в i-й строке и j-м столбце (в случае, если они нумеруются с единицы), можно поступить следующим образом. Если (i + j)mod2 = 0, значит соответствующая клетка должна быть белой, иначе чёрной.

Пример решения
Теги крок-2016, квалификация, разбор

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru7 Русский fcspartakm 2016-04-18 18:47:32 24 Мелкая правка: 'Лучше позд' -> '### Your title here...Лучше позд' (опубликовано)
ru6 Русский fcspartakm 2016-04-18 18:47:12 28 Мелкая правка: '----------### [probl' -> '----------\n### [probl'
ru5 Русский fcspartakm 2016-04-18 18:47:05 1010
ru4 Русский fcspartakm 2016-04-18 18:44:20 1626
ru3 Русский fcspartakm 2016-04-18 18:42:43 23 Мелкая правка: 'и $(i + j)~mod,2016-04-18~2 = 0$, зн' -> 'и $(i + j) mod 2 = 0$, зн'
ru2 Русский fcspartakm 2016-04-18 18:41:12 23 Мелкая правка: 'и $(i + j) mod 2 = 0$, зн' -> 'и $(i + j)~mod~2 = 0$, зн'
ru1 Русский fcspartakm 2016-04-18 18:40:56 1437 Первая редакция (сохранено в черновиках)