x[i] - y[i] = a * i + b

x[i-1] - y[i-1] = a * (i-1) + b

------------------------------------

x[i] - x[i-1]  - ( y [i] - y[i-1] ) = a



Let x1[i] = x[i] - x[i-1], i > 0. and y1[i] = y[i] - y[i-1], for i>0.


so ,

x1[i] - y1[i] = a,  a = x1[0] - y1[0].

x1[i-1] - y1[i-1] = a
-------------------------------
x1[i]  - x1[i-1] - (y1[i ] - y1[i-1]) = 0  or,

x1[i] - x1[i-1] = y1[i] - y1[i-1]

Let x2[i] = x1[i] - x1[i-1] = x[i] - 2*x[i-1] + x[i-2], for i>1. and
    y2[i] = y1[i] - y1[i-1] = y[i] - 2*y[i-1] + y[i-2], for i>1.

so  x2[i] = y2[i],  for all 1 < i <= n.

Use KMP.

I didn't try this, yet ).

this may be true: 1.000 > 1.
so add this func:
    double acos1(double x)
    {
        if(x > 1)
          x = 1;
        if(x < -1)
          x = -1;
        return acos(x);
    }

1 4 1
1
1 2 3 4
Ans 5

6 5 50
1 4 6 6 2 5
2 5 10 14 15
Ans 21

6 5 4
1 4 6 6 2 5
2 5 10 14 15
Ans 13

9 5 4
2 4 2 5 3 1 7 2 3
5 6 9 10 14
Ans 22

just use dijkstra and that's all

can anyone please share solution that works under 1 sec and under 10MB, I would really appreaciate it.

my email is: ikhomeriki@gmail.com

had wa on test 17, changed long long to long double and calculated everything until 1e20 and got accepted.

wtf?
what`s wrong?

program asd;
var n,k,i:byte;
    r:word;
    a:array[1..100] of byte;
BEGIN
r:=0;
ReadLn(k,n);
for i:=1 to n do
begin
 Read(a[i]);
 if (r+a[i]-k)>=0 then r:=r+a[i]-k
 else r:=0;
end;
WriteLn(r);
END.

#include <iostream>
using namespace std;
int main()
{
int k,n,l=1;
int r=0;
int* a = new int[1];
cin >> k >> n;
cin >> a[0];
for(int i=1;cin >> a[i];i++) l+=1;
for(int i=0;i<n;i++){
    if(i<l) r+=a[i];
    r-=k;
    if(r<0) r=0;
}
cout << r << endl;
system("pause");
return 0;
}

Что не так?

Edited by author 06.11.2013 23:12

#include <iostream>

using namespace std;

int main()
{
    int k,n,s,i,g,r;
    cin>>k;
    s=0;
    cin>>n;
    int *a=new int[n];
    for (i=0;i<n;i++){
        cin>>a[i];
        s=a[i]+s;
        };
    g=s-(n*k);
    cout<<g;
    return 0;
}

#include<iostream>

using namespace std;

int main()
{
    int k, n, a[1010], A, sklad;
    cin >> k >> n;
    if ((1 <= k && k <= 100) && (1 <= n && n <= 100))
    {
        for (int b = 0; b < n; b++)
        {
            cin >> a[b];
        }
        sklad = 0;
        for (int c = 0; c < n; c++)
        {
            A = k - (a[c] + sklad);
            if (A < 0)
            {
                sklad = -A;
            }
            else
                sklad = 0;
        }
        if (A < 0)
        {
            cout << -A;
        }
        else
            cout << A;
    }
    return 0;
}

I think of "N<=50" as "N,M<=50". Actually M<=N*(N-1)/2. It's a stupid mistake but it took me so much time to check out TAT
(btw, the point to solve the question is GCD(x,x+1)=1, it can be proved that the answer is always "YES".

What's in Test case 12?

Edited by author 12.09.2018 23:08

Please Help. Is it possible to know the contents of test 4
Fyodor Menshiko, what means "Contains empty sequence."?

Edited by author 12.09.2018 10:02

In:
0 0 0 4 0 0 -4 0
0 0 0 2 0 0 0 0
0 0 0 0 0 0 0 0
-4 0 0 0 0 0 0 0
0 0 -1 0 -1 0 0 0
0 0 -1 -6 -1 0 0 0
0 0 -1 -1 -1 0 0 0
0 0 0 0 0 0 0 0
2
White
d7-c5
a5-c5

Out:
Mate

0 0 0 4 0 0 -4 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-4 0 2 0 0 0 0 0
0 0 -1 0 -1 0 0 0
0 0 -1 -6 -1 0 0 0
0 0 -1 -1 -1 0 0 0
0 0 0 0 0 0 0 0

In:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-5 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 -3 0 0 0 0
0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0
6 2 0 0 0 -5 0 0
1
Black
d4-e5

Out:
Draw

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-5 0 0 0 0 0 0 0
0 0 0 0 -3 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0
6 2 0 0 0 -5 0 0

In:
0 -1 0 0 0 0 0 0
0 0 0 -4 0 0 0 0
0 6 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
6 1 0 0 0 0 0 0
1
Black
d7-a7

Out:
Mate

0 -1 0 0 0 0 0 0
-4 0 0 0 0 0 0 0
0 6 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
6 1 0 0 0 0 0 0

In:
0 0 0 0 0 0 0 0
0 0 0 -4 0 0 0 0
0 6 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
6 1 0 0 0 0 0 0
1
Black
d7-a7

Out:
Check

0 0 0 0 0 0 0 0
-4 0 0 0 0 0 0 0
0 6 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
6 1 0 0 0 0 0 0

Passing all this tests will probably gives you AC, of course, if you don't make any dumb mistakes like i did :)
GL.

#include <stdio.h>
#include <math.h>
#define M_PI 3.14159

int main() {
  int N;
  float R, result = 0;
  scanf("%d", &N);
  scanf("%f", &R);
  if (N == 1) {
    result = 2 * R * M_PI;
  }
  else
  {
  float nails[N][2];

  for (int i =  0; i < N; i++) {
    for (int j = 0; j < 2; j++) {
      scanf("%f", &nails[i][j]);
    }
  }

  for (int i = 1; i <= N; i++) {
   result += sqrt((nails[i][0] - nails[i - 1][0]) * (nails[i][0] - nails[i - 1][0]) + (nails[i][1] - nails[i - 1][1]) * (nails[i][1] - nails[i - 1][1]));
}

  result += (M_PI * 2 * R);

  }
    printf("%.2f", result);
  return 0;
}

WA On TEST#3 .. any help plz ???

Edited by author 11.09.2018 15:53

Edited by author 11.09.2018 15:53

it's just about implementation, the complexity is too high for these problem, imho

Learn something aboutDSU(disjoint-set-union

http://e-maxx.ru/algo/dsu

Edited by author 07.03.2013 23:32

I still WA on it!!!

In submission #8011723 I allocate queue of size only n, while for correct Ford-Bellman with a queue it should be up top m. Please, take a look into issue.