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<2^{31}). ...
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 H(key)=key%TSize 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. ...
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 (≤100), 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. ...
一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A0 A1 ⋯A N−1 ）变换为（A N−M ⋯A N−1 A 0 A 1⋯A N−M−1 ）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？ ...
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 (≤230). Output Specification: For each test case, print the number of 1’s in one line. ...
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。 得到“答案正确”的条件是： 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符； 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串； 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。 现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。 输入格式： 每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。 输出格式： 每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。 输入样例： 8 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA 输出样例： YES YES YES YES NO NO NO NO 思路 可以找到这样的规律：正确的字符串应该遵循 P 左侧的 A 个数乘 P 与 T 中间的 A 个数等于 T 右侧的 A 个数。且 P 和 T 的个数必须为1，中间 A 的个数不能为 0，除了 P，A，T 的其他的字符个数必须为 0。 #include <cstdio> #include <cstring> const int maxn = 101; int main() { int n, len; scanf("%d", &n); char str[maxn]; for (int i = 0; i < n; i++) { scanf("%s", str); len = strlen(str); int PNum = 0, TNum = 0, otherNum = 0, PIndex, TIndex; for (int j = 0; j < len; j++) { if (str[j] == 'P') { PNum++; PIndex = j; } else if (str[j] == 'T') { TNum++; TIndex = j; } else if (str[j] != 'A') { otherNum++; } } if (PNum != 1 || TNum != 1 || otherNum != 0 || (TIndex - PIndex) <= 1) { printf("NO\n"); continue; } int leftA = PIndex, midA = TIndex - PIndex - 1, rightA = len - TIndex - 1; if (leftA * midA == rightA) { printf("YES\n"); } else { printf("NO\n"); } } 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. ...
There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition? For example, given N=5 and the numbers 1, 3, 2, 4, and 5. We have: ...
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number. Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given. Input Specification: Each input file contains one test case. Each case occupies a line which contains 4 positive integers: ...
Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively. Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence. Input Specification: Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤10^5) is the number of integers in the sequence, and p (≤ 10^9 ) is the parameter. In the second line there are N positive integers, each is no greater than 10^9. ...