読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

RCC 2014 Warmup - Div1 A. Football

Codeforces

Codeforcesで開催されたRCC Warmupに参加。
ABCを解いたもののBは計算量の見積もりが甘すぎてミス。
辛うじてCが解けたことでレート改善。
http://codeforces.com/contest/418/problem/A

問題

チーム数Nと勝利数Kが与えられる。
Nチーム数で互いに試合を行う。同じチームのペアは最大1回しか試合できない。
チームK回以上勝利できるような試合結果がありうるなら、それを生成せよ。

解法

Nチームなら各チームは(N-1)回試合を行う。
よって(N-1)/2回までなら勝利できる。

Nチームを順に円形に並べて、それぞれ右側Kチームに勝利するような試合結果を生成すればよい。

int N,K;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	if(2*K+1>N) return _P("-1\n");
	_P("%d\n",N*K);
	FOR(i,N) {
		FOR(y,K) _P("%d %d\n",i+1,(i+1+y)%N+1);
	}
}

解法

これはこれで解けたからいいんだけど、各チーム同じ回数試合をしないといけないと勘違いしてHack失敗したのは反省。

広告を非表示にする