It is the problem 1490 "Fire Circle" with the limitation of R equal to 10^9 instead of 10^5. If you have an efficient solution of problem 1490, try to solve this one.

Edited by author 02.08.2015 11:36

Can not figure out the right solution that passes the test

My WA#7-program had two mistakes:
1) The output information about bloggers should have the same order as in the input. I.e. for sample test the answer

_denplusplus_
1:
2: strange_human, xoposhiy
3:

xoposhiy
1: _denplusplus_, strange_human
2: strange_human
3: strange_human

strange_human
1: _denplusplus_, xoposhiy
2: xoposhiy
3: xoposhiy

is wrong. By the way, there's nothing said about it in the problem!
But when I corrected this mistake I still had WA#7.

2) Wrong output: in several cases a comma was outputed before first name in list. Just a stupid mistake :) After correcting it I got AC.

If you're using C++, you should use a class that allow you to use big numbers. I performed that making a bigNum struct, that store the number in a string. It has one function, that multiplies that value by a given integer. Then, return that value. Once you got that, make a function powBigNum, with parameters:

-a bigNum struct
-the exponent
-The number that you'll use as product.

this function returns a bigNum struct. So, you'll get in the main code something like that:

        if(n%3 == 0)
            cout << powBigNum(num, n/3, 3).n;
        else if(n%3 == 1)
            cout << powBigNum(num, (n/3)-1, 3).product(4);
        else if(n%3 == 2)
            cout << powBigNum(num, (n/3), 3).product(2);

My program got AC in 0.031 sec 368 KB. Hope you get AC too.

My mistake was usage of queue when the correct is using a stack. Only changed that, and then got AC 0.015 sec 480 KB. I'm so happy :D

Edited by author 05.08.2015 05:31

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <cstdio>

using namespace std;

double dist(int x1, int y1, int x2, int y2)
{
     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}



int main()
{
     double mlen,rlen,dmin,dmax,dtemp,dab_bc_ca[3];
     //mlen is the perpendicular distance from C to AB
     //rlen is Rope Length
     //dab_bc_ca is length of AB, BC and CA
     int x1,y1,x2,y2,cx,cy;
     cin>>x1>>y1>>x2>>y2>>cx>>cy>>rlen;

     if (x1==x2 & y1==y2) //when A and B are same points
     {
          dtemp=dist(x1,y1,cx,cy);
          if (dtemp>rlen)
          dmin=dist(x1,y1,cx,cy)-rlen;
          else dmin=0.00;
          printf("%.2f\n%.2f",dmin,dmin);

     }
     else if (x1!=x2 or y1!=y2)
     {
     mlen=cx*(y1-y2)+cy*(x2-x1)+y1*(x1-x2)-x1*(y1-y2);
     mlen=abs(mlen)/dist(x1,y1,x2,y2);

     if (mlen==0)//Check the position of C, inside AB or Not?
     {
          if (dist(x1,y1,cx,cy)+dist(x2,y2,cx,cy)==dist(x1,y1,x2,y2)) printf("0.00\n");
          else {
                    dtemp=min(dist(cx,cy,x1,y1),dist(cx,cy,x2,y2));
                    if (rlen>=dtemp) printf("0.00\n");
                    else printf("%.2f\n",dtemp-rlen);
               }
          dmax=max(dist(x1,y1,cx,cy),dist(x2,y2,cx,cy));
          if (rlen>=dmax) cout<<"0.00";
          else printf("%.2f",dmax-rlen);
     }
     else //C is outside of AB
     {
          dab_bc_ca[0]=dist(x1,y1,x2,y2); //AB
          dab_bc_ca[1]=dist(x2,y2,cx,cy); //BC
          dab_bc_ca[2]=dist(x1,y1,cx,cy); //CA
          sort(dab_bc_ca+0,dab_bc_ca+3);
          if (dab_bc_ca[2]*dab_bc_ca[2]>dab_bc_ca[1]*dab_bc_ca[1]+dab_bc_ca[0]*dab_bc_ca[0])
          {
               //For Obtuse Angle Triangle
               dab_bc_ca[2]=dist(x1,y1,cx,cy); //CA
               dab_bc_ca[1]=dist(x2,y2,cx,cy); //CB
               dtemp=max(dab_bc_ca[2],dab_bc_ca[1]);
               //Rope length is biggest
               if (rlen>=dtemp) printf("0.00\n0.00");
               else
               {
                    dtemp=min(dist(x1,y1,cx,cy),dist(x2,y2,cx,cy));
                    if (rlen>=dtemp) printf("0.00\n");
                    else printf("%.2f\n",dtemp-rlen);
                    dtemp=max(dist(x1,y1,cx,cy),dist(x2,y2,cx,cy));
                    printf("%.2f",dtemp-rlen);
               }

          }

          else
          {
               //for Acute angle Triangle
               if (rlen>=mlen) cout<<"0.00\n"<<endl;
               else printf("%.2f\n",mlen-rlen);
               dtemp=max(dist(x1,y1,cx,cy),dist(x2,y2,cx,cy));
               if (rlen>=dtemp) cout<<"0.00";
               else printf("%.2f",dtemp-rlen);
          }
     }
     }
     return 0;
}

The suggested Scala solution for the A+B problem ran with time ~0.3. My own solution was only fractionally better.

object Problem1000 {
  def main(args: Array[String]) {
    val expression = io.Source.stdin.getLines().next().split(" ")
    println(expression(0).toInt + expression(1).toInt)
  }
}

So I'm wondering if Scala is simply an impractical choice going forwards or if perhaps the the Scala judge is running suboptimally?

Edited by author 05.08.2015 00:44

How to do my program more simply? Who khow?
When I send this program - Time limit Exceed on 20 test.
Help, who can!

Program zadacha;
var a:array[1..10000] of integer; b,c,i,j,n:integer; d:array[0..100000] of longint; m:longint;
begin
readln(n);
for i:=1 to n do
 read(a[i]);

readln(m);
for i:=1 to m do begin
 read(b,c);
  for j:=b to c do
   d[i]:=d[i]+a[j];
 end;
for i:=1 to m do
writeln(d[i]);
end.

Я решил стандартно с помощью маски: Dp[mask], где mask - очередное состояние. Рассмотрел все переходы с потерями и выбрал минимальный из них. Асимптотика O(N*2^N). Как решить эффективней (кроме оптимизации в переходах,т.е. не рассматривать,скажем три нуля подряд в маске) не знаю. Может,кто-нибудь даст идею,как кроме стандартной лобовой маски решить?

First code gives wrong answer test #13. In the next code I changed

   System.out.print(2*n/k+2*n%k);

and used Math.ceil()

   System.out.print((int)Math.ceil(2*(float)n/(float)k));

The code was accepted. What's wrong?

Edited by author 03.08.2015 07:16

Edited by author 03.08.2015 07:17

Edited by author 03.08.2015 07:17

Edited by author 03.08.2015 07:17

Edited by author 03.08.2015 07:18

Edited by author 03.08.2015 07:18

Edited by author 03.08.2015 07:22

If you are using BFS, use a adjacency list. It's faster for finding the adjacents nodes. You too should use a "direccion list". It has the same size that the adjacency list, but it's filled with boolean values. For example, in the adjacency list of the node 1, you have nodes 2 3 4. If you need to go uphill from 1 to 2, in the correspondant place of the 2, you should write a 1, and if you need to go downhill, a 0. This is how I solved. I was stuck on time limit when I was using the same format of given data, but later I understood that the adjacency list it's very faster than 2 cols matrix (faster, but uses a lot more memory). Good luck, and try all the test posted in discussion.

2 5 3
01
0
11
10001

ans: 0

Edited by author 26.06.2007 18:43

Each of the cameramen wants Lev to skate along a segment of a straight line from some point to another (and each has specified his own pair of points). Lev has decided to skate along all the specified segments passing from a segment to a segment along a circular arc so that his trajectory has the shape of a smooth curve.

Do Lev move in a circular arc or a straight line?

If there is no arc connecting two consecutive directed segments without breaks, Lev can extend one of the segments so as to connect them by an arc.

For example 2, do these circles valid to this statement?
(-1,-1) radius = sqrt(26)
(1,1) radius = 3*sqrt(2)
(0,0) radius = 2*sqrt(5)

but (-2,-2) radius = 6 is invalid because the endpoint of the segment doesn't end in this circle.
Am I right?

And Finally how do you compute 7.1415926536?
because I find that circle (-1,-1) could yield better solution for about 6.69659557624

If anyone know hint or test case for test#13

why?

Can anyone explain me how we got the sample input ?

why "2 1 1 -2", or "2 1 1 0" is not an answer ?

when i submit i have fail(checker). What can I do with that?

if the "ss" answer equal 60,
update to 0 and change mm = mm+1

:)

The fastest way is to use matrix exponentiation and it is quite simple to understand. The algorithm is O(log n), yes it is that fast!. I got AC with Python 2.7 with 0.046s. Python has an added advantage for this problem since its Integer type can be as big as the RAM of the device being used. With c++ you can still get answers fast, using matrix exponentiation, but the answers are not precise enough, and leads to WA.

Edited by author 29.07.2015 15:42