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

Revision ru2, by fcspartakm, 2016-04-18 18:41:12

644A - Parliament of Berland

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

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

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

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

History

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