Решение задачи №475 «Арифметическая прогрессия - 2» с ACMP
Условие задачи
Задана последовательность натуральных чисел из диапазона [1, 2147483647]. Необходимо определить: можно ли выстроить эти числа в отрезок арифметической прогрессии. При необходимости порядок чисел в последовательности можно изменять.
Требуется написать программу для решения этой задачи.
Входные данные
Входной файл INPUT.TXT содержит последовательность натуральных чисел. Количество чисел в последовательности может быть от 2 до 100 000. Числа в файле разделены пробелами или символами перехода на новую строку.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать либо «Yes» в случае положительного ответа, либо «No» в противоположном случае.
Решение на C++
Решение на C++
#include <stdio.h>
void Swap (int &a,int &b)
{int c=a;a=b;b=c;}
void QuickSort(int a[], int n)
{ int l,r,m;
if(n>1)
{
l=0;
r=n-1;
m=a[n/2];
do{while(a[l]<m)l++;
while(a[r]>m)r--;
if(l<=r)
{
Swap(a[l],a[r]);
l++;
r--;
}
}while(l<=r);
QuickSort(a,r+1);
QuickSort(a+l,n-l);
}
}
int main()
{ int a[100000],n=0,f,d,i;
do{f=scanf("%d",&a[n]);
if(f>0)n++;
}while(f>0);
QuickSort(a,n);
d=a[1]-a[0];f=1;
for(int i = 2; f&&i<n;i++)
if(a[i]-a[i-1]!=d)f=0;
if(f)
printf("Yes");
else printf("No");
}
Условия задач взяты с сайта acmp.ru