ACM试题及答案 猪的安家
Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。这回Andy建造了5个猪圈，但是仍然有1头猪没有地方去，然后Andy又建造了7个猪圈，但是还有2头没有地方去。Andy都快疯了。你对这个事情感兴趣起来，你想通过Andy建造猪圈的过程，知道Andy家至少养了多少头猪。 输入
输入包含多组测试数据。每组数据第一行包含一个整数n (n <= 10) – Andy建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi <= ai <= 1000), 表示Andy建立了ai个猪圈，有bi头猪没有去处。你可以假定(ai, aj) = 1. 输出
输出包含一个正整数，即为Andy家至少养猪的数目。 样例输入 3 3 1 5 1 7 2 样例输出 16
答案:
// 猪的安家.cpp : Defines the entry point for the console application. //
#include \#include \
void main() {
int n;
int s[10][2]; bool r[10]; char ch;
cout<<\请输入次数：\ cin>>n;
for (int i=0;i cout<<\请输入第\次的猪圈个数和剩下的猪：（用--分开）\ cin>>s[i][0]>>ch>>ch>>s[i][1]; } for (i=0;i<10;i++) r[i]=true; for (int sum=1;;sum++) { for (i=0;i r[i]=(sum%s[i][0]==s[i][1]); for (i=0;i if (r[i]==0) break; } if (i==n) break; } cout<<\猪至少有\只。\ } 蛇行矩阵 Problem 蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。 Input 本题有多组数据，每组数据由一个正整数N组成。（N不大于100） Output 对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。 矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。 Sample Input 5 Sample Output 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 答案: //SNAKE 矩阵 //////////////////////////////////////////////////////////////////////////////// #define M 100 int main() { int a[M][M]; int n; printf(\请输入N的值：\\n\ scanf(\ if(n <= 0) return 0; printf(\形成的蛇形矩阵为：\\n\ a[0][0] = 1;//因为每次第一个数必是1 printf(\ for(int i=0;i a[i+1][0] = a[i][0] + i + 1;//提前算出下一行的第一个数据 for(int j=0;j a[i][j+1] = a[i][j] + j + i + 2;//算出每一行的每个数据 printf(\打印每一行的数据 } printf(\打印下一行的第一个数据 } printf(\ return 0; } 平方数 给出包含M个数字的列表，和列表中所有数字的所有质因数。求出最长的子列表，使得子列表中所有数字的乘积是一个完全平方数。 输入 输入文件包含多组测试数据。第一行包含两个整数N , M ( 1 <= N <= 30 , 1 <= M <= 30000 ). N 是质因数的个数。接下来一行有N个整数，给出所有的质因数。然后一行包含M个整数，给出列表。 输入文件结束于N = M = 0. 输出 对于每组数据，输出最长子列表的两个位置坐标l r。l是该子列表在列表中的起始位置，r是结束位置。如果多种情况都满足子列表长度最大，输出l最小的一个。如果不存在这样的子列表输出“None”。 样例输入 3 4 2 3 5 4 9 25 6 3 4 2 3 5 6 6 3 3 0 0 样例输出 1 3 1 4 答案: #include using namespace std; #define MAX_N 30 #define MAX_M 30000 void squareNumber(int *A,int *B,int N,int M); void main() { int A[MAX_N]; int B[MAX_M]; int N,M; cin>>N>>M; int i; while (N!=0||M!=0) { for (i=0;i cin>>A[i]; } for (i=0;i cin>>B[i]; } squareNumber(A,B,N,M); cin>>N>>M; } } void squareNumber(int *A,int *B,int N,int M) { int i,j,k,t; bool flag; int num[MAX_N]={0}; int temp=1; int len_max=0; int r=0; int f=0; for (i=0;i for (j=i+1+len_max;j<=M;j++) { for (k=0;k num[k]=0; } for (k=i;k temp=B[k]; while (temp!=1) { flag=false; for (t=0;t if (temp%A[t]==0) { temp/=A[t]; num[t]++; flag=true; } } if (!flag)