EOJ Monthly 2018.3

985月赛我只喜欢ECNU.jpg

A. 打工时不可能打工的

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

我 Ayano 就是破产，吃白菜，从这里跳下去，也绝对不打一天工！

然而现实是，没有钱就还是得打工的，否则生活无法继续啊。

现在你已经身无分文，信用卡也不欠钱，n 天后就是你的信用卡最后还款期，你必须在第 n 天结束时还清所有的借款。（这 n天里你通过信用卡借的款项也必须在那时还清）你知道接下来 n 天每天打工的收入 ai 和你预计的开销 bi，你想要打尽量少天数的工，又不至于破产。

每天的开销是一定发生的，打工只能按天为单位打工。

Input

第 1 行包含一个整数 n 表示总天数。（1≤n≤200 000）
第 2 行包含 n 个整数，第 i 个整数表示 ai。
第 3 行包含 n 个整数，第 i 个整数表示 bi。（1≤ai,bi≤100 000）

Output

如果你在 n 天后能还清信用卡，输出最少的打工天数；如果不能，输出 Game Over!。

Examples

input

output

就是你要还的钱是一定的，选择钱最多的天打工就是了

#include<bits/stdc++.h>

using namespace std;

const int N=;

int a[N];

int main()

{

    ios::sync_with_stdio(false);

    int n;

    cin>>n;

    for(int i=;i<n;i++)

        cin>>a[i];

    long long s=;

    for(int i=,x;i<n;i++)

        cin>>x,s+=x;

    sort(a,a+n);

    long long f=;

    for(int i=;i<n;i++)

    {

        f+=a[n-i-];

        if(f>=s)

        {

            cout<<i+<<"\n";

            return ;

        }

    }

    cout<<"Game Over!\n";

    return ;

}

B. 蛇形矩阵

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

蛇形矩阵是我最喜欢的矩阵之一。n 阶蛇形矩阵由前 n2 个正整数顺时针从外到内盘绕而成。

例如四阶具有如下形式：

五阶（奇数阶数）在中心位置略有不同：

1  2  3  4  5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

由于这种盘绕的方式过分诡异，无法简单的用数学语言表示。所以无聊又过分的出题人想让你算出这个矩阵每一行的和。

Input

输入一个整数 n (1≤n≤200 000)。

Output

输出 n 行 n 个整数，依次为每一行的和。

Examples

input

output

input

output

input

output

这个规律还是很好找的，就是等差数列啊，然后每次取首尾两个求一下前缀和，因为一个+1一个-1所以那个和是相等的

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

ll a[N];

int main()

{

    int n;

    cin>>n;

    ll l=,r=n,f=n,s=;

    a[]=(l+r)*f/;

    a[n]=a[]+(f-)**f;

    for(int i=;i<=(n+)/;i++)

    {

        s+=r;

        l+=*f-,f=f-,r=l+f-;

        s+=l;

        a[i]=s+(l+r)*f/;

        a[n-i+]=a[i]+(f-)**f;

    }

    for(int i=;i<=n;i++)

        cout<<a[i]<<"\n";

}

巴特西

EOJ Monthly 2018.3

Input

Output

Examples

Input

Output

Examples

最新文章

热门文章