C. Polycarpus' Dice

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/534/problem/C

Description

Polycarp has n dice d₁, d₂, ..., d_n. The i-th dice shows numbers from 1 to d_i. Polycarp rolled all the dice and the sum of numbers they showed is A. Agrippina didn't see which dice showed what number, she knows only the sum A and the values d₁, d₂, ..., d_n. However, she finds it enough to make a series of statements of the following type: dice i couldn't show number r. For example, if Polycarp had two six-faced dice and the total sum is A = 11, then Agrippina can state that each of the two dice couldn't show a value less than five (otherwise, the remaining dice must have a value of at least seven, which is impossible).

For each dice find the number of values for which it can be guaranteed that the dice couldn't show these values if the sum of the shown values is A.

Input

The first line contains two integers n, A (1 ≤ n ≤ 2·10⁵, n ≤ A ≤ s) — the number of dice and the sum of shown values where s = d₁ + d₂ + ... + d_n.

The second line contains n integers d₁, d₂, ..., d_n (1 ≤ d_i ≤ 10⁶), where d_i is the maximum value that the i-th dice can show.

Output

Print n integers b₁, b₂, ..., b_n, where b_i is the number of values for which it is guaranteed that the i-th dice couldn't show them.

Sample Input

input1

2 8
4 4

input2

2 3
2 3

Sample Output

3 3

0 1

HINT

题意

给你n个骰子，然后每个骰子有d[i]面，给你一个a，a表示这n个骰子所扔的点数和

然后问你，每一个骰子有多少个数不能投掷到~

题解：

首先，我设骰子扔的点数为x，那么0<x<=d[i]，这个是显然的吧
我们设其他骰子扔到的点数为y，则y+x=a，这个也是显然的

y>=n-1，也就是其他的所有骰子都扔1

y<=sum-num[i]，也就是其他所有骰子都扔最大值

那么就出来了三个不等式，然后随便解一下就好啦

对了，注意longlong

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //无限大

const int inf=0x3f3f3f3f;

/*

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("\n");

}

*/

//**************************************************************************************

ll num[maxn];

ll ans[maxn];

int main()

{

    ll n,a;

    cin>>n>>a;

    ll sum=;

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

    {

        cin>>num[i];

        sum+=num[i];

    }

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

    {

        ans[i]=min((a+(ll)-n),num[i])-max((a+num[i]-sum),(ll))+;

        ans[i]=num[i]-ans[i];

    }

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

        cout<<ans[i]<<" ";

}

秒客网

Codeforces Round #298 (Div. 2) C. Polycarpus' Dice 数学