[Question] Dart

September 27, 2021By Simo Game

Title description

Xiao Ming likes to play darts, and he will record each score in an array. Today there is a dart grand prize. The rules for winning the prize are: if you score 4 darts in sequence (a, b, c, d), satisfy a×b×c=d.

Xiao Ming is going to delete the other items in the record, leaving only 4 scores that meet the criteria for the award. He would like to ask how many different solutions do you have?

Input and output format

Input format

The first line, an integer N. (N <= 2000)

The second line, N integers, each integer ranges in [1…

“>10^6

Output format

One line, an integer, representing the number of solutions.

Input and output sample

< strong>Input example one

10 2 2 7 40 160

Output sample one

< div class="col-xs-12">

Input example two

< p>128 64 32 16 8 4 2 1

Output sample two

Problem solution

Violent enumeration a, b, c, ask whether d exists, you can do O( n³) time complexity, but obviously cannot meet the data range of this question.

We can start from another angle. From the question a*b=d/c, we can first enumerate a*b, record the position where b appears, then enumerate d/c, and find the number of cases that satisfy the position of b according to the position of c. This seems to be O(n³), but in fact, using binary search optimization can achieve O(n²logn), which happens to pass this question.

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 2; i + 2 <= n; ++i)

 {

 for(register int j = 1; j j)

 {

 if((long long)a[i] * a[j]> PTS) continue;

 c[a[i] * a[j]].push_back(i);

}

}

 for(register int i = 3; i i)

 {

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += BS(a[j] / a[i], i);

 // cout << i << "" << j < <"" << ans << endl;

}

}

 cout << ans;

 return 0;

}

Reference program O(n²logn) version

However, when the data range is enlarged again In some cases, the above approach will not work. We can look at the shortcomings of the above approach, which lies in the need to find the position of b. If we can enumerate a*b at the same time when enumerating d/c, we can achieve O(n²) time complexity, and this It can be achieved, just use the feature that the position of b is in front of the position of c. For details, please refer to the following program. (And this method is better to write..)

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 3; i i)

 {

 for(register int j = 1; j 1; ++ j)

 {

 if((long long)a[i-1] * a[j]> PTS) continue;

 ++c[a[i-1] * a[j ]];

}

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += c[a[j] / a[i]];

}

}

 cout << ans;

 return 0;

}

reference program O(n²) version

Input example one

10 2 2 7 40 160

Output sample one

Input example one

< p>10 2 2 7 40 160

Output sample one

Input example two

128 64 32 16 8 4 2 1

Output sample Example 2

Problem solution

Violent enumeration a, b, c, ask whether d exists, The time complexity of O(n³) can be achieved, but obviously it cannot meet the data range of this question.

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 2; i + 2 <= n; ++i)

 {

 for(register int j = 1; j j)

 {

 if((long long)a[i] * a[j]> PTS) continue;

 c[a[i] * a[j]].push_back(i);

}

}

 for(register int i = 3; i i)

 {

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += BS(a[j] / a[i], i);

 // cout << i << "" << j < <"" << ans << endl;

}

}

 cout << ans;

 return 0;

}

Reference program O(n²logn) version

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 3; i i)

 {

 for(register int j = 1; j 1; ++ j)

 {

 if((long long)a[i-1] * a[j]> PTS) continue;

 ++c[a[i-1] * a[j ]];

}

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += c[a[j] / a[i]];

}

}

 cout << ans;

 return 0;

}

reference program O(n²) version

Input example two

128 64 32 16 8 4 2 1

< /p>

Sample output 2

Problem solution

Violent enumeration of a, b, c and finding whether d exists can achieve O(n³) time complexity, but obviously it does not satisfy the data range of this question.

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 2; i + 2 <= n; ++i)

 {

 for(register int j = 1; j j)

 {

 if((long long)a[i] * a[j]> PTS) continue;

 c[a[i] * a[j]].push_back(i);

}

}

 for(register int i = 3; i i)

 {

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += BS(a[j] / a[i], i);

 // cout << i << "" << j < <"" << ans << endl;

}

}

 cout << ans;

 return 0;

}

Reference program O(n²logn) version

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 3; i i)

 {

 for(register int j = 1; j 1; ++ j)

 {

 if((long long)a[i-1] * a[j]> PTS) continue;

 ++c[a[i-1] * a[j ]];

}

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += c[a[j] / a[i]];

}

}

 cout << ans;

 return 0;

}

reference program O(n²) version

Share picture

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 2; i + 2 <= n; ++i)

 {

        for(register int j = 1; j < i; ++j)

 {

            if((long long)a[i] * a[j] > PTS) continue;

            c[a[i] * a[j]].push_back(i);

}

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += BS(a[j] / a[i], i);

            // cout << i << " " << j << " " << ans << endl;

        }

}

    cout << ans;

 return 0;

}

参考程序O(n²logn)版

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1];

long long ans;



inline int BS(int x, int p)

{

    int len = c[x].size();

    int lt = 0, rt = len - 1, mid;

    while(lt <= rt)

 {

        mid = lt + rt >> 1;

        if(c[x][mid] >= p) rt = mid - 1;

        else if(mid + 1 < len && c[x][mid + 1] < p) lt = mid + 1;

        else return mid + 1;

}

 return 0;

}



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 2; i + 2 <= n; ++i)

 {

        for(register int j = 1; j < i; ++j)

 {

            if((long long)a[i] * a[j] > PTS) continue;

            c[a[i] * a[j]].push_back(i);

}

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += BS(a[j] / a[i], i);

            // cout << i << " " << j << " " << ans << endl;

        }

}

    cout << ans;

 return 0;

}

分享图片

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = 1; j < i - 1; ++j)

 {

            if((long long)a[i - 1] * a[j] > PTS) continue;

            ++c[a[i - 1] * a[j]];

}

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += c[a[j] / a[i]];

}

}

    cout << ans;

 return 0;

}

参考程序O(n²)版

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = 1; j < i - 1; ++j)

 {

            if((long long)a[i - 1] * a[j] > PTS) continue;

            ++c[a[i - 1] * a[j]];

}

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += c[a[j] / a[i]];

}

}

    cout << ans;

 return 0;

}

Title description

Input and output format

Input format

Output format

Input and output sample

< strong>Input example one

Output sample one

Input example two

Output sample two

Problem solution

Input example one

Output sample one

Input example one

Output sample one

Input example two

Output sample Example 2

Problem solution

Input example two

Sample output 2

Problem solution

Leave a Comment Cancel reply