B (2). Bubble-bubble Sort[提交记录][问题 3462]
时间限制: 2000MS
空间限制: 256MB
结果评判: 文本对比
正确/提交: 7 (5) / 15
官方标签:
用户标记:
题目描述
Bubbles! As a fanatical supporter of the Bubbles Are Perfect Creatures movement, you have accumulated a large collection of bubbles in all colours and sizes. Being a long time member, your bubbles are among the best in the world, and now is the time to show this. Tomorrow, the yearly Bubble Exposition will be held, and your goal is to win the Bubble Prize and become the Bubble Champion!
However, this is not an easy competition. In order to win, you do not only need the most beautiful bubbles, you also need the best-looking placement of bubbles. You have decided to order the bubbles by bubbliness: less bubblier bubbles to the left, more bubblier bubbles to the right. However, it is hard to compare all the bubbles in your collection at once. In fact, you can only compare up tok�bubbles by eye before losing track of all the bubbles. Since your collection consists of more thank�bubbles, you need a fancier sorting algorithm.
Your first thought is to use the best sorting algorithm for bubbly purposes, namely Bubble Sort. However, this is the most prestigious bubble competition, so you decide to do better: Bubble-bubble Sort. It works as follows.
Initially, your bubbles are placed in an arbitrary order. Every hour, you do the following: you look at the firstk�bubbles and place them in the optimal order. Then, you look at bubbles2∼k+12∼�+1and place those in the correct order. Then, you look at bubbles3∼k+23∼�+2, and so on, until you have placed the lastk�bubbles in the correct order. You then admire how the bubble collection looks so far until the next hour begins and you start at the first bubbles again.
Is this algorithm fast enough to place all your bubbles, or do you need to go further and invent a Bubble-bubble-bubble Sort algorithm? To be precise, after how many hours are the bubbles in the optimal positions?
输入描述
The input consists of:
- One line with two integersN,K(2≤K<N≤2500�,�(2≤�<�≤2500), the number of bubbles and the number of bubbles you can sort at once.
- One line withN�integersa(0≤a≤109�(0≤�≤109), the bubbliness of each bubble in the initial placement of your bubble collection.
输出描述
Output the number of hours needed to sort your bubble collection.
样例
输入复制
5 23 4 1 5 2
输出复制
3
输入复制
8 360 8 27 7 68 41 53 44
输出复制
2
输入复制
6 33 2 4 2 3 1
输出复制
3
来源
BAPC 2022 Pre
特判一下，用个is_sorted,ac哩
#includeusing namespace std;#pragma GCC optimize(2)#defineendl '\n'#define lowbit(x) ((x)&-(x))#define pi 3.1415926535const int N=2e6+10;typedef long long ll;ll ans=0,n1,m1;ll t=0,s1=0,s2=0,s3=0,s4=0,max1=0,max2=0,w,min1=100000000,sum=0,n,m,i,j,k,v,l,r;inline int read() {bool sym=0;int res=0;char ch=getchar();while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();while(isdigit(ch)) res =(res<<3)+(res<<1)+(ch^48),ch=getchar();return sym ? -res : res;}void print(int x) {if(!x)return;print(x/10);putchar(x%10+'0');}int isPrime(int n) {float n_sqrt;if(n==1) return 0;if(n==2 || n==3) return 1;if(n%6!=1 && n%6!=5) return 0;n_sqrt=floor(sqrt((float)n));for(int i=5; i>n>>k;for(i=1;i>a[i];if(is_sorted(a+1,a+1+n)){cout<<0;return 0;}for(j=1;j<=10004;j++){for(i=1;i+k<=n+1;i++){sort(a+i,a+i+k);//cout<E (5). Extended Braille[提交记录][问题 3486]
时间限制: 8000MS
空间限制: 512MB
结果评判: 文本对比
正确/提交: 9 (9) / 31
官方标签:
用户标记:
题目描述
The Blind Association for Pretty Calligraphy is annoyed by the lack of emoticons and math symbols in the braille alphabet. Given that the braille alphabet is supported by the Unicode format, it only makes sense to make all Unicode characters supported in braille.
The goal is to extend the braille alphabet to include all Unicode characters. Of course, this will not fit in the standard2×32×3format, so using a bigger box is allowed. Important is that no two braille characters are the same up to translation, i.e., have the same shape. See Figure E.1 for an example. You let a designer make up a large braille alphabet, and your job is to check how many unique shapes there are among the characters.
输入描述
The input consists of:
- One line with an integern�(1≤n≤1051≤�≤105), the number of braille characters.
- Then for each of then�braille characters:
- One line with an integerm�(1≤m≤10001≤�≤1000), the number of dots.
- m�lines, each with two integersx�andy�(|x|,|y|≤1000|�|,|�|≤1000), the coordinates of the dots.
The total number of dots is at most106106.
输出描述
Output the number of distinct braille characters up to translation.
样例
输入复制
220 21 120 11 0
输出复制
1
输入复制
23-1 00 11 03-1 00 -11 0
输出复制
2
来源
BAPC 2022 Pre
vector pair 找个起始点，算差距
#includeusing namespace std;#pragma GCC optimize(2)#defineendl '\n'#define lowbit(x) ((x)&-(x))#define pi 3.1415926535const int N=2e6+10;typedef long long ll;ll ans=0,n1,m1;ll t=0,s1=0,s2=0,s3=0,s4=0,max1=0,max2=0,w,min1=100000000,sum=0,n,m,i,j,k,v,l,r;inline int read() {bool sym=0;int res=0;char ch=getchar();while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();while(isdigit(ch)) res =(res<<3)+(res<F (6). Fastestest Function[提交记录][问题 5879]
时间限制: 1000MS
空间限制: 256MB
结果评判:Special Judge
正确/提交: 12 (12) / 37
官方标签:
用户标记:
题目描述
You are working as a software developer for the Bug Acquisition Programming Company. They developed a specific piece of software called Program C that they sell to their clients. For the past weeks, you have been working on optimising a specific function foo in the
main code path in Program C. You have made it a lot faster and would like to show off to your boss about it.
Your IDE has a nice tool that allows you to profile your code and tell you what percentage of the total running timefootakes. You can run this on the version before your change and after your change. However, you think it looks a lot cooler if you can just tell your boss how
much faster you have made foo itself.
输入描述
The input consists of:
- One line with two integersx�andy�(0<x,y<1000<�,�<100), wherex�is the percentage of the total running time that foo took before optimising andy�the percentage of the total running time it took after optimising.
输出描述
Output the factor of how much fasterfoogot after your optimization.
Your answer should have an absolute or relative error of at most10−610−6.
样例
输入复制
75 50
输出复制
3.0
输入复制
50 75
输出复制
0.3333333333333333
输入复制
50 50
输出复制
1.0
来源
BAPC 2022 Pre
注意100-aa,100-bb;
#includeusing namespace std;//#pragma GCC optimize(2)#defineendl '\n'#define lowbit(x) ((x)&-(x))const int N=2e6+10;typedef long long ll;ll ans=0,n1,m1;ll t=0,s1=0,s2=0,s3=0,s4=0,max1=0,max2=0,w,min1=100000000,sum=0,n,m,i,j,k,v,l,r;inline int read() {bool sym=0;int res=0;char ch=getchar();while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();while(isdigit(ch)) res =(res<<3)+(res<<1)+(ch^48),ch=getchar();return sym ? -res : res;}void print(int x) {if(!x)return;print(x/10);putchar(x%10+'0');}int isPrime(int n) {float n_sqrt;if(n==1) return 0;if(n==2 || n==3) return 1;if(n%6!=1 && n%6!=5) return 0;n_sqrt=floor(sqrt((float)n));for(int i=5; i>aa>>bb;cc=100-aa;dd=100-bb;if(aa==bb){cout<dd){double ee=cc/dd;cout<<fixed<<setprecision(6)<cc){double ee=cc/dd;cout<<fixed<<setprecision(6)<I (9). Jabbing Jets[提交记录][问题 3525]
时间限制: 1000MS
空间限制: 256MB
结果评判: 文本对比
正确/提交: 15 (11) / 101
官方标签:
用户标记:
题目描述
You have just gotten a new job at the Bathroom Accessories Production Company. The first task you are given is to jab holes into showerheads. To prove yourself, you have decided you want to create as many holes as possible.
However, you cannot just randomly drill holes everywhere in the showerhead. (At least, not without getting fired.) In order to ensure that the showerheads look aesthetically pleasing, the company has composed some guidelines which you will have to follow. See Figure J.1 for some examples of aesthetically pleasing showerheads.
- The holes should be arranged in concentric circles of radiir1,r2,…,rn�1,�2,…,��: the center of every hole should be on one of these circles.
- The distance between the centers of any two holes should be at leaste�.
How many holes can you make at most?
输入描述
The input consists of:
- One line with two integersn�ande�(1≤n,e≤1041≤�,�≤104), the number of circles and the minimal distance between holes.
- One line withn�integersr1,…,rn�1,…,��(1≤ri≤1041≤��≤104), the radii of the circles.
It is guaranteed that the numbersri��are given in increasing order, and thatri+1−ri≥e��+1−��≥�. Furthermore, it is guaranteed that increasing any radiusri��by at most10−610−6will not change the final answer.
输出描述
Output the maximal number of holes that you can make in the showerhead.
样例
输入复制
4 12 3 5 7
输出复制
104
输入复制
2 22 5
输出复制
21
输入复制
3 2014 53 80
输出复制
44
来源
BAPC 2022 Pre
注意特判
#includeusing namespace std;//#pragma GCC optimize(2)#defineendl '\n'#define lowbit(x) ((x)&-(x))#define pi 3.1415926535const int N=2e6+10;typedef long long ll;ll ans=0,n1,m1;ll t=0,s1=0,s2=0,s3=0,s4=0,max1=0,max2=0,w,min1=100000000,sum=0,n,m,i,j,k,v,l,r;inline int read() {bool sym=0;int res=0;char ch=getchar();while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();while(isdigit(ch)) res =(res<<3)+(res<K (11). Lots of Liquid[提交记录][问题 3624]
时间限制: 1000MS
空间限制: 1024MB
结果评判:Special Judge
正确/提交: 13 (12) / 74
官方标签:
用户标记:
题目描述
You work at a warehouse that sells chemical products, where somebody just placed an order for all the Boron Acetate Phosphoric Carbonate (BAPC) that you have in store. This liquid is stored in many separate lots, in cube-shaped containers, but your client requires the order to be delivered in a single cubeshaped container that fits all the BAPC liquid perfectly. What should be the size of this container?
输入描述
The input consists of:
- One line with an integern�(1≤n≤1051≤�≤105), the number of cube-shaped containers that you have in store.
- One line withn�floating-point numbersc�(1≤c≤1091≤�≤109), the length of one of the sides for each of these containers.
输出描述
Output the length of one of the sides of the cube-shaped container that will contain all the BAPC liquid.
Your answer should have an absolute or relative error of at most10−610−6.
样例
输入复制
321 28 35
输出复制
42
输入复制
322.10 2022 1337
输出复制
2200.6131345362505
输入复制
31.41421356 2.718281828 3.1415926535
输出复制
3.777901284526486
来源
BAPC 2022 Pre
cbrt 开立方根
#includeusing namespace std;//#pragma GCC optimize(2)#defineendl '\n'#define lowbit(x) ((x)&-(x))const int N=2e6+10;typedef long long ll;ll ans=0,n1,m1;ll t=0,s1=0,s2=0,s3=0,s4=0,max1=0,max2=0,w,min1=100000000,sum=0,n,m,i,j,k,v,l,r;inline int read() {bool sym=0;int res=0;char ch=getchar();while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();while(isdigit(ch)) res =(res<<3)+(res<<1)+(ch^48),ch=getchar();return sym ? -res : res;}void print(int x) {if(!x)return;print(x/10);putchar(x%10+'0');}int isPrime(int n){float n_sqrt;if(n==1) return 0;if(n==2 || n==3) return 1;if(n%6!=1 && n%6!=5) return 0;n_sqrt=floor(sqrt((float)n));for(int i=5;i<=n_sqrt;i+=6){if(n%(i)==0 | n%(i+2)==0) return 0;}return 1;}ll a[1000086];ll ef(ll x){ll aa=0;ll mid;l=1;r=n;while(l>1;if(a[mid]==x){aa=1;break;} if(a[mid]>n;double ans=0;for(i=1;i>aa[i],ans=ans+aa[i]*aa[i]*aa[i];cout<<fixed<<setprecision(7)<<cbrt(ans);return 0;}//mio lover