Poj 2769 Reduced ID Number

Reduced ID Numbers
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; }

좋은 웹페이지 즐겨찾기