0-1背包型

约 3391 个字 444 行代码预计阅读时间 17 分钟

1. [NOIP2001 普及组] 装箱问题

题目描述

有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。

现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 $V$，表示箱子容量。

第二行共一个整数 $n$，表示物品总数。

接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。

输出格式

共一行一个整数，表示箱子最小剩余空间。

样例 #1

样例输入 #1

Text Only
1 2 3 4 5 6 7 8	`24 6 8 3 12 7 9 7`

样例输出 #1

Text Only
1	`0`

提示

对于 $100\%$ 数据，满足 $0<n \le 30$，$1 \le V \le 20000$。

题解

此题属于0-1背包问题

要求剩余空间尽可能小，只需尽可能的装最多

直接排序向背包中装入物品未必得到的是最优解

针对每个物品，我们只需要做出拿和不拿的决策并计算背包容量即可

(1) 正常思维实现的暴力递归

C++
#include<bits/stdc++.h>

using namespace std;

int V,n;
int arrs[35];

int process(int index,int rest){

    if(index > n){
        return 0;
    }
    // 不选当前物品
    int p1 = process(index+1,rest);
    // 选当前物品
    int p2 = 0;
    // 如果有空间存储当前物品，则选
    if(rest-arrs[index]>=0){
        p2 = process(index+1,rest-arrs[index]) + arrs[index];
    }
    return max(p1,p2);
}


int main()
{
    cin >> V >> n;
    if(V<=0){
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i <= n;i++){
        cin >> arrs[i];
    }
    // 背包容量 - 最大存储容量
    cout<< V - process(1,V)<<endl;

    return 0;
}

(2) 动态规划代码

C++
#include<bits/stdc++.h>

using namespace std;

int V,n;
int arrs[35];

int dp[20005];

int main()
{
    cin >> V >> n;
    if(V<=0){
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i <= n;i++){
        cin >> arrs[i];
    }
    for(int i=1;i<=n;i++){
        for(int j = V;j >= 0;j--){
            if(j - arrs[i] >= 0){
                dp[j] = max(dp[j],dp[j-arrs[i]]+arrs[i]);
            }
        }
    }

    // 背包容量 - 最大存储容量
    cout<< V - dp[V]<<endl;

    return 0;
}

2. [NOIP2006 普及组] 开心的金明

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过$N$元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的$N$元。于是，他把每件物品规定了一个重要度，分为$5$等：用整数$1-5$表示，第$5$等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过$N$元（可以等于$N$元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第$j$件物品的价格为$v[j]$，重要度为$w[j]$，共选中了$k$件物品，编号依次为$j_1,j_2,…,j_k$，则所求的总和为：

$v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]$。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为$2$个正整数，用一个空格隔开：$n,m$（其中$N(<30000)$表示总钱数，$m(<25)$为希望购买物品的个数。）

从第$2$行到第$m+1$行，第$j$行给出了编号为$j-1$的物品的基本数据，每行有$2$个非负整数$ v p$（其中$v$表示该物品的价格$(v \le 10000)$，$p$表示该物品的重要度($1-5$)

输出格式

$1$个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值$(<100000000)$。

样例 #1

样例输入 #1

Text Only
1 2 3 4 5 6	`1000 5 800 2 400 5 300 5 400 3 200 2`

样例输出 #1

Text Only
1	`3900`

题解

(1) 暴力递归求解

C++
#include<bits/stdc++.h>

using namespace std;
int n,m;
struct Node{
    int v,w;

}arrs[30];

int process(int index, int rest){
    if(index > m){
        return 0;
    }
    // 不选
    int p1 = process(index+1,rest);
    // 选
    int p2 = 0;
    // 如果选的决策有效
    if(rest - arrs[index].v >= 0){
        p2 = process(index+1,rest - arrs[index].v) + arrs[index].v * arrs[index].w;
    }
    return max(p1,p2);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin >> arrs[i].v >> arrs[i].w;
    }
    cout << process(1,n);
    return 0;
}

(2) 动态规划代码

C++
#include<bits/stdc++.h>

using namespace std;
int n,m;
struct Node{
    int v,w;

}arrs[30];

int dp[50005];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin >> arrs[i].v >> arrs[i].w;
    }
    for(int i = 1;i <= m;i++){
        for(int j = n;j>=0;j--){
            if(j-arrs[i].v >= 0){
                dp[j] = max(dp[j],dp[j-arrs[i].v] + arrs[i].v*arrs[i].w );
            }
        }
    }
    cout << dp[n];


    return 0;
}

3. 最大约数和

题目描述

选取和不超过 $S$ 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数 $S$。

输出格式

输出最大的约数之和。

样例 #1

样例输入 #1

Text Only
1	`11`

样例输出 #1

Text Only
1	`9`

提示

【样例说明】

取数字 $4$ 和 $6$，可以得到最大值 $(1+2)+(1+2+3)=9$。

【数据规模】

对于 $100 \%$ 的数据，$1 \le S \le 1000$。

题解

思路: - 先求1-s中的每个数的约数和nums[i] ---> nums[i]就作为价值数组存在. - 总背包体积s ---> 不解释. - 题目转换为: 在不超过总体积s的情况下，尽可能使得背包中的价值最大. - 那么体积是什么呢？就是在1-s里选的数的值。---> 题目要求所选数之和不能大于s,这就是体积数组.

动态规划代码

C++
#include<bits/stdc++.h>

using namespace std;

// 求某个数的约数和
int getSum(int n)
{
    int sum = 0;
    // 约数不含它本身
    for(int i=1;i < n;i++){
        // 如果能被整数，就是一个约数，则加起来
        if(n % i == 0){
            sum += i;
        }
    }
    // 返回约数和
    return sum;
}
int nums[1003];
int dp[1003];
int main()
{
    int s;
    cin >> s;
    for(int i=1;i<=s;i++){
        nums[i] = getSum(i);
    }
    // i表示选的数
    for(int i=1;i <= s;i++){
        // j表示容量
        for(int j=s; j>=i;j--){
            // 0-1背包状态转移方程
            dp[j] = max(dp[j],dp[j-i] + nums[i]);
        }
    }
    cout << dp[s] << endl;
    return 0;
}

4. [蓝桥杯 2021 省 AB] 砝码称重

题目描述

你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_{1}, W_{2}, \cdots, W_{N}$ 。请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数: $W_{1}, W_{2}, W_{3}, \cdots, W_{N}$ 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

Text Only
1 2	`3 1 4 6`

样例输出 #1

Text Only
1	`10`

提示

【样例说明】

能称出的 10 种重量是: $1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11$ 。

\[ \begin{aligned} &1=1 \\ &2=6-4(\text { 天平一边放 } 6, \text { 另一边放 4) } \\ &3=4-1 \\ &4=4 \\ &5=6-1 \\ &6=6 \\ &7=1+6 \\ &9=4+6-1 \\ &10=4+6 \\ &11=1+4+6 \end{aligned} \]

【评测用例规模与约定】

对于 $50 \%$ 的评测用例, $1 \leq N \leq 15$ 。

对于所有评测用例, $1 \leq N \leq 100, N$ 个砝码总重不超过 $10^5$。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

题解

分析:

(1) 给定N个不同重量的砝码，取这N个砝码去放在天平上称质量，可以称出多少种质量。 (2) 确定可以求出的质量范围大小：1 -> sum = ∑W[i] (3) 假定放左边为负权值，右边为正权值，面对第i个砝码可做出的三种决策及质量: - 不取 - 取来放左边 --- abs(w - w[i])
- 取来放右边 --- w + w[i] - w ∈ (1,sum)

(4) 设dp[i][j]表示选取i个砝码是否可以称出质量为j的可行解，则根据上述三种决策可以得到下面的状态转移方程:
C++
1
dp[i][j] = dp[i-1][j] || dp[i-1][abs(j - w[i])] ||  dp[i-1][j + w[i]]
(5) 在1-sum中累加可行解的个数，即：
C++
1
ans = ∑dp[n][j]==true ,j∈[1,sum]

动态规划代码

C++
#include<bits/stdc++.h>

using namespace std;

int n,w[105];
int dp[103][100003];
int main()
{
    cin >> n;
    int sum = 0;
    for(int i=1;i<=n;i++){
        cin >> w[i];
        // 计算可求重量的上限，下限为0
        sum += w[i];
    }
    dp[0][0] = 1;
    // 取第i砝码是否存在可行重量j，如果存在，则有一个可求出的重量
    for(int i=1;i<=n;i++){
        // 可称出的重量不会出现重复，因为j代表的就是可称出来的重量值
        for(int j=sum;j>=0;j--){
            // 不取这个砝码 || 将这个砝码放在左边 || 将这个砝码放在右边
            dp[i][j] = dp[i-1][j] || dp[i-1][abs(j-w[i])] || dp[i-1][j+w[i]];
        }
    }
    int ans = 0;
    // n个砝码，在1-sum的重量范围内 有多少个可行解
    for(int i=1;i<=sum;i++){
        if(dp[n][i]){
            ans++;
        }
    }
    cout << ans;

    return 0;
}

5. [HAOI2012] 音量调节

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。输入文件中整数 $beginLevel$，代表吉他刚开始的音量，整数 $maxLevel$，代表吉他的最大音量。音量不能小于 $0$ 也不能大于 $maxLevel$。输入中还给定了 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

输入格式

第一行依次为三个整数 $n$，$beginLevel$ 和 $maxLevel$。

第二行依次为 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$。

输出格式

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 $0$ 或者高于 $maxLevel$，输出 -1。

样例 #1

样例输入 #1

Text Only
1 2	`3 5 10 5 3 7`

样例输出 #1

Text Only
1	`10`

提示

$1\le n\le 50$，$1\le c_i\le maxLevel$，$1\le maxLevel\le 1000$，$0\le beginLevel\le maxLevel$。

题解

分析：

可以先分析出该歌手在演出期间都能到达哪些音量，然后安装音量大小进行变量

设dp[i][j]表示前i首歌是否可以到达音量j,可以到达的话,dp[i][j] = 1,否则dp[i][j] = 0
针对第i首歌，可以做出的决策是：调高或调低，只要满足情况,就有:
C++
1
2
 dp[i][j-c[i]] = 1
 dp[i][j+c[i]] = 1
从maxLevel开始向下遍历，输出最大值

AC代码

C++
#include<bits/stdc++.h>

using namespace std;

int c[55];
int dp[55][1005];
int main()
{
    int n,bL,mL;
    cin >> n >> bL >> mL;
    for(int i=1;i<=n;i++){
        cin >> c[i];
    }
    // 开始时
    dp[0][bL] = 1;

    for(int i=1;i<=n;i++){
        for(int j=mL;j>=0;j--){
            // 条件是: 上一个音量大小可达，当前音量的改变需要不低于0 或 不高于mL
            if(dp[i-1][j] && j-c[i] >= 0){
                dp[i][j-c[i]] = 1;
            }
            if(dp[i-1][j] && j+c[i] <= mL){
                dp[i][j+c[i]] = 1;
            }
        }
    }

    for(int i=mL;i>=0;i--){
        if(dp[n][i]){
            // 可达到，输出i
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 <<endl;
    return 0;
}

6. 小书童——刷题大军

题目背景

数学是火，点亮物理的灯；物理是灯，照亮化学的路；化学是路，通向生物的坑；生物是坑，埋葬学理的人。文言是火，点亮历史宫灯；历史是灯，照亮社会之路；社会是路，通向哲学大坑；哲学是坑，埋葬文科生。——小A

题目描述

小A“刷题”十分猖狂，明目张胆地“刷题”。他现在在小书童里发现了n样他喜欢的“题目”，每“题”都有他的需要时间，而老师布置了m项作业，每项作业都有它的需要时间及分值，老师规定k分以上算及格。小A只剩r个单位时间，他想在及格的基础上更多地“刷题”。

输入格式

第一行：n m k r。第二行：n个数，代表每“题”他的需要时间。第三行：m个数。表示每项作业它的需要时间。第四行：m个数。代表每项作业它的分值。

输出格式

一个数，代表小A能刷几道题

样例 #1

样例输入 #1

Text Only
1 2 3 4	`3 4 20 100 15 20 50 10 15 40 40 5 5 10 15`

样例输出 #1

Text Only
1	`2`

提示

没有不能及格的情况

对于100%的数据，$n\le 10,m\le 10,k\le 50,r\le 150$

题解

分析：

小A想要刷n道题，但老师布置了m项作业需要完成，作业分数需要达到k分才算及格，给出每道题的解决时间pro[i]、每项作业的解决时间hmr[i]和分数hms[i]以及可用时间r,问在及格的情况下，最多可以刷几道题?

(1) 设dp[j] 为j时间内拿到的分数 (2) 计算1->r时间内，每个时间可以拿到的分数 - 0-1背包问题 - 背包容量：r - 物品体积：hmr[i] - 物品价值：hms[i] - 求r下得到的最大价值 (3) 遍历1->r，找到dp[i] >= k时的i值 ---> 此时的i是做作业花去的时间; (4) 求可用于刷题的世界tt = r - i; (5) 问题又转换为：tt时间内，最多能获取多少个pro数组中的元素 - 采用贪心策略，对pro数组进行排序，每次选取时间花费最小值，直到无法选取，即可得到刷题数ans

AC代码

C++
#include<bits/stdc++.h>

using namespace std;
int n,m,k,r,ans;
int pro[160],hwt[160],hws[160];
int dp[105];
int main()
{
    cin >> n >> m >> k >> r;
    for(int i=1;i<=n;i++){
        cin >> pro[i];
    }
    sort(pro+1,pro+1+n);

    for(int i=1;i<=m;i++){
        cin >> hwt[i];
    }
    for(int i=1;i<=m;i++){
        cin >> hws[i];
    }
    // m项作业，r时间内，可以获得的最大分数
    for(int i=1;i<=m;i++){
        for(int j=r;j>=hwt[i];j--){
            dp[j] = max(dp[j],dp[j-hwt[i]]+hws[i]);
        }
    }
    // 贪心策略：每次选取花销最小的值
    sort(dp,dp+r+1);
    int ti;
    for(int i=0; i <= r;i++){
        if(dp[i] >= k){
            // 减去做作业的时间
            ti = r - i;
            break; // 找到及格分数，就直接跳出
        }
    }

    for(int i=1;i<=n && ti-pro[i] >=0;i++){
        ans++;
        ti-=pro[i];
    }

    cout << ans;
    return 0;
}

7. 精卫填海

题目描述

【问题描述】

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

事实上，东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。

输入格式

输入文件的第一行是三个整数：v、n、c。

从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式

输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出’Impossible’（不带引号）。

样例 #1

样例输入 #1

Text Only
1 2 3	`100 2 10 50 5 50 5`

样例输出 #1

Text Only
1	`0`

样例 #2

样例输入 #2

Text Only
1 2 3	`10 2 1 50 5 10 2`

样例输出 #2

Text Only
1	`Impossible`

提示

【数据范围】

对于20%的数据，0<n<=50。

对于50%的数据，0<n<=1000。

对于100%的数据，0<n<=10000，所有读入的数均属于[0,10000]，最后结果<=c。

题解

针对每个石子，有选和不选两种决策，且石子只能选一次 ---> 0-1背包问题

剩下体力的c，可视为背包容量

n个石子，代表着n个物品

移动石子所需体力m，视为物品重量

石子体积k，视为物品价值

最低价值V，视为需要得到的最低价值

题目转变为: 在满足最低价值v的情况下，最多还能装多少？若不能满足v，输出“Impossible”

AC代码

C++
#include<bits/stdc++.h>

using namespace std;
/*

    背包容量: c
    物品个数: n
    每件物品:
              > 重量(体积)：m
              > 价值：k

    需要装入的最低价值: v

    思路:
        (1) 求出1-c内可以装入的最大价值 dp[i]
        (2) 遍历1-c,找到第一次满足 dp[i] >= v 的i值, 此时c-i ---> 就是既能满足v，有处于最大空间容量的情况
        (2) 不存在dp[i] >= v ---> 不能填满海，输出 impossible
*/

int v,n,c;
int m[10001],k[10001];
int dp[10001];

int main()
{
    cin >> v >> n >> c;
    for(int i=1;i<=n;i++){
        cin >> k[i] >> m[i];
    }
    // 求出容量1-c区间内 各体力能填入的最大体积
    for(int i=1;i<=n;i++){
        for(int j=c; j>=m[i]; j--){
            dp[j] = max(dp[j],dp[j-m[i]]+k[i]);
        }
    }
    // 找到恰好满足v的体力值
    for(int i=1;i<=c;i++){
        if(dp[i] >= v){
            // 一旦找到， c-i就是既满足最低要求v，又留有最大体力情况下的剩余体力值
            cout << c-i << endl;
            return 0;
        }
    }
    cout << "Impossible" << endl;

    return 0;
}

完全背包问题

1. A+B Problem

题目描述

给定一个正整数 $n$，求将其分解成若干个素数之和的方案总数。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数表示方案总数。

样例 #1

样例输入 #1

Text Only
1	`7`

样例输出 #1

Text Only
1	`3`

样例 #2

样例输入 #2

Text Only
1	`20`

样例输出 #2

Text Only
1	`26`

提示

样例解释

存在如下三种方案：

$7=7$。
$7=2+5$。
$7=2+2+3$。

数据范围及约定

对于 $30\%$ 的数据 $1\le n\le 10$。
对于 $100\%$ 的数据，$1\le n\le 10^3$。

题解

分析：

(1) 给定一个正整数n，将其分成若干个素数，问有多少种分法？ (2) 求出2-n中的所有素数，存储进数组prim[i]中,记录素数的个数cnt (3) 此时题目就转变为了完全背包问题（取与不取的问题） - 容量为n - 价值为prim[i] → 本题中没啥用 - 体积也为prim[i] - 求恰好可以装满背包的方案数?

(4) 对于第i个prim数组元素，可做出的决策为: 取与不取，并且每个数满足条件下可以取无限次 (5) 设dp[j] 表示取可以实现装满j容积的方案数，则：
C++
1
2
3
4
// 当前方案数 = 取 + 不取 
// 取的话,加到方案总数里，然后容积减去相应的prim值
// 不取的话,dp[i-1][j-prim[i]]的值默认为0 
dp[j] = dp[j] + dp[i-1][j-prim[i]]

AC代码

C++
#include<bits/stdc++.h>

using namespace std;

long long dp[1005],n;

int isPrim(int num){

    for(int i=2;i < num;i++){
        if(num%i==0){
            return 0;
        }
    }
    return 1;
}
int vs[1005];
int main()
{
    cin >> n;
    int cnt = 0;
    // 获取素数
    for(int i=2;i<=n;i++){
        if(isPrim(i)){
            vs[++cnt] = i;
        }
    }
    // 边界：当容积为0时，方案数为1
    dp[0] = 1;
    for(int i=1;i<=cnt;i++){
        for(int j=vs[i];j<=n;j++){ // 完全背包代码
            dp[j] = dp[j] + dp[j-vs[i]];
        }
    }
    cout << dp[n] << endl;
    return 0;
}

2. [AHOI2001]质数和分解

题目描述

任何大于 $1$ 的自然数 $n$ 都可以写成若干个大于等于 $2$ 且小于等于 $n$ 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如，$9$ 的质数和表达式就有四种本质不同的形式：

$9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7$ 。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数 $n$ 可以写成多少种本质不同的质数和表达式。

输入格式

文件中的每一行存放一个自然数 $n(2 \leq n \leq 200)$ 。

输出格式

依次输出每一个自然数 $n$ 的本质不同的质数和表达式的数目。

样例 #1

样例输入 #1

Text Only
1 2	`2 200`

样例输出 #1

Text Only
1 2	`1 9845164`

题解

先将2-n范围内的所有素数求出，并存放在一个arrs数组中

arrs数组中的每个元素就代表着背包选取时的代价

题目就此转变为完全背包的记数问题

AC代码

C++
#include<bits/stdc++.h>

using namespace std;

/*
    (1) 求出1-n直接的素数数组nums
    (2) 转变为完全背包的记数问题
        > 重量 nums[i]
        > 价值 nums[i]
*/

int n,cnt;

int arrs[105];

// 判断素数
int isPrim(int n)
{
    for(int i=2; i<=sqrt(n); i++)
    {
        if(n % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
int dp[201];
int main()
{
    // 题目：输入一个n，输出一个ans
    while(cin >> n)
    {
        // 每次输入，cnt，dp都要清零
        cnt = 0;
        for(int i=1;i<=n;i++){
            dp[i] = 0;
        }
        for(int i=2; i<=n; i++)
        {
            if(isPrim(i))
            {
                arrs[++cnt] = i;
            }
        }
        // 开始要赋值为1
        dp[0] = 1;
        for(int i=1; i<=cnt; i++)
        {
            for(int j=arrs[i]; j<=n; j++)
            {
                // 完全背包记数问题的代码
                dp[j] += dp[j-arrs[i]];
            }
        }
        cout << dp[n] << endl;
    }

    return 0;
}