ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1042. Central Heating

i just solve it,but got WR!it passed many tests,how it is WR!(help me,thanks)
Posted by daizi sheng(from USTC) 23 Oct 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!
Posted by daizi sheng(from USTC) 23 Oct 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