A. Bob and BoB
Bob’s university is arranging BoB (Battle of Brains) 2018, which is a programming contest for freshman and sophomore students. He is in doubt about participating in it. He thinks it is a waste of time if, at least half of the contestants don’t receive prizes.After talking with the judges, Bob has found out the number of participants, apart from him, and the number of unique prizes to be distributed. He learned that there are four different types of prizes to be awarded, and none of the contestants will receive more than one prize. Do not confuse the rule used by Bob’s university with yours. A contestant can receive two different prizes in the contest you are currently participating in. Total number of registrants, apart from Bob, is N. General registration is closed now, so there won’t be anyone else entering the competition. But Bob can still enter, as he managed to convince the judges that there were unavoidable circumstances, for which he couldn’t register in due time. Now Bob will attend the contest if, after his inclusion, at least half of the participants receive prizes. Otherwise, he’ll skip the contest.
Will Bob BoB? Or will Bob not BoB?
Input Specification The first line of input will contain an integer T, indicating the number of test cases. Following T lines each will contain 5 space separated integers N, A, B, C, D. Here N is the number of participants, apart from Bob. A, B, C, and D are the number of prizes of the four different types.
Constraints
● 1 ≤ T ≤ 1000
● 1 ≤ N ≤ 1000
● 1 ≤ A, B, C, D ≤ N
● A+B+C+D ≤ N
Output Specification
If Bob will participate in BoB, then print “Yes”, otherwise print “No". Do not print the quotation marks. Print the output of separate cases in separate lines. Follow the exact format provided in
sample I/O.
2
Sample
Input Output
2
124 3 3 10 8
124 20 20 10 20
No
Yes
被英文gank的一题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,a,b,c,d;
int main(){
int T;cin>>T;
while(T--){
scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
if((a+b+c+d)*2>=n+1) puts("Yes");
else puts("No");
}
}
#include<bits/stdc++.h>B. Vibranium Gift
Let’s start with a well-known tricky question:
Which is heaviest, 1 kilogram of gold or 1 kilogram of feathers? If you are smart enough, you will immediately give the correct answer! And if you are unfortunate enough, you will go for GOLD!
Don’t be sad. I’ve another question for you: If you had two boxes, both of the same size, and you filled one with gold and one with feathers, which box would be the heaviest? The box filled with gold of course! Because feathers aren’t as dense as the gold, the same volume of feathers would be much lighter! Here comes the concept of density. Density is defined by the mass of an object divided by its volume: density= mass/volume
Your task is different by the way. Tomorrow is the birthday of your best friend named Shahed. You want to give him Liquid Vibranium as a gift!! (You realized it would be a unique birthday gift). So, you wanted to pour all the liquid Vibranium of mass M and density D in a bounding shape and wrap it with a wrapping paper. (Because you don’t want to let people know about your secret that you have liquid Vibranium except your friend!). You live in such a city that doesn’t have wrapping papers! You need to order wrapping papers from outside your city and it is costly. So, you need to pay as less money as possible in wrapping the birthday gift of your friend. Find the minimum area of the wrapping paper you need to use for wrapping the bounding shape.
Constraints
1≤T≤1000
1≤M≤10
5
1≤D≤10
5
4
Input
First line will contain the number of test cases T (1 ≤ T ≤ 1000). Next T lines will contain two integers M and D.
Output
For each case, print the case number and the desired result rounded to four decimal places. (Please see sample cases to understand the format)
Sample
Input Output
5
1 2
30 400
11 112
79 100000
500 12
Case 1: 3.0465
Case 2: 0.8601
Case 3: 1.0294
Case 4: 0.0413
Case 5: 58.1224
1)You can choose any bounding shape of your choice. The main task is to reduce the area of the wrapping paper.
2)The density of Liquid Vibranium is changeable. (Yes, it is weird.)
简单计算几何，被输出gank了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const double pi=acos(-1.0);
const int maxn=(int)2e5+100;
double m,d;
int main(){
int T;cin>>T;
rep(ca,1,T){
printf("Case %d: ",ca);
scanf("%lf%lf",&m,&d); double v=m/d;
printf("%.4lf\n",pow(pow(3.0*v/(4.0*pi),1.0/3),2)*4.0*pi);
}
}
C. The Blood Moon
Alan is going to watch the Blood Moon (lunar eclipse) tonight for the first time in his life. But his
mother, who is a history teacher, thinks the Blood Moon comes with an evil intent. The ancient Inca
people interpreted the deep red coloring as a jaguar attacking and eating the moon. But who
believes in Inca myths these days? So, Alan decides to prove to her mom that there is no jaguar.
How? Well, only little Alan knows that. For now, he needs a small help from you. Help him solve the
following calculations so that he gets enough time to prove it before the eclipse starts.
Three semicircles are drawn on AB, AD, and AF. Here CD is perpendicular to AB and EF is
perpendicular to AD. Given the radius of the semicircle ADBCA, find out the area of the lune AGFHA
(the shaded area). Assume that pi = acos(-1.0) (acos means cos inverse)
Input
Input starts with an integer T (1 ≤ T ≤ 10000), denoting the number of test cases.
Each case contains one integer r, the radius of the semicircle ADBCA (1 ≤ r ≤ 10000).
6
Output
For each case, print the case number and the shaded area rounded to exactly four places after the
decimal point in a line. See sample cases for details.
Sample
Input Output
1
2
Case 1: 1.0000
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const double pi=acos(-1.0);
const int maxn=(int)2e5+100;
double r;
int main(){
int T;cin>>T;
rep(ca,1,T){
printf("Case %d: ",ca);
scanf("%lf",&r);
printf("%.4lf\n",r*r/4.0);
}
}
D. Palindrome and Chocolate
Ainum and Arya are very good friends! Arya is a competitive programmer who is always crazy about
problem-solving, on the other hand, Ainum is a very studious girl who loves chocolate but she is not
that much interested in problem-solving and programming contest. One day they decide to play a
game called “Bolo toh dekhi?”. Arya knows that Ainum is very fascinated with palindromic numbers.
A number which reads the same forward and backward is called a palindromic number.
Since Arya is not a very easy person, so he likes odd numbers rather than palindromic numbers. Arya
gives Ainum a very large integer number N (1 ≤ N ≤10
9
) and asks Ainum to tell what is the nth ODD
length palindromic integer number. He also told if she can solve this problem then he will give her
a Dairy Milk Silk.
Now, Ainum becomes very tensed as she is not that much good at problem-solving. So, she came to
you and asked if you can solve this problem for her then she will give you 1/3 of the chocolate.
For this problem, you should assume that 1 is the first ODD length palindromic number, not 0!!!
Can you help her?
Input Specification
The first line of the input will be an integer the number of test cases T. Each of the following T lines
will contain an integer number N.
Output Specification
For each test case, print the case number and the N
th ODD length palindromic integer number. See
the sample test cases.
Constraints
1≤T≤10000
1≤N≤1000000000
8
Sample
Input Output
2
9
10
Case 1: 9
Case 2: 101
Any character or incident that matches with real life is not intentional. You may assume that all characters are
fictional.
傻逼题，正着输一遍反着输一遍
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const double pi=acos(-1.0);
const int maxn=(int)2e5+100;
string n;
int main(){
int T;cin>>T;
rep(ca,1,T){
cout<<"Case "<<ca<<": ";
cin>>n; cout<<n;
reverse(n.begin(),n.end());
rep(i,1,n.length()-1) cout<<n[i];
cout<<endl;
}
}
E. Jumpy Robot
In a 1D infinite grid [0, inf], Jumpy Robot is standing on 0th cell.
Initially, it has a power of jumping over exactly 2d cells. After each jump, d is decremented by one. If
d becomes negative, then the robot cannot jump anymore.
The robot can jump forward or backward but cannot go left/backward to a negative cell because it
doesn't exist. Also, the robot cannot skip a move, in other words, d won’t be decremented without
making a move.
For example, Let’s say initially d was 4 which means it can jump over exactly 16 cells. The robot can
jump and move to 16th cell and then d will become 3 (But it couldn’t move to -16th cell because it
doesn’t exist). Then it can jump over 8 cells and can either move forward and go to 24th cell or
move backward and go to 8th cell. Then d will become 2 and the robot can jump 4 cells in either
direction. But it cannot skip the moves of jumping 16 or 8 cells and directly jump over 4 cells.
Tell me if the robot can reach to Xth cell after some moves or it is impossible. If it is possible, then
also print the number of jumps needed.
Constraints
0 ≤ d ≤ 60
0 ≤ X ≤ 10
18
Input
First line will contain the number of test cases T (1 ≤ T ≤ 10
5
). Each of the next T lines will contain
two integers d and X. Dataset is huge. Please use faster I/O methods.
Output
For each test case, in a single line, print the case number. Then print the result which is the
following:
If it is impossible to reach X, print “NO”, otherwise print “YES” and the number of moves in a single
line.
(Please see sample cases to understand the format)
10
Sample
Input Output
4
2 6
2 5
3 8
1 5
Case 1: YES 2
Case 2: YES 3
Case 3: YES 1
Case 4: NO
简单模拟，每次只能往x的方向走，注意特判x=0的情况
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const double pi=acos(-1.0);
const int maxn=(int)2e5+100;
int d;
ll x;
int solve(){
scanf("%d%lld",&d,&x);
if(x==0) return 0;
ll pos=0;
int ans=0;
while(d>=0){
++ans;
ll len=(ll)pow(2,d);
d--;
if(pos>x) pos-=len;
else if(pos<x) pos+=len;
if(pos==x) return ans;
}
return -1;
}
int main(){
int T;cin>>T;
rep(ca,1,T){
printf("Case %d: ",ca);
int ans=solve();
if(ans!=-1) printf("YES %d\n",ans);
else puts("NO");
}
}
F. Special Birthday Card
It is the year 2022 and Ayush is 3 years old now. He has already started competitive programming. He wants to become a top-rated contestant like - Dibyo, The Legendary Grandmaster. A few months ago, Ayush collected a large number of documentation/books on graph theory. He started to learn about graph theory. The definitions of graph and tree seemed very complicated to him. He thought that all graphs are trees and all trees are graphs. But we know that his assumption is not correct. A Graph is made up of vertices which are connected by edges. It may be undirected, or its edges may be directed from one vertex to another. It may contain one or more cycles or not. On the other hand, a Tree is an undirected graph in which any two vertices are connected by exactly one path. It does not contain any cycle. A few days ago, on his third birthday, Ayush got an opportunity to meet Dibyo. It’s a great day for him !! He discussed with Dibyo about the basic graph algorithms. After the discussion, Ayush understood the basic difference between a general graph and a tree. Ayush received a birthday card sent by Dibyo. He found the following problem on the card. “X is an integer. For any X, you have to add a bidirectional edge from X to its all distinct divisors except for 1 and X itself. Again, for every divisor of X except for 1 and itself, you have to do the same things. And also do the same things recursively for the divisors of divisors. You can add an edge if there is no edge between them. Finally, you will get a connected bidirectional graph. Definitely, the final graph does not contain any self-loops or multiple edges between the same pair of integers/nodes. Here a graph consists of only 1 node is considered a tree. If X is equal to 12, then the divisors of X are 1, 2, 3, 4, 6, 12. So at first, we add bidirectional edges between 12 and the divisors of 12 except for 1 and 12 itself. It will be like the following graph - 12 Then if we do the same things for 6, we will get the following graph - Again, if we continue the same thing recursively for the other divisors of 12, all divisors of divisors of 12, divisors of divisors of divisors of 12 and so on. Finally, we will get the following graphIt is a cyclic graph but not a tree because it contains multiple cycles. In the problem, you are given an integer N. For every integer from 1 to N if you do the same things described above individually, then you get either a tree or cyclic graph for each integer. Now if the great contestant Dibyo chooses an integer randomly from 1 to N, what is the probability of the graph for the integer being a tree.” 13 Ayush tried hard to solve the problem. But unfortunately, he could not be able to solve the problem. Can you help Ayush? Input Specification The first line of input will contain an integer T, the number of test cases. Each test cases contains an integer N. Output Specification For each case of input, you should print a line containing the case number and the expected output in the form of p/q where GCD(p,q) is equal to 1. Check the sample input and output for more details. GCD - Greatest Common Divisor Constraints 1 <= T <= 100000 1 <= N <= 1000000 Sample Input Output 2 100 50 Case 1: 3/5 Case 2: 33/50 Use faster I/O methods. See the following figures for better understanding. 14 Figure 1: Final graph for 24 Figure 2: Final graph for 48
显然可以得出，只有质数和两个质数的乘积是符合条件的，维护一个前缀和就好啦
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
int n,sum=0;
int check[maxn];
int prime[maxn];
void Prime(int N){
rep(i,1,N) check[i]=1;
for(int i=2;i<=N;i++){
if(check[i]) prime[++sum]=i;
for(int j=1;j<=sum&&i*prime[j]<=N;j++){
check[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
}
void pre(){
Prime(maxn-100);
rep(i,1,sum) for(int j=i;j<=sum&&1ll*prime[i]*prime[j]<=maxn-100;++j) check[1ll*prime[i]*prime[j]]=1;
//cout<<sum<<endl;
rep(i,2,maxn-100) check[i]+=check[i-1];
}
void solve(){
scanf("%d",&n);
int ans=check[n];
int g=__gcd(ans,n);
printf("%d/%d\n",ans/g,n/g);
}
int main(){
int T;cin>>T;
pre();
rep(ca,1,T){
printf("Case %d: ",ca);
solve();
}
}
G. Ainum’s Delusion
Ainum the hacker-girl is a legendary wizard of computer land. To protect her people from the alien
virus invasion, she is trying to create a very powerful magical string, a string of magical gems. Each
gem is represented by lowercase Latin letters (a….z).
She has collected N magical gems already and connected them one by one to create the string. To
make sure that her people are safe, she needs to know the ultimate power of her string.
The ultimate power of her string is the summation of simple powers of all substrings of the string. A
substring is a contiguous sequence of characters within a string. For instance, “nomi” is a substring
of the word “polynomial” but "nominal" is not. Simple power of a substring s can be calculated by
the following formula:
Here, |s| = length of s, s[i] = ascii value of ith character of s.
Ainum is a very busy person, so she came to you for help. Can you help her? As the ultimate power
of her string can be very big, output the result modulo 1000000007 (10
9 + 7).
Input Specification
Input starts with a positive integer T (1≤T≤ 40), denoting the number of test cases. Each case starts
with an integer N (1≤N≤100000), the length of Ainum’s string followed by a string of length N
containing only lowercase Latin letters (a…..z).
Output Specification
For each case, print the case number and the ultimate power of Ainum’s string modulo 1000000007
(10
9 + 7). See sample for more details.
16
Sample
Input Output
2
1
a
2
ac
Case 1: 97
Case 2: 588
Explanation for second case: ac has 3 different substrings - a, ac, c. Simple powers of them are 97, 392 and 99
respectively.
单点贡献是i*(1ll*n+1)*(n-i+1)>>1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n;
char str[maxn];
void solve(int ca){
printf("Case %d: ",ca);
scanf("%d%s",&n,str+1);
ll ans=0;
rep(i,1,n){
ll res=1ll*i*(1ll*n+1)*(n-i+1)>>1;
ans=(ans+str[i]*res)%mod;
}
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
rep(i,1,T) solve(i);
}
