Lual.ru

Thank you! I change "while(scanf("%d",&n)!=EOF)" to "scanf("%d",&n)"  and got AC.
I think there is something wrong with the ninth data.

try this test:
input:
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
output:
Draw

first my code write 31.

I agree that proving the correctness of your solution is
a bit time-consuming for this task.  Nevertheless, in the
end the proof isn't that complicated, so I'll post it here
in case someone finds it interesting.

Suppose that we managed to position the plates (s straight
segments and t turns) on the plane so that the line segments
on them form a closed path.  Let's introduce a coordinate
system so that each plate can be described by a pair of
integers (X, Y) giving the coordinates of its lower left
corner.  Let's start at any point in our closed path and
traverse the entire path until we get back to the point where
we started.  At each point where we enter a new plate,
let's look at the coordinates (X, Y) of the plate we're
entering, and let's record a triple (x, y, d), where
x = X mod 2, y = Y mod 2, and d is the direction we're facing
at this particular point (one of N, W, S, E).

If we know the triple (x, y, d) at the time we entered
a plate, and if we know whether that plate is a left turn,
a right turn, or a straight one, we can easily determine
the triple that we'll get at the time we leave this plate
and enter the next one.  Thus for example, from 00N,
a left turn takes you into 10W, a right turn takes you into
10E, and a straight segment takes you into 01N.
If we keep computing possible transitions, we end up with
a kind of state transition diagram with 16 possible states.

I can't draw the diagram nicely here, but we can approximate
it by arranging the states into a 4*4 grid:

  00N 00S 01N 01S
  10W 10E 00W 00E
  11S 11N 10S 10N
  01E 01W 11E 11W

The transitions between states are very systematic:

(1) A straight segment changes the state so that you remain
in the same row, but move from the first column to the third
(or vice versa), or from the second column to the fourth
(or vice versa).

(2) If you are in the left half of the grid (first two columns),
a left turn moves you one row down (or from the fourth row back
to the first one) but leaves you in the same column.
A right turn moves you one row down as well, but it also switches
you from the first to the second column and vice versa.

(3) If you are in the right half of the grid (third and fourth column),
a right turn moves you one row up (or from the first row into
the fourth row) and leaves you in the same column.
A left turn moves you one row up as well, but it also switches
you from the third to the fourth column and vice versa.

Of course, if our path is truly closed, we will finish
in the same state where we started.  We can assume without loss
of generality that this state is 00N -- if it wasn't, we could
always move and rotate the entire path (i.e. all the plates)
a little bit.

From (1) it follows that every straight segment moves us from
the left half of the grid to the right one or vice versa.
Since we started on the left half (in 00N) and have to finish
there as well, it follows that the number of straight segments,
i.e. s, must be even.

From (2) and (3) it follows that every turn moves us from
an odd row to an even row or vice versa.  Since we started
in the first row (in 00N) and must finish in the same row,
it follows that the number of turns, i.e. t, must be even.

We can also notice that a turn will always change the direction
(the third character in our state) while a straight segment
will leave it unchanged.  For the path to be closed, we must
be facing each of the four possible directions at some point,
so we require at least four turns; thus t has to be >= 4.

Now let's consider the special case when s = 0, i.e. there
are no straight lines.  Only the first two columns of our
state grid are reachable (from 00N) in that case, and each
turn we take moves us from the current row to the next row
below it.  Since we started in the first row and must finish
in the  first row as well, it follows that in this case t must
be a multiple of 4.

So, to summarize what we've seen so far:
- s and t must be even
- t must be >= 4
- if s = 0, then t must be a multiple of 4.

Nearly all (s, t) that meet these constraints can be solved
if we start by manually constructing solutions for cases where
s = 0 and t = 4 or 16; and also for cases where s = 2 and
t = 6 or 8 or 10.  It is also easy to extend these paths by
inserting 2 straight segments at a time, or by inserting 8 turns
at a time.  The only case which remains unsolved by these
constructions is s = 0, t = 8.  It turns out that no closed path
exists with 8 turns and 0 straight segments, but I don't have
an elegant proof of this (it is however easy to verify it with
a program, using recursion).

1) I'm pretty sure it can't, since otherwise my AC solution has a big chance to divide by zero.
2) 3
0 0
3 0
0 3
answer: 1.9308
Yeah, this is a pretty simple test but it actually helped me to overcome that WA #2.

2

я так понимаю, тест 9 выглядит как 1 N.
Но тогда вопрос в 4 тесте. Как он выглядит?
оч-но, что первое число =1, а второе неизвестно.

Your test was added. Thank you.

You are probably joking =) Why did you decide that there can be at most 32 numbers in the input???

1) If N==a^2, that is if N is a full square, the answer is 1

2) Try N = a^2 + b^2. Brute force, but "clever" brute force.
This is the most expensive part of the algo

3) N is NOT a sum of 3 squares <=> N=(8k+7)*4^m
This is a fast step, about O(log(N))

4) Lagrange theorem states: each number may be presented as a sum of 4 squares: N = a^2 + b^2 + c^2 + d^2
So if the upper three cases fails, the answer will be 4.

simple DP:
int leftPos[char][pos] position of char which is left or equal of pos
int lastPos[mask] : for substring s[lastPos[mask]..s.length()-1] we can get all name of sportman with char which is  in mask.
=)

Вопрос снят. Ошибку нашел.

a better way:
#include<iostream>
using namespace std;
int main(){
    int lock1,lock2;
    cin>>lock1>>lock2;
    if(lock1%2==0||lock2%2==1){
        cout<<"yes";
    }else{
        cout<<"no";
    }
    return 0;
}

What's the meaning of your code ? and I'm not sure what's the main method to steal the bike by the thief.
Could you mind tell me ?

Edited by author 05.11.2012 22:48

I'd be more interested in your memory strategy. I don't think DP alg will differ much for the same problem

Maybe the test data are so simple, and DP is able to accept.
But I don't think DP method is right.

Time : 0.015 (I think its the minimal time)  C++ using maps and vectors

Used DP

Want d code? gaston770@gmail.com

Less than 15 lines of the algorithm

My solution cost monstrously 0.187s using DP...

Легко решается с динамическим програмированием. Делишь сумму камней на 2 части, потом запускаешь рюкзак до суммы камней/2, ответом будет являться abs(sum-2*maxx), где sum - сумма камней, а maxx - макс. вес, который мы можем поместить в наш "рюкзак"