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

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

What the heck is wrong with this stupid problem?
Послано Jiang Xu 16 июл 2005 03:08
I've seen there are many WA's for this problem, even if you only need basic knowledge to solve it. Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 101

typedef struct shit
{
int x, y;
};

shit a[MAXN];
int N, i, j;
int m[MAXN];

int cmp(shit a, shit b)
{
return a.x < b.x ? 1 : 0;
}

int main(void)
{
scanf("%d\n", &N);
for (i = 0; i < N; i ++)
scanf("%d %d\n", &(a[i].x), &(a[i].y));
sort(a, a + N, cmp);

int ans = 1;
m[0] = 1;
for (i = 1; i < N; i ++)
{
m[i] = 1;
for (j = 0; j < i; j ++)
if (a[j].y < a[i].y && 1 + m[j] > m[i])
m[i] = 1 + m[j];

if (m[i] > ans) ans = m[i];
}

printf("%d\n", N - ans);

return 0;
}
Re: What the heck is wrong with this stupid problem?
Послано Sandro 16 июл 2005 22:37
Try K=0. Good luck!
Re: What the heck is wrong with this stupid problem?
Послано Macarie 18 июл 2005 14:39
"Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3..."
Oh yeah...
Re: What the heck is wrong with this stupid problem?
Послано Danica Porobic 19 июл 2005 01:50
I couldn't find bug in your source, but since I had many problems myself on this one I can send you my code. E-mail me on dporobic at gmail dot com .
Re: What the heck is wrong with this stupid problem?
Послано Jiang Xu 11 авг 2005 00:02
You were right. Thanks!