The input is not very usual!!! n goes BEFORE m.
This permutation cost me 11 unsuccessfull submissions! :)

Edited by author 24.03.2005 21:11

At first I had no ideas how to solve it ))
Then I thought that it is a completely physical problem and started to write formulas....
When, after about an hour, I came to integrals I understood that........ I am not a physicist... but I am a PROGRAMER! And at the same moment a good idea came to me: "Oh my God, It is a kind of a labyrinth!"
In 10 minutes source was done and I got AC. Now I am thinking... how easier to be a programmer, than physicist :)))

//WA..
#include <stdio.h>
#include <string.h>
#define maxn 100100
#define lcase(a) (a>='A'&&a<='Z'?a+32:a)

char s[maxn],ch;
long sp;
char strs[35][30] = {
"and",
"array",
"begin",
"case",
"class",
"const",
"div",
"do",
"else",
"end",
"for",
"function",
"if",
"implementation",
"interface",
"mod",
"not",
"of",
"or",
"procedure",
"program",
"record",
"repeat",
"shl",
"shr",
"string",
"then",
"to",
"type",
"unit",
"until",
"uses",
"var",
"with",
"while"
};
char tmp[maxn];
char tmp2[maxn];

long bs () {
    long l, m, r, t;

    l = 0;
    r = 34;

    while (l<=r) {
        m = ((l+r)>>1);
        t = strcmp(strs[m],tmp2);
        if (t == 0)
            return m;
        if (t > 0)
            r = m - 1;
        else
            l = m + 1;
        }
    return -1;
    }

void comment (long l, long r) {

    printf("<span class=comment>");
    for (;l<=r;l++)
        printf("%c",s[l]);
    printf("</span>");
    }

void string (long l, long r) {

    printf("<span class=string>");
    for (;l<=r;l++)
        printf("%c",s[l]);
    printf("</span>");
    }

void number (long l, long r) {

    printf("<span class=number>");
    for (;l<=r;l++)
        printf("%c",s[l]);
    printf("</span>");
    }

void identifier (long l, long r) {
    long i;

    i = 0;
    for (;l<=r;l++) {
        tmp2[i] = lcase(s[l]);
        tmp[i ++] = s[l];
        }
    tmp2[i] = 0;
    tmp[i] = 0;
    i = bs();
    if (i > -1)
        printf("<span class=keyword>%s</span>",tmp);
    else
        printf("%s",tmp);
    }

int main () {
    long i,j,t;

    sp = 0;
    while (scanf("%c",&ch) > 0)
        s[sp++] = ch;
    s[sp] = 0;
    for (i=0;i<sp;) {
        if (s[i] == '{') {
            //Comment Type 1
            j = i + 1;
            while (s[j] != '}')
                j ++;
            comment(i,j);
            i = j + 1;
            }
        else
            if (s[i] == '/' && s[i+1] == '/') {
                //Comment Type 2
                j = i + 1;
                while (s[j] != '\n')
                    j ++;
                comment(i,j - 1);
                i = j;
                }
            else
                if (s[i] == '\'') {
                    j = i + 1;
                    while (s[j] != '\'')
                        j ++;
                    string(i,j);
                    i = j + 1;
                    }
                else
                    if (s[i] == '#' && s[i+1]>='0' && s[i+1]<='9') {
                        j = i + 2;
                        while (s[j] >= '0' && s[j] <= '9')
                            j ++;
                        string(i,j - 1);
                        i = j;
                        }
                    else
                        if (s[i]>='0' && s[i]<='9') {
//                            while (1);
                            t = 0;
                            j = i + 1;
                            while (s[j] >= '0' && s[j] <= '9' || s[j] == '.' && s[j+1] >= '0' && s[j+1] <= '9' && !t) {
                                if (s[j] == '.')
                                    t ++;
                                j ++;
                                }
                            number(i,j - 1);
                            i = j;
                            }
                        else
                            if (s[i] >= 'A' && s[i] <= 'Z' || s[i] >= 'a' && s[i] <= 'z' || s[i] == '_') {
                                j = i + 1;
                                while (s[j] >= 'A' && s[j] <= 'Z' || s[j] >= 'a' && s[j] <= 'z' || s[j] >= '0' && s[j] <= '9' || s[j] == '_')
                                    j ++;
                                identifier(i,j - 1);
                                i = j;
                                }
/*
                            else
                                if (s[i] == '.' && s[i+1] >= '0' && s[i+1] <= '9') {
                                    j = i + 1;
                                    while (s[j] >= '0' && s[j] <= '9')
                                        j ++;
                                    number(i,j - 1);
                                    i = j;
                                    }
*/
                            else
                                //Others
                                printf("%c",s[i++]);
        }

    return 0;
    }

I can't imagine how its possible. Test 1 == Sample Test 1, I think.

Here is my code (I delete it when I find the bug):

[code deleted]

Oh, I am too stupid... Don't read this!!!!!!!!

Edited by author 17.08.2007 13:33

i'm sorry for posting my code here, it will be deleted as soon as i figure out my problem.

it's O(n^2) algo based on recursion with caching. the main idea is following:
1. I make an edge from first vertex to all others. Let the edge be (0,i), then optimal answer will be dist(0,i)+(optimal_answer(0,i-1))+(optimal_answer(i,n)). Here and afterwards vertex n is the same with vertex 0. Or optimal answer will be dist(0,i)+(optimal_answer(i,1))+(optimal_answer(n,i+1)).
2. Optimal_answer(fr,to) is:
2.1 min(Optimal_answer(fr+1,to)+dist(fr,fr+1),Optimal_answer(to,fr+1)+dist(fr,to))
in case fr<to
2.2 min(Optimal_answer(to,fr-1)+dist(fr,to),Optimal_answer(fr-1,to)+dist(fr,fr-1))
in case fr>to

Optimal_answer(fr,to) returns length of the path _starting_ with fr and _ending_ with to. it's some kind of directed path :)

based on this facts i wrote this program:

 [CODE WAS HERE]


which is WAing on test 2 :( I don't know, maybe i have only a little stupid mistake, or my algo is incorrect at all. But my friend sais it's ok, so ...


Thanks in advance

Edited by author 01.03.2007 18:11

Edited by author 02.03.2007 16:07

help me!
const
n=2;
var
i,l:longint;
q,w,e:array[1..n] of longint;
a,b,c,p,h,r:real;
Begin
for i:=1 to 2 do
read(q[i]);
for i:=1 to 2 do
read(w[i]);
for i:=1 to 2 do
read(e[i]);
read(l);
if q[1]-w[1]=0 then h:=abs(e[1]-w[1])
                else h:=abs(e[2]-q[2]-(w[2]-q[2])*(e[1]-q[1])/(w[1]-q[1]))/sqrt(1+sqr((w[2]-q[2])/(w[1]-q[1])));
c:=sqrt(sqr(q[2]-w[2])+sqr(q[1]-w[1]));
a:=sqrt(sqr(e[2]-w[2])+sqr(e[1]-w[1]));
b:=sqrt(sqr(q[2]-e[2])+sqr(q[1]-e[1]));
if a*a+b*b<c*c then h:=h
               else
               begin
               if a*a+c*c<b*b then h:=a;
               if b*b+c*c<a*a then h:=b;
               end;
if h>l then h:=h-l
       else h:=0;
writeln(h:5:2);
if a>b then begin if a>l then r:=a-l
                         else r:=0;
            end
       else begin if b>l then r:=b-l
                         else r:=0;
            end;
writeln(r:5:2);
readln;
readln;
end.

Edited by author 17.08.2007 02:59

1 067 KB
used 30 bit structure with queue
struct cell {
   unsigned value : 30;
   cell (unsigned in) : value (in) {};
};
std::queue <cell> major;
ok, queue build with pointers, so lets soluted witout it

971 KB
used 30 bit structure with vector
std::vector <cell> major;
hm...
ok let's try other way


used indexing of values - there are 100'000 posible values, so let's indexing every value and storage indexes
std::map <int, int> i2v, v2i;
1 223 KB

bad way, well let's make crazy thing - build bit storage with next structure - for every value calculate number of max bit with help of next function
int length (unsigned in) {
   int result (0);
   while (in) {
      ++result;
      in >>= 1;
   };
   return result;
};
than push into storage last {length (value)} bits of value and than 5 bits, which content number of bits of this value (maximum value is 1'000'000 so maximum count of bits is 30, thats why counter of bits count must have 5 bits)
ok for example if PUSH value 5 [101]
length (5) return 3, we push into storage bits [101] and than five bits with length of value bits - 3 [00011]
std::list <unsigned char> major;
783 KB

...
yeah, last idea - use bit storage and indexing values
803 KB

guys, who solved this problem with C++ - you are genius, I am out of ideas, have smb other one ?

I thing, that my program solve this task!
But wrong Test#4.
What I hadn't read?
Sum of all thing must be 100 00?
I don't know...
[или я просто не фтыкаю информатику  ;)]
==== SOURSE ====

Var
 cur,last:longint;
 i,n:longint;
 s:string;
 f:boolean;
Begin
 readln(n);
 readln(s);
 last:=GetProc(s);
 sum:=0;
 f:=false;
 for i:=2 to n do
    Begin
     readln(s);
     cur:=GetProc(s);
     if (last>=cur) then cur:=last
                    else
                      Begin
                         f:=true;
                         cur:=last;
                      End;
    End;
 if f then writeln('NO')
      else writeln('YES');
End.

*** GetProc - returne procent of thing.

WA on 2

WA on 2

Hic.. help me, i have some problem on test #6... :-/

#include<stdio.h>
#include<math.h>

double
x0,q0,x1,q1,x2,q2,a,b,c,a0,b0,c0,a1,b1,c1,cx,cq,r,minx,maxx,minq,maxq;

double roundup(double num)
{
  if((long)(num)==num)return num;
  else if(num>0)return(long)(num+1);else return(long)(num);
}

double rounddown(double num)
{
  if((long)(num)==num)return num;
  else if(num>0)return(long)(num);else return(long)(num-1);
}

int main()
{
  scanf("%lf%lf%lf%lf%lf%lf",&x0,&q0,&x1,&q1,&x2,&q2);
  minx=x0;if(minx>x1)minx=x1;
  maxx=x0;if(maxx<x1)maxx=x1;
  minq=q0;if(minq>q1)minq=q1;
  maxq=q0;if(maxq<q1)maxq=q1;
  cx=(x0+x1)/2;cq=(q0+q1)/2;
  a=q1-q0;b=x0-x1;c=x1*q0-x0*q1;
  if(a!=0){a0=b/a;b0=-1;c0=cq-a0*cx;}
    else{a0=1;b0=0;c0=-cx;}
  cx=(x0+x2)/2;cq=(q0+q2)/2;
  a=q2-q0;b=x0-x2;c=x2*q0-x0*q2;
  if(a!=0){a1=b/a;b1=-1;c1=cq-a1*cx;}
    else{a1=1;b1=0;c1=-cx;}
  cx=(b0*c1-b1*c0)/(a0*b1-a1*b0);cq=(a1*c0-a0*c1)/(a0*b1-a1*b0);
  r=sqrt((x0-cx)*(x0-cx)+(q0-cq)*(q0-cq));
  a=q1-q0;b=x0-x1;c=x1*q0-x0*q1;
  if((a*x2+b*q2+c)*(a*(cx-r)+b*cq+c)>=0)minx=cx-r;
  if((a*x2+b*q2+c)*(a*(cx+r)+b*cq+c)>=0)maxx=cx+r;
  if((a*x2+b*q2+c)*(a*cx+b*(cq-r)+c)>=0)minq=cq-r;
  if((a*x2+b*q2+c)*(a*cx+b*(cq+r)+c)>=0)maxq=cq+r;
  minx=roundup(minx);
  maxx=rounddown(maxx);
  minq=roundup(minq);
  maxq=rounddown(maxq);
  if(minx<-1000)minx=-1000;if(minq<-1000)minq=-1000;
  if(maxx>1000)maxx=1000;if(maxq>1000)maxq=1000;
  printf("%0.0lf",fabs((maxx-minx)*(maxq-minq)));
  return 0;
}

Can I use any functions from string.h? I've got Compile Error and can't understand where is the problem? (I suspect string functions)
How can I find out where is the problem?

I've been keeping getting the judge message "Fail (Validator)" and wondering about it!
When I chose to have it send an auto-judge reply to get some further information, it said : "Validating program crashed while testing your solution's output." could any administor have this program checked?

Thanks

#include <iostream>
#include <math.h>
using namespace std;
double store[1000000];
int main()
{
int i=0;
while(cin>>store[i++]);
for (i--;i>=0;i--)
printf("%.4lf\n",sqrt(store[i]));
return 0;
}

  var
    n, m : longint;
    f : boolean;
    done : array[1..100] of boolean;
    put : array[1..100, 0..100] of longint;
    board : array[1..100] of longint;
        row, order : array[0..10] of longint;

  procedure sort;
    var
    i, j, x, y : longint;
    begin
      for i := 1 to n - 1 do
        for j := i + 1 to n do
          if board[i] < board[j]
            then begin
          x := board[i];
          board[i] := board[j];
          board[j] := x;
        end;
      for i := 1 to m - 1 do
        for j := i + 1 to m do
          if row[i] < row[j]
            then begin
          x := row[i];
          row[i] := row[j];
          row[j] := x;
          x := order[i];
          order[i] := order[j];
          order[j] := x;
        end;
    end;

  procedure init;
    var
    i, j, x : longint;
    begin
      readln(n, m);
      f := false;
          fillchar(put, sizeof(put), 0);
      fillchar(done, sizeof(done), false);
      for i := 1 to n do
        begin
              readln(board[i]);
            end;
      row[0] := 0;
      for i := 1 to m do
            begin
          readln(row[i]);
              order[i] := i;
        end;
    end;

  procedure print;
    var
    i, j, l : longint;
    begin
      for i := 1 to m do
        begin
          writeln(put[i, 0]);
          for j := 1 to put[i, 0] do
            write(put[i, j], ' ');
          writeln;
        end;
      halt;
    end;

  procedure make(k : longint);
    var
    i : longint;
    begin
      if f then exit;
      if (k = m + 1)
        then begin
          print;
          f := true;
          exit;
        end;
      for i := 1 to n do
        if (not done[i]) and (board[i] <= row[k])
          then begin
        done[i] := true;
                dec(row[k], board[i]);
                inc(put[order[k], 0]);
        put[order[k], put[order[k], 0]] := board[i];
        make(k + ord(row[k] = 0));
        if f then exit;
        dec(put[order[k], 0]);
                inc(row[k], board[i]);
        done[i] := false;
          end;
    end;

  begin
           init;
    sort;
    make(1);
  end.

Yes, I passed it just by searching. But firstly I sorted the ships
from short to long, then it was easy to cut the useless branch and
retrace when necessary.

Edited by author 16.08.2007 09:29