F - Fixing Banners
Harbin, whose name was originally a Manchu word meaning "a place for drying fishing nets", grew from a small rural settlement on the Songhua River to become one of the largest cities in Northeast China. Founded in 1898 with the coming of the Chinese Eastern Railway, the city first prospered as a region inhabited by an overwhelming majority of the immigrants from the Russian Empire. Now, Harbin is the capital of Heilongjiang province and the largest city in the northeastern region of the People's Republic of China. It serves as a key political, economic, scientific, cultural, and communications hub in Northeast China, as well as an important industrial base of the nation.
This year, a CCPC regional contest is going to be held in this wonderful city, hosted by Northeast Forestry University. To ensure the contest will be a success and enjoyed by programmers around the country, preparations for the event are well underway months before the contest.
You are the leader of a student volunteer group in charge of making banners to decorate the campus during the event. Unfortunately, your group made a mistake and misprinted one of the banners. To be precise, the word "harbin" is missing in that banner. Because you don't have time to reprint it, the only way to fix it is to cut letters from some used old banners and paste them onto the misprinted banner. You have exactly six banners, and for some reason, you must cut exactly one letter from each banner. Then, you can arrange and paste the six letters onto the misprinted banner and try to make the missing word "harbin". However, before you start cutting, you decide to write a program to see if this is possible at all.
Input
The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤50000)T (1≤T≤50000), the number of cases.
For each case, the input contains six lines. Each line contains a non-empty string consisting only of lowercase English letters, describing the letters on one of the old banners.
The total length of all strings in all cases doesn't exceed 2⋅1062⋅106.
Output
For each case, print the string "Yes" (without quotes) if it is possible to make the word "harbin", otherwise print the string "No" (without quotes).
Example
Input
2 welcome toparticipate inthe ccpccontest inharbin inoctober harvest belong ninja reset amazing intriguingOutput
No Yes代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=4e6+7; const int mod=1e9+7; ll n,t,m,s,ss,k; char x[maxn]; int a[7][7]; int vis[7]; int flag=0; void dfs(int i) { if(i==7) { flag=1; return; } if(flag) return; for(int j=1;j<=6;j++) { if(vis[j]==0&&a[j][i]==1) { vis[j]=1; dfs(i+1); vis[j]=0; } } } int main() { cin>>t; while(t--) { flag=0; for(int i=1;i<=6;i++) { vis[i]=0; for(int j=1;j<=6;j++) a[i][j]=0; cin>>x; n=strlen(x); for(int j=0;j<n;j++) { if(x[j]=='h') a[i][1]=1; if(x[j]=='a') a[i][2]=1; if(x[j]=='r') a[i][3]=1; if(x[j]=='b') a[i][4]=1; if(x[j]=='i') a[i][5]=1; if(x[j]=='n') a[i][6]=1; } } dfs(1); if(flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }I - Interesting Permutation
DreamGrid has an interesting permutation of 1,2,…,n1,2,…,n denoted by a1,a2,…,ana1,a2,…,an. He generates three sequences ff, gg and hh, all of length nn, according to the permutation aa in the way described below:
For each 1≤i≤n1≤i≤n, fi=max{a1,a2,…,ai}fi=max{a1,a2,…,ai};For each 1≤i≤n1≤i≤n, gi=min{a1,a2,…,ai}gi=min{a1,a2,…,ai};For each 1≤i≤n1≤i≤n, hi=fi−gihi=fi−gi.BaoBao has just found the sequence hh DreamGrid generates and decides to restore the original permutation. Given the sequence hh, please help BaoBao calculate the number of different permutations that can generate the sequence hh. As the answer may be quite large, print the answer modulo 109+7109+7.
Input
The input contains multiple cases. The first line of the input contains a single integer TT (1≤T≤200001≤T≤20000), the number of cases.
For each case, the first line of the input contains a single integer nn (1≤n≤1051≤n≤105), the length of the permutation as well as the sequences. The second line contains nn integers h1,h2,…,hnh1,h2,…,hn (1≤i≤n,0≤hi≤1091≤i≤n,0≤hi≤109).
It's guaranteed that the sum of nn over all cases does not exceed 2⋅1062⋅106.
Output
For each case, print a single line containing a single integer, the number of different permutations that can generate the given sequence hh. Don't forget to print the answer modulo 109+7109+7.
Example
Input
3 3 0 2 2 3 0 1 2 3 0 2 3Output
2 4 0Note
For the first sample case, permutations {1,3,2}{1,3,2} and {3,1,2}{3,1,2} can both generate the given sequence.
For the second sample case, permutations {1,2,3}{1,2,3}, {2,1,3}{2,1,3}, {2,3,1}{2,3,1} and {3,2,1}{3,2,1} can generate the given sequence.
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=4e6+7; const int mod=1e9+7; ll n,t,m; ll a[maxn]; int main() { cin>>t; while(t--) { scanf("%lld",&n); scanf("%lld",&a[1]); int flag=1; if(a[1]!=0) flag=0; for(int i=2;i<=n;i++) { scanf("%lld",&a[i]); if(i==2) { if(a[i]==0||a[i]>=n) flag=0; } else { if(a[i]>=n||a[i]<a[i-1]) flag=0; } } if(flag==0) cout<<0<<'\n'; else { if(n==1) cout<<1<<'\n'; else { ll ans=1; ll k=0; for(int i=2;i<=n;i++) { if(a[i]==a[i-1]) { ans*=k; ans%=mod; k--; } else { ans*=2; ans%=mod; k+=(a[i]-a[i-1]-1); } } ans%=mod; cout<<ans<<'\n'; } } } return 0; }J - Justifying the Conjecture
The great mathematician DreamGrid proposes a conjecture, which states that:
Every positive integer can be expressed as the sum of a prime number and a composite number.DreamGrid can't justify his conjecture, so you are invited to write a program to verify it. Given a positive integer nn, find a prime number xx and a composite number yy such that x+y=nx+y=n.
A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. Note that 11 is neither a prime number nor a composite number.
Input
The input contains multiple cases. The first line of the input contains a single integer TT (1≤T≤1051≤T≤105), the number of cases.
For each case, the only line of the input contains a single integer nn (1≤n≤1091≤n≤109).
Output
For each case, print two integers xx and yy in a single line, where 1≤x,y<n1≤x,y<n. If there are multiple valid answers, you may print any of them. If there is no valid answer, print the integer −1−1 instead.
Example
Input
3 4 6 7Output
-1 2 4 3 4代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=4e5+7; const int mod=1e9+7; ll n,t,m,s,x,y; ll a[maxn]; int main() { cin>>t; while(t--) { cin>>n; if(n<=4) cout<<-1<<endl; else if(n%2==0) { cout<<2<<" "<<n-2<<endl; } else { if(n<=5) cout<<-1<<endl; else { cout<<3<<" "<<n-3<<endl; } } } return 0; }K - Keeping Rabbits
DreamGrid is the keeper of nn rabbits. Initially, the ii-th (1≤i≤n1≤i≤n) rabbit has a weight of wiwi.
Every morning, DreamGrid gives the rabbits a carrot of weight 11 and the rabbits fight for the only carrot. Only one rabbit wins the fight and eats the carrot. After that, the winner's weight increases by 11. The whole process of fighting and eating ends before the next morning.
DreamGrid finds that the heavier a rabbit is, the easier it is to win a fight. Formally, if the weights of the rabbits are w′1,w′2,…,w′nw1′,w2′,…,wn′ before a fight, the probability that the ii-th rabbit wins the fight is
w′i∑j=1nw′jwi′∑j=1nwj′
He wants to know the expected weight of every rabbit after kk days (kk carrots are given and eaten).
Input
The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤105)T (1≤T≤105), the number of cases.
For each case, the first line of the input contains two integers nn and kk (1≤n≤105,1≤k≤1091≤n≤105,1≤k≤109). The second line contains nn integers w1,w2,…,wnw1,w2,…,wn (1≤i≤n,1≤wi≤1091≤i≤n,1≤wi≤109).
It's guaranteed that the sum of nn over all cases doesn't exceed 106106.
Output
For each case, print a single line containing nn space-separated real numbers, where the ii-th (1≤i≤n1≤i≤n) number should be equal to the expected weight of the ii-th rabbit after kk days.
Your answer will be considered correct if the absolute or relative error does not exceed 10−410−4.
Example
Input
3 1 1 2 2 2 1 3 3 2 1 1 1Output
3.00000000 1.50000000 4.50000000 1.66666667 1.66666667 1.66666667代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=4e5+7; const int mod=1e9+7; ll n,t,m,s,ss,k; ll a[maxn]; int main() { cin>>t; while(t--) { scanf("%lld %lld",&n,&k); s=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); s+=a[i]; } for(int i=1;i<=n;i++) { double x=a[i]*1.0/s; printf("%.8lf ",x*(s+k)); } cout<<'\n'; } return 0; }
