Guest User

Untitled

a guest
Mar 24th, 2014
269
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/rope>
  3. #define clr(x) memset((x), 0, sizeof(x))
  4. #define all(x) (x).begin(), (x).end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
  8. #define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
  9. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  10. #define ford(i, n) for(int i=(n)-1; i>=0; i--)
  11. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  12. #define in(x) int (x); input((x));
  13. #define x first
  14. #define y second
  15. #define less(a,b) ((a) < (b) - EPS)
  16. #define more(a,b) ((a) > (b) + EPS)
  17. #define eq(a,b) (fabs((a) - (b)) < EPS)
  18. #define remax(a, b) ((a) = (b) > (a) ? (b) : (a))
  19. #define remin(a, b) ((a) = (b) < (a) ? (b) : (a))
  20. using namespace std;
  21. template <typename T>
  22. T gcd(T a, T b)
  23. {
  24.     while (b > 0)
  25.     {
  26.         a %= b;
  27.         swap(a, b);
  28.     }
  29.     return a;
  30. }
  31. typedef long double ld; template <class _T> inline _T sqr(const _T& x) {return x * x;} template <class _T> inline string tostr(const _T& a) {ostringstream os(""); os << a; return os.str();} const ld PI = 3.1415926535897932384626433832795L; const double EPS = 1e-9; char TEMPORARY_CHAR; typedef long long ll; typedef unsigned long long ull; typedef set < int > SI; typedef vector < int > VI; typedef vector < vector < int > > VVI; typedef map < string, int > MSI; typedef pair < int, int > PII; const int INF = 1e9; inline void input(int &a) {a = 0; while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') && (TEMPORARY_CHAR != '-')){} char neg = 0; if (TEMPORARY_CHAR == '-') {neg = 1; TEMPORARY_CHAR = getchar();} while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {a = 10 * a + TEMPORARY_CHAR - '0'; TEMPORARY_CHAR = getchar();} if (neg) a = -a;} inline void out(int a) {if (!a) putchar('0'); if (a < 0) {putchar('-'); a = -a;} char s[10]; int i; for(i = 0; a; ++i) {s[i] = '0' + a % 10; a /= 10;} ford(j, i) putchar(s[j]);} inline int nxt() {in(ret); return ret;}
  32.  
  33. vector <int> a;
  34.  
  35. vector <vector <int> > ans;
  36.  
  37. int n;
  38.  
  39. void rec3(int s) {
  40.     if (s == n) {
  41.         if (a.size() < best)
  42.             ans.clear();
  43.         if (a.size() <= best) {
  44.             ans.push_back(a);
  45.             best = min(best, (int)a.size());
  46.         }
  47.         return;
  48.     }
  49.     if (3 * s + 1 <= n) {
  50.         a.push_back(2 * s + 1);
  51.         rec3(3 * s + 1);
  52.         a.pop_back();
  53.     }
  54.     if (s + a.back() <= n) {
  55.         a.push_back(a.back());
  56.         rec3(s + a.back());
  57.         a.pop_back();
  58.     }
  59. }
  60.  
  61. int main()
  62. {
  63.     ios_base::sync_with_stdio(false);
  64.     a.push_back(1);
  65.     cin >> n;
  66.  
  67.     rec3(1);
  68.     cout << ans.size() << " " << ans[0].size() << endl;
  69.     sort(all(ans));
  70.     for (int i = 0; i < ans.size(); ++i) {
  71.         for (int v : ans[i]) {
  72.             cout << v << " ";
  73.         }
  74.         cout << endl;
  75.     }
  76.  
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment