. - empty cage
1 - chess knight
2 - cells under attack

8 | . . . . . . . .
7 | . . . . . . . .
6 | . . 2 . 2 . . .
5 | . 2 . . . 2 . .
4 | . . . 1 . . . .
3 | . 2 . . . 2 . .
2 | . . 2 . 2 . . .
1 | . . . . . . . .
___________________
    a b c d e f g h
    1 2 3 4 5 6 7 8

is it possible to solve this problem with "smart" backtracking algo using a lot of restrictions ?

Please I got Crash(Stack Overflow), I implemented my first heavy-light descomposition and tried this problem, but I got this.

I got AC, I had to  convert the DFS to BFS, to evade the StackOverflow.

Edited by author 02.11.2011 04:45

Edited by author 02.11.2011 07:20

Edited by author 02.11.2011 08:20

Sir Isaac Newton is important to this problem.
In TWO different ways.

Why WA 28?I don't understand.
Here is my code:
program gjkh;
var a,b,ch,n,i,kol,sh,fir,sec,thi:longint;
m:array[1..100001]of longint;
flag:boolean;
begin
read(a);readln(b);
n:=0;
while not seekeof do begin
read(ch);
  if (n=0)or(m[n]<>ch)then begin
  n:=n+1;
  m[n]:=ch;
  end;
end;
flag:=true;
kol:=1;
for i:=1 to n do begin
if (i=1)then fir:=m[i]
  else begin
    if (flag=true)then begin
    sec:=m[i];
    flag:=false;
    end
    else begin
    thi:=m[i];
      if ((thi-sec)*(sec-fir)>0)then begin
      fir:=sec;sec:=thi;
      end
      else begin
      fir:=thi;
      kol:=kol+1;
      flag:=true;
      end;
    end;
  end;
end;
writeln(kol);
end.

Edited by author 16.06.2021 15:21

Edited by author 16.06.2021 15:22

see https://github.com/yosupo06/library-checker-problems/issues/610

my AC does not pass this short test

#include<algorithm>
#include<cstdio>
using namespace std;
#define MAX_N 250000

int n, i, t1, t2;
int *heap;

int main(){
    scanf("%d", &n);
    heap = new int[n/2+2];
    for(i = 0; i < n/2+1; ++i){
        scanf("%d", heap+i);
        push_heap(heap, heap+i+1);
    }

    for(i = 0; i < n/2-(n+1)%2; ++i){
        scanf("%d", heap+n/2+1);
        push_heap(heap, heap+n/2+2);
        pop_heap(heap, heap+n/2+2);
    }

    if(n%2){
        printf("%d.0\n", heap[0]);
    }else{
        t1 = heap[0];
        pop_heap(heap, heap+n/2+1);
        t2 = heap[0];
        if((t1+t2)%2){
            printf("%d.5\n", t1/2+t2/2);
        }else{
            printf("%d.0\n", t1/2+t2/2+t1%2);
        }
    }
    delete[] heap;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int i,j,k,l,ii;
    int m,n;
    int girls[101];
    int boys[101];
    int count = 0;
    int upsets = 0, girlUpsets = 0, boyUpsets = 0, currentUpsets = 0;
    int happyGirls = 0;
    int chooseGirl = 0, chooseBoy = 0;

    for (i = 0; i <= 100; i ++)
    {
        girls[i] = 0;
        boys[i] = 0;
    }

    cin >> n >> m; //n girls m boys
    for (i = 1; i <= n; i ++)
    {
        cin >> girls[i];
    }
    for (j = 1; j <= m; j ++)
    {
        cin >> boys[j];
    }

    count = min (m, n);
    //计算无配对upset值
    for (i = 1; i <= n; i ++)
        upsets += girls[i];


    happyGirls = 0;


    for (i = 1; i <= count; i ++)

    {
        for (j = 1; j <= n; j ++)
            for ( k = 1; k <= m; k ++)
            {
                girlUpsets = 0;
                boyUpsets = 0;
                //计算girl upset值
                for (l = 1; l <= n; l ++)
                {
                    if (l != j)
                    {
                        girlUpsets += girls[l];
                    }
                }


                //计算boy upset值
                for (l = 1; l <= m; l ++)
                {
                    if (l != k)
                        boyUpsets += boys[l] * (happyGirls + 1);
                    //cout << "werqe: " << boys[l] << '\t' << boyUpsets << endl;
                }


                currentUpsets = girlUpsets + boyUpsets;
                if (currentUpsets < upsets)
                {
                    upsets = currentUpsets;
                    chooseGirl = j;
                    chooseBoy = k;
                }

            }

        if (chooseBoy != 0  && chooseGirl != 0)
        {
            happyGirls ++;

            //删除第chooseGirl个girl
            for (ii = chooseGirl; ii <= n - 1; ii ++)
               girls[ii] = girls[ii + 1];
            n --;

            //删除第chooseBoy个boy
            for (ii = chooseBoy; ii <= m - 1; ii ++)
                boys[ii] = boys[ii + 1];
            m --;
        }

    }
    cout << upsets << endl;
    return 0;
}

Find a robust feature to distinguish different bones with same total dots.
This really is an easy problem once you find that feature.

Try this tests

INPUT
tram
OUTPUT
Tram driver

INPUT
tram.tram
trolleybus
OUTPUT
Tram driver

i need some test... i guess the mistake is about "tram", i don't know which pattern of "tram*" should be counted

My solution is fast! valery@uni.lg.ua

Why is here the runtime error on the 6 test?
What test is 6?

#include <iostream>
#include <cmath>
using namespace std;

void ghjkl(long double p)
{cout << fixed;
cout.precision(4);
cout << p << endl;}

int main() {
long double a[1000]={-1.0};
long long i=0;
while(cin)
{cin >> a[i];
i++;}
i=i-2;
long double b[1000];
for(int k=0; k<1000; k++)
{b[k]=sqrt(a[k]);}
for(int m=i; m>=0; m--)
{ghjkl(b[m]);}
return 0;
}

Edited by author 24.03.2021 16:53

Edited by author 24.03.2021 16:54

Hi,

Well it took me a while to figure out as to how to approach this problem but as it turned out it is pretty straightforward. I divided the problem into two parts. First I printed out the elements up until the middle diagonal. And then the elements after that.

Here is the format of the numbers for 4 X 4 array

0,0  0,1  0,2  0,3
1,0  1,1  1,2  1,3
2,0  2,1  2,2  2,3
3,0  3,1  3,2  3,3

We can see a pattern here. First print the element 0,0.

Then -> 1,0 to 0,1    (i = 1 to i = 0 and j = 0 to j = 1)
Then -> 2,0 to 0,2    (i = 2 to i = 0 and j = 0 to j = 2)
Then -> 3,0 to 0,3    (i = 3 to i = 0 and j = 0 to j = 3)

So, basically as we are heading towards the main diagonal, we are increasing the value of i and at the same time running j from 0 to i.

Implementing this will get you the first 10 out of 16. For the rest of them, we have the same pattern again but this time its reverse

Then -> 3,1 to 1,3    (i = 3 to i = 1 and j = 1 to j = 3)
Then -> 3,2 to 2,3    (i = 3 to i = 2 and j = 2 to j = 3)
Then the last element 3,3

So, this just requires some clever manipulation of the for loops or while loops.

gives me WA 1

In order to achieve absolute safety providing electricity to the camps, besides an electric supplying system, the host organization set up a path from a reserved electricity generator (which is placed in one of the camps) to every camp once,
this means that, thare is only and only one path from Pi camp to Pj camp.

Можете дать подсказку?
Я понял что количество всех пар всегда три
И число дней как посчитать
Но не могу подобрать алгоритм чтобы вывести в каком порядке будут солдаты выходить на дежурство

Edited by author 02.06.2021 13:24

Hint: Binary search!!

Solution: This is a pretty easy binary search problem. All we need is to check for every number of the second list(as first list is sorted in ascending order) let's denote as x, if we can find y = 10000-x in the first list. If we find y for any x(from the 2nd list) then we will print "YES". Because we already got a pair x, y for which x + y = 10000.

So, the complexity is NlogN(as we are doing binary search for every element of a list in the worst case).

[Code was deleted]

Edited by moderator 06.06.2021 03:06