INTEST - Enormous Input Test

no tags 

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

hide comments
Rafael Perrella: 2014-02-09 08:57:49

How to get 0.5s in C/C++? I can't make it go lower than 0.7s...

Shashank Gupta: 2013-11-10 17:41:50

@numerix OK I'll look, thanks. :)

numerix: 2013-11-10 17:33:11

@Shashank Gupta: You will find some hints according this question on the SPOJ forum (Python subforum). If you do not find what you are looking for, you may ask there.

Shashank Gupta: 2013-11-10 17:21:25

@numerix Can you give me a hint in figuring out how? Maybe cStringIO? I'm not able to use Python for a lot of problems because I'm just stuck on the input :\ I have to use C/C++.

numerix: 2013-11-10 14:29:29

@Shashank Gupta: You can get AC with Python without psyco. But it's not easily done.

Shashank Gupta: 2013-11-10 08:04:31

To do this in Python, you need psyco, but psyco is no longer available in SPOJ. In a C/C++ like language use a large character buffer and parse the input yourself rather than using formatted strings/iostreams. Of course, it's easy to go under the time limit using just scanf/printf or sync_with_stdio = False, but you won't get "super" speed. ;)

Last edit: 2013-11-10 08:06:37
Mohammed Hafez: 2013-08-03 22:03:25

OK, I get 0.81 sec
1. How to make my solution faster?
2. @richi18007 How can saving the input in an array (storing large numbers) and then processing it make it faster? "I calculate on the fly" !!!
Thanks :)

Last edit: 2013-09-03 17:05:51
Mitch Schwartz: 2013-07-10 19:29:45

@Adamax: A problem may have multiple data sets (where a data set is an input file paired with an output file), and the total time is the sum of the times for each data set.

Last edit: 2013-07-10 19:34:25
Adamax: 2013-07-10 18:23:06

What is the actual time limit for this problem? It says 8s, but solutions taking over 10 seconds are accepted.

Shubham: 2012-06-11 20:57:35

@Daniel Yes,I got the same results as well :)


Added by:adrian
Date:2004-11-09
Time limit:2.112s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Idea put forward by Michael Mendelsohn