Poj 2769 Reduced ID Number
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 7882
Accepted: 3181
Description
T. Chur teaches various groups of students at university U. Every U-student has a unique Student Identification Number (SIN). A SIN s is an integer in the range 0 ≤ s ≤ MaxSIN with MaxSIN = 10
6-1. T. Chur finds this range of SINs too large for identification within her groups. For each group, she wants to find the smallest positive integer m, such that within the group all SINs reduced modulo m are unique.
Input
On the first line of the input is a single positive integer N, telling the number of test cases (groups) to follow. Each case starts with one line containing the integer G (1 ≤ G ≤ 300): the number of students in the group. The following G lines each contain one SIN. The SINs within a group are distinct, though not necessarily sorted.
Output
For each test case, output one line containing the smallest modulus m, such that all SINs reduced modulo m are distinct.
Sample Input
2
1
124866
3
124866
111111
987651
Sample Output
1
8
이 문제는 폭력적인 해법으로 충분히 쓸 수 있다. 나는 188ms를 썼다.마찬가지로 폭력적인 해법이니 최적화에 주의하지 않으면 TLE가 될 것이다.
①memset의 문제: 표기 수조가 10의 6차례나 열렸고 순환 내에 매번 표기 수조를 완전히 초기화하면 낭비하는 시간이 너무 많다.초기화 가능한 만큼
② 순환 변수 i의 초기 값은 n일 수 있다. 왜냐하면 n개의 서로 다른 수는 n보다 작은 어떤 수취모 연산에 대해 반드시 중복 값이 있기 때문이다.
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>// INT_MAX
#define MAX 1050
#define INF 0x7FFFFFFF
# define eps 1e-5
using namespace std;
bool visit[1000005];
int main()
{
int t,n,i,a[500],j,tmp;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
memset(visit,0,sizeof(bool)*n);//
bool ok;
for(i=n; ; i++)// n
{
ok = 1;
for(j=0; j<n; j++)
{
tmp = a[j] % i;
if(visit[tmp] == 0)
visit[tmp] = 1;
else
{
ok = 0;
memset(visit,0,sizeof(bool)*i);//
break;
}
}
if(ok == 1)
{
printf("%d
",i);
break;
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
깨끗한 것을 보고 싶기 때문에 최적화 함수의 벤치마크에 이용되는 함수의 가시화를 해 보았다결정되지 않음 (자기 만족) 「헤이 이런 거 있어」라고 생각하는 사람 최적화 함수란? 거친 이미지로 1) x + 10 = 25 2) x + 60 = 15 3) x + 45 = 60 의 x를 기계에 구할 때 정확하게 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.