우 객 망 여름 ACM 다 교 훈련소 (7 회) E. Counting 4 - Cliques (구조)

제목 링크
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 262144 K, 기타 언어 524288 K Special Judge, 64bit IO Format:% lld
제목 설명
You love doing graph theory problems. You've recently stumbled upon a classical problem : Count the number of 4-cliques in an undirected graph. Given an undirected simple graph G, a 4-clique of G is a set of 4 nodes such that all pairs of nodes in this set are directly connected by an edge. This task would be too easy for you, wouldn't it? Thus, your task here is to find an undirected simple graph G with exactly k 4-cliques. Can you solve this task?
 
입력 설명:

The first line of input contains a single integer k (1 ≤ k ≤ 106).

출력 설명:

On the first line, output two space-separated integers, n, m (1 ≤ n ≤ 75, 1 ≤ m ≤ n * (n - 1) / 2). On the next m lines, output two space-separated integers denoting an edge of the graph u, v (1 ≤ u, v ≤ n), where u and v are the endpoints of the edge.

Your graph must not contain any self-loops or multiple edges between the same pair of nodes. Any graph that has exactly k 4-cliques and satisfies the constraints will be accepted. It can be proven that a solution always exist under the given constraints.

 
예시 1
입력

1

출력

4 6
1 2
1 3
1 4
2 3
2 4
4 3

설명 하 다.

In the sample, the whole graph is a 4-clique.

 
제목: 하나의 K (1 ~ 1e6) 를 제시 하고 하나의 그림 G 를 구성 하여 조건 을 만족 시 켜 야 한다. 75 개 점 이내 에 무 거 운 변 이 존재 하지 않 고 마침 K 개 (4 시 완전 그림) 가 존재 한다.
        이 그림 G 를 출력 해 야 합 니 다. 형식 은 N, M (N 개 점, M 개 변) 이 고 그 다음 에 M 행동 u, v 입 니 다.
문제 풀이: 분명 한 것 은 구조 문제 이다. 먼저 이 문 제 를 보면 C (n, 4) 를 먼저 폭력 적 으로 뛴다. 이것 은 n 개의 점 의 전체 그림 에 4 개의 완전 그림 이 존재 하 는 수량 이기 때문에 문 제 를 관찰 한 결과 데이터 카드 가 매우 꽉 끼 는 것 을 발견 했다. n > = 72 시 C (n, 4) 가 1e6 보다 많 기 때문이다. 처음에 제 방법 은 K 이내 의 최대 T 개의 전체 그림 을 먼저 얻 은 다음 에 나머지 수량 은 K - C (T, 4) 였 습 니 다.또 하 나 는 한 점 에 전체 그림 을 추가 할 때 답 K 에 대한 공헌 은 C (x, 3) 이 고 여기 의 x 는 이 점 과 전체 그림 에 임 의적 으로 연 결 된 수량 입 니 다. Tmax = 71, 나 는 최소 남 은 4 개의 점 을 취하 여 T 개의 점 의 전체 그림 에 넣 어서 K 를 만 들 수 있 을 지 추측 했다. 평가 희 와 가방 은 모두 나의 결론 이 틀 렸 다 는 것 을 증명 했다. 그러면 나 는 5 개의 점 을 강제로 찾 을 수 밖 에 없 었 다 (즉, T 의 최대 치 는 70 으로 변 했다). 그래서 1e6 이내 의 모든 K 를 만 들 수 있 었 다. (가방 을 사용 할 수 있다 는 것 을 증명 했다)
         그러나 5 개 점 이 남 은 상황 에 대해 서 는 한 점 을 미리 처리 해 야 합 니 다. 그렇지 않 으 면 70 ^ 5 시간 복잡 도 에서 폭발 할 수 있 습 니 다.
코드 는 다음 과 같 습 니 다:

#include
#include
#include
#include
#include
#include
#include
#include