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

Обсуждение задачи 1042. Центральное отопление

i just solve it,but got WR!it passed many tests,how it is WR!(help me,thanks)
Послано daizi sheng(from USTC) 23 окт 2002 10:03
/*if there are some failed tests,give it to me,thanks a lot!
 *mail to me:ls223224@hotmail.com
 */
/*the gaosi
code//////////////////////////////////////////////////////////*/
#include<math.h>
int gcd(int,int);
int lcd(int x,int y)
{
    return x * y / gcd(x,y);
}
int gcd(int x,int y)
{
    /*make sure that x > 0 && y > 0*/
    if(x == 0)
    {
        return y;
    }
    else if(x <= y)
    {
        return gcd(y % x,x);
    }
    else
    {
        return gcd(y,x);
    }
}

int xiao(int a[],int b[],int n,int (* fun)(int,int,int,int),int
_i,int _j)
{
    int i,x,y,t;
    /*found the first non-zero elem of a[]*/
    for(i = 0;i < n;i++)
        if(a[i] != 0)
        {
            break;
        }
    if(i == n)
    {
        /*a[] == zero*/
        return 0;
    }
    x = a[i];
    y = b[i];
    if(y == 0)
    {
        /*ok*/
        return 0;
    }
    t = lcd(abs(x),abs(y));
    if(x * y < 0)
    {
        t *= -1;
    }
    x = t / x;
    y = t / y;
    for(i = 0;i < n;i++)
    {
        b[i] *= y;
        b[i] -= a[i] * x;
    }
    if(fun != 0)
    {
        fun(_i,_j,x,y);
    }
    return 0;
}

int gaosi_change(int *list[],int n,int i,int j,int (* change)
(int,int))
{
    int *t;
    t = list[i];
    list[i] = list[j];
    list[j] = t;
    if(change != 0)
    {
        change(i,j);
    }
    return 0;
}

int gaosi(int *list[],int n,int (* fun)(int,int,int,int),int (*
change)(int,int))
{
    int i,j;
    for(i = 0;i < n;i++)
    {
        for(j = i;j < n;j++)
            if(list[j][i] != 0)
            {
                break;
            }
        if(j == n)
        {
            /*not found*/
            continue;
        }
        gaosi_change(list,n,i,j,change);
        for(j = i + 1;j < n;j++)
        {
            xiao(list[i],list[j],n,fun,i,j);
        }
    }
    return 0;
}

int gaosi_expand(int *list[],int n,int (* fun)(int,int,int,int))
{
    int i,j;
    for(i = n - 1;i >= 0;i--)
    {
        for(j = 0;j < i;j++)
        {
            xiao(list[i],list[j],n,fun,i,j);
        }
    }
    return 0;
}

/*end of the gaosi
code///////////////////////////////////////////////////////////////*/
#include<stdio.h>
#define MAX 260
int table[MAX][MAX];
int n;
int b[MAX];
int *list[MAX];

int init(void)
{
    int i,j;
    scanf("%d",&n);
    for(i = 0;i < n;i++)
    {
        list[i] = table[i];
    }
    for(i = 0;i < n;i++)
    {
        for(j = 0;j < n;j++)
        {
            list[i][j] = 0;
        }
        b[i] = 1;
    }
    for(i = 0;i < n;i++)
    {
        while(1)
        {
            scanf("%d",&j);
            if(j == -1)
                break;
            j--;
            list[j][i] = 1;
        }
    }
    return 0;
}

int myfun(int i,int j,int x,int y)
{
    b[j] *= y;
    b[j] -= b[i] * x;
    return 0;
}

int mychange(int i,int j)
{
    int t;
    t = b[i];
    b[i] = b[j];
    b[j] = t;
    return 0;
}

int fun(void)
{
    gaosi(list,n,myfun,mychange);
    gaosi_expand(list,n,myfun);
    return 0;
}

int output(void)
{
    int i;
    int flag = 0;
    for(i = 0;i < n;i++)
    {
        if(abs(b[i]) % 2 == 1 && abs(list[i][i]) % 2 == 1)
        {
            if(flag != 0)
            {
                printf(" ");
            }
            flag = 1;
            printf("%d",i + 1);
        }
    }
    if(flag == 0)
    {
        printf("No solution\n");
    }
    else
    {
        printf("\n");
    }
    return 0;
}

int main(void)
{
    init();
    fun();
    output();
    return 0;
}


Do not waste your time to see this,i know it is WR!
Послано daizi sheng(from USTC) 23 окт 2002 15:32
> /*if there are some failed tests,give it to me,thanks a lot!
>  *mail to me:ls223224@hotmail.com
>  */
> /*the gaosi
> code//////////////////////////////////////////////////////////*/
> #include<math.h>
> int gcd(int,int);
> int lcd(int x,int y)
> {
>     return x * y / gcd(x,y);
> }
> int gcd(int x,int y)
> {
>     /*make sure that x > 0 && y > 0*/
>     if(x == 0)
>     {
>         return y;
>     }
>     else if(x <= y)
>     {
>         return gcd(y % x,x);
>     }
>     else
>     {
>         return gcd(y,x);
>     }
> }
>
> int xiao(int a[],int b[],int n,int (* fun)(int,int,int,int),int
> _i,int _j)
> {
>     int i,x,y,t;
>     /*found the first non-zero elem of a[]*/
>     for(i = 0;i < n;i++)
>         if(a[i] != 0)
>         {
>             break;
>         }
>     if(i == n)
>     {
>         /*a[] == zero*/
>         return 0;
>     }
>     x = a[i];
>     y = b[i];
>     if(y == 0)
>     {
>         /*ok*/
>         return 0;
>     }
>     t = lcd(abs(x),abs(y));
>     if(x * y < 0)
>     {
>         t *= -1;
>     }
>     x = t / x;
>     y = t / y;
>     for(i = 0;i < n;i++)
>     {
>         b[i] *= y;
>         b[i] -= a[i] * x;
>     }
>     if(fun != 0)
>     {
>         fun(_i,_j,x,y);
>     }
>     return 0;
> }
>
> int gaosi_change(int *list[],int n,int i,int j,int (* change)
> (int,int))
> {
>     int *t;
>     t = list[i];
>     list[i] = list[j];
>     list[j] = t;
>     if(change != 0)
>     {
>         change(i,j);
>     }
>     return 0;
> }
>
> int gaosi(int *list[],int n,int (* fun)(int,int,int,int),int (*
> change)(int,int))
> {
>     int i,j;
>     for(i = 0;i < n;i++)
>     {
>         for(j = i;j < n;j++)
>             if(list[j][i] != 0)
>             {
>                 break;
>             }
>         if(j == n)
>         {
>             /*not found*/
>             continue;
>         }
>         gaosi_change(list,n,i,j,change);
>         for(j = i + 1;j < n;j++)
>         {
>             xiao(list[i],list[j],n,fun,i,j);
>         }
>     }
>     return 0;
> }
>
> int gaosi_expand(int *list[],int n,int (* fun)(int,int,int,int))
> {
>     int i,j;
>     for(i = n - 1;i >= 0;i--)
>     {
>         for(j = 0;j < i;j++)
>         {
>             xiao(list[i],list[j],n,fun,i,j);
>         }
>     }
>     return 0;
> }
>
> /*end of the gaosi
>
code///////////////////////////////////////////////////////////////*/
> #include<stdio.h>
> #define MAX 260
> int table[MAX][MAX];
> int n;
> int b[MAX];
> int *list[MAX];
>
> int init(void)
> {
>     int i,j;
>     scanf("%d",&n);
>     for(i = 0;i < n;i++)
>     {
>         list[i] = table[i];
>     }
>     for(i = 0;i < n;i++)
>     {
>         for(j = 0;j < n;j++)
>         {
>             list[i][j] = 0;
>         }
>         b[i] = 1;
>     }
>     for(i = 0;i < n;i++)
>     {
>         while(1)
>         {
>             scanf("%d",&j);
>             if(j == -1)
>                 break;
>             j--;
>             list[j][i] = 1;
>         }
>     }
>     return 0;
> }
>
> int myfun(int i,int j,int x,in