lol kek

input file:
1
Isenbae Isen Isenbaeva

and, what what is your answer?

Edited by author 25.06.2013 19:22

Edited by author 25.06.2013 19:22

Edited by author 25.06.2013 19:23

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

int N, M, S, T, A, B, P;
int total = 0;

struct Edge {
    int to, next;
    double prob;
} edges[100010];

int head[100010];
int parent[100010], dist[100010];
double prob[100010];

void addEdge(int start, int end, int p) {
    edges[total].to = end;
    edges[total].next = head[start];
    edges[total].prob = 1.0 - (double)p / 100.0;
    head[start] = total++;
}

// The most tricky part is the probability, we are looking for the probability
// of meeting Kraken in any route so it should be P(A|B), which equals to
// P(A) + P(B) - P(AB)
int main() {
    memset(head, -1, sizeof head);
    memset(parent, -1, sizeof parent);
    memset(dist, -1, sizeof dist);
    cin >> N >> M >> S >> T;
    for (int i = 0; i <= N; i ++)
        prob[i] = 0.0;

    for (int i = 1; i <= M; i ++) {
        cin >> A >> B >> P;
        addEdge(A, B, P);
        addEdge(B, A, P);
    }

    queue<int> q;
    q.push(S);
    dist[S] = 0 ;
    prob[S] = 1.0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int idx = head[u]; idx != -1; idx = edges[idx].next) {
            int v = edges[idx].to;
            double p = edges[idx].prob;
            if (dist[v] == -1 || (dist[v] == dist[u] + 1 && prob[v] < prob[u] * p)) {
                if (dist[v] == -1) {
                    q.push(v);
                }
                dist[v] = dist[u] + 1;
                prob[v] = prob[u] * p;
                parent[v] = u;
            }
        }
    }

    vector<int> path;
    for (int i = T; i != S; i = parent[i]) {
        path.push_back(i);
    }
    path.push_back(S);
    cout << path.size() << " ";
    printf("%.7f\n", 1.0 - prob[T]);
    for (int i = path.size() - 1; i >= 1; i --)
        cout << path[i] << " ";
    cout << path[0] << endl;

    return 0;
}

5
4
1 3 6 1

answer:3



Edited by author 29.05.2011 11:06

Done with queue + segment tree, AC in 0.265 on Visual C++ 2017

I have WA, but I don't guess at the feature of this test. Does anyone have a problem with this test? Please comment your trick.

#include <cstdio>
char ch, res;
int main (){
    while(scanf(" %c", &ch)!= EOF||(printf("%d\n", res)&0))
        res= (res*10+ ch-'0')%7;
}

outputon

YES

Edited by author 28.08.2018 23:32

Shortest path with respect to number of crossed walls is also shortest with respect to number of moves.

Edited by author 28.08.2018 21:03

less than can't be equal!

#include <stdio.h>
int main ()
{
    int m ,i, sum;
    scanf("%d", &m);
    if(m >= 0){
         sum = (m*(m+1))/2 ;
         printf("%d\n", sum);
         }
    else{
        for(i=1, sum =0; i>=m; i-- ){
            sum = sum+i;
        }
        printf("%d\n", sum);
    }
    return 0;
}

I use unsigned long long and STL vector with very simple algorithm: store x1, x2, x3 in the vector, then find the minimal diffenrence and push it in the vector (repeat the process until minimal difference is 0). I got AC.
I suppose that the tests are not strong enough. I wonder whether there is any test whose output is very large since I don's believe vector can store too many elements.
P/S: I'm a beginner so I'm very glad to study from all of you :-)!

I use
type[256*1024]
int main(){ ... }

run successfully .

but use struct as

int main()
{ type[256*1024] }

get error :  access violation

and use

type[256*1024 / sizeof(type)]

get error : access violation

what is the "A size of the input stream does not exceed 256 KB." means!

def chk(m):
    for i in range(0, int(len(m)/2)):
        if m[i] != m[len(m)-i-1]:
            if m[i] > m[len(m)-i-1]:
                m[len(m)-i-1] = m[i]
            else:
                m[len(m)-i-1] = m[i]
                m = inc(m, len(m)-i-2)
                chk(m)
    return m
def inc(y, x):
    if y[x]<9:
        y[x] += 1
    else:
        y[x] = 0
        inc(y, x-1)
    return y
v = list(input())
l = list(map(int, v))
if(len(v)==1):
    print(v[0])
else:
    l = chk(l)
    print("".join(str(o) for o in l))

I tried to do it with char input, the same happens.
tested everything I could find, but passed all the tests
don't know what to do


#include <iostream>
#include <string>
using namespace std;


int main()
{
    string alf = "abcdefghijklmnopqrstuvwxyz";
    char alp[26] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    string inp;
    cin >> inp;
    short *arr = new short[inp.length()];
    short *out = new short[inp.length()];
    short prev = 0;
    for (short i = 0; i < inp.length(); i++)
    {
        short num = alf.find(inp[i]) + 1;
        if (num <= 5)
            num += 26;
        while (arr[i - 1] > num)
            num += 26;
        arr[i] = --num;
    }
    out[0] = arr[0] - 5;
    for (short i = 1; i < inp.length(); i++)
        out[i] = arr[i] - arr[i - 1];
    for (int i = 0; i < inp.length(); i++)
        cout << alf[out[i]];

    delete[] arr;
    delete[] out;
    return 0;
}

I use about 3*n operations but TL81 or TL84!!!

I got TL because I used map(int, input().split())

Edited by author 22.08.2018 00:07

What is the intended solution for this problem? I used simulated annealing in order to get AC, but I don't think this is intended to pass.

ssssss
tTTTTT
Sandro

I get WA on 14 test. Please give me tests!