used dijkstra and update the probability (distance in normal dijkstra) of node v for v like below:
dis[father[v]]=dis[father[v]] + edge(father[v],v).value - dis[father[v]]*edge(father[v],v).value

is there any problem?!

I'm not good enough in probability theory...

Edited by author 15.08.2015 22:01

1)3
  111
  111
  111
 yes

2)3
  111
  101
  111
 no

3)5
  11100
  10000
  00011
  11000
  00000
 no

4)5
  11111
  00011
  01111
  00001
  00111
 yes

I am getting wrong answer. But output is identical in my computer. Here is my code -

#include <stdio.h>
#include <math.h>
#define ARRSIZE 32768

int main(){
    unsigned long int n, a[ARRSIZE];
    int i = -1;

    while(!feof(stdin)){
        i++;
        scanf("%lu", &n);
        a[i] = n;
    }

    i--;

    for(; i >=0; i--){
        printf("%0.4lf\n", sqrt(a[i]));
    }

    return 0;
}

1 2 3 4
1 3 4 2
1 4 2 3

2 4 3 1
2 3 1 4
2 1 4 3

3 2 4 1
3 4 1 2
3 1 2 4

4 2 1 3
4 1 3 2
4 3 2 1

Edited by author 14.08.2015 23:03

111 211
3
10

the answer is 0 or 1... why?

thanks you..

Hello, here is my code
using System;

public class Program
{
    public static void Main(String[] args)
    {

        var a = Convert.ToInt32(Console.ReadLine());
        var b = Convert.ToInt32(Console.ReadLine());

        var ans = (b-a + 1) / 2;

        if (b % 2 > 0)
            ans++;

        Console.WriteLine(ans);
    }
}

I can not find out the problem :(

Here is a special case test:

Input:
2 4
1 2
3 4

Possible output:
49
1 2 50 49

Create an unordered map <int, set <int> > and for each number in the input insert it's index to the corresponding position in the map, then for each query use manipulations with upper_bound in the set.

Looks like O(nlogn + qlogn).

Edited by author 13.08.2015 20:29

Any idea?

if {(1^n + 2^n + 3^n + 4^n) % 10} is equal to 0, then we find 1 zero.
if {(1^n + 2^n + 3^n + 4^n) % 100} is equal to 0, then we find 2 zeros.
and so on....

now, how to calculate {(1^n + 2^n + 3^n + 4^n) % 10}:

Look,
 {(1^n + 2^n + 3^n + 4^n) % 10}
=((1^n % 10) + (2^n % 10) + (3^n % 10) + (4^n % 10)) % 10   [simple modulo equivalencies]

now,
 (4^n % 10)
= ((((((4%10)*4)%10)*4)%10)*4)%10 . . . . . . . (n times)    [(4%10), then multiply by 4, then mod 10, loop for n times]
similarly for (2^n % 10) and (3^n % 10).   No need for 1, because (1^n % 10) is always 1.

In this way, calculate the rusult of {(1^n + 2^n + 3^n + 4^n) % m} for m = 10, 100, ans so on...  and count zeros... :)


** to know more about modulo equivalencies,
http://en.wikipedia.org/wiki/Modulo_operation

** solution C++:
(don't see the solution before trying, at first try yourself)

http://github.com/shahed-shd/Online-Judge-Solutions/blob/master/Timus-Online-Judge/1295.%20Crazy%20Notions.cpp


Edited by author 13.08.2015 15:51

Edited by author 13.08.2015 23:02

Hi all.
I use dfs to find the number of connected components.
If there are 2 components,then i output each of them as a single team.If there is only 1 CC,then i output numbers from 1 to n/2  and from n/2+1 to n.
Otherwise "No solution".
It seems to me correct,but....
Or tell me some tests that prove my idea's fail)

Deleted.

Edited by author 24.01.2010 03:44

Spoiler alert!!!

I've been struggling a lot with make_heap(), pop_heap() and push_heap(), but I decided to make my own heap structure and got Accepted

Here's the structure (not the solution) : http://pastie.org/10344200

check the test where answer is 1

I divided given graph into biconnected components, and then worked with created DAG. This solution is O(N^2) and runs in 0.203 seconds. But there are solutions with better time. Is there faster algo for this problem?
P.S. sorry for bad english((

//package timus;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.StringTokenizer;

public class p1423 {
    static char[] t;
    static char[] p;
    static int[] pi;
    static int N;

    public static void main(String[] args) throws FileNotFoundException {
        InputStream is = System.in;
        FastScanner sc = new FastScanner(new InputStreamReader(is));
        N = sc.nextInt();
        String tt = sc.next();
        tt += tt;
        t = tt.toCharArray();
        p = sc.next().toCharArray();
        pi = new int[N];
        System.out.println(KMPMatcher());
    }

    static int KMPMatcher() {
        computePrefixFunction();
        int equals = 0;
        for (int i = 0; i < N + N; i++) {
            while (equals > 0 && p[equals] != t[i])
                equals = pi[equals - 1];
            if (p[equals] == t[i])
                equals++;
            if (equals == N) {
                if (i == N - 1) {
                    return 0;
                } else {
                    return N + N - (i + 1);
                }
            }
        }
        return -1;
    }

    static void computePrefixFunction() {
        int k = 0;
        for (int q = 1; q < N; q++) {
            while (k > 0 && p[k] != p[q])
                k = pi[k - 1];
            if (p[k] == p[q])
                k++;
            pi[q] = k;
        }
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(Reader in) {
            br = new BufferedReader(in);
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

"floor space one million square kilometers", so maximum number of slabs damaged by the fire is 1e12, but brute force solution (TL17) with ad-don "if(res>1e12)res=1e12" has WA14

#include <iostream>
#include <math.h>

using namespace std;

int main(){

    double x;
    int i;

    cin >> x;

    x = fmod (x, 7.0);

    printf("%.0f",x);

    system("pause");
    return 0;

}

Edited by author 18.08.2014 21:49

You don't need to calculate the topological order. If you first calculate the topological order, and then try to "verify" the study order, will complicate a simple problem.