1: be careful of float point...
2: if there are K guys paid more than they drinked, the answer shouldn't be 100.0 / k, you should consider how much they paid...

I use bs + MST(Prim), please help me!!! Here is my code:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#define MAXN 1005
#define MAXE 500005
#define oo 1e100
#define EPS 1e-9
#define nabs(x) ((x) < 0? -(x) : (x))
using namespace std;
struct edge {
    int to, l, c, back;
    edge() {
    }
    edge(int _to, int _l, int _c, int _back) {
        to = _to;
        l = _l;
        c = _c;
        back = _back;
    }
} E[MAXE + MAXE];

int n, m, ce;
int ptr[MAXN];
long double d[MAXN];
bool mark[MAXN];

void add_edge(int a, int b, int l, int c) {
    E[ce] = edge(b, l, c, ptr[a]);
    ptr[a] = ce++;
    E[ce] = edge(a, l, c, ptr[b]);
    ptr[b] = ce++;
}
long double Prim(long double x) {
    for (int i = 1; i < n + 1; i++)
        d[i] = oo;
    d[1] = 0;

    long double res = 0, _min, val;
    int v, w;
    memset(mark, 0, sizeof(mark));
    for (int pass = 0; pass < n; pass++) {
        _min = oo;
        for (int i = 1; i < n + 1; i++)
            if (!mark[i] && d[i] < _min) {
                v = i;
                _min = d[i];
            }

        mark[v] = true;
        res += _min;

        for (int i = ptr[v]; i != -1; i = E[i].back) {
            w = E[i].to;
            val = E[i].c - x * E[i].l;
            d[w] = min(d[w], val);
        }
    }

    return res;
}
int main() {
    int a, b, l, c;
    memset(ptr, -1, sizeof(ptr));
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d%d%d", &a, &b, &l, &c);
        add_edge(a, b, l, c);
    }

    if(n == 1){
        cout << "0" << endl;
        return 0;
    }

    long double lo = 0, hi = 1e15, mit, fmit, flo;
    for (; nabs(hi - lo) > EPS;) {
        mit = (lo + hi) / 2;
        fmit = Prim(mit);
        flo = Prim(lo);
        if (flo * fmit < 0)
            hi = mit;
        else
            lo = mit;
    }


    cout << setprecision(8) << lo << endl;

}

No 1585
VAR pingvins:String; n,a,b,c,i:Integer;
begin
  Readln(n);
  a:=0; b:=0; c:=0;
  FOR i:=1 TO n DO
  begin
    Readln(pingvins);
    Case pingvins OF
     'Emperor Penguin' : a:=a+1;
     'Little Penguin' : b:=b+1;
     'Macaroni Penguin' : c:=c+1;
    end;
  end;
  IF (a>b) and (a>c) THEN Writeln('Emperor Penguin');
  IF (b>a) and (b>c) THEN Writeln('Little Penguin');
  IF (c>a) and (c>b) THEN Writeln('Macaroni Penguin');
end.

Where is problem?

#include<iostream>
#include<map>
using namespace std;
int main()
{
    map<int,int>a;
    int n,k,i,m,l,p=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
    cin>>k; a[k]++;
    }

    cin>>m;
    for(i=0;i<m;i++)
    {
    cin>>k; a[k]++;
    }

    cin>>l;
    for(i=0;i<l;i++)
    {
    cin>>k; a[k]++;
    if(a[k]==3){p++;}
    }


    cout<<p;

    //system("pause");
    return 0;}

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int N;
    double sum;
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
    {
        int p;
        scanf("%d", &p);
        sum += (double)p;
    }
    sum /= double(N);
    printf("%.6lf", sum);
    return 0;
}

Here is my code:

#include <iostream>

using namespace std;

int x[200];

int compare (const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

int main()
{
    int r[200], a = 3;
    long min;
    bool z = false;
    for (int  i = 0; i<3; i++)
        cin>>x[i];
    for ( ; ; )
    {
        qsort (x, a, sizeof(int), compare);
        min = 1000000000;
        for (int i = 0; i<a-1; i++)
        {
            r[i] = abs(x[i] - x[i+1]);
            if (r[i]<min)
                min = r[i];
        }
        x[a] = min;
        for (int j = 0; j<a; j++)
        {
            if (x[j] == min)
            {
                z = true;
                break;
            }
        }
        if (z == true) break;
        a++;
    }
    printf("%d", a - 1);
    return 0;
}

Where is my mistake?

" It is a tradition that a subordinate's computer has number that is greater than the number of his commander's computer. Each military person"  why there are some ki > i ? in th 9th case, isn't it a tree with the root 1?

What is special in test # 4?
I tried all examples on the webboard and my program gives the correct result.


Edited by author 28.09.2012 15:13

input->1
output->1

I'm received WA1 using standart bubble-sort (without saving original order). My answer for  example task is correct (at least my solution coverred task conditions):

ex. answer | my answer
3 5        |3 5
26 4       |22 4
22 4       |26 4
16 3       |20 3
20 3       |16 3
1 2        |11 2
11 2       |1 2
7 1        |7 1

In example task sorted array has saved original order. Maybe it cause wrong answer 1?
At that case this important condition must be set in task.

I think my program is correct. Who can tell me why I got wa?

#include<cstdio>
#include<cstdlib>
#include<cstring>
char a[100005],b[100000];
char cs[]="=+-*/0123456789)(";
bool pd(char ch){
    for(int i=0;i<17;i++)
       if(ch==cs[i]) return 1;
    return 0;
}

int main(){
    while(gets(b)){
       strcat(a,b);
    }
    int len=strlen(a);
    int ha=0,k=0;
    for(int i=0;i<len;i++){
         if(ha){
            if(a[i]=='*' && a[i+1]==')')
                ha=0;
         }else{
            if(a[i]=='*' && a[i-1]=='(')
                ha=1;
            else{
                if(k>0 && (!pd(a[i]))){ printf("NO"); return 0; }
                if(a[i]=='(') k++;
                if(a[i]==')') k--;
                if(k<0) { printf("NO"); return 0;}
            }
         }
    }
    if(ha || k!=0) { printf("NO"); return 0; }
    else printf("YES");
    system("pause");
    return 0;
}

New problem 1797 was added to the Problem set. Thanks to Xie Lingxi.

Edited by author 27.09.2012 00:47

Give me some test please i have WA13

Here is my code:


type My=record
       den,ost,sez:longint;
     end;
     Matr=array[1..101,1..101] of longint;

var m,n,l,i,j,h,k,min,o,sum:longint;
    a: Matr;
    q: array[1..101] of longint;
    w: array[1..101] of my;
    f:boolean;

procedure floyd(var  c:matr);
var i,j,k:longint;
begin
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if c[i,k]+c[k,j]<c[i,j] then c[i,j]:=c[i,k]+c[k,j];
  for i:=1 to n do c[i,i]:=0;
end;



begin
  readln(n,m);
  for i:=1 to n do
    for j:=1 to n do a[i,j]:= 1000000;
  for i:=1 to m do begin
    read(l);
    for j:=1 to l do read(q[j]);
    for j:=1 to l-1 do
      for h:=j+1 to l do begin
        a[q[j],q[h]]:=4;
        a[q[h],q[j]]:=4;
      end;
  end;
  floyd(a);
  readln(k);
  for i:=1 to k do readln(w[i].den,w[i].ost,w[i].sez);
  min:=1000000;
  for i:=1 to n do begin
  sum:=0;
    f:=true;
    for j:=1 to k do begin
      if w[j].sez=0 then
        if (w[j].den<a[i,w[j].ost]) then begin
          f:=false;
          break;
        end
        else sum:=sum+a[i,w[j].ost];
    end;

    if (f) and (min>sum) then begin
      o:=i;
      min:=sum;
    end;
  end;

  if min=1000000 then writeln(0)
  else writeln(o,' ',min);
end.

/*
 * Filename:      1079.c
 * Author:        Junwei Wang(wakemecn@gmail.com)
 * Last Modified: 2012-09-26 14:13
 * Description:
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long a[100001];
long max[10001];
long i;
long n;

long compute(long num)
{
    if (num % 2 == 0)
        return a[num / 2];
    return a[num / 2] + a[num / 2 + 1];
}

int main(void)
{
    a[0] = 0;
    a[1] = 1;

    max[0] = 0;
    max[1] = 1;

    for (i=2; i<=99999; i++) {
        a[i] = compute(i);
//        printf("a[%ld]=%ld\n", i, a[i]);

        if (a[i] > max[i-1])
            max[i] = a[i];
        else
            max[i] = max[i-1];
    }

    scanf("%ld", &n);
    if (n == 0)
        exit(0);
    do {
        printf("%ld\n", max[n]);
        scanf("%ld", &n);
    } while (n);
}

I use rools of tree. and i have crashed test#2
==>
# include <stdio.h>

long n;
long u[500005],v[500005],w[500005];
long m;
long x[750075],y[750075];
long t[100005][5];
long q[200],s[200];

int main()
{
    scanf("%ld",&n);

    for(int i=0;i<n-1;i++)
    {
        scanf("%ld %ld %ld",&u[i],&v[i],&w[i]);

        if(u[i]<v[i])
        {
            if(v[i]%2==0)
            t[u[i]][0]=w[i];

            else
            t[u[i]][1]=w[i];
        }

        else
        {
            if(u[i]%2==0)
            t[v[i]][0]=w[i];

            else
            t[v[i]][1]=w[i];
        }
    }

    int r=0,d=0,e=0;

    while(e<17)
    {
        q[e]=r;
        s[e]=d;
        r=r*2+1;
        d=d*2+2;
        e++;
    }

    scanf("%ld",&m);

    for(int i=0;i<m;i++)
    scanf("%ld %ld",&x[i],&y[i]);

    for(int i=0;i<m;i++)
    {
        long sum=0;

        while(x[i]!=y[i])
        {
            for(int j=e;j>=0;j--)
            {
                if(x[i]>=q[j] && x[i]<=s[j])
                {
                    int a;
                    if(x[i]%2==0)
                    {
                        a=x[i]/2-1;
                        sum+=t[a][0];
                    }

                    else
                    {
                        a=x[i]/2;
                        sum+=t[a][1];
                    }
                    x[i]=a;
                    break;
                }

                if(y[i]>=q[j] && y[i]<=s[j])
                {
                    int a;
                    if(y[i]%2==0)
                    {
                        a=y[i]/2-1;
                        sum+=t[a][0];
                    }

                    else
                    {
                        a=y[i]/2;
                        sum+=t[a][1];
                    }
                    y[i]=a;
                    break;
                }

            }
        }

        printf("%ld\n",sum);
    }
return 0;
}

Edited by author 26.09.2012 11:23

can you give me test#2 i have wrong answer at test#2

 why wrong answer at test#2