ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1273. Шпалы

why wa on test#7? Help
Послано LeXuS[Alex Kalugin] 12 июл 2004 01:27
{$R+}
var
     a, b: array[1 .. 101] of longint;
     y1, y2: array[1 .. 101] of longint;
     j, k, i, n, max, ind: longint;
     bn : boolean;
begin
 read (n);
 for i := 1 to n do read (y1[i], y2[i]);
 repeat
  bn := true;
  for i := 1 to n - 1 do
  for j := i + 1 to n do begin
    if (b[i] = 0) and (b[j] = 0) then
      if ((y1[i] > y1[j]) and (y2[i] < y2[j])) or
       ((y1[i] < y1[j]) and (y2[i] > y2[j])) or
        (y1[i] = y1[j]) or (y2[i] = y2[j]) then
         begin
          bn := false;
          inc (a[i]);
          inc (a[j]);
         end;
    end;
  max := 0;
  for i := 1 to n do if a[i] > max then begin max := a[i]; ind := i; end;
  if max > 0 then begin inc (k); b[ind] := 1; end;
  for i := 1 to n do a[i] := 0;
 until bn = true;
 writeln (k);
end.
Greedy doesn't work :)
Послано Vlad Veselov [PMG17, Vinnitsa - KNU, Kiev] 12 июл 2004 18:31
Try test
5
5 3
4 6
2 4
3 1
7 5
Correct answer is 2, but your - 3.
You can remove second and third ties.
Re: Greedy doesn't work :)
Послано KIEV_lyceum_№145 (Grinenko,Kalugin,Ryjouk) 12 июл 2004 19:32
Thanks! I Understand...
Just use DP (-)
Послано Dmitry 'Diman_YES' Kovalioff 12 июл 2004 21:32
Re: Just use DP (-)
Послано LeXuS[Alex Kalugin] 12 июл 2004 23:47
what is DP?
Dynamic programing :) (-)
Послано Dmitry 'Diman_YES' Kovalioff 13 июл 2004 12:10
Re: Dynamic programing :) (-)
Послано LeXuS[Alex Kalugin] 13 июл 2004 14:58
ok...
Help me with test 7!
Послано UMC (SSAU) 3 дек 2007 19:32
#include <iostream>

using namespace std;

void main()
{
    int y1[100];
    int y2[100];
    int n,i,q,u;

    int ct[100];
    int cty1[10000];
    int cty2[10000];
    int cr = 0,res = 0;

    int spect[100];

    cin >> n;

    for(i = 0; i<n; i++)
    {
        cin >> y1[i];
        cin >> y2[i];

        ct[i] = 0;
    }

    for(i = 0; i<n; i++)
    {
        for(q = i+1; q<n; q++)
        {
            if ( ((y1[i]>=y1[q]) && (y2[i]<=y2[q])) || ((y1[i]<=y1[q]) && (y2[i]>=y2[q])) )
            {
                ct[i]++;
                ct[q]++;

                cty1[cr] = i;
                cty2[cr] = q;
                cr++;
            }
        }
    }

    while(cr!=0)
    {
        int max = ct[0];
        int mid = 0;

        int l = 0;

        for(u = 0; u<n; u++)
        {
            if (ct[u]>max) { max = ct[u]; mid = u; }
        }

        for(u = 0; u<n; u++)
        {
            if (ct[u]==max) { spect[l] = u; l++; }
        }

        ///////////
        int mini = 10000;
        int minid = spect[0];

        for(u = 0; u<l; u++)
        {
            int cur = 0;

            for(int y = 0; y<l; y++)
                if (y!=u)
                    for(int o = 0; o<cr; o++)
                        if ( (cty1[o]==spect[u] && cty2[o]==spect[y]) || (cty2[o]==spect[u] && cty1[o]==spect[y]) ) cur++;

            if (cur<mini) { minid = spect[u]; mini = cur; }
        }
        ///////////

        mid = minid;

        for(i = 0; i<cr; i++)
        {
            if (cty1[i]==mid)
            {
                ct[cty2[i]]--;

                if (i!=cr-1)
                {
                    cty1[i] = cty1[cr-1];
                    cty2[i] = cty2[cr-1];
                }

                cr--;
                i--;
            } else
            {
                if (cty2[i]==mid)
                {
                    ct[cty1[i]]--;

                    if (i!=cr-1)
                    {
                        cty1[i] = cty1[cr-1];
                        cty2[i] = cty2[cr-1];
                    }

                    cr--;
                    i--;
                }
            }
        }

        ct[mid] = 0;
        res++;
    }

    cout << res;
    cin >> res;
}

P.S. it works with

5
5 3
4 6
2 4
3 1
7 5