[Daily] 20200813

文書ディレクトリ

C題[Codeforces 125C] Hobbits' Party

C題[Codeforces 125C] Hobbits’ Party
タイトルリンク
考え方:2つの要求があります:1人は最大2日招待されて、任意の2日はきっと同じ人が招待されます.だから最良の案はきっと任意の2日間招待された人の中で、一人だけが同じだ.すなわち、任意の2日間に1人を消費し、k日間にk*(k-1)/2人を消費すると、最大日数kはn>=k*(k-1)/2を満たす最大のkであるべきである.kが得られた後,任意の2日間で1人を消費する過程をk 2列挙し,結果シーケンスを得た.

//AC  
#include
using namespace std;
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int n,k,cnt;
vector<int>ans[1000];
int main(){
	cin>>n;
	for(int i=2;i<=n;i++)
		if(n>=i*(i-1)/2)k=i;else break;
	cout<<k<<endl;
	for(int i=1;i<=k;i++)
		for(int j=i+1;j<=k;j++){
			ans[i].push_back(++cnt);
			ans[j].push_back(cnt);
		}
	for(int i=1;i<=k;i++){
		for(auto j:ans[i])printf("%d ",j);
		puts("");
	}
}