ACM ICPC - теория чисел

Question

Я практиковал ACM ICPC в прошлом проблемы http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1030

Я не могу решить эту проблему и совершенно не знаю, как сделать это эффективно в течение 3 секунд. Я думаю, что эта проблема основана на теории чисел, но не знаю точно, что делать. Спасибо!

Answer 1

Хотя трехмерные векторы и многие переменные преобразованы в векторные задачи, они несколько сложны, поэтому мы можем сначала уменьшить размерность и изменить исходное уравнение на:A[1]* (s[1][2]-s[1][1], s[1][3]-s[1][1]) + a[2]* (s[2][2]- s[2][1], s[2][3]- s[2][1]) +.....+a[n]* (s[n][2]- s[n][1],..+a[n]*) = (()), Двумерный вектор рассматривается как вектор, начинающийся с начала координат в плоской системе координат. Если есть только два вектора, потому что a[i] является неотрицательным числом, поэтому угол должен быть PI когда есть только два вектора. N векторов может удовлетворять вышеприведенному уравнению, если угол между двумя соседними векторами не превышает PI, Код не длинный, но ему нужно математическое мышление. T_T Вот правильный код.

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

const int maxn=1000+5;
const double PI=acos(-1);
int main()
{
    int n;
    double A[maxn];
    while(scanf("%d",&n),n)
    {
        int s1,s2,s3;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&s1,&s2,&s3);
            A[i]=atan2(s2-s1,s3-s1);
        }
        sort(A,A+n);
        double tmp=0;
        for(int i=1;i<n;i++)
            tmp=max(tmp,A[i]-A[i-1]);
        tmp=max(tmp,A[0]-A[n-1]+2*PI);
        if(tmp<=PI)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

Answer 2

Поэтому я считаю, учитывая:

(a1,b1,c1), (a2,b2,c2) ... (an,bn,cn)

Вам необходимо решить, существуют ли неотрицательные коэффициенты:

X = (x1,x2,...,xn)

такой, что

x1*a1 + x2*a2 + ... + xn*an == 
x1*b1 + x2*b2 + ... + xn*bn == 
x1*c1 + x2*c2 + ... + xn*cn

Маленькая линейная алгебра - это все, что нужно.

Подсказка: попробуйте построить вход с n == 4, так что все 4 xis должны быть положительными для решения проблемы (а это не может быть решено только с 3). Это возможно?