Edited by author 29.10.2011 23:25

I think, my solution is very tricky. It can be more simpler and smaller. How many lines of code your solution?

Note that FIRST PERSON IN THE INPUT sends a message first!

Please.

why WA on 3 test?

test #2: M==1 => read N numbers from and output index of minimal
test #3: N==1 => output '1' M times

Может ли после разделения западная часть принадлежать Финляндии, а восточная Швеции?

My AC program uses algorithm with process modelling. It's complexity is O(N) in memory and time.

3
0 0 0

I am nearly crumble !!!

I've got wrong answer on 20th test. Please could anybody give me some test, which will help?

In 2 sample:

Arch?????rchibaldIronfist
Archibald

but we can put Archibald from 1st position and from 9th position. Why answer is 1?

Edited by author 14.10.2011 19:50

this is my solutioon please help me!


#include <iostream>
#include <stdio.h>
using namespace std;
long a[50001], sum=0;
void merge(long,long,long);
void merge_sort(long low,long high)
{
 long mid;
 if(low<high)
 {
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
void merge(long low,long mid,long high)
{
 long h,i,j,b[50001],k;
 h=low;
 i=low;
 j=mid+1;
 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   h++;
  }
  else
  {
   b[i]=a[j]; sum+=mid-h+1;
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 for(k=low;k<=high;k++) a[k]=b[k];
}

int main(){

 long num,i,a[50001];;
 cin>>num;
 for(i=1;i<=num;i++)
 {
  cin>>a[i] ;
 }if(num==1)cout<<a[1];
 else{
 merge_sort(1,num);
 cout<<a[num/2];
}return 0;}

2
8 0 0
8 100 0

Answer: 11600

CONST
  BigNum = 31337;
VAR
  N, I, J : LongInt;
  X, Y, R : ARRAY[1..1010] OF Extended;
  MinX, MaxX, MinY, MaxY, cX, cY : Extended;
  SMinX, SMaxX, SMinY, SMaxY, Best, Sum : Extended;
LABEL L1, L2, L3, L4;
BEGIN
  ReadLn(N);
  ReadLn(R[1], X[1], Y[1]);
  MinX := X[1]-R[1];
  MaxX := X[1]+R[1];
  MinY := Y[1]-R[1];
  MaxY := Y[1]+R[1];
  FOR I := 2 TO N DO
    BEGIN
      ReadLn(R[I], X[I], Y[I]);
      IF X[I]-R[I] < MinX THEN MinX := X[I]-R[I];
      IF X[I]+R[I] > MaxX THEN MaxX := X[I]+R[I];
      IF Y[I]-R[I] < MinY THEN MinY := Y[I]-R[I];
      IF Y[I]+R[I] > MaxY THEN MaxY := Y[I]+R[I];
    END;
  IF ((MaxX-MinX) <= 100) AND ((MaxY-MinY) <= 100) THEN
    BEGIN
      Write(100*100);
      Halt;
    END;
  SMaxX := MaxX;
  SMaxY := MaxY;
  SMinX := MinX;
  SMinY := MinY;
  IF (SMaxX-SMinX) < 100 THEN SMaxX := SMinX+100;
  IF (SMaxY-SMinY) < 100 THEN SMaxY := SMinY+100;
  Best := (SMaxX-SMinX)*(SMaxY-SMinY);
  FOR I := 1 TO N DO
    BEGIN
      cX := X[I]+R[I];
      cY := Y[I]-R[I];
      SMinX := +BigNum;
      SMaxX := -BigNum;
      SMinY := +BigNum;
      SMaxY := -BigNum;
      FOR J := 1 TO N DO
        BEGIN
          IF ((X[J]+R[J]) <= cX) AND (Y[J]-R[J] >= cY) THEN Continue;
          IF (X[J]-R[J] < cX) AND (Y[J]-R[J] >= cY) AND
          (X[J]+R[J] > cX) THEN GOTO L1;
          IF (X[J]+R[J] <= cX) AND (Y[J]+R[J] > cY) AND
          (Y[J]-R[J] < cY) THEN GOTO L1;
          IF X[J]-R[J] < SMinX THEN SMinX := X[J]-R[J];
          IF X[J]+R[J] > SMaxX THEN SMaxX := X[J]+R[J];
          IF Y[J]-R[J] < SMinY THEN SMinY := Y[J]-R[J];
          IF Y[J]+R[J] > SMaxY THEN SMaxY := Y[J]+R[J];
        END;
      IF SMinX = BigNum THEN Continue;
      IF (SMinX < cX) AND (SMaxY > cY) THEN Continue;
      IF (SMaxX-SMinX) < 100 THEN SMaxX := SMinX+100;
      IF (SMaxY-SMinY) < 100 THEN SMaxY := SMinY+100;
      IF (cX-MinX) < 100 THEN cX := MinX+100;
      IF (MaxY-cY) < 100 THEN cY := MaxY-100;
      Sum := (SMaxX-SMinX)*(SMaxY-SMinY)+(cX-MinX)*(MaxY-cY);
      IF (Best > Sum) THEN Best := Sum;
L1:
    END;
  FOR I := 1 TO N DO
    BEGIN
      cX := X[I]+R[I];
      cY := Y[I]+R[I];
      SMinX := +BigNum;
      SMaxX := -BigNum;
      SMinY := +BigNum;
      SMaxY := -BigNum;
      FOR J := 1 TO N DO
        BEGIN
          IF ((X[J]+R[J]) <= cX) AND (Y[J]+R[J] <= cY) THEN Continue;
          IF (X[J]-R[J] < cX) AND (Y[J]+R[J] <= cY) AND
          (X[J]+R[J] > cX) THEN GOTO L2;
          IF (X[J]+R[J] <= cX) AND (Y[J]+R[J] > cY) AND
          (Y[J]-R[J] < cY) THEN GOTO L2;
          IF X[J]-R[J] < SMinX THEN SMinX := X[J]-R[J];
          IF X[J]+R[J] > SMaxX THEN SMaxX := X[J]+R[J];
          IF Y[J]-R[J] < SMinY THEN SMinY := Y[J]-R[J];
          IF Y[J]+R[J] > SMaxY THEN SMaxY := Y[J]+R[J];
        END;
      IF SMinX = BigNum THEN Continue;
      IF (SMinX < cX) AND (SMinY < cY) THEN Continue;
      IF (SMaxX-SMinX) < 100 THEN SMaxX := SMinX+100;
      IF (SMaxY-SMinY) < 100 THEN SMaxY := SMinY+100;
      IF (cX-MinX) < 100 THEN cX := MinX+100;
      IF (cY-MinY) < 100 THEN cY := MinY+100;
      Sum := (SMaxX-SMinX)*(SMaxY-SMinY)+(cX-MinX)*(cY-MinY);
      IF (Best > Sum) THEN Best := Sum;
L2:
    END;
  FOR I := 1 TO N DO
    BEGIN
      cX := X[I]-R[I];
      cY := Y[I]-R[I];
      SMinX := +BigNum;
      SMaxX := -BigNum;
      SMinY := +BigNum;
      SMaxY := -BigNum;
      FOR J := 1 TO N DO
        BEGIN
          IF ((X[J]-R[J]) >= cX) AND (Y[J]-R[J] >= cY) THEN Continue;
          IF (X[J]-R[J] < cX) AND (Y[J]-R[J] >= cY) AND
          (X[J]+R[J] > cX) TH

Дайте тест пожалуйста на котором можно понять условие задачи...

Разве для 4 студентов будет всего 2 пары?
А чем не устраивает вариант:
3
1 2
2 3
1 4
Тогда 1 и 2 студенты имеют по 2 друга, а 3 и 4 по 1, что в свою очередь подходит под "крах критерия успеха".

Can anyone tell me how to use dynamic programming in this problem