I've found that test #1 is the same as sample. I've special-cased it in my program to output exactly what is in the sample output, but I still get WA1. Why?

Looks like it depends on language: C and Java program output exactly the same, but C program passes the test, and Java program doesn't.

Edited by author 03.08.2011 00:41

#include<stdio.h>
#include<conio.h>
int main()
{
    int a, sum = 0;
scanf("%d",&a);
    if( a > 0 )
    {
        for ( int i = -1; i <= a; i++)
        sum += i;
    }

    else
    {
        for (int i = 1; i <= -a; i++)
        sum += i;
        sum = 1 - sum;
    }
printf("summa ravna %d",sum);
getch();
}

#include <stdio.h>
#include <math.h>
long long int k,n;
void reverce (void);
int main(void)
{
  reverce();
  return 0;

}

void reverce (void)
{
    long long int a;
    while(scanf("%lld", &a))
      {
        k++;
        n++;
        reverce();
      }
    if (k == n)
      {
         n--;
         return;
      }
    printf("%.4lf\n", (double)sqrt(a));
}

Edited by author 29.11.2012 01:43

I use dijkstra algo, what's wrong?
code



#include <cstdio>
#include <vector>
#include <map>
#include <set>
using namespace std;
const long long INF=100000000;
typedef unsigned long long ULL;
typedef pair<long long,long long> pii;
typedef vector<vector<long long> > VVI;
typedef vector<long long> vi;
typedef map<long long,vi> MIV;
MIV network;
VVI G;

long long n=1,n_int;
void init_vert(){
        for (long long i=0;i<=n;++i){
                vector< long long > temp;
                G.push_back(temp);
            }
        for (MIV::iterator it=network.begin();it!=network.end();++it){
            for(vi::iterator vit=it->second.begin();vit!=it->second.end();++vit){
                for(vi::iterator vit2=it->second.begin();vit2!=it->second.end();++vit2){
                    G[*vit].push_back(*vit2);
                }
            }
        }
    }

long long read_network(){
    long long res=0;
    long long mask=0;
    long r1,r2,r3,r4;
    long m1,m2,m3,m4;
    scanf("%ld.%ld.%ld.%ld",&r1,&r2,&r3,&r4);
    scanf("%ld.%ld.%ld.%ld",&m1,&m2,&m3,&m4);

    res+=r1&m1;res<<8;
    res+=r2&m2;res<<8;
    res+=r3&m3;res<<8;
    res+=r4&m4;

        return res;
    }


vector<long long> dist,parent;


void dejkstra(long long s){
    dist.assign(n+1,INF);
    parent.assign(n+1,INF);
    dist[s]=0;
    set<pair<long long,long long>  > q;
    q.insert(make_pair(dist[s],s));
    while (!q.empty()){
            long long v=q.begin()->second;
            q.erase(q.begin());
            for (size_t j=0;j<G[v].size();++j){
                    long long to=G[v][j];
                    if (dist[v]+1<dist[to]){
                            q.erase(make_pair(dist[to],to));
                            dist[to]=dist[v]+1;
                            parent[to]=v;
                            q.insert(make_pair(dist[to],to));
                        }
                }
        }
    }

int main(){
        //freopen("in","r",stdin);
        scanf("%lld",&n);
        long long n_n_m=0;
        for (size_t i=0;i<n;++i){
            scanf("%lld",&n_int);
            for (size_t j=0;j<n_int;++j){
                n_n_m=read_network();
                network[n_n_m].push_back(i+1);
            }
        }
        init_vert();
        long long _beg,_end;
        scanf("%lld%lld",&_beg,&_end);
        dejkstra(_beg);


        if (dist[_end]==INF){
                printf("No\n");
                return 0;
            }
        else{
                printf("Yes\n");
                long long p=_end;
                vector<long long>res;
                printf("%lld ",_beg);

                while(p!=_beg){
//                        printf(">>>%d\n",p);
                        res.push_back(p);
                        p=parent[p];


                    }
                 for (vi::reverse_iterator it=res.rbegin();it!=res.rend();++it){
                        printf("%lld ",*it);
                    }

                printf("\n");
            }
        return 0;
    }

Please send me.

var a,b,n,k:integer;
begin
readln(n,k);
a:=n div 2;
if k>a then b:=n-k
       else if (k=a) or (k=a+1) then b:=0
                                else b:=a-k;
writeln(b)
end.

Right... I guess this problem was put in here for comic relief. :)

For crying out loud, the author didn't even bother to increase the limits so as to make this a 'bignum' problem... :P

У меня программа получила AC, хотя на тест 1999 выдавала ответ 1991... мне кажется, что это не совсем верно...

I got WA on Test 16,but I don't know why.

Interesting, most people hit WA2 then AC, but I skipped WA2 and jumped right to WA3, seem to be the first to hit it.   Can't find the error....switched to java & BigInteger thinking numerical overflow in c++ may be the issue but still WA3.   Argh.

I've read it for 15 min..AC at the first time...
sort all the integer to a descending sequence.
repeat for n-1 times:
combine a[1] and a[2](2sqrt(xy))
delete(a[1],a[2])
insert the new real number into the sequence
and remember to keep the descending.

print the final a[1].

4
1
4
5
6
ans: 17

-->  1,4    4
<-- 1        1
--> 1,5     5
<-- 1        1
--> 1,6     6
               17

My code...

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

struct LAN
{
    int somay;
    char **IP;
    char **Sub;
};

int ChungMang(int a, int b, LAN *L);
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq);
void Show(int dau, int cuoi, int prev[]);

void main ()
{
    int somang;
    cin>>somang;
    LAN *L;
    L= new LAN[somang+1];
    for(int i =1;i<=somang;i++)
    {
        cin>>L[i].somay;
        L[i].IP=new char*[L[i].somay];
        L[i].Sub=new char*[L[i].somay];
        for(int j = 0;j<L[i].somay;j++)
        {
            L[i].IP[j]=new char[100];
            L[i].Sub[j]=new char[100];
            cin>>L[i].IP[j]>>L[i].Sub[j];
        }
    }
    int dau, cuoi;
    cin>>dau>>cuoi;
    int d[91];
    int prev[91];
    int label[91];
    int kq=1;
    Dijkstra(L,d,prev,label,dau,cuoi,somang,kq);
    if(kq==0)
        return;
    cout<<"Yes\n";
    Show(dau,cuoi,prev);
}
void Init(int d[], int prev[], int label[], int n, int dau)
{
    for(int i=1; i<=n;i++)
    {
        d[i]=-1;
        prev[i]=-2;
        label[i]=1;
    }
    d[dau]=0;
}
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq)
{
    Init(d,prev,label,somang,dau);
    while(label[cuoi]==1)
    {
        int iMin = -1;
        int v = -1;
        for(int i=1;i<=somang;i++)
        {
            if(label[i]==1 && d[i]!=-1&&(d[i]<iMin||iMin==-1))
            {
                iMin = d[i];
                v=i;
            }
        }
        if(iMin == -1)
        {
            cout<<"No";
            kq =0;
            break;
        }
        d[v]=iMin;
        label[v]=0;
        for(int j=1;j<=somang;j++)
        {
            if(label[j]==1&& ChungMang(v,j,L)==1)
            {
                d[j]=d[v]+1;
                prev[j]=v;
            }
        }
    }
}
int Test(char *IP3, char *IP4, char *Sub3, char *Sub4)
{
    char *IP1 = IP3;
    char *IP2=IP4;
    char *Sub1= Sub3;
    char *Sub2=Sub4;
    int i=0;
    int nIP=0;
    int nSub=0;
    while(nIP!=3)
    {
        if(IP1[i]=='.')
            nIP++;
        i++;
    }
    nIP=i;
    i=0;
    while(nSub!=3)
    {
        if(Sub1[i]=='.')
            nSub++;
        i++;
    }
    nSub=i;
    IP1[nIP]='\0';
    IP2[nIP]='\0';
    Sub1[nSub]='\0';
    Sub2[nSub]='\0';
    if(strcmp(IP1,IP2)==0&&strcmp(Sub1,Sub2)==0)
        return 1;
    return 0;
}

int ChungMang(int a, int b, LAN *L)
{
    int giong=0;
    for(int i=0;i<L[a].somay;i++)
    {
        for(int j = 0;j<L[b].somay;j++)
        {
            if(Test(L[a].IP[i],L[b].IP[j],L[a].Sub[i],L[b].Sub[j]))
                return 1;
        }
    }
    return 0;
}
void Show(int dau, int cuoi, int prev[])
{
    int temp[100];
    int i=99;
    int k = cuoi;
    cout<<dau;
    while (k != dau)
    {
        temp[i]=k;
        k=prev[k];
        i--;
    }
    for(int j = i+1;j<100;j++)
    {

            cout<<" "<<temp[j];
        cout<<endl;
    }
}

this kind of problems are easy,, i guess they exist to build up your confidence. xD

then check carefully your solution for n=3 :)

i found my mistake :)

Edited by author 15.10.2012 19:23

Edited by author 15.10.2012 19:23

What is wrong with my code? I can't figure out by myself:(

Some people talking about some tricky case. What is it?