53S01串作者: turbo时间限制: 1s章节: 字符串问题描述s01串初始为0按以下方式变换0变11变01所以变换规律如下1次变换后12次变换后01;3次变换后1014次变换后011015次变换后10101101......输入说明输入1个整数n范围为0n19表示变换的次数输出说明n次变换后的s01串行首行尾无空格也无空行。#include stdio.h #include string.h int main(){ int n; scanf(%d, n); char str[10000] {0}; str[0] 0; str[1] \0; int count 0; while(count n){ int len strlen(str); char new_str[1000000]; int idx 0; for(int i 0; i len; i){ if(str[i] 0) new_str[idx] 1; else{ new_str[idx] 0; new_str[idx] 1; } } new_str[idx] \0; strcpy(str, new_str); count; } printf(%s, str); return 0; }54身份证排序作者: Turbo时间限制: 1s章节: 基本练习字符串问题描述安全局搜索到了一批(n个)身份证号码希望按出生日期对它们进行从大到小排序如果有相同日期则按身份证号码从大到小进行排序。身份证号码为18位的数字组成出生日期为第7到第14位输入说明第一行一个整数n表示有n个身份证号码余下的n行每行一个身份证号码。n100000输出说明按出生日期从大到小排序后的身份证号每行一条#include stdio.h #include string.h int main() { int n; scanf(%d, n); char ids[n][20]; char dates[n][9]; for(int i 0; i n; i){ scanf(%s, ids[i]); strncpy(dates[i], ids[i] 6, 8); dates[i][8] \0; } for(int i 0; i n - 1; i){ for(int j i 1; j n; j){ if(strcmp(dates[i], dates[j]) 0){ char temp[20]; strcpy(temp, ids[i]); strcpy(ids[i], ids[j]); strcpy(ids[j], temp); strcpy(temp, dates[i]); strcpy(dates[i], dates[j]); strcpy(dates[j], temp); } else if(strcmp(dates[i], dates[j]) 0){ if(strcmp(ids[i], ids[j]) 0){ char temp[20]; strcpy(temp, ids[i]); strcpy(ids[i], ids[j]); strcpy(ids[j], temp); strcpy(temp, dates[i]); strcpy(dates[i], dates[j]); strcpy(dates[j], temp); } } } } for(int i 0; i n; i) printf(%s\n, ids[i]); return 0; }55回文数作者: Turbo时间限制: 1s章节: 模拟问题描述若一个数首位不为零从左向右读与从右向左读都一样我们就将其称之为回文数。我们现在需要产生回文数步骤如下给定一个10进制数56将56加65即把56从右向左读得到121是一个回文数。又如对于10进制数87STEP18778 165STEP2165561 726STEP3726627 1353STEP413533531 4884在这里的“一步”是指进行了一次N进制的加法上例最少用了4步得到回文数4884。写一个程序给定一个N2N10或N16进制数M其中16进制数字为0-9与A-F求最少经过几步可以得到回文数。如果在30步以内包含30步不可能得到回文数则输出“Impossible!”输入说明两行N与M输出说明如果能在30步以内得到回文数输出“STEPxx”不含引号其中xx是步数否则输出一行”Impossible!”不含引号#include stdio.h #include string.h #include ctype.h #define MAX_LEN 1000 int toDigit(char c) { if (c 0 c 9) return c - 0; if (c A c F) return c - A 10; if (c a c f) return c - a 10; return 0; } char toChar(int n) { if (n 10) return n 0; return n - 10 A; } int isPal(char *s) { int len strlen(s); for (int i 0; i len / 2; i) { if (s[i] ! s[len - 1 - i]) return 0; } return 1; } int main() { int N; char M[MAX_LEN]; scanf(%d %s, N, M); char num[MAX_LEN], rev[MAX_LEN]; strcpy(num, M); for (int step 0; step 30; step) { if (isPal(num)) { printf(STEP%d\n, step); return 0; } if (step 30) break; int len strlen(num); for (int i 0; i len; i) rev[i] num[len - 1 - i]; rev[len] \0; int carry 0; char result[MAX_LEN] {0}; int idx 0; for (int i len - 1; i 0 || carry; i--) { int a (i 0) ? toDigit(num[i]) : 0; int b (i 0) ? toDigit(rev[i]) : 0; int sum a b carry; result[idx] toChar(sum % N); carry sum / N; } strcpy(num, result); } printf(Impossible!\n); return 0; }56新生舞会作者: Turbo时间限制: 1s章节: 结构体问题描述新生舞会开始了。n名新生每人有三个属性姓名、学号、性别。其中姓名用长度不超过20的仅由大小写字母构成的字符串表示学号用长度不超过10的仅由数字构成的字符串表示性别用一个大写字符‘F’或‘M’表示。任意两人的姓名、学号均互不相同。换言之每个人可被其姓名或学号唯一确定。输入m对舞伴的信息姓名或学号判断他们是否能共舞。两人能共舞的充要条件为两人性别相异。输入说明第一行一个整数n2n1000表示学生人数。接下来的n行每行依次包含一名新生的姓名、学号、性别分别用一个空格隔开。之后的一行是一个整数m(1m1000)表示询问舞伴的对数。接着的m行每行包含两个舞伴的信息姓名或学号保证两个信息不属于同一人中间用一个空格隔开。输出说明对于每个询问输出一行如果两人可以共舞输出一个大写字母‘Y’否则输出一个大写字母‘N’。#include stdio.h #include string.h typedef struct{ char name[20]; char id[10]; char xb; }Student; int main(){ int n; scanf(%d, n); Student stu[n]; for(int i 0; i n; i) scanf(%s %s %c, stu[i].name, stu[i].id, stu[i].xb); int m; scanf(%d, m); char a[20], b[20]; for(int i 0; i m; i){ scanf(%s %s, a, b); int x, y; for(int j 0; j n; j){ if(strcmp(a, stu[j].name) 0 || strcmp(a, stu[j].id) 0){ x j; break; } } for(int j 0; j n; j){ if(strcmp(b, stu[j].name) 0 || strcmp(b, stu[j].id) 0){ y j; break; } } if(stu[x].xb ! stu[y].xb) printf(Y\n); else printf(N\n); } return 0; }57班级排名作者: Turbo时间限制: 1s章节: 结构体问题描述达达在陶陶的影响下也对学习慢慢的产生了兴趣。他在每次考试之后都会追着老师问自己在班级的总名次是多少。考试一多老师也不耐烦了于是他给了达达所有人的成绩让他自己去算出自己的排名。可人太多了达达也无法立即算出来于是他想让你帮帮他。输入说明第一行为一个整数N代表班级的学生总数。接下来N行每行一个字符串代表一个学生的姓名第一行总是DaDa。接下来一行一个整数M代表一共有M次考试。每次考试有N行每行有以一个空格分隔的一个正整数S和一个字符串P代表名字为P的学生在这次考试中得了S分。N 100名字长度不超过30分数不超过100输出说明一共M行每行一个整数代表达达在班级里的排名排名是这一次考试过后的所有考试总分排名如果达达和别人并列达达总是排在前面。#include stdio.h #include string.h typedef struct{ char name[35]; int grade; }Student; int main(){ int n; scanf(%d, n); Student stu[n]; for(int i 0; i n; i){ scanf(%s, stu[i].name); stu[i].grade 0; } int m; scanf(%d, m); for(int i 0; i m; i){ for(int j 0; j n; j){ int grade; char name[35]; scanf(%d %s, grade, name); for(int k 0; k n; k){ if(strcmp(name, stu[k].name) 0){ stu[k].grade grade; break; } } } for(int j 0; j n - 1; j){ for(int k j 1; k n; k){ if(stu[j].grade stu[k].grade){ Student temp stu[j]; stu[j] stu[k]; stu[k] temp; } else if(stu[j].grade stu[k].grade){ if(strcmp(DaDa, stu[k].name) 0){ Student temp stu[j]; stu[j] stu[k]; stu[k] temp; } } } } int count 0; for(int j 0; j n; j){ count; if(strcmp(DaDa, stu[j].name) 0){ printf(%d\n, count); break; } } } return 0; }58铺地毯作者: Turbo时间限制: 1s章节: 结构体问题描述为了准备一个学生节组织者在会场的一片矩形区域可看做是平面直角坐标系的第一象限铺上一些矩形地毯。一共有n 张地毯编号从1 到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意在矩形地毯边界和四个顶点上的点也算被地毯覆盖。输入说明输入共 n2 行。第一行一个整数 n表示总共有n 张地毯。接下来的 n 行中第i1 行表示编号i 的地毯的信息包含四个正整数abgk每两个整数之间用一个空格隔开分别表示铺设地毯的左下角的坐标ab以及地毯在x轴和y 轴方向的长度。第 n2 行包含两个正整数x 和y表示所求的地面的点的坐标xy。0≤n≤10,0000≤a, b, g, k≤100,000。输出说明输出共 1 行一个整数表示所求的地毯的编号若此处没有被地毯覆盖则输出-1。#include stdio.h typedef struct { int a; // 左下角x坐标 int b; // 左下角y坐标 int g; // x轴方向长度 int k; // y轴方向长度 } Carpet; int main() { int n; scanf(%d, n); Carpet carpets[10005]; // n最大10000 for (int i 1; i n; i) { scanf(%d %d %d %d, carpets[i].a, carpets[i].b, carpets[i].g, carpets[i].k); } int x, y; scanf(%d %d, x, y); int result -1; // 初始化为-1表示没有被覆盖 // 从后往前遍历地毯因为后铺的在上层 for (int i n; i 1; i--) { // 检查点(x,y)是否在地毯i内 if (x carpets[i].a x carpets[i].a carpets[i].g y carpets[i].b y carpets[i].b carpets[i].k) { result i; break; // 找到最上面的地毯直接退出 } } printf(%d\n, result); return 0; }59最小乘积作者: Turbo时间限制: 1s章节: 枚举问题描述给两组数各n个。请调整每组数的排列顺序使得两组数据相同下标元素对应相乘然后相加的和最小。要求程序输出这个最小值。例如两组数分别为:1 3 -5和-2 4 1那么对应乘积取和的最小值应为(-5) * 4 3 * (-2) 1 * 1 -25输入说明第一个行一个数T表示数据组数。后面每组数据先读入一个n接下来两行每行n个数每个数的绝对值小于等于1000。n8,T1000输出说明一个数表示答案。#include stdio.h #include stdlib.h // 比较函数用于升序排序 int cmp_asc(const void* a, const void* b) { return *(int*)a - *(int*)b; } // 比较函数用于降序排序 int cmp_desc(const void* a, const void* b) { return *(int*)b - *(int*)a; } int main() { int T; scanf(%d, T); while (T--) { int n; scanf(%d, n); int a[10], b[10]; // n 8 // 读取数组a for (int i 0; i n; i) { scanf(%d, a[i]); } // 读取数组b for (int i 0; i n; i) { scanf(%d, b[i]); } // 对数组a进行升序排序 qsort(a, n, sizeof(int), cmp_asc); // 对数组b进行降序排序 qsort(b, n, sizeof(int), cmp_desc); // 计算最小乘积和 long long sum 0; // 用long long防止溢出 for (int i 0; i n; i) { sum (long long)a[i] * b[i]; } printf(%lld\n, sum); } return 0; }60排队打水问题作者: Turbo时间限制: 1s章节: 贪心问题描述有n个人排队到r个水龙头去打水他们装满水桶的时间t1、t2………..tn为整数且各不相等应如何安排他们的打水顺序才能使他们总共花费的时间最少输入说明第一行nr (n500,r75)第二行为n个人打水所用的时间Ti (Ti100)输出说明最少的花费时间#include stdio.h int main(){ int n, r; scanf(%d %d, n, r); int time[n]; for(int i 0; i n; i) scanf(%d, time[i]); //按打水时间从小到大排序 for(int i 0; i n - 1; i){ for(int j i 1; j n; j){ if(time[i] time[j]){ int temp time[i]; time[i] time[j]; time[j] temp; } } } int taps[r]; for(int i 0; i r; i) taps[i] 0; int total_time 0; //给每个人分配水龙头 for(int i 0; i n; i){ //找当前时间最短的水龙头 int min_tap 0; for(int j 1; j r; j){ if(taps[j] taps[min_tap]) min_tap j; } //把这个人分配到该水龙头 taps[min_tap] time[i]; total_time taps[min_tap]; } printf(%d\n, total_time); return 0; }66王、后传说作者: turbo时间限制: 1s章节: 递归问题描述地球人都知道在国际象棋中后如同太阳光芒四射威风八面它能控制横、竖、斜线位置。看过清宫戏的中国人都知道后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围但也总能找到相安无事的办法。所有中国人都知道皇权神圣伴君如伴虎触龙颜者死......现在有一个n*n的皇宫国王占据他所在位置及周围的共9个格子这些格子皇后不能使用如果国王位于王宫的边缘占用的格子可能不到9个。当然皇后也不会攻击国王。现在知道了皇宫的规模n国王的位置x,y国王位于第x行第y列行和列号从1开始请问有多少种方案放置n个皇后使她们不能互相攻击同一横线、竖线、斜线上只能有一个皇后。输入说明输入仅一行包含三个整数表示皇宫的规模nn12及国王的位置x和y坐标。输出说明一个整数表示放置n个皇后的方案数#include stdio.h #include stdlib.h #define MAX_N 15 int n, x, y; int count 0; // 方案数 int board[MAX_N][MAX_N]; // 棋盘0表示可放置1表示皇后-1表示国王占据 // 检查当前位置是否可以放置皇后 int is_safe(int row, int col) { // 检查同一列 for (int i 0; i row; i) { if (board[i][col] 1) { return 0; } } // 检查左上对角线 for (int i row - 1, j col - 1; i 0 j 0; i--, j--) { if (board[i][j] 1) { return 0; } } // 检查右上对角线 for (int i row - 1, j col 1; i 0 j n; i--, j) { if (board[i][j] 1) { return 0; } } return 1; } // 深度优先搜索放置皇后 void dfs(int row) { if (row n) { // 所有行都放置了皇后 count; return; } // 尝试在当前行的每一列放置皇后 for (int col 0; col n; col) { // 如果这个位置不是国王占据的且可以安全放置 if (board[row][col] ! -1 is_safe(row, col)) { board[row][col] 1; // 放置皇后 dfs(row 1); // 处理下一行 board[row][col] 0; // 回溯 } } } int main() { scanf(%d %d %d, n, x, y); // 调整坐标题目中行列从1开始我们转换为从0开始 x--; // 行号-1 y--; // 列号-1 // 初始化棋盘 for (int i 0; i n; i) { for (int j 0; j n; j) { board[i][j] 0; } } // 标记国王占据的位置国王所在及周围8个格子 for (int i x - 1; i x 1; i) { for (int j y - 1; j y 1; j) { if (i 0 i n j 0 j n) { board[i][j] -1; // 标记为国王占据 } } } // 开始DFS搜索 dfs(0); printf(%d\n, count); return 0; }68FBI树作者: Turbo时间限制: 1s章节: 深度优先搜索问题描述我们可以把由“0”和“1”组成的字符串分为三类全“0”串称为B串全“1”串称为I串既含“0”又含“1”的串则称为F串。FBI树是一种二叉树它的结点类型也包括F结点B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T递归的构造方法如下1)T的根结点对应的内容为S因此其类型与串S的类型相同2)若串S的长度大于1将串S从中间分开分为等长的左右子串S1和S2由左子串S1构造左子树T1由右子串S2构造右子树T2。现在给定一个长度为2N的“01”串请用上述构造方法构造出一棵FBI树并输出它的后序遍历序列。输入说明第一行是一个整数N0 N 10第二行是一个长度为2N的“01”串。输出说明包括一行这一行只包含一个字符串即FBI树的后序遍历序列。#include stdio.h #include string.h #include stdlib.h char str[1025]; // 2^10 1024加上结束符 int length; // 判断字符串类型 char get_type(int left, int right) { int has_zero 0, has_one 0; for (int i left; i right; i) { if (str[i] 0) { has_zero 1; } else if (str[i] 1) { has_one 1; } // 如果既包含0又包含1可以直接返回F if (has_zero has_one) { return F; } } if (has_zero) return B; if (has_one) return I; return B; // 实际上不会执行到这里 } // 递归构建FBI树并后序遍历 void build_and_traverse(int left, int right) { // 只有一个字符的情况 if (left right) { printf(%c, str[left] 0 ? B : I); return; } // 计算中间位置 int mid (left right) / 2; // 后序遍历左子树 - 右子树 - 根 build_and_traverse(left, mid); // 遍历左子树 build_and_traverse(mid 1, right); // 遍历右子树 // 输出根节点类型 printf(%c, get_type(left, right)); } int main() { int N; scanf(%d, N); scanf(%s, str); length strlen(str); // 递归构建并后序遍历 build_and_traverse(0, length - 1); printf(\n); return 0; }79无重叠区间作者: Turbo时间限制: 1s章节: 贪心问题描述给定一个区间的集合找到需要移除区间的最小数量使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”但没有相互重叠。示例 1:输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1解释: 移除 [1,3] 后剩下的区间没有重叠。示例 2:输入: [ [1,2], [1,2], [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:输入: [ [1,2], [2,3] ]输出: 0解释: 你不需要移除任何区间因为它们已经是无重叠的了。输入说明首先输入区间集合的大小n(n20000)然后输入n行每行2个整数表示区间的起始和结束。输出说明输出一个整数#include stdio.h #include stdlib.h typedef struct { int start; int end; } Interval; // 比较函数按结束时间升序排序 int cmp(const void* a, const void* b) { Interval* interval_a (Interval*)a; Interval* interval_b (Interval*)b; if (interval_a-end ! interval_b-end) { return interval_a-end - interval_b-end; } return interval_a-start - interval_b-start; } int main() { int n; scanf(%d, n); Interval intervals[n]; for (int i 0; i n; i) { scanf(%d %d, intervals[i].start, intervals[i].end); } // 按结束时间升序排序 qsort(intervals, n, sizeof(Interval), cmp); int count 0; // 选择的不重叠区间数量 int last_end -1; // 上一个选择的区间的结束时间 for (int i 0; i n; i) { // 如果当前区间的开始时间 上一个选择区间的结束时间 // 说明不重叠选择当前区间 if (intervals[i].start last_end) { count; last_end intervals[i].end; } // 否则当前区间与上一个区间重叠不选择 } // 需要移除的区间数量 总区间数 - 选择的不重叠区间数 printf(%d\n, n - count); return 0; }70排列问题作者: Turbo时间限制: 1s章节: 深度优先搜索问题描述求一个0N-1的排列即每个数只能出现一次给出限制条件一张N*N的表第i行第j列的1或0表示为j这个数能不能出现在i这个数后面并保证表中的第i行第i列为0i和j都从0开始将这个排列看成一个自然数求从小到大排序第K个排列。样例输入3 20 1 11 0 00 1 0样例输出1 0 2解释对于N3的没有任何限制的排列如下第一0 1 2第二0 2 1第三1 0 2第四1 2 0第五2 0 1第六2 1 0根据题目所给的限制条件由于2不能出现在1后面0不能出现在2后面第一0 2 1第二1 0 2第三2 1 0输入说明第一行为N和K,接下来的N行每行N个数0表示不能1表示能N10K500000输出说明所求的排列#include stdio.h #include string.h int n, k; int matrix[12][12]; // 限制矩阵 int used[12]; // 标记数字是否已使用 int path[12]; // 当前排列路径 int count 0; // 计数器 int found 0; // 是否找到结果 // 深度优先搜索生成排列 void dfs(int depth) { if (found) return; // 如果已经找到结果直接返回 if (depth n) { // 找到一个完整排列 count; if (count k) { found 1; // 输出结果 for (int i 0; i n; i) { printf(%d, path[i]); if (i n - 1) printf( ); } printf(\n); } return; } for (int i 0; i n; i) { if (!used[i]) { // 数字i未被使用 // 检查限制条件 if (depth 0 || matrix[path[depth - 1]][i] 1) { used[i] 1; path[depth] i; dfs(depth 1); used[i] 0; if (found) return; } } } } int main() { scanf(%d %d, n, k); // 读取限制矩阵 for (int i 0; i n; i) { for (int j 0; j n; j) { scanf(%d, matrix[i][j]); } } // 初始化 memset(used, 0, sizeof(used)); memset(path, 0, sizeof(path)); // 深度优先搜索 dfs(0); return 0; }90拉丁正方形作者: xxx时间限制: 1s章节: 深度优先搜索问题描述一种正方形的数字编排1 2 3 4 52 1 4 5 33 4 5 1 24 5 2 3 15 3 1 2 4是一个5*5的拉丁正方形每个1到5的整数在每行每列都出现且出现一次。写个程序计算N*N的的拉丁正方形的总数且要求第一行是 1 2 3 4 5.......N输入说明一行包含一个整数N( 2 N 7)输出说明只有一行表示拉丁正方形的个数且拉丁正方形的第一行为 1 2 3 . . . N.#include stdio.h int n; int count 0; int square[8][8]; // 拉丁方n≤7索引从1开始 int row_used[8][8]; // row_used[i][num]第i行是否已使用数字num int col_used[8][8]; // col_used[j][num]第j列是否已使用数字num // 深度优先搜索 void dfs(int row, int col) { if (row n) { // 所有行都填完了 count; return; } if (col n) { // 当前行填完了填下一行 dfs(row 1, 2); // 第1列固定为1,2,3...n return; } // 尝试所有可能的数字 for (int num 1; num n; num) { // 检查数字是否可用 if (!row_used[row][num] !col_used[col][num]) { // 放置数字 square[row][col] num; row_used[row][num] 1; col_used[col][num] 1; // 递归填充下一个位置 dfs(row, col 1); // 回溯 row_used[row][num] 0; col_used[col][num] 0; } } } int main() { scanf(%d, n); // 初始化第一行固定为1,2,3,...,n for (int j 1; j n; j) { square[1][j] j; row_used[1][j] 1; col_used[j][j] 1; } // 初始化第一列固定为1,2,3,...,n for (int i 2; i n; i) { square[i][1] i; row_used[i][i] 1; col_used[1][i] 1; } // 从(2,2)开始搜索 dfs(2, 2); printf(%d\n, count); return 0; }94最大值路径作者: Turbo时间限制: 1s章节: 宽度优先搜索问题描述有n阶方阵从矩阵的左下角元素为起点从行或列向右或向上两个方向上移动直到右上角。求出有多少条路径可以使得经过的元素累加值最大最大值是多少。例以下矩阵的最大值是47走的路线其中之一是545665466输入说明首先输入n2n10然后输入n行n列方阵元素每个元素都是整数。输出说明输出一行为两个空格分隔的整数第一个表示最大值路径的条数第二个表示最大值。#include stdio.h #include stdlib.h int n; int matrix[12][12]; // 存储矩阵 long long dp[12][12]; // dp[i][j]从起点到(i,j)的最大路径和 long long cnt[12][12]; // cnt[i][j]从起点到(i,j)的最大路径和的数量 int main() { scanf(%d, n); // 读取矩阵 for (int i 1; i n; i) { for (int j 1; j n; j) { scanf(%d, matrix[i][j]); } } // 初始化起点是左下角 (n,1) dp[n][1] matrix[n][1]; cnt[n][1] 1; // 初始化最左边一列只能向上走 for (int i n-1; i 1; i--) { dp[i][1] dp[i1][1] matrix[i][1]; cnt[i][1] 1; // 只有一条路径 } // 初始化最下面一行只能向右走 for (int j 2; j n; j) { dp[n][j] dp[n][j-1] matrix[n][j]; cnt[n][j] 1; // 只有一条路径 } // 动态规划计算其他位置 for (int i n-1; i 1; i--) { for (int j 2; j n; j) { // 可以从下面(i1,j)或左边(i,j-1)过来 long long from_below dp[i1][j]; long long from_left dp[i][j-1]; if (from_below from_left) { dp[i][j] from_below matrix[i][j]; cnt[i][j] cnt[i1][j]; } else if (from_below from_left) { dp[i][j] from_left matrix[i][j]; cnt[i][j] cnt[i][j-1]; } else { // 相等 dp[i][j] from_below matrix[i][j]; cnt[i][j] cnt[i1][j] cnt[i][j-1]; } } } // 结果是右上角 (1,n) printf(%lld %lld\n, cnt[1][n], dp[1][n]); return 0; }