I've solved 1079,but this problem...Is any trick there?

Edited by author 01.09.2007 22:19

I submited several times and i got WA at test #8.
I really appreciate if you would be so kind by giving me test #8.
Thank you.

Edited by author 30.09.2005 16:11

Edited by author 30.09.2005 16:11

Hello,

I often want to brag about my accomplishments at acm.timus.ru, I want to show how many problems I have solved and that I'm one of the most geeky participant of Timus.

I very much like the way projecteuler encourages boasting, it has a profile with level and number of problems solved.

In the end, such a feature would benefit everyone: Timus users can boast, Timus itself gets more visibility and new participants.

# 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

1) число может быть с ведущими нулями
2) выводить надо с ведущими нулями(если они есть)

короче вот тест
1)
0

000000000002

2)
2
02

020000000089

AC code?
Put here..

my solution : for (i = 1; i<=n; i++) printf("%d ",i);
    for (i = n; i > 1; i--) printf("%d ",i);
had ac... but it's wrong!!

Edited by author 18.09.2012 18:57

Edited by author 18.09.2012 18:57

find out such x that 2^x < n < 2^(x+1)
2^x means 2*2*...*2 x times

x=log(n)/log(2);//c++


the maximum value of a[i] i=1,2,...,2^x is
max=f(x);
where f(x) is the fibonacci sequence
f(0)=1 f(1)=1 f(n)=f(n-2)+f(n-1)

so i just have to look if there is a larger number from 2^x to n

it is easy to find out the value of a[i] without knowing a[1]...a[i-1]

if l=2*k and r=2*p
m=(l+r)/2
a[m]=a[l]+a[r];

it is rather easy to prove that
a[2^x]=1;
a[2^(x+1)]=1;

so you just have to do a binary search for i from 2^x to 2^(x+1) calculating the values for the left and right border

this is the function that does exactly that //c++
int b(long l,long r,long i,int v1,int v2)
{
long m=(l+r)/2;
if (i==m)    return (v1+v2);
if (i<m)    return j(l,m,i,v1,v1+v2);
        return j(m,r,i,v1+v2,v2);
}


I DON'T UNDERSTAND WHY, BUT WHEN I USE MATH.H I GET COMPILATION ERROR


good luck !!!

Hi Experts,

           Can you explain the sample test case in problem?
Thanks in advance
Anupam

try this test
2
11.02.2000 12.02.2000 11.02.2001
09.02.2001 11.02.2001 10.02.2002
-----------
1

:)

I have submitted for about 100 times with my (another) ID and finally get AC. Here I want to say something about the problem.

1. Is this problem easy?
Yes, very much. I think this problem could be regarded as 'PROBLEM FOR BEGINNERS'.
BTW, I think after reading my note, EVERYONE will be able to solve the problem.

2. What does the chessboard look like?
The chessboard is a common 8*8-board. The coordinates are marked with a~h(lowercase) and 1~8. 'a1' is a black cell.

3. How many players are there?
EXACTLY TWO.

4. Are all the checkers put on the black cell of the board?
Yes.

5. What does it mean by JUMPING OVER?
B could JUMPING OVER A, if A is at one of the four corners of B. (Use coordinates, (-1, -1), (-1, 1), (1, -1), (1, 1)). Do NOT think there are far-away jumpings, such as 'a1' jumps over 'c3'.

6. It says that, after jumping over, the checker mustn't fall over the board, is it right?
Yes!

7. It says that, after jumping over, the checker must be located at a FREE cell. What does FREE mean?
It means EMPTY cell, a cell without ANYTHING (and, within the board boundary).

8. What does it mean by "ONE OF THE OPPONENTS" gets the opportunity?
Let us call the two players Alice and Bob.
After Bob, for example, makes a move, if one of Alice's checker could fell one of Bob's checker, OR one of Bob's checker could fell one of Alice's checker, we think that "ONE OF THE OPPONENTS" have the opportunity.
WARNING: In BOTH cases above, it was Bob who will lose the game at once.

9. Are there mistakes in the test data?
No. There are no checkers put outside the board (such as a9 or g3), and no two checkers at the same place.

10. Could the output be '32'?
Yes. You can construct the case yourself.

11. Could the output be 'Draw'?
Yes. You can construct the case yourself.

12. Why did the author of this note use nearly 100 times to get AC?
Maybe something was wrong with him. Don't be like him :)


At last, we take a look at some cases:
(1)
b2
a1
(Some other 30 moves)
Answer should be 2: Although 'a1' could not be felled by 'b2' (Question 6), but 'b2' could be felled by 'a1', so the second player loses at once (Question 8).

(2)
a1
d4
b2
c3
(Some other 28 moves)
In this case, we could NOT judge the result with the first 4 moves (Questions 7 & 8).

(3)
a1
h8
a3
h6
a5
h4
a7
h2
b2
g7
b4
g5
b6
g3
b8
g1
c1
f8
c3
f6
c5
f4
c7
f2
d2
e7
d4
e5
d6
e3
d8
e1
It's a 'Draw' game (Questions 6, 7 & 8).

So, Good luck for EVERYONE.

Why there so strict timelimit.
I solved this problem in OpenCup (where LT is 2 s). But for solve it there I need to make some optimization. Is it possible to increse timelimit to 2sec ?

My solution is O(NlogN).

Edited by author 01.04.2008 15:17

So the problems says that 1 <= N <= 100, so I declare a nice unsigned char mem[100*100].
I get WA on test 4.
I go and read all the discussion about wrong awsers but none of those offer anything I didn't figure out already.
I change the declaration to unsigned char mem[256*256] and voila, the solution is magically accepted.
Does anyone have an idea why 100*100 bytes aren't enough?

what the fuck is test#4?
y don't u just post the content of those fucking tests?

Can anyone explain the DP algorithm logic posted for this problem through examples??

This is my code, it works good on the sample test, but I get WA1

#include <stdio.h>

unsigned int w[20], s, i, n, max, h, j, k, r[20], l[20];
bool a[50001]={1}, u[50001][20];

int main (void){
    scanf("%u", &n);
    for(i = 0; i < n; i++){
        scanf("%u", &w[i]);
        h += w[i];
    }
    for(i = 1; i <= h/2; i++)
        for(j = 0; j < n; j++){
            if(u[i - w[j]][j] == 0 && a[i - w[j]] && i - w[j] >= 0){
                a[i]++;
                for(k = 0; k < n; k++)
                    u[i][k] = u[i-w[j]][k];
                u[i][j]++;
                max = i;
                j = n;
            }
        }
    printf("%i", h - 2*max);
    return 0;
}

horizontally of vertically in any direction
->
horizontally or vertically in any direction