It says, that K is an amount of stones BETWEEN other stones. Why does Test4 answer equal n-1. I suppose it should be n-2, shouldn't it?

Edited by author 26.12.2016 16:46

you must sort in ascend and descend order !!!

6
1 3 2 6 5 4

answer: 0

Edited by author 31.10.2017 02:47

it's one of the most awful descriptions of the problems i've ever seen. some corner cases, which are really questionable, are not explained. it really irritates because instead of solving the next problem you need to guess what the answer is. how should i know what is the answer for 1? i am not linguist, but smth tells me, that there are no situation when you can find elements in between in the list of one element. what is the answer? should i put 0, 1, etc? after all it's not a competition, i can't even ask the judge or stuff how should i interpret the problem itself.

Edited by author 31.10.2017 02:27

Transposing means swapping two tombstones NOT reversing the order of all the stones between selected two.

if stones are sorted then answer is n-1

It took me a while to find out this special case :)

# include <iostream>
# include <cstdio>

using namespace std;

const int Maxn = 130012;

int n, ans1, ans2, L1, L2, x, p[Maxn], q1, q2;

int GCD (int a, int b){

 if (b > a) return GCD(b, a);
 else
 if (b == 0) return a;
 else
return GCD(b, a % b);

}



int main () {
    freopen ("1.txt", "r", stdin);
    freopen ("2.txt", "w", stdout);

    cin>>n;

    for (int i = 1; i <= n; i++){
     cin>>x;
     p[x] = i;
    }

    q1 = 0;
    q2 = n + 1;
    ans1 = 0;
    ans2 = 0;

    for (int i = 1; i <= Maxn; i++){
        if (p[i] > 0) {
          q1 ++; q2 --;

          L1 = p[i] - q1; if (L1 < 0) L1 = -L1;
          L2 = p[i] - q2; if (L2 < 0) L2 = -L2;

          if (L1 > 0)
              if (ans1 > 0) ans1 = GCD(ans1, L1); else ans1 = L1;

          if (L2 > 0)
              if (ans2 > 0) ans2 = GCD(ans2, L2); else ans2 = L2;



        }

    }

    if (ans1 == 0) ans1 = n - 1; else ans1 --;
    if (ans2 == 0) ans2 = n - 1; else ans2 --;

    if (ans1 > ans2) cout<<ans1; else cout<<ans2;

return 0;
}

Edited by author 19.09.2012 17:23

I dont understand the problem itselk. what does K stands for?

For test
5
2 1 3 4 5

my AC program outputs
3

but it's obvious that it's wrong.

Meanwhile my program using GCD gets WA...

WA:
...
ans = gcd (ans, d - 1)
...
print (ans)


AC:
...
ans = gcd (ans, d)
...
print (ans - 1)


;-)

I've AC but I can't undestand how prove that GCD gives right answer?

I got AC for this problem 2 minutes ago. OMG !
In this problem you can sort stones in incresing or descreasing order !!

Edited by author 12.11.2006 02:59

I don't know where the mistake is in my program.Please give me some tests that are difficult.I tried several tests I made but I can't find where is my mistake.Thank you very much!!

5
1
1
1
1
1
5 or 3?

Const
  Maxn                = 130002;
Var
  N, I, X, L, Ans     : LongInt;
  P                   : Array[0..MaxN] of LongInt;

Function GCD(X,Y:LongInt):LongInt;
Begin
  If Y>X Then
    GCD:=GCD(Y,X)
  Else
    If Y=0 Then
      GCD:=X
    Else
      GCD:=GCD(Y, X MOD Y);
end;

begin
  Readln(N);
  For I := 1 To N Do
  Begin
    Read(X);
    P[X]:=I;
  End;
  X:=0;
  Ans:=0;
  For I := 1 To MaxN Do
    If P[I]>0 Then
    Begin
      Inc(X);
      L:=Abs(P[I]-X);
      If L>0 Then
        If Ans>0 Then
          Ans:=GCD(Ans,L)
        Else
          Ans:=L;
    End;
  If Ans=0 Then
    WriteLn(N-1)
  Else
    WriteLn(Ans-1);
end.

AC(+)
time 0.031
memory 660 kb

Hi! I used sorting ( qsort ) and gcd but I keep getting WA ( #3 ). Please give me some tricky tests or if someone could please take a look on my code I'll send it to him/her. My e-mail dporobic@eunet.yu.

I've got AC, but I don't know the reason exactly.
I just guessed it, and got AC.

//  {$I+,Q+,R+,S-}
program Sorting_the_tombstones ;
  const
    maxn = 130000;
    mask : longint = 30000;
  var
    i,j,k,n,kk,t,ss  : longint;
    a  : array[1..maxn]of integer;
    aa : array[1..maxn]of byte;
    b  : array[0..maxn div 8]of byte;
  function gcd(a,b : longint ) : longint ;
    begin
      while b>0 do
        begin
          a:=a mod b;
          if a=0 then break;
          b:=b mod a;
        end;
      gcd:=a+b;
    end;
  begin
   //main;
  end.

look i only use such few various...but the online judge said i used 1009kb!!why?

type
  maxm=1..130001;
var
 m,p:array [1..130001] of maxm;
 n,i1,j1,l,k:longint;

function nod(a,b:maxm):maxm;
begin
while (a<>0) and (b<>0) do
    if a>b then a:=a mod b else b:=b mod a;
if a=0 then nod:=b else nod:=a;
end;

procedure swapl(var a,b:maxm);
var
d:maxm;
begin
d:=a;
a:=b;
b:=d;
end;

procedure sort(l,r:maxm);
var
 i,j,x:maxm;
begin
i:=l;
j:=r;
x:=m[(r+l) div 2];
repeat
while m[i]<x do inc(i);
while m[j]>x do dec(j);
if i<=j then begin
swapl(m[i],m[j]);
swapl(p[i],p[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

begin
readln(n);
for i1:=1 to n do readln(m[i1]);
for i1:=1 to n do p[i1]:=i1;
sort(1,n);


l:=1;
while (p[l]-l=0) and (l<>n+1) do inc(l);

if l=n+1 then begin
write(n-1);
halt;
end;
k:=abs(p[l]-l);


for i1:=l+1 to n do begin
if p[i1]-i1=0 then continue;
k:=nod(k,abs(p[i1]-i1));
end;
write(k-1);
end.