A problem of sorting
Problem Description
There are many people's name and birth in a list.Your task is to print the name from young to old.(There is no pair of two has the same age.)
Input
First line contains a single integer T≤100 which denotes the number of test cases.
For each test case, there is an positive integer n(1≤n≤100) which denotes the number of people,and next n lines,each line has a name and a birth's year(1900-2015) separated by one space.
The length of name is positive and not larger than 100.Notice name only contain letter(s),digit(s) and space(s).
Output
For each case, output n lines.
Sample Input
2
1
FancyCoder 1996
2
FancyCoder 1996
xyz111 1997
Sample Output
FancyCoder
xyz111
FancyCoder
Source
题目类型：简单字符串处理
算法分析：一次将一整行都读入进来，然后从后向前将年份和名字分离开来，最后直接排序输出答案即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r #define CPPFF ifstream cin ("aaa.txt") #define CFF freopen ("aaa.txt", "r", stdin) #define LL long long #define ULL unsigned long long const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int MOD = 1e9 + 7; const int maxn = 1000 + 66; struct node { string s; int v; }; node aa[maxn]; bool cmp (node a, node b) { return a.v > b.v; } int PP (string &s) { int sum = 0, wei = 1; for (int i = s.size () - 1; i >= s.size () - 4; i--) { sum += (s[i] - '0') * wei; wei *= 10; } return sum; } string TT (string &s) { string res; for (int i = 0; i <= s.size () - 6; i++) res += s[i]; return res; } int main() { // CPPFF; int t; cin >> t; while(t--) { int n; cin >> n; string ss; cin.ignore (); for (int i = 1; i <= n; i++) { getline (cin, ss); aa[i].v = PP (ss); aa[i].s = TT (ss); } sort (aa + 1, aa + 1 + n, cmp); for (int i = 1; i <= n; i++) cout << aa[i].s << endl; } return 0; } |
B The Factor
Problem Description
There is a sequence of n positive integers. Fancycoder is addicted to learn their product, but this product may be extremely huge! However, it is lucky that FancyCoder only needs to find out one factor of this huge product: the smallest factor that contains more than 2 factors（including itself; i.e. 4 has 3 factors so that it is a qualified factor）. You need to find it out and print it. As we know, there may be none of such factors; in this occasion, please print -1 instead.
Input
The first line contains one integer T (1≤T≤15), which represents the number of testcases.
For each testcase, there are two lines:
1. The first line contains one integer denoting the value of n (1≤n≤100).
2. The second line contains n integers a1,…,an (1≤a1,…,an≤2×109), which denote these n positive integers.
Output
Print T answers in T lines.
Sample Input
2
3
1 2 3
5
6 6 6 6 6
Sample Output
6
4
Source
题目类型：素因子分解
算法分析：直接将输入的数进行素因子分解，最后进行一次排序。如果len的长度大于等于2，则有解，且解就是最小的两个数的乘积。否则无解。注意合数有小于等于其根号值的素因子，但是输入的数可能是一个素数！！！所以直接使用factor[i]表示素数i的个数是会RE的~~
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r #define CPPFF ifstream cin ("aaa.txt") #define CFF freopen ("aaa.txt", "r", stdin) #define LL long long #define ULL unsigned long long const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int MOD = 1e9 + 7; const int maxn = 60000 + 66; LL factor[maxn], len; void Get (LL val) { for (LL i = 2; i * i <= val; i++) { while (val % i == 0) { factor[len++] = i; val /= i; } } if(val > 1) factor[len++] = val; } int main() { // CPPFF; int t; cin >> t; while (t--) { int n; cin >> n; memset (factor, 0, sizeof (factor)); len = 0; for (LL i = 1; i <= n; i++) { LL val; cin >> val; Get (val); } sort (factor, factor + len); if (len >= 2) { LL res = 1; res *= factor[0]; res *= factor[1]; cout << res << endl; } else cout << "-1" << endl; } return 0; } |
C Geometric Progression
Problem Description
Determine whether a sequence is a Geometric progression or not.
In mathematics, a **geometric progression**, also known as a **geometric sequence**, is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. For example, the sequence 2, 6, 18, 54, ... is a geometric progression with common ratio 3. Similarly 10, 5, 2.5, 1.25, ... is a geometric sequence with common ratio 1/2.
Examples of a geometric sequence are powers rk of a fixed number r, such as 2k and 3k. The general form of a geometric sequence is
a, ar, ar2, ar3, ar4, …
where r ≠ 0 is the common ratio and a is a scale factor, equal to the sequence's start value.
Input
First line contains a single integer T(T≤20) which denotes the number of test cases.
For each test case, there is an positive integer n(1≤n≤100) which denotes the length of sequence,and next line has n nonnegative numbers Ai which allow leading zero.The digit's length of Ai no larger than 100.
Output
For each case, output "Yes" or "No".
Sample Input
4
1
0
3
1 1 1
3
1 4 2
5
16 8 4 2 1
Sample Output
Yes
Yes
No
Yes
Source
题目类型：高精度计算
算法分析：首先全零数列是可以的，然后对于非全零数列，使用a[i] * a[i]是否等于a[i-1] * a[i+1]来判断，注意这里要额外判断a[i]是否等于0！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
package supermaker; import java.io.*; import java.math.*; import java.util.*; import java.text.*; public class Main { public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub // FileInputStream fis = new FileInputStream(new File("aaa.txt")); // System.setIn(fis); Scanner cin = new Scanner(new BufferedInputStream(System.in)); BigDecimal[] aa = new BigDecimal[166]; int t; t = cin.nextInt(); for (int i = 1; i <= t; i++) { int n; n = cin.nextInt(); for (int j = 1; j <= n; j++) { aa[j] = cin.nextBigDecimal(); } if (n == 1) System.out.println("Yes"); else if (n == 2) { if (aa[1].compareTo(BigDecimal.valueOf(0)) == 0 && aa[2].compareTo(BigDecimal.valueOf(0)) != 0 || aa[1].compareTo(BigDecimal.valueOf(0)) != 0 && aa[2].compareTo(BigDecimal.valueOf(0)) == 0) System.out.println("No"); else System.out.println("Yes"); } else { boolean is_zero = true; for (int j = 1; j <= n; j++) { if (aa[j].compareTo(BigDecimal.valueOf(0)) != 0) { is_zero = false; break; } } if (is_zero == true) System.out.println ("Yes"); else { BigDecimal vala, valb; boolean is_valid = true; for (int j = 2; j <= n - 1; j++) { vala = aa[j].multiply(aa[j]); valb = aa[j-1].multiply(aa[j+1]); if (vala.compareTo(valb) != 0 || aa[j].compareTo(BigDecimal.valueOf(0)) == 0) { is_valid = false; break; } } if (is_valid) System.out.println ("Yes"); else System.out.println ("No"); } } } } } |
D Reflect
Problem Description
We send a light from one point on a mirror material circle,it reflects N times and return the original point firstly.Your task is calcuate the number of schemes.
Input
First line contains a single integer T(T≤10) which denotes the number of test cases.
For each test case, there is an positive integer N(N≤106).
Output
For each case, output the answer.
Sample Input
14
Sample Output
4
Source
题目类型：欧拉函数求解
算法分析：如果选择一个发射器与水平方向的角度a，则圆心角转过的角度是2a。为了使得经过n次反射之后光线还能回来，需要满足2a * (n + 1) = 2 * k * PI。化简得a = k / (n + 1) * PI，此时只要找到合适的k，使得a是一个最简分数即可，这个问题转换成了求解1~n+1中与n+1互素的数的个数，直接打出euler函数表，查询即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 66; LL euler[maxn]; void Get () { for (LL i = 1; i < maxn; i++) euler[i] = i; for (LL i = 2; i < maxn; i += 2) euler[i] >>= 1; for (LL i = 3; i < maxn; i += 2) { if (euler[i] == i) { for (LL j = 1; j * i < maxn; j++) euler[j*i] = euler[j*i] - euler[j*i] / i; } } } int main() { // CPPFF; Get (); int t; cin >> t; while (t--) { int n; cin >> n; cout << euler[n+1] << endl; } return 0; } |
- « 上一篇：HihoCoder挑战赛14(2/4)
- xdu1076：下一篇 »