fork(2) download
  1. #include <set>
  2. #include <map>
  3. #include <list>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <complex>
  15. #include <iostream>
  16. #include <algorithm>
  17.  
  18. #include <ctime>
  19. #include <deque>
  20. #include <bitset>
  21. #include <cctype>
  22. #include <utility>
  23. #include <cassert>
  24. using namespace std;
  25.  
  26. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  27. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  28. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  29. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  30. #define SZ(S) ((int) ((S).size()))
  31.  
  32. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  33. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  34. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  35.  
  36. void addEdges(vector< pair<int,int> > &res, int need, int nLeaf) {
  37. int add = 0;
  38. FOR(i,1,nLeaf) FOR(j,i+1,nLeaf) {
  39. if (add >= need) return ;
  40.  
  41. ++add;
  42. res.push_back(make_pair(i, j));
  43. }
  44. }
  45.  
  46. int main() {
  47. ios :: sync_with_stdio(false); cin.tie(NULL);
  48. cout << (fixed) << setprecision(6);
  49. int s;
  50. while (cin >> s) {
  51. if (s == 0) {
  52. cout << 1 << ' ' << 0 << endl;
  53. }
  54. else if (s == 2 || s == 5) {
  55. cout << "Impossible" << endl;
  56. continue;
  57. }
  58. else {
  59. int nLeaf = 1;
  60. while (nLeaf * nLeaf < s) ++nLeaf;
  61.  
  62. int n = nLeaf + 1;
  63. vector< pair<int,int> > res;
  64. FOR(i,1,nLeaf) res.push_back(make_pair(n, i));
  65.  
  66. int m = nLeaf * nLeaf;
  67. int need = m - s;
  68. addEdges(res, need, nLeaf);
  69.  
  70. cout << n << ' ' << res.size() << endl;
  71. REP(i,res.size()) cout << res[i].first << ' ' << res[i].second << endl;
  72. }
  73. }
  74. return 0;
  75. }
  76.  
  77.  
Success #stdin #stdout 0s 3436KB
stdin
6
stdout
4 6
4 1
4 2
4 3
1 2
1 3
2 3