Codeforces Round ＃802 (Div. 2)(A-D)

A. Optimal Path

Problem - A - Codeforceshttps://codeforces.com/contest/1700/problem/A The question , From left to right , Go from top to bottom to give a n*m Table from 1 Start assignment , Find a way , Make its weight ( The values of all the grids on the road are added ) Minimum .

Ideas : Sign in , Go right from the first grid to the boundary , Then go down to the result .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n,m;
    cin>>n>>m;
    int ans=0;
    ans+=(1+m)*m/2;
    ans+=(m+m+(n-1)*m)*n/2;
    ans-=m;
    cout<<ans<<"\n";
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

---

B. Palindromic Numbers

Problem - B - Codeforceshttps://codeforces.com/contest/1700/problem/B

The question : To give you one n, There's another number , Add this number to this n Is a number of digits ( No lead 0), Become a palindrome .

Ideas : greedy , simulation , Reduce operation . When the first digit of the given number is not 9 when , Take a length of n, Everyone for 9 Subtract the given number from the given number , Is the result . If the first one is 9, Then we can go to a single digit n+1 Each of you is 1 Number of numbers , To subtract a given number , that will do . Here the subtraction is done with high precision .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
char s[100005];
vector<int>sub(vector<int>&a,vector<int> &b)
{
    vector<int> c;
    for(int i = 0,t = 0; i < a.size(); i++){
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t+10)%10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while(c.size()>1&&c.back()==0) c.pop_back();
    return c;
}
void solve()
{
    int n;
    cin>>n>>s+1;
    if (s[1] != '9')
    {
        for(int i=1;i<=n;i++)
            cout<<9-(s[i]-'0');
        cout<<'\n';
    }
    else
    {
        vector<int>a,b;
        for(int i=1;i<=n+1;i++) 
            a.push_back(1);
        for(int i=n;i;i--) 
            b.push_back(s[i]-'0');
        auto c=sub(a,b);
        for(int i=c.size()-1;i>=0;i--) 
            cout<<c[i];
        cout<<'\n';
    }
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

---

C. Helping the Nature

Problem - C - Codeforceshttps://codeforces.com/contest/1700/problem/C The question : Give you an array , You can choose 1-i The elements of will they -1, You can also choose i-n The elements of will they -1, You can also put all of them +1, How many times can you set all the elements to 0.

Ideas : See section operation , And it's c topic , Just think of the prefix and , Start with difference . Sure enough , When converted to difference is , These three operations change . The first operation becomes sub[1]-1,sub[i+1]+1, The second operation is sub[i]-1, The third is sub[1]+1. Then you can evaluate the difference array directly . When the current element <0 when , Just use the first operation to set it to 0. When >0 The second operation is used when . Finally, the second and third operations are used to handle sub[1] that will do .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int arr[200005];
int sub[200005];
void solve()
{
    int ans=0,n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&arr[i]);
        sub[i]=arr[i]-arr[i-1];
    }
    for(int i=2;i<=n;i++)
    {
        if(sub[i]<0)
        {
            sub[1]-=abs(sub[i]);
            ans+=abs(sub[i]);;
        }
        else
            ans+=sub[i];
    }
    ans+=abs(sub[1]);
    printf("%lld\n",ans);
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

---

D. River Locks

Problem - D - Codeforcesqqhttps://codeforces.com/contest/1700/problem/D The question : Yes n A reservoir , Each reservoir can have a faucet above it to prevent water , Continuous reservoirs can also discharge water continuously , Per second 1 Premium .n Ask , Every time I ask t To fill all the reservoirs in seconds, turn on a few taps .

Ideas : Wonderful thinking problem . I thought of it from the beginning , Divide the total amount of water by time , Rounding up , You'll need a few taps to fill it up . however , There are some situations to consider , The first few reservoirs must take time to fill up , Will flow to the next reservoir , That is to say, what we should consider is to use the time when all the reservoirs in front are full to remove the given time , To know how many taps are needed . So we need to prefix each reservoir and remove the number of reservoirs that are currently convenient , Rounding up , This number is the time required to fill the first few reservoirs currently traversed . To ensure that all reservoirs are filled , Going to this time max, If it's less than this max, It means that I may not be full when I reach a reservoir , Water doesn't flow down . This is -1 The situation of , The remaining total water consumption divided by time can be rounded down .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
int x,sum[200005];
void solve()
{
    int n,q,maxx=-1;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        sum[i]=sum[i-1]+x;
        maxx=max(maxx,(sum[i]-1)/i+1);
    }
    scanf("%lld",&q);
    while(q--)
    {
        int y;
        scanf("%lld",&y);
        if(y<maxx)
            printf("-1\n");
        else
            printf("%lld\n",(sum[n]-1)/y+1);
    }
    return;
}
signed main()
{
    solve();
    return 0;
}

come on. !