您将如何解决以下问题？ [英] How will you solve the following problem ?

问题描述

Alexey正在尝试为一个非常简单的微控制器开发一个程序。它随着时间的推移从各种传感器读数，这些读数必须在特定的常规时间发生。不幸的是，如果其中两个读数同时发生，微控制器会冻结并且必须重置。



有N种不同的传感器可以定期读取数据。对于从1到N的每个i，传感器i的读数将每隔几毫秒发生，第一次读数在微控制器上电后恰好在几毫秒内发生。每个读数在Alexey的微控制器上只需要一毫秒。



阿列克谢想知道微控制器打开后何时会冻结。



输入



输入的第一行包含一个整数T，表示测试用例的数量。下面是对T测试案例的描述。



第一行包含表示传感器数量的单个整数N.



第二行包含N个以空格分隔的整数A1，A2，...，AN，表示测量频率。也就是说，传感器i将每隔几毫秒读取，第一次读数在微控制器首次打开后的几毫秒内发生。



输出 <对于每个测试用例，输出一行包含微控制器冻结的毫秒数。



约束

1≤T≤10

2≤N≤500

1≤Ai≤10^ 9



示例

输入：

3

3

2 3 5

4

1 8 7 11

4

4 4 5 6



输出：

6

7

4



和时间限制是1秒。



我尝试过：



我想出了以下代码： -

Alexey is trying to develop a program for a very simple microcontroller. It makes readings from various sensors over time, and these readings must happen at specific regular times. Unfortunately, if two of these readings occur at the same time, the microcontroller freezes and must be reset.

There are N different sensors that read data on a regular basis. For each i from 1 to N, the reading from sensor i will occur every Ai milliseconds with the first reading occurring exactly Ai milliseconds after the microcontroller is powered up. Each reading takes precisely one millisecond on Alexey's microcontroller.

Alexey wants to know when the microcontroller will freeze after he turns it on.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line contains single integer N denoting the number of sensors.

The second line contains N space-separated integers A1, A2, ..., AN denoting frequency of measurements. Namely, sensor i will be read every Ai milliseconds with the first reading occurring Ai milliseconds after the microcontroller is first turned on.

Output

For each test case, output a single line containing the number of milliseconds until the microcontroller freezes.

Constraints
1 ≤ T ≤ 10
2 ≤ N ≤ 500
1 ≤ Ai ≤ 10^9

Example
Input:
3
3
2 3 5
4
1 8 7 11
4
4 4 5 6

Output:
6
7
4

And time limit is 1 second.

What I have tried:

I came up with the following code :-

#include<stdio.h>
 
int main(void)
{
    int t, n, i, flag;
    scanf("%d", &t);
 
    while(t--)
    {
        scanf("%d", &n);
        long a[n], time;
 
        scanf("%ld", &a[0]);
        time = a[0];
 
        for(i = 1; i < n; i++){
            scanf("%ld", &a[i]);
 
            if(a[i] < time)
                time = a[i];
        }
 
        flag = 0;
 
        while(flag != 2)
        {
            flag = 0;
 
            for(i = 0; i < n; i++)
            {
                if(time % a[i] == 0)
                    flag++;
 
                if(flag == 2)
                    break;
 
            }
 
 
            if(flag != 2)
                time++;
 
        }
 
        printf("%ld\n", time);
    }
 
    return 0;
}

但是超过1秒的时限。任何人都可以建议更快的方法来解决这个问题吗？

But the time limit of 1 second is exceeding. Can anyone suggest a faster method to solve this problem ?

推荐答案

使用

With

long a[n], time;

， a [n] 在编译时设置。如果 n 设置为500，它会正常工作，但事实并非如此。您的 n 是在运行时设置的，在这种情况下， a 必须是指向数组的指针，并且数组必须在运行时动态分配。

动态数组：使用malloc（）和realloc（） - C / C ++教程 - Codecall [ ^ ]

C内存分配使用malloc（），calloc（），free（）& realloc（） [ ^ ]

[ ^ ]



像你这样的Lopoks使用蛮力方法找到2个传感器。你需要聪明一点。

每隔300000毫秒（5米）发射一次传感器，每720000毫秒（12米）发射一次，你会检查每毫秒还是你有一个更聪明的方法来查找下一次碰撞是在1小时？

, the size of a[n] is set at compile time. It would work fine if n was set to 500, but it was not the case. Your n is set at runtime, and in this case, a must be a pointer to an array and the array must be allocated dynamically at runtime.
Dynamic Arrays: Using malloc() and realloc() - C/C++ Tutorials - Codecall[^]
C Memory Allocation Using malloc(), calloc(), free() & realloc()[^]
[^]

Lopoks like you use a brute force method to find 2 sensors colision. You need to get smart.
With a sensor firing every 300000 ms (5m) and another every 720000 ms (12m) will you check every milli-seconds or do you have a smarter way to find that the next collision is in 1 hour ?

如果你无法完全解决问题，请尝试解决其中的一部分问题。在您的情况下，这意味着：尝试解决两个计时器的问题（N == 2）。他们什么时候第一次同时开火？答案：在最小公倍数时也称为最小公倍数（LCD）。现在，如果你谷歌，你会发现有一个聪明的方法来计算这个。现在我们有一种方法来计算两个计时器的时间而不必测试每毫秒！一旦我们得到了，我们可以将它推广到N个计时器。所以我们必须检查每个计时器到彼此的计时器。在查看如何计算两个数字的LCD时，您会发现最耗时的部分可以从之前的计算中分享。因此，这可以实现一个很好的优化。



所以，这是你的行动计划：



1 ）谷歌术语最不常见的除数和研究



2）认识到两个定时器的问题与寻找最不常见的除数相同



3）现在通过为每对定时器计算LCD来解决您的问题



4）通过提取来优化您的解决方案最耗时的部分（分解）并且只进行一次。



这肯定会减少最多500对计时器的计算时间（约125,000 LCD计算）到一秒钟以下。



如果你对这四个步骤中的任何一个有问题，你可能会问这个问题。但没有人会（或应该）在银盘上为您提供解决方案。这是你的作业，应该帮助你学习一些东西，而不是我们。

If you can't solve a problem in its full complexity, try to solve a part of it. In your case that means: Try to solve the problem for two timers (N == 2). When will they fire the first time simultaneously? Answer: At the time of the smallest common multiple also called the least common multiple (LCD). Now, if you google that you will find that there is a smart method for calculating this. And now we have a method to calculate that time for our two timers without having to test each millisecond! Once we got that we can generalize that to N timers. So we have to check each timer to each other timer. And when looking at how the LCD of two numbers is calculated you will find that the most time consuming part of this can be shared from previous calculations. So that allows for a nice optimization.

So, here is you plan of action:

1) Google the term "least common divisor" and study that

2) Realize that the problem for two timers is the same as finding their least common divisor

3) Now solve your problem by calculating the LCD for every pair of timers

4) Optimize your solution by extracting the most time-consuming part (the factorization) and do it just once.

That will certainly reduce your calculation time for up to 500 pairs of timers (about 125.000 LCD calculations) to under a second.

If you have problems with any of those four steps you may ask a question about just that. But nobody will (or should) deliver the solution to you on a silver platter. It is your homework and should help you to learn something, not us.

这篇关于您将如何解决以下问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！