codeforces GYM 101431D(構造)

Problem D. Vera and Dogs

構造

GYM

題目連結

題目大意

有N個房子和N*X隻狗。每個房子可以成為X隻狗的第一選擇和另外X隻狗的第二選擇。每隻小狗都隻有一個第一選擇和一個第二選擇。小狗優先選擇第一選擇的房子，如果房子滿了，就選擇第二選擇。每個房子隻能容納X+1隻小狗。每天晚上都會有一間房子不能使用。問，怎麼配置設定小狗的第一選擇和第二選擇，使得無論哪間房子不能使用，都能保證所有小狗都有房間選擇(輸出任意一組解)。無解輸出

-1

資料範圍： 1≤N,X≤2017 X∗N≤2017

解答

如果 X≥N 則無解。

否則，對于第i個房子，可以讓其成為X隻狗的第一選擇，然後這X隻狗的第二選擇分别選擇編号為 i+1 , i+2 , … , i+X 房子即可(編号大于N的減N)。這樣正好就可以配置設定完。

AC代碼