2018 IEEE极限编程大赛题解

去年742，今年72，也算一种小小的进步。

明年前30（笑

1. Drawing Rooted Binary Trees

给定一个树的中序和前序的遍历，要求输出这棵树（包括空格的）

 1 #include <iostream>//
 2 #include <string.h>//
 3 #include <stdio.h>//
 4 #include <stdlib.h>//
 5 #include <math.h>//
 6 #include <string.h>//
 7 #include <vector>//STL vetor
 8 #include <list>//STL list
 9 #include <map>// STL map
10 #include <queue>// STL queue
11 #include <set>// STL set
12 #include <stack>//sTL stack
13 #include <bitset>//bitset
14 #include <algorithm>//STL
15 #include <numeric>//
16 #include <functional>//STL
17 #include <limits.h>//
18 #include <fstream>
19 using namespace std;
20 typedef int LL;
21 int Tr[30][4];
22 int n;
23     char z[30];
24     char q[30];
25 int D;
26 int w;
27 int DFS(int L,int R,int x,int d){
28     int i;
29     Tr[ q[x]-'a' ][3]=d;
30     int xx=x;
31    // printf("%d %d %c %d xx=%d,w=%d
",L,R,q[x],d,x,w);
32     if (L==R){
33         D=max(D,d);
34         Tr[q[x]-'a'][0]=Tr[q[x]-'a'][1]='@';
35         Tr[q[x]-'a'][2]=w;
36         w++;
37         return x;
38     }
39     for (i=L;i<=R;i++){
40         if (z[i]==q[x]) break;
41     }
42     if (i!=L){
43         Tr[q[x]-'a'][0]=q[x+1];
44         x++;
45         x=DFS(L,i-1,x,d+1);
46     }else{
47         Tr[q[x]-'a'][0]='@';
48     }
49     Tr[q[xx]-'a'][2]=w;
50     w++;
51     if (i!=R){
52         Tr[ q[xx]-'a'][1]=q[x+1];
53         x=DFS(i+1,R,x+1,d+1);
54     }else{
55         Tr[q[xx]-'a'][1]='@';
56     }
57     return x;
58 }
59 char Out[30];
60 int main(){
61 
62     while(scanf("%s%s",z,q)!=EOF){
63     n=strlen(z);
64     D=1;
65     w=0;
66     DFS(0,n-1,0,1);
67     //printf("%d
",D);
68       //  for (int j=0;j<n;j++){printf("%c L=%c R=%c %d D=%d
",q[j],Tr[ q[j]-'a' ][0], Tr[ q[j]-'a' ][1],Tr[ q[j]-'a' ][2],Tr[ q[j]-'a' ][3]); }
69     for (int i=1;i<=D;i++){
70         for (int j=0;j<n;j++){ Out[j]=' ';}
71         Out[n]=0;
72         for (int j=0;j<n;j++){
73             if ( Tr[ q[j]-'a' ][3]==i  ){
74                 Out[ Tr[q[j]-'a' ][2]  ]=q[j];
75             }
76         }
77         printf("%s
",Out);
78     }
79     }
80     return 0;
81 }

2. Barter System

Standard input

The first line of the input is an integer

The next line contains another integer

Standard output

For each of the

It can be shown that $Y^{-1} ( ext{mod} 998244353)X⋅Y−1 (mod 998244353).$$

If the exchange rate can not be computed using the given information, print -1.

Constraints and notes

$10^41≤N,Q≤2⋅104$$
All exchange rates are consistent

  1 #pragma GCC optimize(3)
  2 #include <bits/stdc++.h>
  3 #include <unordered_map>
  4 using namespace std;
  5 
  6 const double EPS = 1e-9;
  7 const int INF = 2147483647;
  8 const int LLINF = 9223372036854775807;
  9 const double PI = acos(-1.0);
 10 
 11 #define     REP(i, a, b)  for(int i = (a); i < (b); i++)
 12 #define     PER(i, a, b)  for(int i = (a); i > (b); i--)
 13 #define     FOREACH(i,t)  for(typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
 14 #define     NEED_CLOCK    printf("Time: %f
",double(clock())/CLOCKS_PER_SEC)
 15 #define     MP(x, y)      make_pair(x, y)
 16 #define     PB(x)         push_back(x)
 17 #define     SET(a)        memset(a,-1,sizeof(a))
 18 #define     CLR(a)        memset(a,0,sizeof(a));
 19 #define     MEM(a,x)      memset(a,x,sizeof(a)) 
 20 #define     ALL(x)        begin(x),end(x)
 21 #define     LL            long long
 22 #define     Lson          (index * 2)
 23 #define     Rson          (index * 2 + 1)
 24 #define     pii           pair< int, int >
 25 #define     pll           pair< LL, LL >
 26 #define     MAXN          21000+5
 27 
 28 template< class T > inline T _abs(T a) { return a >= 0 ? a : -a; }
 29 template< class T > inline T sqr(T a) { return a*a; }
 30 template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % b)); }
 31 template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b))*(b)); }
 32 template< class T > inline T lowbit(T x) { return x&-x; }
 33 
 34 inline int READ() {
 35     char ch;
 36     while ((ch = getchar()) < 48 || 57 < ch);
 37     int ans = ch - 48;
 38     while (48 <= (ch = getchar()) && ch <= 57) 
 39         ans = (ans << 3) + (ans << 1) + ch - 48;
 40     return ans;
 41 }
 42 ///************************************START**************************************///
 43 const long long MOD = 998244353;
 44 int pre[MAXN];
 45 LL dis[MAXN];
 46 int findSet(int x) {
 47     if (pre[x] == x)return x;
 48     if (x < 0)return -1;
 49     int ths = pre[x];
 50     int rhs = findSet(pre[x]);
 51     if (ths >= 0 && rhs >= 0)
 52         pre[x] = rhs;
 53     dis[x] = (dis[x] * dis[ths]) % MOD;
 54     return rhs;
 55 }
 56 LL poww(LL x, LL n)
 57 {
 58     LL res = 1;
 59     while (n > 0)
 60     {
 61         if (n % 2 == 1)
 62         {
 63             res = res*x;
 64             res = res%MOD;
 65         }
 66         x = x*x;
 67         x = x%MOD;
 68         n >>= 1;
 69     }
 70     return res;
 71 }
 72 LL inv(LL x) {
 73     return poww(x, MOD - 2);
 74 }
 75 string s1, s2;
 76 unordered_map<string, int>mp;
 77 int main() {
 78     int n; scanf("%d", &n);
 79     //MEM(dis, 1);
 80     for (int i = 0; i < n+100; i++){
 81         pre[i] = i;
 82         dis[i] = 1;
 83     }
 84     int id = 1;
 85     while (n--) {
 86         LL rate;
 87         cin >> s1 >> s2 >> rate;
 88         if (mp.find(s1)==mp.end())mp[s1] = id++;
 89         if (mp.find(s2)==mp.end())mp[s2] = id++;
 90         int fx = findSet(mp[s1]), fy = findSet(mp[s2]);
 91         dis[fy] = (1ll * (dis[mp[s1]] * rate) % MOD*inv(dis[mp[s2]])) % MOD;
 92         pre[fy] = fx;
 93     }
 94     int q; scanf("%d", &q);
 95     while (q--) {
 96         cin >> s1 >> s2;
 97         if (s1 == s2) {
 98             printf("1
");
 99             continue;
100         }
101         if (mp.find(s1) == mp.end() || mp.find(s2) == mp.end()) {
102             printf("-1
");
103             continue;
104         }
105         int fx = findSet(mp[s1]), fy = findSet(mp[s2]);
106         if (fx != fy) {
107             printf("-1
");
108             continue;
109         }
110         else {
111             printf("%lld
", (dis[mp[s2]] * inv(dis[mp[s1]])) % MOD);
112         }
113     }
114     return 0;
115 }

3. Troll Coder

You have found a huge treasure on an island, but the only access point to that island is a bridge guarded by a giant Troll! In order to cross the bridge, you have to guess a sequence of

Interaction

Your program must exchange information with the Troll by submitting queries and reading answers.

Note that you must flush the buffer so that the output reaches the Troll. Here we ilustrate it for several languages.

At the beginning of each test case, the Troll will give you a single integer

To submit a query, your program should output the letter Q followed by a space and by a binary sequence of length

Constraints and notes

This task is NOT adaptive
Your program can submit at most

 1 #include<iostream>
 2 using namespace std;
 3 int a[110];
 4 int n,cnt,tmp;
 5 int flip(int &num){
 6     if(num==0){
 7         num=1;
 8         return 1;
 9     }else{
10         num=0;
11         return 0;
12     }
13 }
14 int main()
15 {
16     cin>>n;
17     cout<<"Q ";
18     for(int i=0;i<n-1;++i){
19         a[i]=0;
20         cout<<a[i]<<" ";
21     }
22     a[n-1]=0;
23     cout<<a[n-1]<<endl;
24     cin>>cnt;
25     if(cnt==n){
26         cout<<"A ";
27         for(int i=0;i<n-1;++i){
28             cout<<a[i]<<" ";
29         }
30         cout<<a[n-1]<<endl;
31     }else if(cnt==0){
32         cout<<"A ";
33         for(int i=0;i<n-1;++i){
34             cout<<flip(a[i])<<" ";
35         }
36         cout<<flip(a[n-1])<<endl;
37     }else{
38         for(int i=0;i<n;++i){
39             cout<<"Q ";
40             for(int j=0;j<n-1;++j){
41                 if(i!=j) cout<<0<<" ";
42                 else cout<<1<<" ";
43             }
44             if(i!=n-1) cout<<0<<endl;
45             else cout<<1<<endl;
46             cin>>tmp;
47             if(tmp>cnt){
48                 a[i]=1;
49             }
50         }
51         cout<<"A ";
52         for(int i=0;i<n-1;++i){
53             cout<<a[i]<<" ";
54         }
55         cout<<a[n-1]<<endl;
56 
57     }
58     return 0;
59 }

4. Xtreme Fake Coins

Help IBM research's puzzlemaster to verify solutions for May 2018's challenge.

There are

Find all counterexamples of two pairs of coins

Standard input

The first line contains two comma separated integers,

The next

There always is an equal amount of coins on both sides.

Standard output

List of lexicographically ordered counterexamples for the solution.

Each of them consists of two letters, an = sign and then another two letters.

A counterexample is a set of two pairs that cannot be distinguished by the set of

Constraints and notes

The counterexamples should be formed using only the first

  1 #pragma GCC optimize(3)
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 
  5 const double EPS = 1e-9;
  6 const int INF = 2147483647;
  7 const int LLINF = 9223372036854775807;
  8 const double PI = acos(-1.0);
  9 
 10 #define     REP(i, a, b)  for(int i = (a); i < (b); i++)
 11 #define     PER(i, a, b)  for(int i = (a); i > (b); i--)
 12 #define     FOREACH(i,t)  for(typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
 13 #define     NEED_CLOCK    printf("Time: %f
",double(clock())/CLOCKS_PER_SEC)
 14 #define     MP(x, y)      make_pair(x, y)
 15 #define     PB(x)         push_back(x)
 16 #define     SET(a)        memset(a,-1,sizeof(a))
 17 #define     CLR(a)        memset(a,0,sizeof(a));
 18 #define     MEM(a,x)      memset(a,x,sizeof(a)) 
 19 #define     ALL(x)        begin(x),end(x)
 20 #define     LL            long long
 21 #define     Lson          (index * 2)
 22 #define     Rson          (index * 2 + 1)
 23 #define     pii           pair< int, int >
 24 #define     pll           pair< LL, LL >
 25 #define     MOD           ((int)1000000007)
 26 #define     MAXN          300000
 27 
 28 template< class T > inline T _abs(T a) { return a >= 0 ? a : -a; }
 29 template< class T > inline T sqr(T a) { return a*a; }
 30 template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % b)); }
 31 template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b))*(b)); }
 32 template< class T > inline T lowbit(T x) { return x&-x; }
 33 
 34 inline int READ() {
 35     char ch;
 36     while ((ch = getchar()) < 48 || 57 < ch);
 37     int ans = ch - 48;
 38     while (48 <= (ch = getchar()) && ch <= 57) 
 39         ans = (ans << 3) + (ans << 1) + ch - 48;
 40     return ans;
 41 }
 42 ///************************************START**************************************///
 43 string g[MAXN][2];
 44 string ans[MAXN][2];
 45 int n, m;
 46 char c[MAXN];
 47 
 48 vector<string>v;
 49 void generate() {
 50     for (int i = 0; i < n; i++) {
 51         for (int j = i + 1; j < n; j++) {
 52             string a;
 53             a.push_back('A' + i);
 54             a.push_back('A' + j);
 55             v.push_back(a);
 56         }
 57     }
 58     return;
 59 }
 60 
 61 int check(int k, string s) {
 62     int l0 = g[k][0].find(s[0]) == -1 ? 0 : 1;
 63     int r0 = g[k][1].find(s[0]) == -1 ? 0 : 1;
 64     int l1 = g[k][0].find(s[1]) == -1 ? 0 : 1;
 65     int r1 = g[k][1].find(s[1]) == -1 ? 0 : 1;
 66 
 67     int left = l0 + l1, right = r0 + r1;
 68     if (left == right)return 0;
 69     else if (left > right)return 1;
 70     else if (left < right)return 2;
 71 }
 72 
 73 int main() {
 74     scanf("%d,%d", &n, &m);
 75     generate();
 76 
 77     for (int i = 0; i < m; i++) {
 78         scanf("%s", c);
 79         int j = 0;
 80         string a, b;
 81         for (j = 0; j < strlen(c); j++) {
 82             if (c[j] != '-') a.push_back(c[j]);
 83             else break;
 84         }
 85         for (j += 1; j < strlen(c); j++) {
 86             b.push_back(c[j]);
 87         }
 88         g[i][0] = a;
 89         g[i][1] = b;
 90     }
 91 
 92     int cnt = 0;
 93     for (int i = 0; i < v.size(); i++) {
 94         for (int j = i + 1; j < v.size(); j++) {
 95             //cout << v[i] << " " << v[j] << endl;
 96             int flag = 1;
 97             for (int k = 0; k < m; k++) {
 98                 if (check(k, v[i]) != check(k, v[j])){
 99                     flag = 0;
100                     break;
101                 }
102             }
103             if (flag) {
104                 ans[cnt][0] = v[i];
105                 ans[cnt][1] = v[j];
106                 cnt++;
107             }
108         }
109     }
110 
111     for (int i = 0; i < cnt; i++) {
112         cout << ans[i][0] << '=' << ans[i][1] << endl;
113     }
114 
115     return 0;
116 }

5. Magic Spell

Write a program that gives the correct output for a legal input – to discover the correct function see the input/output examples.

Standard Input

The first line contains an integer

Standard output

Print the answer on the first line. It is guaranteed that it can be represented as a signed

 1 #include <iostream>//数据输入输出流
 2 #include <string.h>//字符串操作函数
 3 #include <stdio.h>//C的输入输出
 4 #include <stdlib.h>//定义杂项函数及内存分配函数
 5 #include <math.h>//C中的数学函数
 6 #include <string.h>//c++中的string类 他不能用strcpy等c函数去操作
 7 #include <vector>//STL vetor容器
 8 #include <list>//STL list
 9 #include <map>// STL map
10 #include <queue>// STL queue
11 #include <set>// STL set
12 #include <stack>//sTL stack
13 #include <bitset>//bitset可按位定义串//比如：bitset <1000> all;定义一个1000位的串
14 #include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
15 #include <numeric>//常用数字操作 一般和algorithm搭配使用
16 #include <functional>//STL定义运算函数（代替运算符）
17 #include <limits.h>//定义各种数据类型最值常量
18 #include <fstream>
19 #include <cstring>
20 using namespace std;
21 typedef int LL;
22 int a[20];
23 LL Get(char *s) {
24     if (strcasecmp(s, "xrtp") == 0) return 0ll;
25     if (strcasecmp(s, "pmr") == 0) return 1ll;
26     if (strcasecmp(s, "yep") == 0) return 2ll;
27     if (strcasecmp(s + 1, "jtrr") == 0) return 3ll;
28     if (strlen(s) == 4 && s[0] == 'g' &&s[1] == 'p') return 4ll;
29     if (strcasecmp(s, "gobr") == 0) return 5ll;
30     if (strlen(s) == 3 && s[0] == 'd' && s[1] == 'o') return 6ll;
31     if (strcasecmp(s, "drbrm") == 0) return 7ll;
32     if (strcasecmp(s, "rohjy") == 0) return 8ll;
33     if (strcasecmp(s, "momr") == 0) return 9ll;
34     if (strcasecmp(s, "yrm") == 0) return 10ll;
35     if (strcasecmp(s + 2, "rbrm") == 0) return 11ll;
36     if (strlen(s) == 6 && s[0] == 'y' &&s[1] == 'e'&&s[2] == 'r') return 12ll;
37     if (strlen(s) == 8 && s[1] == 'j' &&s[2] == 'o'&&s[3] == 't') return 13ll;
38     if (strlen(s) == 8 && s[0] == 'g' &&s[1] == 'p'&&s[3] == 't') return 14ll;
39     if (strlen(s) == 7 && s[0] == 'g' &&s[1] == 'o'&&s[2] == 'g') return 15ll;
40     return -1;
41 }
42 char s[1000];
43 char ss[1000];
44 string ns;
45 long long x, ans;
46 int n;
47 vector<vector<string> > v;
48 int main() {
49     /*scanf("%d", &n);
50     ans = 1ll;
51     for (int i = 0; i < n; i++) {
52         getline(cin, ns);
53         x = 0ll;
54         int Len = 0;
55         int j, cnt = 0;
56         puts(ss);
57         x = x * 16ll + Get(ss);
58         Len += strlen(ss);
59 
60         ans = ans*x;
61     }
62     printf("%lld
", ans);
63     return 0;*/
64 
65     int n; cin >> n;
66     ans = 1ll;
67     while (n--) {
68         vector<string> vt;
69         while (1) {
70             string s;
71             cin >> s;
72             vt.push_back(s);
73             if (getchar() == '
') break;
74         }
75         v.push_back(vt);
76     }
77     for (int i = 0; i < v.size();i++) {
78         x = 0ll;
79         for (int j = 0; j < v[i].size(); j++) {
80             for (int k = 0; k < v[i][j].size(); k++) {
81                 ss[k] = v[i][j][k];
82             }
83             ss[v[i][j].size()] = '';
84             x = x * 16ll + Get(ss);
85         }
86         ans *= x;
87     }
88     printf("%lld
", ans);
89     return 0;
90 }

6. Bear Sums

Mitsos the bear is challenging his brother Vangelis with a mathematical task. Mitsos provides a list of integers

Since Vangelis is a confident engineer, he decided to write a program that would do all the computations for him and skip the trouble of thinking. Your task is to help Vangelis write a program that reads the input list

Standard input

On the first line there will be an integer number

On the first line of each test case, there will be
On the second line, there will be

All values for the elements of list

Standard output

For each test case you will have to write one line that contains:

If there is an unique solution: Write two elements,
If there are multiple solutions: Pick the first complete pair that appears on the list and provides the correct sum. Print the two list elements forming this pair in increasing order, as above.
If there is no solution: Print the error message !OK.

Constraints and notes

$-10^6 < S < 10^6−106<S<106$
$10^40≤E≤2⋅104$
The sum of values of $10^7107$

  1 #pragma GCC optimize(3)
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 
  5 const double EPS = 1e-9;
  6 const int INF = 2147483647;
  7 const int LLINF = 9223372036854775807;
  8 const double PI = acos(-1.0);
  9 
 10 #define     REP(i, a, b)  for(int i = (a); i < (b); i++)
 11 #define     PER(i, a, b)  for(int i = (a); i > (b); i--)
 12 #define     FOREACH(i,t)  for(typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
 13 #define     NEED_CLOCK    printf("Time: %f
",double(clock())/CLOCKS_PER_SEC)
 14 #define     MP(x, y)      make_pair(x, y)
 15 #define     PB(x)         push_back(x)
 16 #define     SET(a)        memset(a,-1,sizeof(a))
 17 #define     CLR(a)        memset(a,0,sizeof(a));
 18 #define     MEM(a,x)      memset(a,x,sizeof(a)) 
 19 #define     ALL(x)        begin(x),end(x)
 20 #define     LL            long long
 21 #define     Lson          (index * 2)
 22 #define     Rson          (index * 2 + 1)
 23 #define     pii           pair< int, int >
 24 #define     pll           pair< LL, LL >
 25 #define     MOD           ((int)1000000007)
 26 #define     MAXN          20000+10
 27 
 28 template< class T > inline T _abs(T a) { return a >= 0 ? a : -a; }
 29 template< class T > inline T sqr(T a) { return a*a; }
 30 template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % b)); }
 31 template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b))*(b)); }
 32 template< class T > inline T lowbit(T x) { return x&-x; }
 33 
 34 inline int READ() {
 35     char ch;
 36     while ((ch = getchar()) < 48 || 57 < ch);
 37     int ans = ch - 48;
 38     while (48 <= (ch = getchar()) && ch <= 57) 
 39         ans = (ans << 3) + (ans << 1) + ch - 48;
 40     return ans;
 41 }
 42 ///************************************START**************************************///
 43 int ini[MAXN];
 44 struct node{
 45     int id, val;
 46     bool operator < (const node & rhs) const {
 47         return val < rhs.val || (val == rhs.val&&id < rhs.id);
 48     }
 49 }a[MAXN];
 50 
 51 struct fi{
 52     int p1, p2;
 53     bool operator < (const fi &rhs)const {
 54         return p2 < rhs.p2 || (p2 == rhs.p2&&p1 < rhs.p1);
 55     }
 56 }ans[MAXN];
 57 
 58 int lowbou(int l, int r, int tar){
 59     while (l <= r) {
 60         int mid = (l + r) / 2;
 61         if (a[mid].val < tar) l = mid + 1;
 62         else r = mid - 1;
 63     }
 64     return l;
 65 }
 66 
 67 int main() {
 68     int T; scanf("%d", &T);
 69     while (T--) {
 70         int sum, e; scanf("%d%d", &sum, &e);
 71         if (e == 0) {
 72             printf("!OK
");
 73             continue;
 74         }
 75         for (int i = 0; i < e; i++) {
 76             a[i].id = i;
 77             scanf("%d", &a[i].val);
 78             ini[i] = a[i].val;
 79         }
 80 
 81         sort(a, a + e);
 82         int cnt = 0;
 83         for (int i = 0; i < e; i++) {
 84             int need = sum - a[i].val;
 85             int pos = lowbou(0, e - 1, need);
 86             if (pos != e && a[pos].val == need && a[pos].id != a[i].id) {
 87                 ans[cnt] = { a[i].id,a[pos].id };
 88                 if (ans[cnt].p1 > ans[cnt].p2){
 89                     swap(ans[cnt].p1, ans[cnt].p2);
 90                 }
 91                 cnt++;
 92             }
 93         }
 94         if (cnt == 0) {
 95             printf("!OK
");
 96             continue;
 97         }
 98 
 99         sort(ans, ans + cnt);
100         //cout << ans[0].p1 << " " << ans[0].p2 << endl;
101         if (ini[ans[0].p1] > ini[ans[0].p2])
102             swap(ini[ans[0].p1], ini[ans[0].p2]);
103         printf("%d %d
", ini[ans[0].p1], ini[ans[0].p2]);
104         //cout << endl;
105     }
106     return 0;
107 }

7. Lemons

If life gives you lemon trees, make sure they have enough water!

Pantelis owns a small field of lemon trees on the foot of the Troodos mountain. He has chosen to grow his trees at this location mainly because Troodos mountain has a continuous source of fresh water for watering the trees. The water captured on the slopes, at high altitudes, flows under gravity via the stream and it is stored and distributed through an underground network of water pipes and water pumps.

Unfortunately, earlier this morning, Pantelis noticed that the flow of water from the water pump in his field is significantly reduced, and this will severely affect this season’s crop of lemons. Watering lemon trees is tricky. Too little or too much water and the tree will die. You should never let a lemon tree dry out completely for more than a day. Pantelis suspects that one of the water pumps on the channel has malfunctioned causing the water shortage. He needs to immediately determine which pump malfunctioned, notify maintenance in order to get it fixed and re-establish the regular water flow to his trees. Since the water runs in underground pipes he has no way of knowing if the flow is reduced in the pipes. He needs to climb the mountain and methodically check each of the water pumps for shortage in water levels in order to figure out which one is damaged.

There are

Pantelis needs to minimize the time needed to find the damaged water pump. Therefore, your program should find a plan to minimize the time to find the damaged water pump in the worst case scenario.

Standard input

The input consists of three space-separated integers

Standard output

The output consists of a single integer. The minimum worst-case time to find the damaged water pump.

Constraints and notes

$10^42≤N≤104$

 1 #include <iostream>//数据输入输出流
 2 #include <string.h>//字符串操作函数
 3 #include <stdio.h>//C的输入输出
 4 #include <stdlib.h>//定义杂项函数及内存分配函数
 5 #include <math.h>//C中的数学函数
 6 #include <string.h>//c++中的string类 他不能用strcpy等c函数去操作
 7 #include <vector>//STL vetor容器
 8 #include <list>//STL list
 9 #include <map>// STL map
10 #include <queue>// STL queue
11 #include <set>// STL set
12 #include <stack>//sTL stack
13 #include <bitset>//bitset可按位定义串//比如：bitset <1000> all;定义一个1000位的串
14 #include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
15 #include <numeric>//常用数字操作 一般和algorithm搭配使用
16 #include <functional>//STL定义运算函数（代替运算符）
17 #include<limits.h>//定义各种数据类型最值常量
18 #include <fstream>
19 using namespace std;
20 typedef int LL;
21 int main(){
22     int n,m,s;
23     scanf("%d%d%d",&n,&m,&s);
24     int now=1;
25     int End=n;
26     int Wgo=m;
27     int Wdo=s;
28     int step;
29     int ans=0;
30     while(now!=End){
31         step = (now+End)/2 + (now+End)%2;
32         ans+=(step-now)*Wgo+Wdo;
33         now=step;
34     }
35     printf("%d
",ans);
36     return 0;
37 }

8. Make Distinct

You are given an array of

Standard input

The first line contains an integer

The second line contains

Standard output

Print the answer on the first line.

Constraints and notes

$10^51≤N≤2⋅105$
$A_i leq N1≤Ai≤N for all valid ii$

  1 #pragma GCC optimize(3)
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 
  5 const double EPS = 1e-9;
  6 const int INF = 2147483647;
  7 const int LLINF = 9223372036854775807;
  8 const double PI = acos(-1.0);
  9 
 10 #define     REP(i, a, b)  for(int i = (a); i < (b); i++)
 11 #define     PER(i, a, b)  for(int i = (a); i > (b); i--)
 12 #define     FOREACH(i,t)  for(typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
 13 #define     NEED_CLOCK    printf("Time: %fMAXN",double(clock())/CLOCKS_PER_SEC)
 14 #define     MP(x, y)      make_pair(x, y)
 15 #define     PB(x)         push_back(x)
 16 #define     SET(a)        memset(a,-1,sizeof(a))
 17 #define     CLR(a)        memset(a,0,sizeof(a));
 18 #define     MEM(a,x)      memset(a,x,sizeof(a)) 
 19 #define     ALL(x)        begin(x),end(x)
 20 #define     LL            long long
 21 #define     Lson          (index * 2)
 22 #define     Rson          (index * 2 + 1)
 23 #define     pii           pair< int, int >
 24 #define     pll           pair< LL, LL >
 25 #define     MOD           ((int)1000000007)
 26 #define     MAXN          200000+5
 27 
 28 template< class T > inline T _abs(T a) { return a >= 0 ? a : -a; }
 29 template< class T > inline T sqr(T a) { return a*a; }
 30 template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % b)); }
 31 template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b))*(b)); }
 32 template< class T > inline T lowbit(T x) { return x&-x; }
 33 
 34 inline int READ() {
 35     char ch;
 36     while ((ch = getchar()) < 48 || 57 < ch);
 37     int ans = ch - 48;
 38     while (48 <= (ch = getchar()) && ch <= 57) 
 39         ans = (ans << 3) + (ans << 1) + ch - 48;
 40     return ans;
 41 }
 42 ///************************************START**************************************///
 43 int n, now;
 44 int a[MAXN], root[MAXN];
 45 int L[MAXN], R[MAXN], tot[MAXN];
 46 
 47 struct Ltree {
 48     int cnt;
 49     int l[MAXN], r[MAXN];
 50     int v[MAXN], Size[MAXN], d[MAXN];
 51     int merge(int x, int y) {
 52         if (x == 0 || y == 0)return x + y;
 53         if (v[x] < v[y])swap(x, y);
 54         r[x] = merge(r[x], y);
 55         Size[x] = Size[l[x]] + Size[r[x]] + 1;
 56         if (d[r[x]] > d[l[x]])swap(l[x], r[x]);
 57         d[x] = d[r[x]] + 1;
 58         return x;
 59     }
 60     inline int top(int x) {
 61         return v[x];
 62     }
 63     inline int size(int x) {
 64         return Size[x];
 65     }
 66     inline void pop(int &x) {
 67         x = merge(l[x], r[x]);
 68     }
 69     inline int new_heap(int x) {
 70         v[++cnt] = x;
 71         Size[cnt] = 1;
 72         l[cnt] = r[cnt] = d[cnt] = 0;
 73         return cnt;
 74     }
 75 }h;
 76 int check(LL ans) {
 77     while (ans) { int x = ans% 10; ans /= 10; }
 78     return 1;
 79 }
 80 int main() {
 81     LL ans = 0;
 82     scanf("%d", &n);
 83     for (int i = 1; i <= n; i++) {
 84         scanf("%d", &a[i]);
 85     }
 86     sort(a + 1, a + n + 1);
 87     for (int i = 1; i <= n; i++) {
 88         a[i] -= i;
 89     }
 90     for (int i = 1; i <= n; i++) {
 91         now++;
 92         root[now] = h.new_heap(a[i]);
 93         L[now] = i;
 94         R[now] = i;
 95         tot[now] = 1;
 96         while (now > 1) {
 97             if (h.top(root[now - 1]) <= h.top(root[now]))break;
 98             else {
 99                 now--;
100                 root[now] = h.merge(root[now], root[now + 1]);
101                 tot[now] += tot[now + 1];
102                 R[now] = R[now + 1];
103                 while (h.size(root[now]) * 2 > tot[now] + 1)
104                     h.pop(root[now]);
105             }
106         }
107     }
108     for (int i = 1; i <= now; i++) {
109         int t = h.top(root[i]);
110         for (int j = L[i]; j <= R[i]; j++) {
111             if(check(ans)) 
112                 ans += abs(a[j] - t);
113         }
114     }
115     cout << ans << endl;
116     return 0;
117 }

9. Telescope Scheduling

Time limit: 10000 ms
Memory limit: 256 MB

Joe and his friends want to observe the stars tonight using a unique telescope. Joe is an astronomy student and has a list of each of the stars that will be visible in the sky. Each star appears inside a certain time window with the possibility of multiple stars to overlap, so the group assigned a value to each star indicating the desirability of observing it.

The input consists on a list

a start time $S_iSi after which the star will be available for observation;$
a finish time $F_iFi after which the star will no longer be available;$
a positive integer $D_iDi indicating the desirability to see the ii-th star.$

In order to satisfy the desirability of seeing the $S_iSi to F_iFi (inclusive). Thus, two stars, ii and jj, are not simultaneously observable (i.e. they conflict) if the time interval [S_i,F_i][Si,Fi] intersects the time interval [S_j,F_j][Sj,Fj]. Given the list LL of time intervals of availability of the stars in the sky, the optimization problem is to schedule the observations in a non-conflicting way so as to maximize the total desirability of the observations that are included in the schedule.$

Standard input

The first line of the input contains a positive integer

Each of the following $(S_iSi) and finish (F_iFi) times of each star together with the desirability D_iDi of seeing that star.$

Standard output

Print the sum of the desirability of the stars included in the schedule on the first line.

Constraints and notes

$10^41≤N≤104$
$S_i,F_i leq 1 0000≤Si,Fi≤1 000$
$D_i leq 5 0001≤Di≤5 000$

 1 #include <iostream>//数据输入输出流
 2 #include <string.h>//字符串操作函数
 3 #include <stdio.h>//C的输入输出
 4 #include <stdlib.h>//定义杂项函数及内存分配函数
 5 #include <math.h>//C中的数学函数
 6 #include <string.h>//c++中的string类 他不能用strcpy等c函数去操作
 7 #include <vector>//STL vetor容器
 8 #include <list>//STL list
 9 #include <map>// STL map
10 #include <queue>// STL queue
11 #include <set>// STL set
12 #include <stack>//sTL stack
13 #include <bitset>//bitset可按位定义串//比如：bitset <1000> all;定义一个1000位的串
14 #include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
15 #include <numeric>//常用数字操作 一般和algorithm搭配使用
16 #include <functional>//STL定义运算函数（代替运算符）
17 #include<limits.h>//定义各种数据类型最值常量
18 #include <fstream>
19 using namespace std;
20 typedef int LL;
21 int dp[1003][1003];
22 
23 int main(){
24     int n,x,y,z;
25     scanf("%d",&n);
26     memset(dp,0,sizeof(dp));
27     int m=1000;
28     for (int i=0;i<n;i++){
29         scanf("%d%d%d",&x,&y,&z);
30         dp[x][y]=max(dp[x][y],z);
31         //m=max(m,y);
32     }
33     int R;
34     for (int len=2;len<=m+1;len++){
35         for (int L=0;L<=m-len+1;L++){
36             R=L+len-1;
37             for (int k=L;k<R;k++){
38                 dp[L][R]=max(dp[L][R],dp[L][k]+dp[k+1][R]);
39             }
40         }
41     }
42     printf("%d
",dp[0][m]);
43     return 0;
44 }

10. Xplore

Time limit: 5000 ms
Memory limit: 256 MB

Click here to learn more about Xplore API

The IEEE Xplore Application Programming Interface (API) is an efficient data delivery vehicle for content indexing/discovery as well as text and data mining of IEEE metadata content of academic publications. Loading a database/repository using the content delivered by the IEEE API can be subsequently used to draw domain/subject relationships, data analytics, and various other use cases for researchers. To learn more about the IEEE Xplore API please visit developer.ieee.org and register for an API key. All participants of the IEEEXtreme 12.0 competition will have access to the IEEE API during and after the competition, for a limited period of time, to discover its research utility potential.

A useful metric commonly associated with academic publishing is the h-index. An author with an index of

For this challenge, write a program that reads a set of

Standard input

The input will consist of an integer

Each entry will follow a format described in the Xplore API website: developer.ieee.org/docs/read/Metadata_API_responses

Standard output

Print the authors ranked by their h-index followed by a space and by the h-index itself. The authors should be ranked alphabetically if there are ties.

Constraints and notes

 1 import json
 2 class data:
 3     def __init__(self, name, num):
 4         self.name = name
 5         self.num = num
 6 
 7 n=int(input())
 8 l=list()
 9 while n>0:
10     s=str(input())
11     json_data=json.loads(s)
12     l.append(json_data)
13     n=n-1
14 
15 name=list()
16 cite_num=list()
17 for i in range(len(l)):
18     l2=l[i]['authors']['authors']
19     for j in range(len(l2)):
20         name.append(l2[j]['full_name'])
21         cite_num.append(l[i]['citing_paper_count'])
22 
23 d={}
24 for i in range(len(name)):
25     if name[i] in d:
26        l=d[name[i]]
27        l.append(cite_num[i])
28        d[name[i]]=l
29     else:
30        l=list()
31        l.append(cite_num[i])
32        d[name[i]]=l
33 
34 d2={}
35 for key in d:
36     l3=d[key]
37     l3.sort(reverse=True)
38     h_index=0
39     for i in range(len(l3)):
40         if l3[i]>=i+1:
41             h_index=h_index+1
42     d2[key]=-1*h_index
43 
44 tmp=[]
45 for key in d2:
46     tmp.append(data(key,d2[key]))
47 tmp=sorted(tmp,key=lambda x:(x.num,x.name))
48 for i in range(len(tmp)):
49     print(tmp[i].name+" "+str(-1*tmp[i].num))
50     
51

11. Tree Fun

Time limit: 1000 ms
Memory limit: 256 MB

You are given a tree with

The input contains the structure of the tree as well as a list of

After performing all the operations in the input, print the maximum score in the tree.

Standard Input

The first line of the input contains two integers: the number of nodes

The next $U_iUi, V_iVi denoting an edge between U_iUi and V_iVi.$

The following $A_iAi, B_iBi, K_iKi representing the starting node, ending node, and score to add along the path.$

Standard Output

A single integer representing the maximum score in the tree.

Constraints and notes

$10^51≤N,M≤105$
$U_i, V_i, A_i, B_i < N0≤Ui,Vi,Ai,Bi<N$
$K_i leq 1 0001≤Ki≤1 000$

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <algorithm>
  6 using namespace std;
  7 const int N = 1e5 + 10, M = 30005, mod = 1e9 + 7, inf = 0x3f3f3f3f;
  8 typedef long long ll;
  9 
 10 int head[N], t = 1, sz, v[N], pos[N], belong[N], siz[N], vis[N], n, m, p, C[N], deep[N], fa[N][18];
 11 struct data { int to, next; }e[N * 3];
 12 //树链
 13 void add(int u, int v) { e[t].to = v; e[t].next = head[u]; head[u] = t++; }
 14 void dfs1(int x) {
 15     siz[x] = vis[x] = 1;
 16     for (int i = 1; i <= 17; i++) {
 17         if (deep[x] < (1 << i)) break;
 18         fa[x][i] = fa[fa[x][i - 1]][i - 1];
 19     }
 20     for (int i = head[x]; i; i = e[i].next) {
 21         if (vis[e[i].to]) continue;
 22         deep[e[i].to] = deep[x] + 1;
 23         fa[e[i].to][0] = x;
 24         dfs1(e[i].to);
 25         siz[x] += siz[e[i].to];
 26     }
 27 }
 28 void dfs2(int x, int chain) {
 29     int k = 0;
 30     sz++;
 31     pos[x] = sz;
 32     belong[x] = chain;
 33     for (int i = head[x]; i; i = e[i].next)
 34         if (deep[x] < deep[e[i].to] && siz[k] < siz[e[i].to]) k = e[i].to;
 35     if (k == 0)return;
 36     dfs2(k, chain);
 37     for (int i = head[x]; i; i = e[i].next)
 38         if (deep[x] < deep[e[i].to] && k != e[i].to) dfs2(e[i].to, e[i].to);
 39 }
 40 int lca(int x, int y) {
 41     if (deep[x] < deep[y]) swap(x, y);
 42     int t = deep[x] - deep[y];
 43     for (int i = 0; i <= 17; i++)
 44         if (t&(1 << i)) x = fa[x][i];
 45     for (int i = 17; i >= 0; i--)
 46         if (fa[x][i] != fa[y][i]) {
 47             x = fa[x][i];
 48             y = fa[y][i];
 49         }
 50     if (x == y) return x;
 51     return fa[x][0];
 52 }
 53 //数据结构
 54 void update(int x, int c) {
 55     while (x <= n) {
 56         C[x] += c;
 57         x += x&-x;
 58     }
 59 }
 60 int ask(int x) {
 61     int sum = 0;
 62     while (x > 0) {
 63         sum += C[x];
 64         x -= x&-x;
 65     }
 66     return sum;
 67 }
 68 void solvechange(int x, int f, int c) {
 69     while (belong[x] != belong[f]) {
 70         update(pos[belong[x]], c);
 71         update(pos[x] + 1, -c);
 72         x = fa[belong[x]][0];
 73     }
 74     update(pos[f], c);
 75     update(pos[x] + 1, -c);
 76 }
 77 void scan() {
 78     for (int i = 1; i < n; i++) {
 79         int x, y;
 80         scanf("%d%d", &x, &y);
 81         x++, y++;
 82         add(x, y); add(y, x);
 83     }
 84     dfs1(1);
 85     dfs2(1, 1);
 86 
 87     for (int i = 1; i <= n; i++) {
 88         update(pos[i], v[i]);
 89         update(pos[i] + 1, -v[i]);
 90     }
 91     char ch[3];
 92     int x, y, c;
 93     for (int i = 1; i <= p; i++) {
 94         scanf("%d%d%d", &x, &y, &c);
 95         x++, y++;
 96         int t = lca(x, y);
 97         solvechange(x, t, c);
 98         solvechange(y, t, c);
 99         solvechange(t, t, -c);
100     }
101     int ans = -0x3f3f3f3f;
102     for (int i = 1; i <= n; i++) {
103         ans = max(ans, ask(pos[i]));
104     }
105     printf("%d", ans);
106 }
107 void init() {
108     memset(head, 0, sizeof(head));
109     t = 1;
110     sz = 0;
111     memset(fa, 0, sizeof(fa));
112     memset(deep, 0, sizeof(deep));
113     memset(v, 0, sizeof(v));
114     memset(vis, 0, sizeof(vis));
115     memset(C, 0, sizeof(C));
116     memset(pos, 0, sizeof(pos));
117 }
118 int main() {
119     while (scanf("%d%d", &n, &p) != EOF) {
120         init();
121         scan();
122     }
123     return 0;
124 }

12. Bit Soccer

Time limit: 500 ms
Memory limit: 256 MB

Peredo is a computer scientist who loves soccer. His favorite soccer player is Paolo Guerrero, one of the best Peruvian players, and his favorite team is the Brazilian national team.

He has a very large database of players with videos, photos, and many statistics related to their performance in hundreds of games. He uses his database to compute a binary performance index that tracks the players' abilities across 40 possible game metrics.

The performance index represents all possible soccer abilities of each player with a

Based on these numbers, Peredo created a simulation game that takes the performance indices and combines multiple players to form a team performance index.

The team performance index is such that if a single player has a

You are given a list of players in your roster represented by their performance indices in decimal format and your tasks is to combine a subset from your roster to form your starting team and to obtain a specific team performance index. There is no limit to the number of players that can form the starting team.

As an example, simplifying with just 4 game metrics, if we have two players on our starting team with performance indices

Standard input

The first line of the input contains an integer $P_iPi, denoting the performance indices of each player. The third line contains an integer QQ, denoting the number of queries, and each of the next QQ lines contains an integer GG that represents the goal team performance index.$

Standard output

For each query, print YES if it is possible to select a starting team from the roster and obtain the team performance index

Constraints and notes

$10^51≤N≤105$
$P_i, G leq 2^{40}-11≤Pi,G≤240−1$

 1 #pragma GCC optimize(3)
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 const double EPS = 1e-9;
 6 const int INF = 2147483647;
 7 const int LLINF = 9223372036854775807;
 8 const double PI = acos(-1.0);
 9 
10 #define     REP(i, a, b)  for(int i = (a); i < (b); i++)
11 #define     PER(i, a, b)  for(int i = (a); i > (b); i--)
12 #define     FOREACH(i,t)  for(typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
13 #define     NEED_CLOCK    printf("Time: %f
",double(clock())/CLOCKS_PER_SEC)
14 #define     MP(x, y)      make_pair(x, y)
15 #define     PB(x)         push_back(x)
16 #define     SET(a)        memset(a,-1,sizeof(a))
17 #define     CLR(a)        memset(a,0,sizeof(a));
18 #define     MEM(a,x)      memset(a,x,sizeof(a)) 
19 #define     ALL(x)        begin(x),end(x)
20 #define     LL            long long
21 #define     Lson          (index * 2)
22 #define     Rson          (index * 2 + 1)
23 #define     pii           pair< int, int >
24 #define     pll           pair< LL, LL >
25 #define     MOD           ((int)1000000007)
26 #define     MAXN          100005
27 
28 template< class T > inline T _abs(T a) { return a >= 0 ? a : -a; }
29 template< class T > inline T sqr(T a) { return a*a; }
30 template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % b)); }
31 template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b))*(b)); }
32 template< class T > inline T lowbit(T x) { return x&-x; }
33 
34 inline int READ() {
35     char ch;
36     while ((ch = getchar()) < 48 || 57 < ch);
37     int ans = ch - 48;
38     while (48 <= (ch = getchar()) && ch <= 57) 
39         ans = (ans << 3) + (ans << 1) + ch - 48;
40     return ans;
41 }
42 ///************************************START**************************************///
43 LL a[MAXN];
44 int main() {
45     int n; scanf("%d", &n);
46     for (int i = 0; i < n; i++) {
47         scanf("%lld", &a[i]);
48     }
49     int q; scanf("%d", &q);
50     for (int i = 0; i < q; i++) {
51         LL g; scanf("%lld", &g);
52         LL now = 0;
53         for (int j = 0; j < n; j++) {
54             //cout << (a[j] & g) << endl;
55             if ((a[j] & g) == a[j]) {
56                 now = now | a[j];
57             }
58         }
59         if (now == g) printf("YES
");
60         else printf("NO
");
61     }
62     return 0;
63 }

2018 IEEE极限编程大赛 题解

1. Drawing Rooted Binary Trees

2. Barter System

Standard input

Standard output

Constraints and notes

3. Troll Coder

Interaction

Constraints and notes

4. Xtreme Fake Coins

Standard input

Standard output

Constraints and notes

5. Magic Spell

Standard Input

Standard output

6. Bear Sums

Standard input

Standard output

Constraints and notes

7. Lemons

Standard input

Standard output

Constraints and notes

8. Make Distinct

Standard input

Standard output

Constraints and notes

9. Telescope Scheduling

Standard input

Standard output

Constraints and notes

10. Xplore

Standard input

Standard output

Constraints and notes

11. Tree Fun

Standard Input

Standard Output

Constraints and notes

12. Bit Soccer

Standard input

Standard output

Constraints and notes

2018 IEEE极限编程大赛题解