Lyft Level 5 Challenge 2018

A. King Escape

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, x[3], y[3];
 5 
 6 int f1(int X, int Y)
 7 {
 8     return X - Y - x[2] + y[2];
 9 }
10 
11 int f2(int X, int Y)
12 {
13     return x[2] + y[2] - X - Y;
14 }
15 
16 bool ok()
17 {
18     //if (f1(x[0], y[0]) * f1(x[1], y[1]) < 0) return false;
19     //if (f2(x[0], y[0]) * f2(x[1], y[1]) < 0) return false;
20     if (x[0] > x[1]) swap(x[0], x[1]);
21     if (y[0] > y[1]) swap(y[0], y[1]);
22     if (y[2] >= y[0] && y[2] <= y[1]) return false;
23     if (x[2] >= x[0] && x[2] <= x[1]) return false;
24     return true;
25 }
26 
27 int main()
28 {
29     while (scanf("%d", &n) != EOF)
30     {
31         scanf("%d%d", x + 2, y + 2);
32         for (int i = 0; i < 2; ++i) 
33             scanf("%d%d", x + i, y + i);
34         puts(ok() ? "YES" : "NO");
35     }
36     return 0;
37 }

View Code

B. Square Difference

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 int t; ll a, b;
 6 
 7 bool ok(ll x)
 8 {
 9     ll limit = sqrt(x);
10     for (ll i = 2; i <= limit && i < x; ++i)
11         if (x % i == 0)
12             return false;
13     return true;
14 }
15 
16 int main()
17 {
18     scanf("%d", &t);
19     while (t--)
20     {
21         scanf("%lld%lld", &a, &b);
22         if (a - b != 1) puts("NO");
23         else
24             puts(ok(a + b) ? "YES" : "NO");
25     }
26     return 0;
27 }

View Code

C. Permutation Game

Solved.

题意：

$A和B玩游戏，一个人能从i移动到j$

$当且仅当a[i] < a[j] 并且|i - j| equiv 0 pmod a[i]$

$判断以每个数为下标作起点,A先手能否必胜$

思路：

我们考虑一个位置什么时候必败

$它下一步没有可移动的位置$
$它的下一步状态没有一处是必败态$

倒着处理出每个位置的状态即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 int n, a[N], ans[N], pos[N];
 6 
 7 int main()
 8 {
 9     while (scanf("%d", &n) != EOF)
10     {
11         for (int i = 1; i <= n; ++i) scanf("%d", a + i), pos[a[i]] = i;
12         for (int i = n; i >= 1; --i)
13         {
14             int id = pos[i];
15             bool flag = 0;
16             for (int j = id - i; j >= 1; j -= i)
17                 if (a[j] > i && ans[a[j]] == 0)
18                 {
19                     flag = 1;
20                     break;
21                 }
22             if (flag == 0) for (int j = id + i; j <= n; j += i)
23                 if (a[j] > i && ans[a[j]] == 0)
24                 {
25                     flag = 1;
26                     break;
27                 }
28             ans[i] = flag; 
29         }
30         for (int i = 1; i <= n; ++i) 
31             putchar(ans[a[i]] ? 'A' : 'B');
32         puts("");
33     }
34     return 0;
35 }

View Code

D. Divisors

Upsolved.

题意：

给出一些$a_i, 求 prod a_i 的因子个数$

$保证a_i 有3-5个因数$

思路：

对一个数求因子个数假设它质因数分解之后是$n = p_1^{t_1} cdot p_2^{t_2} cdots p_n^{t_n}$

那么因子个数就是$(t_1 + 1) cdot (t_2 + 1) cdots (t_n + 1)$

我们考虑什么样的数有$3-5个因数$

$平方数、立方数、四次方数、n = p cdot q (p, q 是不同的质数)$

$对于前三类数，可以暴力破出，考虑第四类$

$如果它的p, q在序列中是唯一的，那么我们不需要管它具体是多少$

$直接得到p, q的数量就是这个数的数量$

$否则，拿这个数和别的数作gcd就可以破出p, q$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 1010
 6 const ll MOD = (ll)998244353;
 7 int n; ll a[N];
 8 map <ll, int> mp, num;  
 9 
10 void work(ll a)
11 {
12     ll limit = pow(a, 1.0 / 4);
13     for (ll i = limit + 10; i >= limit - 10 && i >= 1; --i)
14         if (i * i * i * i == a)
15         {
16             mp[i] += 4;
17             return;
18         }
19     limit = pow(a, 1.0 / 3);
20     for (ll i = limit + 10; i >= limit - 10 && i >= 1; --i)
21         if (i * i * i == a)
22         {
23             mp[i] += 3;
24             return;
25         }
26     limit = pow(a, 1.0 / 2);
27     for (ll i = limit + 10; i >= limit - 10 && i >= 1; --i)
28         if (i * i == a)
29         {
30             mp[i] += 2;
31             return;
32         }
33     ++num[a]; 
34 }
35 
36 ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
37 
38 int main()
39 {
40     while (scanf("%d", &n) != EOF) 
41     {
42         mp.clear(); num.clear(); 
43         for    (int i = 1; i <= n; ++i)
44         {
45             scanf("%lld", a + i);
46             work(a[i]);
47         }
48         ll res = 1;  
49         for (auto it : num)
50         {
51             ll tmp;
52             bool flag = true;
53             for (int i = 1; i <= n; ++i) 
54                 if (a[i] != it.first && (tmp = gcd(it.first, a[i])) != 1)
55                 {
56                     mp[tmp] += it.second;
57                     mp[it.first / tmp] += it.second; 
58                     flag = false;
59                     break;
60                 }
61             if (flag) res = (res * (it.second + 1) % MOD * (it.second + 1)) % MOD;
62         }
63         for (auto it : mp)
64             res = (res * (it.second + 1)) % MOD;
65         printf("%lld
", res);
66         fflush(stdout);
67     }
68     return 0;
69 }

View Code