头像

刘兆洲


访客:851

离线:6小时前


活动打卡代码 AcWing 176. 装满的油箱

刘兆洲
12小时前
// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

const int Maxn = 1005, Maxm = 2e4 + 5;
int n, m, c, s, e, q, cnt = 0, ans, p[Maxn];
int head[Maxn], ver[Maxm], nxt[Maxm], edge[Maxm];
inline void AddEdge(int u, int v, int w) {
    ver[++cnt] = v, edge[cnt] = w, nxt[cnt] = head[u], head[u] = cnt;
    ver[++cnt] = u, edge[cnt] = w, nxt[cnt] = head[v], head[v] = cnt;
}

struct state {
    int u, d, f;
    state(void) { u = d = f = 0; }
    state(int _u, int _d, int _f) : u(_u), d(_d), f(_f) {}
    inline bool operator < (const state&rhs) const { return d > rhs.d; }
};

int dis[Maxn][105]; bool vis[Maxn][105];
inline int Dijkstra(void) {
    int ret = 0x3f3f3f3f; priority_queue <state> q;
    Ms(dis, 0x3f), Ms(vis, false);
    dis[s][0] = 0; q.push(state(s, 0, 0));
    while (!q.empty()) {
        int u = q.top().u, f = q.top().f; q.pop();
        if (u == e) return dis[u][f];
        if (vis[u][f]) continue; vis[u][f] = true;
        if (f + 1 <= c && dis[u][f + 1] > dis[u][f] + p[u]) {
            dis[u][f + 1] = dis[u][f] + p[u]; q.push(state(u, dis[u][f + 1], f + 1));
        }

        for (int i = head[u]; i; i = nxt[i]) {
            if (f >= edge[i] && dis[ver[i]][f - edge[i]] > dis[u][f]) {
                dis[ver[i]][f - edge[i]] = dis[u][f];
                q.push(state(ver[i], dis[ver[i]][f - edge[i]], f - edge[i]));
            }
        }
    } for (int i = 0; i <= c; i++) chkmin(ret, dis[e][i]); return ret;
}

signed main(void) {
//  file("");
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(p[i]);
    for (int i = 1, u, v, w; i <= m; i++)
        read(u), read(v), read(w), AddEdge(u + 1, v + 1, w);
    for (read(q); q; q--) {
        read(c), read(s), read(e); ++s, ++e; ans = Dijkstra();
        if (ans == 0x3f3f3f3f) puts("impossible"); else writeln(ans);
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/





活动打卡代码 AcWing 339. 圆形数字

刘兆洲
13小时前
// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

ll f[35][35][2]; 
inline void prework(void) {
    f[1][1][1] = f[1][0][0] = 1ll;
    for (int i = 2; i <= 31; i++)
    for (int j = 0; j <= i; j++) {
        if (j < i) f[i][j][0] = f[i - 1][j][1] + f[i - 1][j][0];
        if (j) f[i][j][1] = f[i - 1][j - 1][0] + f[i - 1][j - 1][1];
    }
}

int a, b, n, num[35];
inline ll solve(int x) {
    n = 0; ll ret = 0ll; int cnt0 = 0, cnt1 = 1;
    for (; x; x >>= 1) num[++n] = x & 1;

    for (int i = n - 1; i >= 1; i--)
    for (int j = 0; j <= i >> 1; j++) ret += f[i][j][1];

    for (int i = n - 1; i >= 1; i--) if (num[i]) {
        for (int j = 0; j <= i; j++)
            if (cnt1 + j <= cnt0 + i - j) ret += f[i][j][0]; ++cnt1;
    } else ++cnt0; return ret;
}

signed main(void) {
//  file("");
    prework(); read(a), read(b);
    writeln(solve(b + 1) - solve(a));
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/





活动打卡代码 AcWing 338. 计数问题

// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

int ret[2][10], f[20][10][10], p10[20], num[20], n;
inline void prework(void) { p10[0] = 1;
    for (int i = 1; i <= 9; i++) p10[i] = p10[i - 1] * 10;

    for (int i = 1; i <= 9; i++)
    for (int j = 0; j <= 9; j++) {
        for (int k = 0; k <= 9; k++)
        for (int p = 0; p <= 9; p++)
            f[i][j][p] += f[i - 1][k][p];
        f[i][j][j] += p10[i - 1];
    }
}

inline void solve(int x, int *ans) {
    n = 0; do { num[++n] = x % 10; x /= 10; } while(x);

    for (int i = 1; i < n; i++)
    for (int j = 1; j <= 9; j++)
    for (int k = 0; k <= 9; k++) ans[k] += f[i][j][k];

    for (int i = 1; i < num[n]; i++)
    for (int k = 0; k <= 9; k++) ans[k] += f[n][i][k];

    for (int i = n - 1; i >= 1; i--) {
        for (int j = 0; j < num[i]; j++)
        for (int k = 0; k <= 9; k++) ans[k] += f[i][j][k];
        for (int j = n; j > i; j--) ans[num[j]] += num[i] * p10[i - 1];
    }
} int l, r;

signed main(void) {
//  file("");
    prework();
    while (~scanf("%d%d", &l, &r)) { Ms(ret, 0);
        if (!l && !r) break; if (l > r) swap(l, r);
        solve(l, ret[0]); solve(r + 1, ret[1]);
        for (int i = 0; i <= 9; i++) writeln(ret[1][i] - ret[0][i], i == 9 ? '\n' : ' ');
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/





活动打卡代码 AcWing 311. 月之谜

// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

int n, p, num[20]; ll f[20][180][180];
inline ll dp(int len, int sum, bool lim, int mod) {
    if (len == 0) return sum == p && mod == 0 ? 1 : 0;
    if (!lim && f[len][sum][mod] != -1) return f[len][sum][mod];
    int up = lim ? num[len] : 9; ll ret = 0ll;
    for (int i = 0; i <= up; i++) ret += dp(len - 1, sum + i, lim && i == num[len], (mod * 10 + i) % p);
    return lim ? ret : f[len][sum][mod] = ret;
}

inline ll solve(ll x) {
    n = 0; ll ret = 0ll;
    while (x) { num[++n] = x % 10; x /= 10; }
    for (p = 1; p <= 165; p++) Ms(f, -1), ret += dp(n, 0, true, 0);
    return ret;
} ll a, b;

signed main(void) {
//  file("");
    read(a), read(b);
    writeln(solve(b) - solve(a - 1));
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/





活动打卡代码 AcWing 310. 启示录

// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

ll f[25][5]; int T, n, m;
inline void prework(void) {
    f[0][0] = 1;
    for (int i = 0; i <= 20; i++) {
        for (int j = 0; j < 3; j++) {
            f[i + 1][j + 1] += f[i][j];
            f[i + 1][0] += f[i][j] * 9;
        } f[i + 1][3] += f[i][3] * 10;
    }
}

signed main(void) {
//  file("");
    prework();
    for (read(T); T; T--) { read(n);
        for (m = 3; f[m][3] < n; m++);
        for (int i = m, k = 0; i; i--) {
            for (int j = 0; j <= 9; j++) {
                ll cnt = f[i - 1][3];
                if (j == 6 || k == 3)
                    for (int l = max(3 - k - (j == 6), 0); l < 3; l++) cnt += f[i - 1][l];
                if (cnt < n) n -= cnt;
                else {
                    if (k < 3) k = j == 6 ? k + 1 : 0;
                    putchar(j + 48); break;
                }
            }
        } puts("");
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/





活动打卡代码 AcWing 351. 树网的核

// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

const int Maxn = 5e5 + 5, Maxm = 1e6 + 5;
int n, s, cnt = 0, head[Maxn], nxt[Maxm], ver[Maxm], edge[Maxm];
inline void AddEdge(int u, int v, int w) {
    ver[++cnt] = v, edge[cnt] = w, nxt[cnt] = head[u], head[u] = cnt;
    ver[++cnt] = u, edge[cnt] = w, nxt[cnt] = head[v], head[v] = cnt;
} bool vis[Maxn]; int dis[Maxn], fat[Maxn], l1 = 1, l2 = 1;

inline void dfs(int u) {
    for (int i = head[u]; i; i = nxt[i]) {
        if (vis[ver[i]] || ver[i] == fat[u]) continue;
        fat[ver[i]] = u; dis[ver[i]] = dis[u] + edge[i];
        dfs(ver[i]);
    }
}

signed main(void) {
//  file("");
    read(n), read(s);
    for (int i = 1, u, v, w; i < n; i++)
        read(u), read(v), read(w), AddEdge(u, v, w);
    dfs(l1); for (int i = 1; i <= n; i++) if (dis[i] > dis[l1]) l1 = i;
    Ms(fat, 0); Ms(dis, 0); dfs(l1); l2 = 1;
    for (int i = 1; i <= n; i++) if (dis[i] > dis[l2]) l2 = i;
    int ret = 0x3f3f3f3f, j = l2;
    for (int i = l2; i; i = fat[i]) {
        while (fat[j] && dis[i] - dis[fat[j]] <= s) j = fat[j];
        chkmin(ret, max(dis[j], dis[l2] - dis[i]));
    } for (int i = l2; i; i = fat[i]) vis[i] = true;
    for (int i = l2; i; i = fat[i]) dis[i] = 0, dfs(i);
    for (int i = 1; i <= n; i++) chkmax(ret, dis[i]); writeln(ret);
    //  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/





活动打卡代码 AcWing 283. 多边形

// luogu-judger-enable-o2
//Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    template <class T>
    inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) {while (isspace(x = gc()));}

    template <class T>
    inline void write(T x)
    {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) {write(x); puts("");}
    template <class T> inline void writeln(T x, char c) {write(x); putchar(c);}
    template <class T> inline void writeln(char c, T x) {putchar(c); write(x);}

    template <class T> inline void chkmax(T &x, const T y) {x > y ? x = x : x = y;}
    template <class T> inline void chkmin(T &x, const T y) {x < y ? x = x : x = y;}
    template <class T> inline T min(const T&x, const T&y, const T&z) {
        return x < y ? (x < z ? x : z) : (y < z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }
}

using namespace Base;

enum {
    Maxn = 105
};

const int Inf = 1 << 30;

int n, tot = 0, ans = -(1 << 15);
int num[Maxn >> 1], dp[Maxn][Maxn][2];
char opt[Maxn];

inline void Polygon_Dp(void) {
    for (register int len = 2; len <= n; len++)
        for (int l = 1, r; l <= 2 * n - len + 1; l++) {
            r = l + len - 1;
            for (register int k = l; k < r; k++)
                if (opt[k + 1] == 't') {
                    chkmax(dp[l][r][0], dp[l][k][0] + dp[k+1][r][0]);
                    chkmin(dp[l][r][1], dp[l][k][1] + dp[k+1][r][1]);
                } else {
                    chkmax(dp[l][r][0], max(dp[l][k][0] * dp[k+1][r][0], dp[l][k][1] * dp[k+1][r][1]));
                    chkmin(dp[l][r][1], min(dp[l][k][1] * dp[k+1][r][1], dp[l][k][1] * dp[k+1][r][0], dp[l][k][0] * dp[k+1][r][1]));
                }
        }
}

signed main(void) {
    read(n);
    for (int i = 1; i <= n; i++)
        readch(opt[i]), read(num[i]);

    for (int i = 1; i <= n << 1; i++)
        for (int j = i; j <= n << 1; j++)
            dp[i][j][0] = -Inf, dp[i][j][1] = Inf;

    for (int i = 1; i <= n; i++) {
        dp[i][i][0] = num[i];
        dp[i][i][1] = num[i];
        dp[i + n][i + n][0] = num[i];
        dp[i + n][i + n][1] = num[i];
        opt[i + n] = opt[i];
    }

    Polygon_Dp();

    for (int i = 1; i <= n + 1; i++)
        chkmax(ans, dp[i][i + n - 1][0]);
    writeln(ans);

    for (int i = 1; i <= n; i++)
        if (dp[i][i + n - 1][0] == ans) writeln(i, ' ');

    return 0;
}

/**/




活动打卡代码 AcWing 284. 金字塔

// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

const int mod = 1e9;
char str[305]; int f[305][305];
inline int solve(int l, int r) {
    if (l > r) return 0;
    if (l == r) return 1;
    if (f[l][r] != -1) return f[l][r];
    f[l][r] = 0; if (str[l] == str[r]) {
        for (int k = l + 2; k <= r; k++) {
            f[l][r] = (f[l][r] + 1ll * solve(l + 1, k - 1) * solve(k, r) % mod) % mod;
        }
    } return f[l][r];
}

signed main(void) {
//  file("");
    readstr(str + 1); Ms(f, -1);
    writeln(solve(1, strlen(str + 1)));
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/





活动打卡代码 AcWing 274. 移动服务

// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

const int Maxn = 205, Maxm = 1005;
int n, m, c[Maxn][Maxn], p[Maxm];
int f[Maxm][Maxn][Maxn];

signed main(void) {
//  file("");
    read(n), read(m); Ms(f, 0x3f);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) read(c[i][j]);
    for (int i = 1; i <= m; i++) read(p[i]);

    f[1][3][2] = f[1][2][3] = c[1][p[1]];
    f[1][2][1] = f[1][1][2] = c[3][p[1]];
    f[1][3][1] = f[1][1][3] = c[2][p[1]];

    for (int i = 1; i < m; i++)
    for (int x = 1; x <= n; x++)
    for (int y = 1; y <= n; y++) {
        if (x == y || x == p[i] || y == p[i]) continue;
        chkmin(f[i + 1][x][y], f[i][x][y] + c[p[i]][p[i + 1]]);
        chkmin(f[i + 1][p[i]][y], f[i][x][y] + c[x][p[i + 1]]);
        chkmin(f[i + 1][x][p[i]], f[i][x][y] + c[y][p[i + 1]]);
    } int ret = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        if (i == j || i == p[m] || j == p[m]) continue;
        chkmin(ret, f[m][i][j]);    
    }
    writeln(ret);
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/






// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
    inline char gc(void)
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }

    #define gc() getchar()

    template <class T> inline void read(T &x)
    {
        T flag = (T) 1; x = 0; static char ch = gc();
        for (; ch > '9' || ch < '0'; ch = gc())
            flag = ch == '-' ? -1 : 1;
        for (; ch >= '0' && ch <= '9'; ch = gc())
            x = (x << 1) + (x << 3) + (ch & 15);
        x *= flag; return;
    }

    inline void readstr(string&x) {
        x = ""; static char ch;
        while (isspace(ch = gc()));
        while (x += ch, !isspace(ch = gc()));
    }

    inline void readstr(char *s) {
        do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
        do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
        *s = 0; return;
    }

    inline void printstr(string x, int num = 0, char ch = '\n') {
        for (int i = num; i < x.size(); ++i)
            putchar(x[i]); putchar(ch);
    }

    inline void readch(char&x) { while (isspace(x = gc())); }

    char pf[100000], *o1 = pf, *o2 = pf + 100000;
    #define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
    template <class T>
    inline void println(T x, char c = '\n') {
        if (x < 0) ot(45), x = -x;
        static char s[15], *b; b = s;
        if (!x) *b ++= 48;
        for (; x; * b ++= x % 10 + 48, x /= 10);
        for (; b-- != s; ot(*b)); ot(c);
    }

    template <class T> inline void write(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); return;
    }

    template <class T> inline void writeln(T x) { write(x); puts(""); }
    template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
    template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

    template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
    template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
    template <class T> inline T max(const T&x, const T&y, const T&z) {
        return x > y ? (x > z ? x : z) : (y > z ? y : z);
    }

    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;

    #define Ms(arr, opt) memset(arr, opt, sizeof(arr))
    #define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
    #define Mp(x, y) make_pair(x, y)

    inline void file(string str) {
        freopen((str + ".in").c_str(), "r", stdin);
        freopen((str + ".out").c_str(), "w", stdout);
    }

    struct Vector {
        double x, y;
        Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

        inline Vector Vary(void) { return Vector(x, -y); }

        inline bool operator < (const Vector&rhs)
        const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
        inline Vector operator - (const Vector&rhs)
        const { return Vector(x - rhs.x, y - rhs.y); }
        inline Vector operator + (const Vector&rhs)
        const { return Vector(x + rhs.x, y + rhs.y); }

        inline Vector operator * (const double&rhs)
        const { return Vector(x * rhs, y * rhs); }
        inline Vector operator / (const double&rhs)
        const { return Vector(x / rhs, y / rhs); }

        inline Vector operator * (const Vector&rhs)
        const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    }; typedef Vector Complex;
}

using namespace Base;

inline void dread(double &x) {
    double flg = 1, pot = 0.1; x = 0; static char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') flg = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
    if (ch == '.') { ch = getchar();
        for (; isdigit(ch); ch = getchar()) x = x + (double)(ch ^ 48) * pot, pot *= 0.1; 
    } x *= flg;
}

const int Maxn = 15;
int n; double a[Maxn][Maxn];

inline void Gauss(double A[Maxn][Maxn]) {
    for (int i = 1, r = 1; i <= n; r = ++i) {
        for (int j = i + 1; j <= n; j++)
            if (fabs(A[j][i]) > fabs(A[r][i])) r = j;
        if (r != i) for (int j = 1; j <= n + 1; j++) swap(A[r][j], A[i][j]);
        if (!A[i][i]) return;
        for (int j = n + 1; j >= 1; j--)
            for (int k = i + 1; k <= n; k++) A[k][j] -= A[k][i] / A[i][i] * A[i][j];
    }

    for (int i = n; i >= 1; i--) {
        for (int j = i + 1; j <= n; j++) A[i][n + 1] -= A[j][n + 1] * A[i][j];
        A[i][n + 1] /= A[i][i];
    }
}

signed main(void) {
//  file("");
    read(n); ++n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < n; j++)
            dread(a[i][j]), a[i][n + 1] -= a[i][j] * a[i][j], a[i][j] *= -2.0;
        a[i][n] = 1;
    } Gauss(a);

    for (int i = 1; i < n; i++) printf("%.3lf", a[i][n + 1]), putchar(i < n - 1 ? ' ' : '\n');
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}

/**/