首页 > 代码库 > April Fools Contest 2017 题解&源码(A,数学 B,数学 C,数学 D,字符串 E,数字逻辑 F,排序,卡时间)

April Fools Contest 2017 题解&源码(A,数学 B,数学 C,数学 D,字符串 E,数字逻辑 F,排序,卡时间)

2024-09-12 02:36:47 219人阅读

A. Numbers Joke

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

Input

The input contains a single integer a (1 ≤ a ≤ 30).

Output

Output a single integer.

Example

Input

Output

题目链接：http://codeforces.com/contest/784/problem/A

分析：百度史蒂芬数，直接打表求解！

下面给出AC代码：

 1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5     int n; 6     while(cin>>n) 7     { 8         if(n==1) 9         cout<<4<<endl;10         else if(n==2)11             cout<<22<<endl;12             else if(n==3)13             cout<<27<<endl;14             else if(n==4)15             cout<<58<<endl;16             else if(n==5)17             cout<<85<<endl;18             else if(n==6)19             cout<<94<<endl;20             else if(n==7)21             cout<<121<<endl;22             else if(n==8)23             cout<<166<<endl;24             else if(n==9)25             cout<<202<<endl;26             else if(n==10)27             cout<<265<<endl;28             else if(n==11)29             cout<<274<<endl;30             else if(n==12)31             cout<<319<<endl;32             else if(n==13)33             cout<<346<<endl;34             else if(n==14)35             cout<<355<<endl;36             else if(n==15)37             cout<<378<<endl;38             else if(n==16)39             cout<<382<<endl;40             else if(n==17)41             cout<<391<<endl;42             else if(n==18)43             cout<<438<<endl;44             else if(n==19)45             cout<<454<<endl;46             else if(n==20)47             cout<<483<<endl;48              else if(n==21)49             cout<<517<<endl;50              else if(n==22)51             cout<<526<<endl;52              else if(n==23)53             cout<<535<<endl;54              else if(n==24)55             cout<<562<<endl;56              else if(n==25)57             cout<<576<<endl;58              else if(n==26)59             cout<<588<<endl;60              else if(n==27)61             cout<<627<<endl;62              else if(n==28)63             cout<<634<<endl;64              else if(n==29)65             cout<<636<<endl;66              else if(n==30)67             cout<<645<<endl;68     }69     return 0;70 }

B. Kids‘ Riddle

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

Programmers‘ kids solve this riddle in 5-10 minutes. How fast can you do it?

Input

The input contains a single integer n (0 ≤ n ≤ 2000000000).

Output

Output a single integer.

Examples

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

题目链接：http://codeforces.com/contest/784/problem/B

分析：化成16进制，然后数圈圈

下面给出AC代码：

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 string s; 5 int a,b,c,d; 6 int main() 7 { 8     int ans; 9     cin>>ans;10     if(ans==0)11     {12         a++;13     }14     while(ans)15     {16         if(ans%16==10)17         {18             a++;19         }20         else if(ans%16==11)21         {22             a+=2;23         }24         else if(ans%16==13)25         {26             a++;27         }28         else if(ans%16==6)29         {30             a++;31         }32         else if(ans%16==8)33         {34             a+=2;35         }36         else if(ans%16==9)37         {38             a++;39         }40         else if(ans%16==0)41         {42             a++;43         }44         else if(ans%16==4)45         {46             a++;47         }48         ans/=16;49     }50     cout<<a<<endl;51     return 0;52 }

C. INTERCALC

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

DO YOU EXPECT ME TO FIND THIS OUT?

WHAT BASE AND/XOR LANGUAGE INCLUDES string?

DON‘T BYTE OF MORE THAN YOU CAN CHEW

YOU CAN ONLY DISTORT THE LARGEST OF MATHEMATICS SO FAR

SAYING "ABRACADABRA" WITHOUT A MAGIC AND WON‘T DO YOU ANY GOOD

THE LAST STACK RUPTURES. ALL DIE. OH, THE EMBARRASSMENT!

I HAVE NO ARRAY AND I MUST SCREAM

ELEMENTS MAY NOT BE STORED IN WEST HYPERSPACE

Input

The first line of input data contains a single integer n (1 ≤ n ≤ 10).

The second line of input data contains n space-separated integers a_i (1 ≤ a_i ≤ 11).

Output

Output a single integer.

Example

Input

4 
2 5 3 1

Output

题目链接：http://codeforces.com/contest/784/problem/C

分析：把每句其中几个字取出来，组合在一起，就是最大值和最后一个数异或

下面给出AC代码：

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 int n,x,mx=0; 5 int main() 6 { 7     cin>>n; 8     for(int i=1;i<=n;i++) 9         cin>>x,mx=max(mx,x);10     cout<<(x^mx);11     return 0;12 }

D. Touchy-Feely Palindromes

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

Input

The only line of the input contains a string of digits. The length of the string is between 1 and 10, inclusive.

Output

Output "Yes" or "No".

Examples

Input

Output

Yes

Input

Output

No

Input

Output

Yes

题目链接：http://codeforces.com/contest/784/problem/D

分析：看是不是回文（436中4,6盲文对称）

技术分享

下面给出AC代码：

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5  6 int s[]={8,-1,-1,-1,6,9,4,-1,0,5}; 7 char st[12313]; 8  9 int main()10 {11     scanf("%s",st+1);int n=strlen(st+1);12     for(int i=1,j=n;i<j;i++,j--)13         if(st[i]!=st[j]&&s[st[i]-‘0‘]!=st[j]-‘0‘) return 0*puts("No");14     if(n&1){if(st[n/2+1]!=‘3‘&&st[n/2+1]!=‘7‘)return 0*puts("No");}15     puts("YES");16     return 0;17 }

E. Twisted Circuit

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

$技术分享$

Input

The input consists of four lines, each line containing a single digit 0 or 1.

Output

Output a single digit, 0 or 1.

Example

Input

Output

题目链接：http://codeforces.com/contest/784/problem/E

分析：一个数字电路，不过或门和异或门是反的，所以。。注意下

下面给出AC代码：

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 string s; 5 int a,b,c,d; 6 int main() 7 { 8     cin>>a>>b>>c>>d; 9     printf("%d\n",((a^b)&(c|d))^((b&c)|(a^d)));10     return 0;11 }

F. Crunching Numbers Just for You

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

You are developing a new feature for the website which sells airline tickets: being able to sort tickets by price! You have already extracted the tickets‘ prices, so there‘s just the last step to be done...

You are given an array of integers. Sort it in non-descending order.

Input

The input consists of a single line of space-separated integers. The first number is n (1 ≤ n ≤ 10) — the size of the array. The following n numbers are the elements of the array (1 ≤ a_i ≤ 100).

Output

Output space-separated elements of the sorted array.

Example

Input

3 3 1 2

Output

1 2 3

Note

Remember, this is a very important feature, and you have to make sure the customers appreciate it!

题目链接：http://codeforces.com/contest/784/problem/F

分析：

排序。不过必须运行时间超过1s，不会怎么控制时间？有个好办法，随便找个代码，反正要运行1s以上的，加进去，然后输出结果就好了，这里我用了网络赛的代码

下面给出AC代码：

  1 #include<bits/stdc++.h>  2 using namespace std;  3   4 #define MAXN 100  5 #define MAXM 10001  6 #define MAXP 266666  7 #define MAX 3200001  8 #define clr(ar) memset(ar, 0, sizeof(ar))  9 #define read() freopen("lol.txt", "r", stdin) 10 #define dbg(x) cout << #x << " = " << x << endl 11 #define chkbit(ar, i) (((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31)))) 12 #define setbit(ar, i) (((ar[(i) >> 6]) |= (1 << (((i) >> 1) & 31)))) 13 #define isprime(x) (( (x) && ((x)&1) && (!chkbit(ar, (x)))) || ((x) == 2)) 14  15  16 namespace pcf 17 { 18 long long dp[MAXN][MAXM]; 19 unsigned int ar[(MAX >> 6) + 5] = {0}; 20 int len = 0, primes[MAXP], counter[MAX]; 21  22 void Sieve() 23 { 24     setbit(ar, 0), setbit(ar, 1); 25     for (int i = 3; (i * i) < MAX; i++, i++) 26     { 27         if (!chkbit(ar, i)) 28         { 29             int k = i << 1; 30             for (int j = (i * i); j < MAX; j += k) setbit(ar, j); 31         } 32     } 33  34     for (int i = 1; i < MAX; i++) 35     { 36         counter[i] = counter[i - 1]; 37         if (isprime(i)) primes[len++] = i, counter[i]++; 38     } 39 } 40  41 void init() 42 { 43     Sieve(); 44     for (int n = 0; n < MAXN; n++) 45     { 46         for (int m = 0; m < MAXM; m++) 47         { 48             if (!n) dp[n][m] = m; 49             else dp[n][m] = dp[n - 1][m] - dp[n - 1][m / primes[n - 1]]; 50         } 51     } 52 } 53  54 long long phi(long long m, int n) 55 { 56     if (n == 0) return m; 57     if (primes[n - 1] >= m) return 1; 58     if (m < MAXM && n < MAXN) return dp[n][m]; 59     return phi(m, n - 1) - phi(m / primes[n - 1], n - 1); 60 } 61  62 long long Lehmer(long long m) 63 { 64     if (m < MAX) return counter[m]; 65  66     long long w, res = 0; 67     int i, a, s, c, x, y; 68     s = sqrt(0.9 + m), y = c = cbrt(0.9 + m); 69     a = counter[y], res = phi(m, a) + a - 1; 70     for (i = a; primes[i] <= s; i++) res = res - Lehmer(m / primes[i]) + Lehmer(primes[i]) - 1; 71     return res; 72 } 73 } 74  75 long long solve(long long n) 76 { 77     int i, j, k, l; 78     long long x, y, res = 0; 79  80     /*for (i = 0; i < pcf::len; i++){ 81          printf("%I64d\n",pcf::Lehmer(n)); 82          x = pcf::primes[i], y = n / x; 83          if ((x * x) > n) break; 84          res += (pcf::Lehmer(y) - pcf::Lehmer(x)); 85      } 86  87      for (i = 0; i < pcf::len; i++){ 88          x = pcf::primes[i]; 89          if ((x * x * x) > n) break; 90          res++; 91      }*/ 92     res=pcf::Lehmer(n); 93     return res; 94 } 95 int xx[100]; 96 int main() 97 { 98     pcf::init(); 99     long long n, res;100     while(cin>>n)101     {102         int x=solve(100000000000);103         for(int i=1; i<=n; i++)104         {105             cin>>xx[i];106         }107         sort(xx+1,xx+n+1);108         for(int i=1; i<=n; i++)109         {110             cout<<xx[i]<<" ";111         }112     }113     return 0;114 }

G. BF Calculator

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

In this problem you will write a simple generator of Brainfuck (https://en.wikipedia.org/wiki/Brainfuck) calculators.

You are given an arithmetic expression consisting of integers from 0 to 255 and addition/subtraction signs between them. Output a Brainfuck program which, when executed, will print the result of evaluating this expression.

We use a fairly standard Brainfuck interpreter for checking the programs:

30000 memory cells.
memory cells store integers from 0 to 255 with unsigned 8-bit wraparound.
console input (, command) is not supported, but it‘s not needed for this problem.

Input

The only line of input data contains the arithmetic expression. The expression will contain between 2 and 10 operands, separated with arithmetic signs plus and/or minus. Each operand will be an integer between 0 and 255, inclusive. The calculations result is guaranteed to be an integer between 0 and 255, inclusive (results of intermediary calculations might be outside of these boundaries).

Output

Output a Brainfuck program which, when executed, will print the result of evaluating this expression. The program must be at most 5000000 characters long (including the non-command characters), and its execution must be complete in at most 50000000 steps.

Examples

Input

2+3

Output

++> 
+++> 
<[<+>-]< 
++++++++++++++++++++++++++++++++++++++++++++++++.

Input

9-7

Output

+++++++++> 
+++++++> 
<[<->-]< 
++++++++++++++++++++++++++++++++++++++++++++++++.

Note

You can download the source code of the Brainfuck interpreter by the link http://assets.codeforces.com/rounds/784/bf.cpp. We use this code to interpret outputs.

题目链接：http://codeforces.com/contest/784/problem/G

分析：没思路！先放放！

April Fools Contest 2017 题解&源码(A,数学 B,数学 C,数学 D,字符串 E,数字逻辑 F,排序,卡时间)

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > April Fools Contest 2017 题解&源码(A,数学 B,数学 C,数学 D,字符串 E,数字逻辑 F,排序,卡时间)

April Fools Contest 2017 题解&源码(A,数学 B,数学 C,数学 D,字符串 E,数字逻辑 F,排序,卡时间)

A. Numbers Joke

B. Kids‘ Riddle

C. INTERCALC

D. Touchy-Feely Palindromes

E. Twisted Circuit

F. Crunching Numbers Just for You

G. BF Calculator

看完仍有疑问？有类似问题直接问程序猿