2012年10月14日 星期日

Codeforces 232C Cycles

這題非常的有趣

是一個我從來都沒有碰過,但卻是非常經典的貪婪題

貪婪作法如下:

創造出一個一個點,將剛創造出的點跟已創造出的點連線,

連越多越好,且若連N條線,依照這樣做出的cycle會剛好有N*(N-1)/2個


//By momo
#include<cstdio>
#include<algorithm>
#define N 110
using namespace std;

int n = 1, k, tbl[N][N];

int main(){
    scanf("%d", &k);
    while(k > 0){
        int m;
        for(m = n; m*(m-1)/2 > k; m--);
        for(int i = 0; i < m; i++) tbl[n][i] = tbl[i][n] = 1;
        k -= m*(m-1)/2;
        n++;
    }
    printf("%d\n", n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            printf("%d", tbl[i][j]);
        }
        puts("");
    }
}

沒有留言:

張貼留言