Я решил стандартно с помощью маски: Dp[mask], где mask - очередное состояние. Рассмотрел все переходы с потерями и выбрал минимальный из них. Асимптотика O(N*2^N). Как решить эффективней (кроме оптимизации в переходах,т.е. не рассматривать,скажем три нуля подряд в маске) не знаю. Может,кто-нибудь даст идею,как кроме стандартной лобовой маски решить?

First code gives wrong answer test #13. In the next code I changed

   System.out.print(2*n/k+2*n%k);

and used Math.ceil()

   System.out.print((int)Math.ceil(2*(float)n/(float)k));

The code was accepted. What's wrong?

Edited by author 03.08.2015 07:16

Edited by author 03.08.2015 07:17

Edited by author 03.08.2015 07:17

Edited by author 03.08.2015 07:17

Edited by author 03.08.2015 07:18

Edited by author 03.08.2015 07:18

Edited by author 03.08.2015 07:22

If you are using BFS, use a adjacency list. It's faster for finding the adjacents nodes. You too should use a "direccion list". It has the same size that the adjacency list, but it's filled with boolean values. For example, in the adjacency list of the node 1, you have nodes 2 3 4. If you need to go uphill from 1 to 2, in the correspondant place of the 2, you should write a 1, and if you need to go downhill, a 0. This is how I solved. I was stuck on time limit when I was using the same format of given data, but later I understood that the adjacency list it's very faster than 2 cols matrix (faster, but uses a lot more memory). Good luck, and try all the test posted in discussion.

2 5 3
01
0
11
10001

ans: 0

Edited by author 26.06.2007 18:43

Each of the cameramen wants Lev to skate along a segment of a straight line from some point to another (and each has specified his own pair of points). Lev has decided to skate along all the specified segments passing from a segment to a segment along a circular arc so that his trajectory has the shape of a smooth curve.

Do Lev move in a circular arc or a straight line?

If there is no arc connecting two consecutive directed segments without breaks, Lev can extend one of the segments so as to connect them by an arc.

For example 2, do these circles valid to this statement?
(-1,-1) radius = sqrt(26)
(1,1) radius = 3*sqrt(2)
(0,0) radius = 2*sqrt(5)

but (-2,-2) radius = 6 is invalid because the endpoint of the segment doesn't end in this circle.
Am I right?

And Finally how do you compute 7.1415926536?
because I find that circle (-1,-1) could yield better solution for about 6.69659557624

If anyone know hint or test case for test#13

why?

Can anyone explain me how we got the sample input ?

why "2 1 1 -2", or "2 1 1 0" is not an answer ?

when i submit i have fail(checker). What can I do with that?

if the "ss" answer equal 60,
update to 0 and change mm = mm+1

:)

The fastest way is to use matrix exponentiation and it is quite simple to understand. The algorithm is O(log n), yes it is that fast!. I got AC with Python 2.7 with 0.046s. Python has an added advantage for this problem since its Integer type can be as big as the RAM of the device being used. With c++ you can still get answers fast, using matrix exponentiation, but the answers are not precise enough, and leads to WA.

Edited by author 29.07.2015 15:42

care about -0.0

plz, help me! why i get crash(access violation).
// LCA (least common ancestor) offline by using interval tree in O(logN)
// Solution by Serekov Abzal

#pragma comment(linker, "/STACK:16777216")

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>

using namespace std;
int ADD = 65536;
int inf = 9999999;
vector <vector <pair<int, int> > > graph;
vector <bool> b(50001, false);
vector <int> h(50001, 0);
vector <int> order;
vector <int> d(50001, 0);
vector <int> first(50001, -1);
pair <int, int> tree[2 * 65536 + 1];
int n, root = 0;
void init_graph()
{
    scanf("%d", &n);
    graph.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }
};
void dfs(int v, int p)
{
    b[v] = true;
    h[v] = p;
    order.push_back(v);
    for (int i = 0; i < graph[v].size(); i++)
        if (!b[graph[v][i].first])
        {
            dfs(graph[v][i].first, p + 1);
            order.push_back(v);
        }
};
void bfs(int v)
{
    queue <int> Q;
    Q.push(v);
    while (!Q.empty())
    {
        int u = Q.front();
        b[u] = true;
        for (int i = 0; i < graph[u].size(); i++)
            if (!b[graph[u][i].first])
            {
                d[graph[u][i].first] = d[u] + graph[u][i].second;
                Q.push(graph[u][i].first);
            }
        Q.pop();
    }
};
void prepare()
{
    h[root] = 0;
    dfs(root, 0);
    for (int i = 0; i < order.size(); i++)
        if (first[order[i]] == -1)
            first[order[i]] = i;
    for (int i = 0; i < n; i++) b[i] = false;
    d[root] = 0;
    bfs(root);
};
int minimum(int u, int v)
{
    int l = u, r = v, ans = inf, ver = inf;
    while (l <= r)
    {
        if (l % 2 == 1)
        {
            if (tree[l].second < ans)
            {
                ans = tree[l].second;
                ver = tree[l].first;
            }
            l++;
        };
        if (r % 2 == 0)
        {
            if (tree[r].second < ans)
            {
                ans = tree[r].second;
                ver = tree[r].first;
            }
            --r;
        }
        l/=2; r/=2;
    }
    return ver;
};
int lca(int u, int v)
{
    int l = first[u] + ADD, r = first[v] + ADD;
    return minimum(l, r);
};
void init_zaprosi()
{
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int ans = d[u] + d[v] - 2 * d[lca(u, v)];
        printf("%d\n", ans);
    }
};
void tree_build()
{
    for (int i = 0; i <= 2 * ADD; i++)
    tree[i] = make_pair(-1, inf);

    for (int i = ADD; i < ADD + order.size(); i++)
    {
        tree[i].first = order[i - ADD];
        tree[i].second = h[order[i - ADD]];
    }
    for (int i = ADD - 1; i > 0; i--)
    {
        if (tree[2 * i].first == -1 || tree[2 * i + 1].first == -1)
        {
            if (!(tree[2 * i].first == -1 && tree[2 * i + 1].first == -1))
            {
                if (tree[2 * i].first == -1) tree[i] = tree[2 * i + 1]; else tree[i] = tree[2 * i];
            }
        }
        else
        {
            if (tree[2 * i].second < tree[2 * i + 1].second) tree[i] = tree[2 * i];    else tree[i] = tree[2 * i + 1];
        }
    }
};
int main()
{
    init_graph();
    prepare();
    tree_build();
    init_zaprosi();
    return 0;
}

This is very easy problem. You can use:
1) BFS or DFS to find the components of the graph;
2) Prim or Kruskal algo for minimum spanning tree.

Can you be more explicit about the error?
I used lots of test cases from discussions and code show's correct results without errors.
Do you need me to post my solution?

Edited by author 29.07.2015 13:55

给二分查找的参数传错了，传的是m。
弄得我都快崩溃了。
不过还好看了解答发现了。
下面是C代码
**********************************************************************************************
#include<stdio.h>
int teacher[15001]={0};
int exist_temp(int temp,int m){
    int first=0,last=m-1,count=0;
    while(first<=last){
        int mid=(first+last)/2;
        if(teacher[mid]==temp){
            count++;
            return count;
        }
        else{
            if(teacher[mid]>temp) last=mid-1;
            else first=mid+1;
        }
    }
    return count;
}
int main(){
    int n,m,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&teacher[i]);
    scanf("%d",&m);
    int count=0,hi=m;
    while(hi--){
        int temp;
        scanf("%d",&temp);
        if(exist_temp(temp,n)!=0)
            count++;
    }
    printf("%d\n",count);
    return 0;
}

I'm using dfs and can't find test for my program :(

Edited by author 02.08.2012 16:46

Is a root node for the tree?

Subj

can somebody explain how the example shown has answer as
6 33
and not
6 44?
are we not supposed to give the word position?