1. Enormous Input Test

I haven't been in these forums for a while... I've been learning much about Linux and about Perl and PHP :-)

I do know a lot of C, but not much C++, and I found a cool website that has an online judge and I've been working on some problems there.

Enormous Input Test

Code:
```The purpose of this problem is to verify whether the method you are using to read input
data is sufficiently fast to handle problems branded with the enormous Input/Output
warning. You are expected to be able to process at least 2.5MB of input data per
second at runtime.

Input:
The input begins with two positive integers n k (n, k<=107). The next n lines of input
contain one positive integer ti, not greater than 109, each.

Output:
Write a single integer to output, denoting how many integers ti are divisible by k.

Example:
Input:
7 3
1
51
966369
7
9
999996
11

Output:
4```
My program failed twice because of exceeded time limit. Here is my code:
Code:
```#include <iostream>

using namespace std;

int main() {
long n, k, count = 0;

cin >> n >> k;
long *ti = new long[n];

for(int i = 0; i < n; i++) {
cin >> ti[i];
}

for(int i = 0; i < n; i++) {
if(ti[i] % k == 0)
count++;
}

cout << count;
}```
What would be a better way to read all the input faster? I also tried reading from cin and testing for division on the same loop, but that was not fast enough either.

Thanks!

2. It does not look like dynamic memory allocation is actually needed.

3. Originally Posted by laserlight
It does not look like dynamic memory allocation is actually needed.
My other variation, which does not use dynamic memory allocation and also failed because of expired time limit.
Code:
```#include <iostream>

using namespace std;

int main() {
long n, k, count = 0;

cin >> n >> k;

for(int i = 0; i < n; i++) {
long ti;
cin >> ti;

if(ti % k == 0)
count++;
}

cout << count;
}```
Oh and on the original post, the max numbers are supposed to be 10^7 and 10^9, not 107 or 109.

4. Originally Posted by samus250
My other variation, which does not use dynamic memory allocation and also failed because of expired time limit.
In that case, consider switching to C-style input to see if it makes any difference.

5. Originally Posted by laserlight
In that case, consider switching to C-style input to see if it makes any difference.
by using scanf("%ld", &x)? ... let's try that.

6. Originally Posted by laserlight
In that case, consider switching to C-style input to see if it makes any difference.
Holy crap it worked!

Though there are people who do it even faster. Mine took 5.36 seconds (8 seconds is the time limit) and some people do it in about 3 seconds (others in less than 1...)

Let's combine dynamic memory allocation with that and see what happens.

7. Almost no difference with dynamic allocation, just .05 seconds faster.
Without dynamic allocation, the program takes 2.5M, with it the program takes 9.9M so storing all the input to memory first is not the way to go.

Thanks a lot laserlight! Any other ideas on how I can make it run faster?

8. Originally Posted by samus250
Almost no difference with dynamic allocation, just .05 seconds faster.
Without dynamic allocation, the program takes 2.5M, with it the program takes 9.9M so storing all the input to memory first is not the way to go.
That is interesting. You mean that using dynamic memory allocation is an improvement? I do not see a space-time trade-off benefit here, so that is puzzling.

9. Originally Posted by laserlight
That is interesting. You mean that using dynamic memory allocation is an improvement? I do not see a space-time trade-off benefit here, so that is puzzling.
Well, the judge told me it took .05 seconds less...

10. Originally Posted by samus250
Well, the judge told me it took .05 seconds less...
Well, that is an example of why we should measure when we want to determine performance
Nonetheless, why not show the source code of both the programs involved?

11. Originally Posted by samus250
Well, the judge told me it took .05 seconds less...
It's just random jitter.

12. Originally Posted by laserlight
Well, that is an example of why we should measure when we want to determine performance
Nonetheless, why not show the source code of both the programs involved?
I will, thing is that I modified it, so I'll make it again.

Also... any idea why is this code giving me a runtime error? (it's C)
Code:
```#include <stdio.h>

int main() {
long n, k, i, ti, count = 0;

scanf("%ld", &n);
scanf("%ld", &k);

for(i = 0; i < n; i++) {
scanf("%ld", &ti);

if(ti % k == 0)
count++;
}

printf("%ld", count);
}```

13. Originally Posted by brewbuck
It's just random jitter.
That's what I was thinking too.

14. My naive first simple implementation did it in 5.39 seconds.

Will try to tweak it further.

Code:
```#include <cstdio>

int main() {
unsigned int n, k, t;
unsigned int count = 0;

scanf("%u %u", &n, &k);

for (unsigned int i = 0; i < n; ++i) {
scanf("%d", &t);
if (!(t % k)) {
++count;
}
}
printf("%d", count);
}```

15. My naive first simple implementation did it in 5.39 seconds.
Naive? Straightforward is more like it , and it is similiar to what samus250 did, hence the similiar timing. Incidentally, scanf and printf belong to the std namespace. Actually, with this particular implementation the initial value n does not seem useful to me (maybe that is a hint), so it seems simpler to write:
Code:
```#include <cstdio>

int main() {
using namespace std;

unsigned int n, k;
scanf("%u %u", &n, &k);

unsigned int count = 0;
while (scanf("%u", &n) == 1) {
if (n % k == 0) {
++count;
}
}
printf("%u", count);
}```