fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int d;
  9.     long long k;
  10.     if (!(cin >> d >> k)) return 0;
  11.  
  12.     vector<pair<int,int>> edges;
  13.     int nxt = 1; // số thứ tự đỉnh tiếp theo (bắt đầu từ 1)
  14.  
  15.     auto add_edge = [&](int u, int v){
  16.         if (u > v) swap(u,v);
  17.         edges.emplace_back(u,v);
  18.     };
  19.  
  20.     if (d == 2) {
  21.         // Dùng star gadget: center nối t lá => tạo t*(t-1)/2 cặp có khoảng cách 2
  22.         long long rem = k;
  23.         while (rem > 0) {
  24.             // tìm t tối đa sao cho t*(t-1)/2 <= rem
  25.             int t = 1;
  26.             int lo = 1, hi = 1000;
  27.             while (lo <= hi) {
  28.                 int mid = (lo + hi) / 2;
  29.                 long long val = 1LL * mid * (mid - 1) / 2;
  30.                 if (val <= rem) { t = mid; lo = mid + 1; }
  31.                 else hi = mid - 1;
  32.             }
  33.             // tạo center
  34.             int center = nxt++;
  35.             // tạo t lá và nối
  36.             for (int i = 0; i < t; ++i) {
  37.                 int leaf = nxt++;
  38.                 add_edge(center, leaf);
  39.             }
  40.             rem -= 1LL * t * (t - 1) / 2;
  41.         }
  42.     } else {
  43.         // d >= 3
  44.         long long rem = k;
  45.         while (rem > 0) {
  46.             // lấy t lớn nhất sao cho t*t <= rem
  47.             int t = (int)floor(sqrt((double)rem));
  48.             if (t == 0) t = 1; // vẫn cần xử lý phần dư nhỏ
  49.             // tạo gadget: một đường (path) có độ dài (d-2) (tức d-1 đỉnh),
  50.             // rồi thêm t lá ở 2 đầu => tạo t * t cặp có khoảng cách d
  51.             // path nodes:
  52.             vector<int> path;
  53.             for (int i = 0; i < d - 1; ++i) {
  54.                 path.push_back(nxt++);
  55.             }
  56.             // nối path
  57.             for (int i = 0; i + 1 < (int)path.size(); ++i) {
  58.                 add_edge(path[i], path[i+1]);
  59.             }
  60.             int left = path.front();
  61.             int right = path.back();
  62.             // thêm t lá bên trái
  63.             for (int i = 0; i < t; ++i) {
  64.                 int u = nxt++;
  65.                 add_edge(left, u);
  66.             }
  67.             // thêm t lá bên phải
  68.             for (int i = 0; i < t; ++i) {
  69.                 int u = nxt++;
  70.                 add_edge(right, u);
  71.             }
  72.             rem -= 1LL * t * t;
  73.         }
  74.     }
  75.  
  76.     int n = nxt - 1;
  77.     int m = (int)edges.size();
  78.  
  79.     // In kết quả
  80.     cout << n << " " << m << "\n";
  81.     for (auto &e : edges) {
  82.         cout << e.first << " " << e.second << "\n";
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 4
stdout
copy 
7 6
1 2
2 3
1 4
1 5
3 6
3 7
https://ideone.com/51v3pr
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!