Acwing week 52

List of topics

AcWing 4422. Intelligence test

Title Description

An intelligence test contains an infinite number of questions , The serial numbers are 1,2,3…
Completion of i The time required for this topic is i(i+1)2.

The total duration of the test is n.

Please calculate , Within the prescribed time , From 1 Start with the questions and answer them in sequence , How many questions can you complete at most ？

Input format
An integer n.

Output format
An integer , Indicates the maximum number of questions that can be completed .

Data range
The first three test points meet 1≤n≤25.
All test points meet 1≤n≤10⁴.

sample input 1：
1
sample output 1：
1
sample input 2：
25
sample output 2：
4

analysis

Can directly simulate to solve this problem ,t(i) = i * (i+1) / 2, from i = 1 Start enumeration , until t(1) + t(2) + … + t(i) > until , The maximum number of questions that can be completed is i - 1.
Of course, you can also directly deduce the formula , Yes i² and i The summation formula of , It is easy to find the sum formula of the sum of the two .

Code

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int sum = 0,i = 0;
    while(sum <= n) {
        i++;
        sum += i * (i + 1) / 2;
    }
    cout<<i - 1<<endl;
    return 0;
}

AcWing 4423. The nearest distance

Title Description

Given a length of n Array of integers for a1,a2,…,an.

For each integer i（1≤i≤n）, Please find an integer j, requirement ：

1≤j≤n
aj=0
If the above two conditions are met ,|i−j| It should be as small as possible .|i−j| The minimum possible value of may be bi To express .
Please calculate and output b1,b2,…,bn.

Ensure that there must be... In the given array 0.

Input format
The first line contains integers n.

The second line contains n It's an integer a1,a2,…,an.

Output format
a line ,n It's an integer b1,b2,…,bn.

Data range
front 4 Test points meet 1≤n≤10.
All test points meet 1≤n≤2×10⁵,−10⁹≤ai≤10⁹.

sample input 1：
9
2 1 0 3 0 0 3 2 4
sample output 1：
2 1 0 1 0 0 1 2 3
sample input 2：
5
0 1 2 3 4
sample output 2：
0 1 2 3 4
sample input 3：
7
5 6 0 1 -2 3 4
sample output 3：
2 1 0 1 2 3 4

analysis

The title requires the output of each element in the array and its nearest 0 The distance between elements , Current 0 The element is either on its left or on its right , It can also be itself . So scan the array left and right , Record 0 At the same time, save the nearest to each element 0 The position of the element .

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200005;
int a[N],l[N];
int main() {
    int n;
    scanf("%d",&n);
    int p = -1e9;
    for(int i = 0;i < n;i++) {
        scanf("%d",&a[i]);
        if(!a[i])   p = i;
        l[i] = p;
    }
    p = 1e9;
    for(int i = n - 1;i >= 0;i--) {
        if(!a[i])   p = i;
        a[i] = min(p - i,i - l[i]);
    }
    for(int i = 0;i < n;i++)    printf("%d ",a[i]);
    return 0;
}

AcWing 4424. equation

Title Description

Given a nonnegative integer d, Please find two non negative real numbers a,b, Make the equation a+b=d and a×b=d Simultaneous establishment .

Input format
The first line contains integers T, Expressing common ownership T Group test data .

Each group of data occupies one row , Contains an integer d.

Output format
Output one line of answers for each group of data ：

If there are a and b, First output a letter Y, Then output any group of a and b.
If there is no a and b, Then a letter is output N.
As long as you output a and b Be able to satisfy at the same time |(a+b)−a×b|≤10⁻⁶ as well as |(a+b)−d|≤10⁻⁶, As correct . In order to guarantee the accuracy , It is recommended that the output results be retained 10 Decimal place .

Data range
The first three test points meet 1≤T≤10.
All test points meet 1≤T≤1000,0≤d≤1000.

sample input ：
10
0
1
2
3
4
5
6
7
8
9
sample output ：
Y 0.0000000000 0.0000000000
N
N
N
Y 2.0000000000 2.0000000000
Y 3.6180339754 1.3819660246
Y 4.7320508212 1.2679491788
Y 5.7912878394 1.2087121606
Y 6.8284271359 1.1715728641
Y 7.8541019708 1.1458980292

analysis

This problem is to solve a system of equations , take b = d - a Into the ab = d, Available ,ab = ad - a² = d, namely a² - da + d = 0; That is, a quadratic equation of one variable ,delta = d² - 4d, because d Nonnegative number , therefore d >= 4 when , The equation has two solutions ,d = 0 when ,a = b = 0; When the equation has a solution ,delta = sqrt(d² - 4d) < d, So whether it's （d + delta) / 2 still （d - delta）/ 2 Are greater than 0 Of , Take one of the solutions and find b that will do , It's not difficult to find out b Also greater than 0 Of , Because two solutions a Not more than d.

Code

#include <cstdio>
#include <cmath>
using namespace std;
int main(){
    int T,d;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&d);
        double delta = d * d - 4 * d;
        if(!d)  puts("Y 0.0000000000 0.0000000000");
        else if(d < 4)  puts("N");
        else {
            delta = sqrt(delta);
            double a = (delta + d) / 2;
            double b = d - a;
            printf("Y %.10lf %.10lf\n",a,b);
        }
    }
    return 0;
}