For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end up at the number 6174 -- the black hole of 4-digit numbers. This number is named Kaprekar Constant.
For example, start from 6767, we'll get:
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...Given any 4-digit number, you are supposed to illustrate the way it gets into the black hole.
Input Specification:
Each input file contains one test case which gives a positive integer N in the range (.
Output Specification:
If all the 4 digits of N are the same, print in one line the equation N - N = 0000. Else print each step of calculation in a line until 6174 comes out as the difference. All the numbers must be printed as 4-digit numbers.
Sample Input 1:
6767Sample Output 1:
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174Sample Input 2:
2222Sample Output 2:
2222 - 2222 = 0000
#include<cstdio> #include<algorithm> using namespace std; bool cmp(int a,int b){ return a > b; } void toarray(int n,int num[]){ for(int i=0;i<4;i++){ num[i] = n%10; n /= 10; } } int tonumber(int num[]){ int sum = 0; for(int i=0;i<4;i++){ sum = sum*10 + num[i]; } return sum; } int main(){ int n; scanf("%d",&n); int num[5]; while(1){ int max1,min1; toarray(n,num); sort(num,num+4); min1 = tonumber(num); sort(num,num+4,cmp); max1 = tonumber(num); n = max1 - min1; printf("%04d - %04d = %04d ",max1,min1,n); if(n==6174 || n==0){ break; } } return 0; }
Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence { 0.1, 0.2, 0.3, 0.4 }, we have 10 segments: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) and (0.4).
Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N, the size of the sequence which is no more than 1. The next line contains N positive numbers in the sequence, each no more than 1.0, separated by a space.
Output Specification:
For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.
Sample Input:
4
0.1 0.2 0.3 0.4Sample Output:
5.00
#include<cstdio> int main(){ int n; scanf("%d",&n); double v,ans = 0; for(int i=1;i<=n;i++){ scanf("%lf",&v); ans += v * i *(n + 1 -i); } printf("%.2f ",ans); return 0; }
The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.
For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.
Input Specification:
Each input file contains one test case. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100.
Output Specification:
For each test case, print the total time on a single line.
Sample Input:
3 2 3 1Sample Output:
41#include<cstdio> int main(){ int n; scanf("%d",&n); int now=0,to; int ans=0; for(int i=0;i<n;i++){ scanf("%d",&to); if(to > now){ ans += (to - now) * 6; }else{ ans += (now - to) * 4; } ans += 5; now = to; } printf("%d ",ans); return 0; }
The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's in 1, 10, 11, and 12.
Input Specification:
Each input file contains one test case which gives the positive N (≤).
Output Specification:
For each test case, print the number of 1's in one line.
Sample Input:
12Sample Output:
5#include<cstdio> int main(){ int n; scanf("%d",&n); int left,now,right; int ans = 0; int a = 1; while(n/a!=0){ left = n / (a*10); now = n / a %10; right = n % a; if(now == 0) ans += left * a; else if(now == 1) ans += left * a + right + 1; else ans += (left+1)*a; a*=10; } printf("%d ",ans); return 0; }
5.3 分数的四则运算
Given N rational numbers in the form numerator/denominator, you are supposed to calculate their sum.
Input Specification:
Each input file contains one test case. Each case starts with a positive integer N (≤), followed in the next line N rational numbers a1/b1 a2/b2 ... where all the numerators and denominators are in the range of long int. If there is a negative number, then the sign must appear in front of the numerator.
Output Specification:
For each test case, output the sum in the simplest form integer numerator/denominator where integer is the integer part of the sum, numerator < denominator, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.
Sample Input 1:
5
2/5 4/15 1/30 -2/60 8/3Sample Output 1:
3 1/3Sample Input 2:
2
4/3 2/3Sample Output 2:
2Sample Input 3:
3
1/3 -1/6 1/8Sample Output 3:
7/24#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; struct Fraction{ ll up; ll down; }; ll gcd(int a,int b){ if(b==0) return a; else return gcd(b,a%b); } Fraction reduction(Fraction result){ if(result.down < 0){ result.up = -result.up; result.down = - result.down; } if(result.up == 0){ result.down = 1; }else{ int d = gcd(abs(result.up),abs(result.down)); result.up /= d; result.down /= d; } return result; } Fraction add(Fraction f1,Fraction f2){ Fraction result; result.up = f1.up * f2.down + f2.up*f1.down; result.down = f1.down * f2.down; return reduction(result); } void showResult(Fraction r){ r = reduction(r); if(r.down == 1){ printf("%lld",r.up); }else if(abs(r.up) > r.down){ printf("%d %d/%d",r.up/r.down,abs(r.up) % r.down,r.down); }else{ printf("%d/%d",r.up,r.down); } } int main(){ int n; scanf("%d",&n); Fraction temp,sum; sum.up = 0; sum.down = 1; for(int i=0;i<n;i++){ scanf("%lld/%lld",&temp.up,&temp.down); sum = add(sum,temp); } showResult(sum); return 0; }
For two rational numbers, your task is to implement the basic arithmetics, that is, to calculate their sum, difference, product and quotient.
Input Specification:
Each input file contains one test case, which gives in one line the two rational numbers in the format a1/b1 a2/b2. The numerators and the denominators are all in the range of long int. If there is a negative sign, it must appear only in front of the numerator. The denominators are guaranteed to be non-zero numbers.
Output Specification:
For each test case, print in 4 lines the sum, difference, product and quotient of the two rational numbers, respectively. The format of each line is number1 operator number2 = result. Notice that all the rational numbers must be in their simplest form k a/b, where k is the integer part, and a/b is the simplest fraction part. If the number is negative, it must be included in a pair of parentheses. If the denominator in the division is zero, output Inf as the result. It is guaranteed that all the output integers are in the range of long int.
Sample Input 1:
2/3 -4/2Sample Output 1:
2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)Sample Input 2:
5/3 0/6Sample Output 2:
1 2/3 + 0 = 1 2/3
1 2/3 - 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; ll gcd(ll a,ll b){ if(b == 0) return a; else{ return gcd(b,a%b); } } struct Fraction{ ll up,down; }a,b; Fraction reduction(Fraction result){ if(result.down < 0){ result.up = -result.up; result.down = - result.down; } if(result.up == 0){ result.down = 1; }else{ int d = gcd(abs(result.up),abs(result.down)); result.up /= d; result.down /= d; } return result; } Fraction add(Fraction f1,Fraction f2){ Fraction result; result.up = f1.up * f2.down + f2.up*f1.down; result.down = f1.down * f2.down; return reduction(result); } Fraction minu(Fraction f1,Fraction f2){ Fraction result; result.up = f1.up * f2.down - f2.up*f1.down; result.down = f1.down * f2.down; return reduction(result); } Fraction multi(Fraction f1,Fraction f2){ Fraction result; result.up = f1.up * f2.up; result.down = f1.down * f2.down; return reduction(result); } Fraction divide(Fraction f1,Fraction f2){ Fraction result; result.up = f1.up * f2.down; result.down = f1.down * f2.up; return reduction(result); } void showResult(Fraction r){ r = reduction(r); if(r.up < 0) printf("("); if(r.down == 1){ printf("%lld",r.up); }else if(abs(r.up) > r.down){ printf("%d %d/%d",r.up/r.down,abs(r.up) % r.down,r.down); }else{ printf("%d/%d",r.up,r.down); } if(r.up < 0){ printf(")"); } } int main(){ scanf("%lld/%lld %lld/%lld",&a.up,&a.down,&b.up,&b.down); //加法 showResult(a); printf(" + "); showResult(b); printf(" = "); showResult(add(a,b)); printf(" "); //减法 showResult(a); printf(" - "); showResult(b); printf(" = "); showResult(minu(a,b)); printf(" "); //乘法 showResult(a); printf(" * "); showResult(b); printf(" = "); showResult(multi(a,b)); printf(" "); //除法 showResult(a); printf(" / "); showResult(b); printf(" = "); if(b.up == 0) printf("Inf"); else showResult(divide(a,b)); printf(" "); return 0; }
PAT B1007 素数对猜想 (20分)
让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<)，请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20输出样例:
4#include<cstdio> #include<cmath> bool isPrime(int a){ if(a<=1) return false; int sqr = (int)sqrt(a*1.0); for(int i=2;i<=sqr;i++){ if(a % i==0) return false; } return true; } int main(){ int n; int count = 0; scanf("%d",&n); for(int i=3;i+2<=n;i=i+2){ if(isPrime(i)==true && isPrime(i+2)){ count++; } } printf("%d ",count); return 0; }
PAT B1013 数素数 (20分)
令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤104，请输出 PM 到 PN 的所有素数。
输入格式：
输入在一行中给出 M 和 N，其间以空格分隔。
输出格式：
输出从 PM 到 PN 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。
输入样例：
5 27输出样例：
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103#include<cstdio> #include<cmath> const int maxn = 10010; long long prime[maxn]; bool isPrime(int a){ for(int i=2;i<=sqrt(a);i++){ if(a % i == 0){ return false; } } return true; } int main(){ int m,n; scanf("%d%d",&m,&n); int num = 1; for(int i=2;num<=n;i++){ if(isPrime(i)==true){ prime[num++] = i; } } int count=0; for(int i=m;i<=n;i++){ printf("%d",prime[i]); count++; if(count %10!=0 && i<n) printf(" "); else printf(" "); } return 0; }
A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.
Now given any two positive integers N (<) and D (1), you are supposed to tell if N is a reversible prime with radix D.
Input Specification:
The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.
Output Specification:
For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.
Sample Input:
73 10
23 2
23 10
-2Sample Output:
Yes
Yes
No#include<cstdio> #include<cmath> bool isPrime(int a){ if(a<=1) return false; int sqr = (int)sqrt(1.0*a); for(int i=2;i<=sqr;i++){ if(a%i == 0) return false; } return true; } int main(){ int num[110]; int n,radix; while(scanf("%d",&n)!=EOF){ if(n<0) break; else{ scanf("%d",&radix); if(isPrime(n) != true){ printf("No "); }else{ int len = 0; do{ num[len++] = n%radix; n /= radix; }while(n != 0); for(int i=0;i<len;i++){ n = n*radix + num[i]; } if(isPrime(n)==true){ printf("Yes "); }else{ printf("No "); } } } } return 0; }
The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be ( where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (≤) and N (≤) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print "-" instead.
Sample Input:
4 4
10 6 4 15Sample Output:
0 1 4 -#include<cstdio> #include<cmath> bool isPrime(int n){ if(n<=1){ return false; } int sqr = (int)sqrt(n * 1.0); for(int i=2;i<=sqr;i++){ if(n % i == 0){ return false; } } return true; } int main(){ int m; scanf("%d",&m); while(isPrime(m)!=true){ m++; } int n; scanf("%d",&n); bool hashtable[10010]={0}; for(int i=0;i<n;i++){ int temp; scanf("%d",&temp); int pos = temp % m; if(hashtable[pos]==false){ hashtable[pos] = true; if(i==0) printf("%d",pos); else printf(" %d",pos); }else{ int step; for(step=1;step<m;step++){ pos = (temp + step*step)%m; if(hashtable[pos]==false){ hashtable[pos] = true; if(i==0) printf("%d",pos); else printf(" %d",pos); break; } } if(step>=m){ if(i>0) printf(" "); printf("-"); } } } return 0; }
Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.
Input Specification:
Each input file contains one test case, which gives the integer N (1<N<).
Output Specification:
For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format factor[1]*factor[2]*...*factor[k], where the factors are listed in increasing order, and 1 is NOT included.
Sample Input:
630Sample Output:
3
5*6*7 #include<cstdio> #include<cmath> typedef long long LL; int main(){ LL n; scanf("%lld",&n); LL sqr = (LL)sqrt(1.0*n); LL ansI=0,ansLen=0; for(int i=2;i<=sqr;i++){ LL temp = 1,j=i; while(1){ temp *= j; if(n%temp != 0) break; if(j-i+1>ansLen){ ansI = i; ansLen = j - i + 1; } j++; } } if(ansLen==0){ printf("1 %lld",n); }else{ printf("%d ",ansLen); for(int i=0;i<ansLen;i++){ printf("%lld",ansI+i); if(i< ansLen - 1){ printf("*"); } } } return 0; }
本题要求计算 /，其中 A 是不超过 1000 位的正整数，B 是 1 位正整数。你需要输出商数 Q 和余数 R，使得 A=B×Q+R 成立。
输入格式：
输入在一行中依次给出 A 和 B，中间以 1 空格分隔。
输出格式：
在一行中依次输出 Q 和 R，中间以 1 空格分隔。
输入样例：
123456789050987654321 7输出样例：
17636684150141093474 3
#include<cstdio> #include<cstring> struct bign{ int num[1010]; int len; }; bign change(char str[]){ bign temp; temp.len = 0; int slen = strlen(str); for(int i=0;i<slen;i++){ temp.num[i] = str[slen-1-i]-'0'; temp.len++; } return temp; } bign divide(bign a,int b,int &r){ bign c; c.len = a.len; for(int i=a.len -1;i>=0;i--){ r = r*10 + a.num[i]; if(r < b) c.num[i] = 0; else{ c.num[i] = r/b; r = r%b; } } while(c.len - 1 >= 1 && c.num[c.len - 1] ==0){ c.len--; } return c; } void showresult(bign n){ for(int i=n.len-1;i>=0;i--){ printf("%d",n.num[i]); } } int main(){ char str[1010]; scanf("%s",str); int n,r=0; scanf("%d",&n); bign a,b; a = change(str); b = divide(a,n,r); showresult(b); printf(" %d",r); return 0; }
Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!
Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.
Input Specification:
Each input contains one test case. Each case contains one positive integer with no more than 20 digits.
Output Specification:
For each test case, first print in a line "Yes" if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or "No" if not. Then in the next line, print the doubled number.
Sample Input:
1234567899Sample Output:
Yes
2469135798 #include<cstdio> #include<cstring> struct bign{ int d[22]; int len; bign(){ memset(d,0,sizeof(d)); len = 0 ; } }; bign change(char str[]){ bign temp; temp.len = strlen(str); for(int i=0;i<temp.len;i++){ temp.d[i] = str[temp.len-i-1]-'0'; } return temp; } bign multi(bign a,int b){ bign c; int carry = 0; for(int i=0;i<a.len;i++){ int temp = a.d[i] * b + carry; c.d[c.len++] = temp % 10; carry = temp / 10; } while(carry != 0){ c.d[c.len++] = carry%10; carry /=10; } return c; } void showresult(bign n){ for(int i=n.len - 1;i>=0;i--){ printf("%d",n.d[i]); } } bool Judge(bign a,bign b){ if(a.len!=b.len){ return false; } int count[10]={0}; for(int i=0;i<a.len;i++){ count[a.d[i]]++; count[b.d[i]]--; } for(int i=0;i<10;i++){ if(count[i]!=0) return false; } return true; } int main(){ char str[22]; scanf("%s",str); bign a = change(str); bign doublea = multi(a,2); if(Judge(a,doublea)==true){ printf("Yes "); showresult(doublea); }else{ printf("No "); showresult(doublea); } return 0; }
Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!
Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.
Input Specification:
Each input contains one test case. Each case contains one positive integer with no more than 20 digits.
Output Specification:
For each test case, first print in a line "Yes" if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or "No" if not. Then in the next line, print the doubled number.
Sample Input:
1234567899Sample Output:
Yes
2469135798
#include<cstdio> #include<cstring> struct bign{ int d[22]; int len; bign(){ memset(d,0,sizeof(d)); len = 0; } }; bign change(char str[]){ bign c; c.len = strlen(str); for(int i=c.len-1;i>=0;i--){ c.d[i] = str[c.len-i-1]-'0'; } return c; } bign multi(bign a,int b){ bign c; int carry = 0; for(int i=0;i<a.len;i++){ int temp = a.d[i]*b + carry; c.d[c.len++] = temp%10; carry = temp/10; } while(carry!=0){ c.d[c.len++] = carry%10; carry /= 10; } return c; } bool Judge(bign a,bign b){ if(a.len != b.len){ return false; } int count[10]={0}; for(int i=0;i<a.len;i++){ count[a.d[i]]++; count[b.d[i]]--; } for(int i=0;i<10;i++){ if(count[i]!=0) return false; } return true; } void showresult(bign a){ for(int i=a.len-1;i>=0;i--){ printf("%d",a.d[i]); } } int main(){ char str[22]; scanf("%s",str); bign a = change(str); bign b = multi(a,2); if(Judge(a,b)==true){ printf("Yes "); showresult(b); }else{ printf("No "); showresult(b); } return 0; }
A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.
Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.
Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.
Input Specification:
Each input file contains one test case. Each case consists of two positive numbers N and K, where N (≤) is the initial numer and K (≤) is the maximum number of steps. The numbers are separated by a space.
Output Specification:
For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.
Sample Input 1:
67 3Sample Output 1:
484
2Sample Input 2:
69 3Sample Output 2:
1353
3#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct bign{ int d[1000]; int len; bign(){ memset(d,0,sizeof(d)); len = 0; } }; bign change(char str[]){ bign c; c.len = strlen(str); for(int i=c.len-1;i>=0;i--){ c.d[i] = str[c.len-1-i]-'0'; } return c; } bign add(bign a,bign b){ bign c; int carry = 0; for(int i=0;i<a.len || i<b.len;i++){ int temp = a.d[i] + b.d[i] + carry; c.d[c.len++] = temp%10; carry = temp/10; } if(carry!=0){ c.d[c.len++] = carry; } return c; } bool Judge(bign a){ for(int i=0;i<=a.len-1;i++){ if(a.d[i]!=a.d[a.len-i-1]) return false; } return true; } void show(bign c){ for(int i=c.len-1;i>=0;i--){ printf("%d",c.d[i]); } printf(" "); } int main(){ char str[1000]; scanf("%s",str); int n; scanf("%d",&n); bign a = change(str); int count = 0; while(count < n && Judge(a)==false){ bign b = a; reverse(b.d,b.d + b.len); a = add(a,b); count++; } show(a); printf("%d",count); return 0; }