Обсуждение @ 1838. Удар самурая @ Timus Online Judge

Ade to admin for input description // Задача 1838. Удар самурая 2 июн 2023 14:56

Aneto beautiful problem // Задача 1838. Удар самурая 10 июл 2012 16:30

nvnp Samurai's Stroke [5] // Задача 1838. Удар самурая 30 апр 2011 18:23

Can the prop be at the end of the stick ?

Isn't it always length of stick for n=2 and n=3 ?

Did i understand the question correctly ?

This was giving WA.

v[0]=0;
int leftend=(v[1]-v[0])*2;
int rightstart=len- ((len-v[n])*2);
// 0 to leftend ,closest v[i];
// rightstart to len closest[j];
//
//
for(i=1;i<=n;i++){
if(leftend<=v[i]) { leftend=v[i];break; }
}

for(i=n;i>=1;i--){
if(rightstart>=v[i]) { rightstart=v[i];break; }
}

printf("%d\n",len-((rightstart-leftend)<0?0:((rightstart-leftend))));

AterLux Re: Samurai's Stroke [4] // Задача 1838. Удар самурая 30 апр 2011 20:10

every remaining peace should be remin at least at two props,
so, for n < 4, there no possible place to stroke (result = l)
Similar you can to ignore the part from 0 to v[2] and from v[n - 1] to l
prop can not be at the end of the stick, but it can be at strike-point (at end of remaining part)
You need to look all interval between v[i] and v[i + 1] for i in 2..(n-2) to find summ of strike-proof places, remaining part will fall, either outside (if strike too close to prop) or inside (if strike too far). So between every props there is only strike-proof interval.
Excuse my English :)

nvnp Re: Samurai's Stroke [3] // Задача 1838. Удар самурая 30 апр 2011 21:23

Can you give an example ? I understand that Gennosuke cuts only once.

An example would help a lot.

I understood as follows

We have props at 1 2 3 4
0 1 2 3 4 5
[START]..v[1]..v[2].v[3]...[vn] XXXXXX[LEN]

now since the left overlang is v[1], for the center of mass to lie between 2 props the closest prop should >=2*v[1] and for the right overlang the center of mass to lie , it should be (len -v[n])*2 , so the closest prop <(len-v[n])*2 . We paint the overhang to these props.

AterLux Re: Samurai's Stroke [2] // Задача 1838. Удар самурая 1 май 2011 02:03

for example

10 4
2 3 7 8

we can't strike at left of 3, because left part will have only 1 prop and will fall down
like this we can't strike at right of 7
so, consider interval 3...7
at position less than 4 - left part of stick will fall down to left (because it's center of mass left-of first prop at position 2)
at position more than 6 - left part will fall to right,
also for right-part.
We can find the only interval we can use - it from 4 thru 6

So, we shall paint 10 - (6 - 4) = 8

Edited by author 01.05.2011 02:08

nvnp Re: Samurai's Stroke [1] // Задача 1838. Удар самурая 13 май 2011 16:35

Can you give an example why we need to summuation of each interval and why we need to round it up ? I think it will always be an integer.

This gives me WA on test 7.

   for(i=1;i<=n;i++) scanf(" %d",&arr[i]);
   arr[i+1]=len;

   /*
    * v0,v1,v2,v3,v4,v5,v6
    */

   int lovr = arr[1] ;
   int rovr = len - arr[n] ;
   int tot = 2*lovr + 2*rovr ;
   int rmax=0,lmax;

   for(i=n-1;i>=1;i--)
   {
        if( ( arr[n] - arr[i] ) > rovr )
        {
             if(i==n-1) {
                    rmax=len-arr[i];
             }
             else {
                 rmax=2*rovr;
             }
             break;
        }
   }

   for(i=2;i<=n;i++)
   {
       if((arr[i]-arr[1]) > lovr)
       {
           if(i==2){
                lmax=arr[i];
           }
           else
           {
               lmax=2*lovr;
           }
            break;
       }
   }

   if(lmax + rmax > len) printf("%d\n",len);
   else if(tot > len) printf("%d\n",len);
   else printf("%d\n",rmax+lmax);

Edited by author 13.05.2011 16:36

AterLux Re: Samurai's Stroke // Задача 1838. Удар самурая 13 май 2011 17:32

try this
13 6
1 2 6 7 11 12

result 8

Ronnie test [1] // Задача 1838. Удар самурая 30 апр 2011 13:46

Viktor WTF????? [1] // Задача 1838. Удар самурая 30 апр 2011 14:07

Обсуждение задачи 1838. Удар самурая