People, __int64 not needed! I quickened my program from 0.31 to 0.15 when returned __int64 to int (if that was not a fluctuation).

Listen here. During one meal Ivan can save about 2*10^6/3 ~ 666667 rub. This is maximum increment of saved money. So at maximum the saved sum will be 2*10^9 + 666667, which is much less than 2^31-1.

My trouble (and most likely yours too) was connected with that i checked if saved sum is strictly greater than n fogetting of the fractional part. This is the case when
( integer part of saved money == n)
BUT
( integer part == n AND fractional part > 0)

1) i had wa35 with eps = 1e-15
2) i had wa82 with eps = 1e-11
3) ac with simple eps = 1e-9

I've already solved this problem in Pascal, but now I'm trying to get through with my C++ code. I see no difference to my accepted solution and interested, what the point.

Can someone help me to understand?

Compiled with Gnu C++ compiler.
#include <cstdio>
#include <vector>

#define ___MAXN 1000

typedef unsigned int uint;
std::vector< std::vector<int> > G(0);
int col[___MAXN] = {0};

void dfs(uint u, uint c)  {
    col[u] = c;
    for (uint v=0; v<G[u].size(); v++)
        if (!col[G[u][v]])
            dfs(G[u][v], 3-col[u]);
}

void colorize() {
    for (uint u=0; u<G.size(); u++)
        if (!col[u])
            dfs(u, 1);
}

int main()  {
    uint n;
    scanf("%u", &n);
    G.resize(n);

    for (uint i=0; i<n; i++) {
        static uint x;
        scanf("%u", &x);
        do  {
            G[i].push_back(x-1);
            scanf("%u", &x);
        }   while (x);
    }
    colorize();
    n = 0;
    for (uint i=0; i<G.size(); i++)
        switch (col[i]) {
        case 0:
            printf("0\n");
            return 0;
        case 1:
            n++;
            break;
        }
    printf("%u\n", n);
    char c = 0;
    for (uint i=0; i<G.size(); i++)
        if (col[i]==1)  {
            printf("%c%u", c, i+1);
            c = ' ';
        }
}

Is test 10 correct? A couple old AC solutions now have WA 10, and my new solution too.



Edited by author 29.04.2009 21:16

program Project1075_chala;

{$APPTYPE CONSOLE}

uses
  SysUtils, math;

  const
  EPS = 0.0000001;

    var
    xa, xb, xc, ya, yb, yc, za, zb, zc, r : integer;
    AB, BC, AC, cos_gamma, cos_gamma1, yoy, vatar, d, h : real;

begin
   read(xa, ya, za);
   read(xb, yb, zb);
   read(xc, yc, zc);
   read(r);
   AB := sqrt(sqr(xb-xa)+sqr(yb-ya)+sqr(zb-za));
   AC := sqrt(sqr(xc-xa)+sqr(yc-ya)+sqr(zc-za));
   BC := sqrt(sqr(xb-xc)+sqr(yb-yc)+sqr(zb-zc));
   if AB + BC <= AC+EPS then d := AB-2*r+PI*r
   else
     if (AC+EPS >= BC + AB) or (BC+EPS >= AC + AB) then d := AB
     else
       begin
         cos_gamma := (AC*AC+BC*BC-AB*AB)/(2*AC*BC);
         h := AC*BC*sqrt(1 - sqr(cos_gamma))/AB;
       if h+EPS >= r then d := AB
       else
         begin
           vatar := 2 * sqrt(sqr(r)-sqr(h));
           cos_gamma1 := (2*sqr(r)-sqr(vatar))/(2*r*r);
           yoy := arccos(cos_gamma1) * r;
           d := AB - vatar + yoy;
         end;
       end;
   writeLn(d:0:2);
end.

thanks

Cannot beat test 41.
Please share any ideas, tricky tests.

In my opinion, for n=4 the correct answer is 20 if I understood the condition of the problem correctly, i.e for n=3 there are exists 2 ways:
123231 and 132321. Please, explain me my mistake if I'm wrong.

What does it mean "to fall" into the gully?
Does it mean that the Pakhom's way intersects polyline ABC?

what is wrong in my solution?

Program N1744;
Var
n,i,j,t,k:integer;
A:array[1..100,1..100] of integer;
R:array[1..50000,1..3] of integer;
begin
  Readln(n);

  for i:=1 to N do
    for j:=1 to N do
    if i<>j then A[i,j]:=0 else A[i,j]:=3;

  k:=0;
  for i:=1 to N do
    for j:=1 to n do
      for t:=1 to n  do

      if (A[i,j]<3)and(A[i,t]<3) and(A[j,t]<3) then
      begin
      inc(k);
      R[k,1]:=i;
      R[k,2]:=j;
      R[k,3]:=t;
      inc(A[i,j]);
      inc(A[i,t]);
      inc(A[j,t]);
      inc(A[j,i]);
      inc(A[t,i]);
      inc(A[t,j]);
      end;
    writeln(k);

    for i:=1 to k do
      writeln(R[i,1],' ',R[i,2],' ',R[i,3]);
    Readln;
end.

is there a difference in what order the output numbers of soldiers?

Edited by author 24.01.2010 16:02

Edited by author 24.01.2010 16:03

I tried to use dynamic programming but failed.Who can tell me how to do it? Thank you very much!

here is my algo
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
const int N=50000;
int a[N],b[N],i,n,k,c[N],d[N],s=0;
bool p=true;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
cin>>k;
int j=k-1;
for(i=0;i<k;i++)
cin>>b[i];
int x=0,y=0;
for(i=0;i<n;i++)
    c[x++]=a[i];
for(i=0;i<k;i++)
    d[y++]=b[i];
nth_element(c,c,c+n);
nth_element(d,d,d+k);
for(i=n-1;i>=0;i--)
{
    while(j>=0)
    {
        s=d[j]+c[i];
        j--;
        if(s==10000)
        {
        p=true;
        break;
        }
        else
            p=false;
    }
    if(p==true)
        break;

}
if(p==true)
{
    cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
return 0;
}

Hello,

The International Institute of Information Technology, Hyderabad, India cordially invites you to be a part of Felicity, the annual cultural and technical festival, to be held from 19th - 21st February,2010.

1) Codecraft 2010

CodeCraft 2010, the online programming competition is all set to start on 14th February,2010. Codecraft requires eight hours of brainstorming over some of the toughest algorithms challenges from various fields of Computer Science.

Where : http://felicity.iiit.ac.in/codecraft/
When  : 14th February , 2010 , 2 pm - 10 pm IST(GMT +5:30).

2) Time Limit Exceeded

This is an unusual programming event which emphasizes on solving problems under special constraints. The event is based on C/C++ with the scoring depending on factors like code length, deviation from the best available solution, or even the number of semi-colons and whitespaces used.

Where : http://felicity.iiit.ac.in/tle
When  : 15th February 2010 2pm to 17th February 2pm (48 hours [2 days]) IST (GMT +5:30).

3) MathematiKa 2010

MathematiKa 2010 is an online mathematical programming contest which emphasizes on fusion of mathematics and computing. Contestants may use ANY language of their choice.

Where : http://felicity.iiit.ac.in/~math
When  : 17th February, 2010 , 4pm  -  12pm IST(GMT +5:30).


You need to REGISTER online to participate in these event. There are prizes in each of the mentioned events, details of which will be put on the site in due time. Kindly visit the respective sites for more details.

For queries , mailto : codecraft10@gmail.com , tle10.001@gmail.com, mathematika1.2k10@gmail.com

--
Thanks and Regards
Team Felicity 2K10

Why WA48? Please, give some tests.

Hello! I have the following task:

I have 2 groups: boys and girls. Each boy has a list of girls' names. The list contains girls he want to dance with. Each girl has the same list with boys' names. I khow, that the quantity of girls is not less, than the quantity of boys. I have to answer the question: are there pairs boy-girl (in each pair the guys want to dance with each other) when all girls will dance? Each list is not empty.

Please, give me an idea to solve this problem. Thank you.

Is string comparing case-sensitive?

I have a good hash function (I think), but i don`t know how to store the hash codes for fast access. please help

Edited by author 12.07.2009 06:39

Be careful!

The input string may contain spaces and/or line breaks!

uses
  SysUtils ,Math;

Var
  a, R:integer;
  s :Real;
begin
  ReadLn(a,R);
  If R > 0.5*a then
    S := pi*R*R + 2*a*sqrt(R*R-0.25*a*a) -4*R*R*arcCos(0.5*a/R);
  else S := pi * R*R;
  WriteLn(S :0:3);
end.

I passed the test in the problem.
But why I couldn't pass the  first test?
Here are my program:
var
  s,s2:string;
  n,i,j,k,l:longint;
  s1,c:array[1..50000]of string;
  m:array[1..100,1..100]of integer;
  b:boolean;
function xun(len:longint):boolean;
  var
    j:longint;
  begin
    if j=1
    then begin
           xun:=true;
           exit;
         end;
    for j:=len-1 downto 1 do
      begin
        if m[j,len]>0
        then begin
               if xun(j)
               then begin
                      write(s1[m[j,len]],' ');
                    end;
             end;
      end;
  end;
begin
  //assign(input,'1002.in');reset(input);
  readln(s);
  repeat
  l:=length(s);
  readln(n);
  for i:=1 to n do
    begin
      b:=false;
      readln(s1[i]);
      for j:=1 to length(s1[i]) do
        case s1[i][j] of
          'i','j':c[i]:=c[i]+'1';
          'a','b','c':c[i]:=c[i]+'2';
          'd','e','f':c[i]:=c[i]+'3';
          'g','h':c[i]:=c[i]+'4';
          'k','l':c[i]:=c[i]+'5';
          'm','n':c[i]:=c[i]+'6';
          'p','r','s':c[i]:=c[i]+'7';
          't','u','v':c[i]:=c[i]+'8';
          'w','x','y':c[i]:=c[i]+'9';
          'o','q','z':c[i]:=c[i]+'0';
        end;
      for j:=1 to l-length(c[i])+1 do
        begin
          s2:=copy(s,j,length(c[i]));
          if s2=c[i]
          then m[j,j+length(c[i])-1]:=i;
        end;
    end;
    for j:=length(s)-1 downto 1 do
      begin
        if m[j,length(s)]>0
        then begin
               if xun(j-1)
               then begin
                      b:=true;
                      write(s1[m[j,length(s)]]);
                      break;
                    end;
             end;
      end;
    if b=false
    then write('No solution.');
    readln(s);
    writeln;
      fillchar(s1,sizeof(s1),0);
      fillchar(c,sizeof(c),0);
      fillchar(m,sizeof(m),0);
  until s='-1';
  //close(input);
end.