transaction transaction transaction

transaction transaction transaction

【2017 ACM/ICPC Asia Regional Shenyang Online】

【DP问题】

Solution:

对于这个问题,首先可以想到一个暴力办法,即把每一种出发点到每一种结束点的可能性都枚举一遍,找到最优解,显然,这种办法虽然可以求出解,但是会超时,因此我们采用dp的办法来解决。我们建立一个二维dp数组,dp[i][0]表示从某个城市购买书籍并运送到这里的最少花费,存储为负值;dp[i][1]表示从某个城市送货到当前城市所能得到的最大收益。显然,dp[i][0] + dp[i][1]表示从某个城市出发经由城市i买到另外一所城市的最大收益,本题的最优解也就在这些值中产生。

#include <iostream>
#include <vector>

using namespace std;

struct node {
    int to, weight;
};

const int NIL = -1;
const int LIM = 1e5 + 10;

int val[LIM], n;
vector<node> edges[LIM];
int dp[LIM][2], ans = 0;

inline int maxi(int a, int b) {
    return a > b ? a : b;
}

void init() {
    ans = 0;
    for (int i = 1; i <= n; i++) {
        edges[i].clear();
    }
}

void dfs(int crt, int from) {
    dp[crt][0] = -val[crt];
    dp[crt][1] = val[crt];
    for (vector<node>::iterator ite = edges[crt].begin(); ite != edges[crt].end(); ite++) {
        int to = ite->to;
        if (to == from) continue;
        dfs(to, crt);
        dp[crt][0] = maxi(dp[crt][0], dp[to][0] - ite->weight);
        dp[crt][1] = maxi(dp[crt][1], dp[to][1] - ite->weight);
    }
    ans = maxi(ans, dp[crt][0] + dp[crt][1]);
}

int main(void) {
    int t, from, to, w;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++)
            scanf("%d", val + i);
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &from, &to, &w);
            edges[from].push_back({to, w});
            edges[to].push_back({from, w});
        }
        dfs(1, NIL);
        printf("%d\n", ans);
    }
    return 0;
}

 

card card card

【2017 ACM/ICPC Asia Regional Shenyang Online】card card card

【循环置尾问题】

Solution:

这道题的关键在于时间消耗,由于循环放到末尾,所以不妨在读取时便复制一份,开一个二倍的数组,而节省时间的关键在于:不要针对每一个为起点进行一次判断,而是直接从这个二倍数组从头到尾遍历一次,每遇到一次penalty为负数导致游戏结束的情况就进行一次初始化,从下一个位置接着来。这么做可以的原因十分简单,可以这样想:如果从第三张牌开始摸到第六张是最大的情况,那么我们不需要再开一次从第四张、第五章、第六张的尝试,因为它们不可能比上面那种情况更优。

另外,采取了一个“哨兵”技巧,即在二倍数组的最后放一个很大的惩罚值,这样是为了避免出现当读取到最后一个牌堆的时候Penalty还是正值而导致这一种情况没有被考虑入可能的答案中。【备注:由于在n*2位置处加上了“哨兵”,我们应当将循环条件设置成i <= n * 2】

#include <iostream>

using namespace std;

const int LIM = 1e6 + 10;
int arr[LIM * 2];
int penal[LIM * 2];

int main(void) {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            scanf("%d", arr + i);
            arr[i + n] = arr[i];
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", penal + i);
            penal[i + n] = penal[i];
        }
        penal[n * 2] = 1e7;
        arr[n * 2] = 0;
        int ans, tp = 0, ti = 0, ts = 0, maxi = 0;
        for (int i = 0; i <= 2 * n; i++) {
            ti += arr[i];
            tp += arr[i] - penal[i];
            if (tp < 0) {
                if (ti > maxi) {
                    maxi = ti;
                    ans = ts;
                }
                tp = ti = 0;
                ts = i + 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

 

 

 

number number number

【2017 ACM/ICPC Asia Regional Shenyang Online】number number number

打表找规律+矩阵快速幂

Solution:

规律与斐波那契数列有关。

#include <iostream>
#include <cstdio>
using namespace std;

const int MOD = 998244353;

typedef unsigned long long ULL;

struct Matrix {
    ULL v[2][2];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    ret.v[i][j] += (v[i][k] * m.v[k][j]) % MOD;
                    ret.v[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
    void operator *= (const Matrix & m) {
        *this = *this * m;
    }
};

Matrix fastPow(Matrix x, ULL n) {
    Matrix ans = {{{1, 0}, {0, 1}}};
    while (n) {
        if (n & 1) ans *= x;
        x *= x;
        n >>= 1;
    }
    return ans;
}

const Matrix trans = {{{1, 1}, {1, 0}}};

int main(void) {
    ios::sync_with_stdio(false);
    ULL k;
    while (cin >> k) {
        if (k == 1) cout << 4 << endl;
        else {
            Matrix transform = fastPow(trans, 2 * (k - 1) - 1);
            cout << (transform.v[0][0] * 8 + transform.v[0][1] * 5 - 1) % MOD << endl;
        }
    }
    return 0;
}

 

cable cable cable

【2017 ACM/ICPC Asia Regional Shenyang Online】cable cable cable

Solution:

对于M个显示器,我们不如这样考虑:对于前K个【备注:题目保证了K不大于M】显示器,分别只与一个信号源连接,需要K根信号线;接下来断言,剩下的M-K个显示器每个都必要与K个信号源连接,也就是K*(M-K)根线,我们使用反证法证明,做如下思考,假如我们在选取K个显示器的时候,先将这K个显示器选定,之后任意从中去除一个显示器,再从剩下的M-K个显示器中选一个假如进来,如果这剩下的显示器中存在一个没有连接到K个信号源的显示器的话,假设它没有连接\(K_a\)信号源,那么,如果我们在选取时不选那个只连接着\(K_a\)信号源的显示器,而选择这个,就会导致不满足K个显示器有K个颜色,故断言必然成立。

因此公式为:

\(k + k * (m – k) = k * (m – k + 1)\)

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

int main(void) {
    ios::sync_with_stdio(false);
    ULL k, m;
    while (cin >> m >> k) {
        cout << k * (m - k + 1) << endl;
    }
    return 0;
}

 

array array array

【2017 ACM/ICPC Asia Regional Shenyang Online】array array array

Solution:

反过来找最长不上升子序列的长度,就是正着找最长不下降子序列的长度,所以这道题其实就是找两次最长不上升子序列,注意,\(O(n^2)\)会超时。

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e5 + 10;
int arr[LIM];
int rarr[LIM];
int dp[LIM];
int rdp[LIM];
int n;

inline int maxi(int a, int b) {
    return a > b ? a : b;
}

int lis() {
    memset(dp, 0, sizeof dp);
    memset(rdp, 0, sizeof rdp);
    int dpl, rdpl;
    dpl = rdpl = 0;
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < dpl; j++) {
            if (arr[i] > dp[j]) {
                dp[j] = arr[i];
                break;
            }
        }
        if (j == dpl) dp[dpl++] = arr[i];
        for (j = 0; j < rdpl; j++) {
            if (rarr[i] > rdp[j]) {
                rdp[j] = rarr[i];
                break;
            }
        }
        if (j == rdpl) rdp[rdpl++] = rarr[i];
    }
    return maxi(dpl, rdpl);
}

int main(void) {
    int t, k;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%d", arr + i);
            rarr[n - i - 1] = arr[i];
        }
        int maxi = lis();
        printf("%s\n", maxi >= n - k ? "A is a magic array." : "A is not a magic array.");
    }
    return 0;
}

 

【2017ACM-ICPC广西邀请赛】Color it

【2017ACM-ICPC广西邀请赛】Color it

【动态线段树】

问题链接:https://vjudge.net/problem/HDU-6183

Solution:

核心思路:由于查询总是对(1, y1) ~ (x, y2)这个范围内进行查询,其中x的起始固定为1,也就是说,对于任意位于y1与y2之间的上色点,只要其横坐标小于x,它就在这个区间内,于是我们可以建立线段树,用y来作为区间,线段树上每个结点的值则是这个y的区间内最小的x,由于有51中颜色【0~50】,需要维护51个这样的线段树。

上边的思路是正确的,但是因为内存限制,无法开51个1e^6 * 2的线段树,因此,我们采用动态化线段树。因为在操作线段树时,我们只需要能够由父结点寻找子节点,而不局限于必须使用index >> 1和index >> 1 | 1的方式,我们可以用两个数组来存储对于任意一个结点其左、右结点在数组中的下标,这样就可以找到一棵树所有的结点,并且,也保证了没有经历过的区间是不会存储的,具体方法如下,tree就是存放数值的线段树,rootPos数组存储51种颜色的树其根节点在tree中的位置,lrt和rrt数组分别表示以其下标作为为tree中位置的结点的左右结点在tree中的位置。

C++代码:

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 1e7;
const int LIM = 2e6;
bool flag;
int tree[LIM], rootPos[51], lrt[LIM], rrt[LIM], num;

inline int mini(int a, int b) {
    return a < b ? a : b;
}

inline void clear() {
    num = 0;
    for (int i = 0; i < LIM; i++) tree[i] = INF;
    memset(rootPos, 0, sizeof rootPos);
    memset(lrt, 0, sizeof lrt);
    memset(rrt, 0, sizeof rrt);
}

inline void pushup(int rt) {
    tree[rt] = mini(tree[lrt[rt]], tree[rrt[rt]]);
}

void update(int l, int r, int si, int x, int &rt) {
    if (l > si || r < si) return;
    if (!rt) rt = ++num;
    if (l == r) {
        if (tree[rt] > x) tree[rt] = x;
        return;
    }
    int mid = (l + r) >> 1;
    update(l, mid, si, x, lrt[rt]);
    update(mid + 1, r, si, x, rrt[rt]);
    pushup(rt);
}

void query(int l, int r, int qs, int qe, int x, int &rt) {
    if (!rt || flag || l > qe || r < qs) return;
    if (l >= qs && r <= qe) {
        if (tree[rt] <= x) flag = true;
        return;
    }
    int mid = (l + r) >> 1;
    query(l, mid, qs, qe, x, lrt[rt]);
    query(mid + 1, r, qs, qe, x, rrt[rt]);
}

int main(void) {
    int op, x, y1, y2, c;
    while (~scanf("%d", &op) && op != 3) {
        if (op == 0) clear();
        else if (op == 1) {
            scanf("%d%d%d", &x, &y1, &c);
            update(1, LIM, y1, x, rootPos[c]);
        } else if (op == 2) {
            scanf("%d%d%d", &x, &y1, &y2);
            int ans = 0;
            for (int i = 0; i <= 50; i++) {
                flag = false;
                query(1, LIM, y1, y2, x, rootPos[i]);
                if (flag) ans++;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

 

【2017ACM-ICPC广西邀请赛】Covering

【2017ACM-ICPC广西邀请赛】Covering

【递推+矩阵快速幂】

问题链接:https://vjudge.net/problem/HDU-6185

Solution 1:

这个是需要的思考较少的办法。暴力dfs算出\(n = 1 … 10\)时的answer,之后根据这个找到递推关系式,之后写出变换矩阵,采用矩阵快速幂来解决。

首先是暴力找前10个答案:

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 10;
bool vis[4][LIM];
int n;
int cnt = 0;

bool find(int & r, int & c) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < n; j++) {
            if (!vis[i][j]) {
                r = i;
                c = j;
                return true;
            }
        }
    }
    return false;
}

void bruteDfs() {
    int r, c;
    if (!find(r, c)) {
        cnt++;
        return;
    }
    if (r < 3 && !vis[r + 1][c]) {
        vis[r][c] = vis[r + 1][c] = true;
        bruteDfs();
        vis[r][c] = vis[r + 1][c] = false;
    }
    if (c < n - 1 && !vis[r][c + 1]) {
        vis[r][c] = vis[r][c + 1] = true;
        bruteDfs();
        vis[r][c] = vis[r][c + 1] = false;
    }
}

int main(void) {
    for (n = 1; n <= 10; n++) {
        memset(vis, false, sizeof vis);
        cnt = 0;
        bruteDfs();
        printf("4*%d : %d\n", n, cnt);
    }
    return 0;
}

得到前十组答案:

4*1 : 1
4*2 : 5
4*3 : 11
4*4 : 36
4*5 : 95
4*6 : 281
4*7 : 781
4*8 : 2245
4*9 : 6336
4*10 : 18061

接着就可以使用这几组数据推出递推式,假设每一项与前一项、前两项…前多项有关,手动高斯消元法逐个尝试求解,可以求出递推关系式,还有一种就是继续写程序暴力,发现递推关系式:

暴力求项数代码:

#include <iostream>

using namespace std;

int main(void) {
    for (int a1 = -10; a1 <= 10; a1++) {
        for (int a2 = -10; a2 <= 10; a2++) {
            for (int a3 = -10; a3 <= 10; a3++) {
                for (int a4 = -10; a4 <= 10; a4++) {
                    if (a1 * 1 + a2 * 5 + a3 * 11 + a4 * 36 == 95 &&
                            a1 * 5 + a2 * 11 + a3 * 36 + a4 * 95 == 281 &&
                            a1 * 11 + a2 * 36 + a3 * 95 + a4 * 281 == 781 &&
                            a1 * 36 + a2 * 95 + a3 * 281 + a4 * 781 == 2245) {
                        printf("f(n) = %df(n - 1) + %df(n - 2) + %df(n - 3) + %df(n - 4)\n", a4, a3, a2, a1);
                    }
                }
            }
        }
    }
    return 0;
}

输出:

f(n) = 1f(n - 1) + 5f(n - 2) + 1f(n - 3) + -1f(n - 4)

写成矩阵变换式:

接下来就可以正式编码了。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const LL MOD = 1000000007;
struct Matrix {
    LL v[4][4];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    ret.v[i][j] += (v[i][k] * m.v[k][j] + MOD) % MOD;       //注意v[i][k] * m.v[k][j]可能会变成负数,需要加上MOD
                    ret.v[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
    void operator *= (const Matrix & m) {
        *this = *this * m;
    }
};
const Matrix base = {{{1, 5, 1, -1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}};
LL start[] = {1, 5, 11, 36};

Matrix fastPow(Matrix x, LL pow) {
    Matrix ans = {{{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}};
    while (pow) {
        if (pow & 1) ans *= x;
        x *= x;
        pow >>= 1;
    }
    return ans;
}

int main(void) {
    ios::sync_with_stdio(false);
    LL n;
    while (cin >> n) {
        if (n <= 4) cout << start[n - 1] << endl;
        else {
            Matrix fac = fastPow(base, n - 4);
            cout << (fac.v[0][0] * start[3]
                    + fac.v[0][1] * start[2]
                    + fac.v[0][2] * start[1]
                    + fac.v[0][3] * start[0]) % MOD << endl;
        }
    }
    return 0;
}

上边那里不加上MOD话,一个出错的例子是,对于输入1000000000,输出会是一个负数。

【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【贪心】

问题链接:https://vjudge.net/problem/HDU-6188

一些数据:

9

1 2 3 3 4 5 5 6 7

12

2 3 4 4 5 6 6 7 8 8 9 10

5

2 2 2 2 2

6

4 4 5 5 6 6

以上数据输出:

3

4

2

3

 

Solution:

解决这道题的核心在于贪心策略。对于任意连续的三个数,假设这三个数出现次数依此是a, b, c,如果组成顺子,显然个数为t = min(a, b, c),而组成对子,则有

ceil(a / 2) + ceil(b / 2) + ceil(c / 2).    【其中ceil()表示向下取整】

显然有如下关系:

ceil(a / 2) + ceil(b / 2) + ceil(c / 2) >= \(\frac{3t}{2}\).

这表明,对于三个连续数,优先取对子会得到较大的值,即对于任意数,优先组成对子。只有在一个数是奇数时才考虑顺子。

先考虑遇到一个数出现了奇数次数,现在需要考虑是否取顺子,这时要看它之后的两个数。如果它之后的两个数都不为0,若第二个数是偶数,则应该都拿对子,因为如果第三个数大于1时,拿顺子要比拿对子的数量至少多1【因为第二个数和第三个数各自组成对子】,这时就可以忽略第一个数即不用拿顺子了;当第二个数是偶数时,如果第三个数是1,这时拿对子至少能拿一个【即第二个数有两个】,而拿顺子则固定只能拿一个了【因为第一个数自己拿完对子后最多只能剩下1,且这里讨论的情况保证第三个数也只有1个】,所以我们那对子总不会差于拿顺子。当第二个数有奇数个时,先拿完对子,剩下了1个,此时第一个数也剩下了1个,只要第三个数不是0个,无论奇偶,拿第三个数全拿对子或在这里取一个顺子剩下的全拿对子没有区别,因为最多只会拆开一个对子,而拆开一个对子后我们又拿了一个顺子,最后数量不会变化。

由此得出贪心策略:

对于任意数,先按照对子将它取完,再看这样操作后是否还有剩余【即判断这个数原本出现的个数是奇数还是偶数】,如果有剩余,则考虑是否要取顺子,如果第二个数的数量是有奇数个且第三个数的数量不为0,则拿顺子,反之不拿顺子。

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6 + 5;
int data[LIM];

int main(void) {
    int n, ans, t;
    while (~scanf("%d", &n)) {
        memset(data, 0, sizeof data);
        ans = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &t);
            data[t]++;
        }
        for (int i = 1; i <= n; i++) {
            ans += data[i] / 2;
            data[i] %= 2;
            if (data[i] && data[i + 1] && data[i + 1] % 2 && data[i + 2]) {
                ans++;
                data[i + 1]--;
                data[i + 2]--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

【2017ACM-ICPC广西邀请赛】CS Course

【2017ACM-ICPC广西邀请赛】CS Course

【前后缀/位数统计+异或的运算性质】

问题链接:https://vjudge.net/problem/HDU-6186

Solution 1:

Core concept:

1. 对于一串数\(a_1, a_2 … a_n\),要求去掉\(a_p (p \in [1, n])\)后,求剩下全部数的与、或、异或的值,为了方便表述,我们将这里的运算用符号\(\oplus\)表示,则当前问题是求:

\(a_1 \oplus … a_{p – 1} \oplus a_{p + 1}… \oplus a_n = ?\).

显然上式等于:

\((a_1 \oplus … a_{p – 1}) \oplus (a_{p + 1} … \oplus a_n)\)

特殊的,对于\(p = 1 or n\),可通过去掉上式左侧圆括号内容或右侧圆括号内容使得等式成立。因此,我们可以开两个数组:

前缀数组pre(\(pre[i] = a_1 \oplus … \oplus a_{p – 1}\))

后缀数组suf(\(suf[i] = a_{p + 1} \oplus … \oplus a_n\)).

2.对于异或运算,我们也可以采用上边的办法,但是,由于有更好的办法(即利用异或运算性质),我们采用另一种办法。

关键:

b ^ b = 0(^表示异或),即一个数总是其自身的异或逆元。

a ^ b = b ^ a,即交换律。

所以我们将a_1 ^ … ^ a_n放到一个变量中(取名为xorans),则除去\(a_k\)后,答案应是:xorans ^ \(a_p\).

#include <iostream>

using namespace std;

const int LIM = 1e5 + 10;
struct node {
    int av, ov;     // "and value" and "or value"
};

int a[LIM];
node pre[LIM], suf[LIM];

int main(void) {
    int n, q;
    int xorans;
    while (~scanf("%d%d", &n, &q)) {
        xorans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            xorans ^= a[i];
            pre[i].av = pre[i].ov = suf[i].av = suf[i].ov = a[i];
            if (i != 1) {
                pre[i].av &= pre[i - 1].av;
                pre[i].ov |= pre[i - 1].ov;
            }
        }
        for (int i = n - 1; i >= 1; i--){
            suf[i].av &= suf[i + 1].av;
            suf[i].ov |= suf[i + 1].ov;
        }
        int p;
        while (q--) {
            scanf("%d", &p);
            if (p == 1) printf("%d %d %d\n", suf[2].av, suf[2].ov, xorans ^ a[1]);
            else if (p == n) printf("%d %d %d\n", pre[n - 1].av, pre[n - 1].ov, xorans ^ a[n]);
            else printf("%d %d %d\n", pre[p - 1].av & suf[p + 1].av, pre[p - 1].ov | suf[p + 1].ov, xorans ^ a[p]);

        }
    }
    return 0;
}

 

Solution 2:

统计所有数各二进制位的1的个数,如果去掉a[k]后,某位上1的个数为n – 1,则与运算后该位是1;如果某位上1的个数大于0,则或运算后该位是1。

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 1e5 + 10;
const int BITS = 32;
int a[LIM];
int cnt[BITS];
int cnttmp[BITS];

int main(void) {
    int n, q;
    int xorans;
    while (~scanf("%d%d", &n, &q)) {
        memset(cnt, 0, sizeof cnt);
        xorans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            xorans ^= a[i];
            int tmp = a[i];
            for (int i = 0; tmp; i++, tmp >>= 1)
                if (tmp & 1) cnt[i]++;
        }
        int p, andans, orans;
        while (q--) {
            andans = orans = 0;
            scanf("%d", &p);
            memcpy(cnttmp, cnt, sizeof cnt);
            int tmp = a[p];
            // 使用cnttmp数组来存储去掉a_p后,各位的1的个数
            for (int i = 0; tmp; i++, tmp >>= 1) {
                if (tmp & 1) cnttmp[i]--;
            }
            for (int i = BITS - 1; i >= 0; i--, tmp >>= 1) {
                andans <<= 1;
                orans <<= 1;
                if (cnttmp[i] == n - 1) andans |= 1;
                if (cnttmp[i] > 0) orans |= 1;
            }
            printf("%d %d %d\n", andans, orans, xorans ^ a[p]);
        }
    }
    return 0;
}

 

【2017ACM-ICPC广西邀请赛】A Math Problem

【2017ACM-ICPC广西邀请赛】A Math Problem

问题链接:https://vjudge.net/problem/HDU-6182

注意:k为15时超过1e18

方法:十分简单的一道题,直接枚举就好。

Solution:

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

ULL fastPow(ULL a, ULL b) {
    ULL ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret *= a;
        a *= a;
    }
    return ret;
}

int main(void) {
    ULL n;
    while (cin >> n) {
        ULL k;
        for (k = 1; k <= 15; k++)
            if (fastPow(k, k) > n) break;
        cout << k - 1 << endl;
    }
    return 0;
}