Use stack for those who know what stack means.

For those who don't , take a look at this:

n++;
cin>>a[n];
if (a[n]==a[n-1]) n-=2;

How input is <wwstdaadierfflitzzz>,but output <stierlitz>?
This is wrong,according case 2 of this problem...

#include <stdio.h>
#include <conio.h>
main()
{ int n, k, a, b, c, tmp;
 scanf("%d%d", &n, &k);
 scanf("%d%d%d", &a, &b, &c);
 if (k>=1)
  if(n<=100)
   if ((a+b+c)<n*k)
   tmp=0;
   else
   tmp=(a+b+c)-n*k;

 printf("%d", tmp);

 getch();
}

In test #15 there are radiobeacons which don't have correct location on the plane (i.e. no one of points 1 <= x,y <= 200 is acceptable) but their signals are identified by checkpoints. In the problem statement we can find, that "N radiobeacons are located on the plane" and "we know ... that their coordinates are integers from 1 to 200". So, I believe that such test cases are incorrect.

"either the previous or the next ticket is lucky." and "one step from happiness"

lucky means: previous OR next, sum of first three digits EQUAL sum of last three digits.

Edited by author 03.10.2012 20:54

а что на русском темы писать нельзя и задачи

#include <stdio.h>
#include <stdlib.h>

main()
{
    int i,j,k,t;
    int sum;
    int max;
    int mark;
    int a[22];
    int* x;
    x=(int*)malloc(1048578*sizeof(int));
    scanf("%d",&a[0]);
    for(i=1,sum=0;scanf("%d",&t)!=EOF;i++)
    {
        for(j=1;j<=i-1 && t>a[j];j++);
        for(k=i-1;k>=j;k--){a[k+1]=a[k];}
        a[j]=t;
        sum+=t;
    }
    x[0]=1;x[1]=0;
    for(i=1;i<=a[0];i++)
    {
        for(j=1,mark=0,max=0;j<=x[0];j++)
        {
            x[j+x[0]]=x[j]+a[i];
            if(x[j]+a[i]<=sum/2)
                max=max>x[j]+a[i]?max:x[j]+a[i];
        }
        x[0]*=2;
    }
    printf("%d",sum-2*max);
}


I test it with a large data but can't find error...

why WA 6, i search two pair, if pair=2, then count++
    #include <queue>
    #include <iostream>
    #include <set>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <string>
    #include <stack>
    #include <sstream>

    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    char a[10000][6];
    void swap(char &a,char &b)
    {
        if(a>b)
        {
            char c;
            c=a;
            a=b;
            b=c;
        }
    }
    int amx(int a,int b)
    {
        if(a>b)
        {
            return(a);
        }
        else return (b);
    }
    int main()
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>a[i][0];
            cin>>a[i][2];
            cin>>a[i][3];
            cin>>a[i][1];
            cin>>a[i][4];
            cin>>a[i][5];
        }
        /*
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<6;j++)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
        */


        int max1=0;
        for(int i=0;i<n;i++)
        {
            int coutn1=0,count2=0,count3=0;
            for(int j=0;j<n;j++)
            {
                //if(i!=j)
                {
                    if(
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5])
                        ))
                        ||
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5])
                        ))
                        )
                    {
                        coutn1++;
                    }
                    if(
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        )
                    {
                        count2++;
                    }
                    if(
                        ((
                        (a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        ||
                        (((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        )
                    {
                        count3++;
                    }

                }
            }
            max1=amx(amx(coutn1,count2),(max1,count3));
        }
        cout<<max1;


    return 0;
    }

Edited by author 03.10.2012 09:29

Pleas Assist=)
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;
int main()
{

double arr[32768];
int i=0;
double value=0;
while(cin>>value)
{
    if (value>0)
    {
        arr[i++]=sqrt(value);
        value=0;
    }
        else break;

}
cout<<setprecision(4)<<fixed;
while(i--)
{
    cout <<arr[i]<<endl;
}
system("pause");

}

Edited by author 15.09.2012 23:36

Give me test 3? please...

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

int main()
{
    int a, sum = 0;
    cin >> a;

    if( a > 0 )
    {
        for ( int i = 1; i <= a; i++)
        sum += i;
    }

    else
    {
        for (int i = 1; i <= abs(a); i++)
        sum += i;
        sum = 1 - sum;
    }

    cout << sum;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct Date
{
    int day;

    int month;

    int year;
};

struct person
{
    int num;

    int live;

    Date die;
};

bool comp(person a, person b)
{
    if (a.live != b.live) return a.live > b.live;
    if (a.die.year != b.die.year) return a.die.year < b.die.year;
    if (a.die.month != b.die.month) return a.die.month < b.die.month;
    if (a.die.day != b.die.day) return a.die.day < b.die.day;
}

bool leap(int year)
{
    if (year%400==0) return 1;
    if (year%100==0) return 0;
    if (year%4==0) return 1;
    else return 0;
}

int monthDay(int year, int month)
{
    if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12) return 31;

    else if (month == 4 || month == 6|| month == 9 || month == 11) return 30;

    else if (leap(year))return 29;

    else return 28;
}

int Distance(Date a, Date b)//a??¨®¨²b  o??e¨º?¨®????1¨¨??¨²
{
    int dis = 0;

    for (int i = a.year+1; i < b.year; ++i)
    {
        if (leap(i)) dis += 366;

        else dis += 365;
    }

    if (a.year != b.year)
    {
        for (int i = a.month+1; i <= 12; ++i)
        {
            dis += monthDay(a.year, i);
        }

        dis += (monthDay(a.year, a.month) - a.day + 1);

        for (int i = 1; i < b.month; ++i)
        {
            dis += monthDay(b.year, i);
        }

        dis += b.day;
    }
    else
    {
        if (a.month != b.month)
        {
            dis += (monthDay(a.year, a.month) - a.day + 1);cout << monthDay(a.year, a.month) << endl;

            for (int i = a.month+1; i < b.month; ++i)
            {
                dis += monthDay(b.year, i);
            }

            dis += b.day;
        }
        else
        {
            dis += (b.day - a.day + 1);
        }
    }

    return dis;
}

int convert(char a, char b)
{
    return (a - '0')*10 + b - '0';
}

int convert(char a, char b, char c, char d)
{
    return (a - '0')*1000 + (b - '0')*100 + (c - '0')*10 + d - '0';
}

void print(Date a)
{
    cout << a.year << " " << a.month << " " << a.day << endl;
}

int main()
{
    int m;

    cin >> m;

    char useless[11];

    Date a, b;

    person p[101];

    for (int i = 0; i < m; ++i)
    {
        scanf("%d.%d.%d", &a.day, &a.month, &a.year);

        cin >> useless;

        scanf("%d.%d.%d", &b.day, &b.month, &b.year);

        p[i].num = i+1;

        p[i].live = Distance(a, b);

        p[i].die = b;
    }

    sort(p, p+m, comp);

    cout << p[0].num << endl;

    system("pause");
}

Time limit decreased from 1 second to 0.5 second (it corresponds better to the original TL in 2004). The problem was rejudged. Many old solutions with TLE verdict got AC, while all new solutions working in time from 0.5 to 1 second got TLE.

      n , k
1. if ( n = 0 ) , then answer = ( 1 ).
2. if ( n = 1 ) , then answer = ( k-1 ).
3. else answer(n) = ( k-1 ) * ( answer(n-1,k) + answer(n-2,k) ).

Edited by author 20.06.2010 04:04

http://acm.timus.ru/rating.aspx?space=1&num=1001&lang=cpp

How to do with 0.015s and 369Kb??

не понимаю

There are a lot of tests (i know two: 4 and 9), in which r <= 0. Please, change it!

I do not understand what is wrong with my code it works ok on my PC:

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "ISO-8859-1"));
        char[] buffer = new char[262144];
        br.read(buffer);
        Scanner in = new Scanner(new String(buffer));
        Stack<String> lifo = new Stack<String>();
        DecimalFormat format = new DecimalFormat("0.00000", new DecimalFormatSymbols(Locale.US));
        while (in.hasNextLong()) {
            lifo.push(format.format(Math.sqrt(in.nextLong())));
        }
        while(!lifo.empty()){
            System.out.println(lifo.pop());
        }
    }

Could someone explain it to me ?

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;

}