[phyrrus9]

Rules:
Your program may be written in any language of your choice
Your program may not take longer than 25 seconds to compute the answer

Problem:
You have a string of N light bulbs, all of which are turned off. Every second (S), light bulbs that are multiples of S toggle their state (off->on, on->off). After T seconds, what is the state of the light bulb in question (Q)?

Inputs:
N, T, Q

Outputs:
state(Q)

+1 rep and 50NSP if your program computes the correct result in under 5 seconds.

NOTE: a random number generator won't work, I will test each program a random number of times.

Limits:
10<N<4,294,967,296
100<T<1,000,000
Q is a 1-bit integer

EDIT: PLEASE include an example of how to compile and run if your language is not C/C++/Java. Sorry @Eclipse, lets see how it handles

[phyrrus9]

Setting a time limit without a specific input is not really logical, since a larger input would make the program's execution time longer. Also, different CPUs will execute shit at different rates. On top of this, different languages are slower/faster than others.

Here's my solution:

Code:

#imports import time #inputs not included in elapsed calculation N = int(raw_input('N > ')) T = int(raw_input('T > ')) #start time recorded start = time.time() #main code bulbs = {} for x in xrange(1, N+1): bulbs[x] = '0' #0 = off, 1 = on for S in xrange(1, T+1): for key in bulbs: if key % S == 0: if bulbs[key] == '0': bulbs[key] = '1' else: bulbs[key] = '0' #elapsed time calculated by current time - start time elapsed = time.time() - start #output def output(): opt = str(raw_input('Would you like to see the state of all bulbs or a specific one? (ALL/ONE) > ')).upper() if opt == 'ALL': for key in bulbs: print 'Bulb ' + str(key) + ' is ' + str(bulbs[key]) elif opt == 'ONE': bn = int(input('Which Bulb? (int) > ')) print 'Bulb ' + str(bn) + ' is ' + str(bulbs[bn]) output() #print elapsed time FOR CALCULATION print 'Time taken: ' + str(elapsed) + ' seconds'

Note: Mine is pretty shite. It can't work with your upper limits because range fucks up, and upon trying different implementations, python runs out of memory. I suppose a low level language like C would've been better but meh.

Example run:

Code:

N > 100000 T > 1000 Would you like to see the state of all bulbs or a specific one? (ALL/ONE) > one Which Bulb? (int) > 1000 Bulb 1000 is 0 Time taken: 15.2100000381 seconds

Actually, the upper limit is imposed for users to make the same mistake you did at simulating it, but not calculating it. Ran into the same problem when I first did this problem.

[Eclipse]

Actually, the upper limit is imposed for users to make the same mistake you did at simulating it, but not calculating it. Ran into the same problem when I first did this problem.

Wait, what? Not quite sure what you're getting at.

EDIT: By the way, what about my comments on the time limit?

[phyrrus9]

Wait, what? Not quite sure what you're getting at.

EDIT: By the way, what about my comments on the time limit?

The speed isn't really effected by the chosen language, it is but its not an entirely important factor.

my code:

Spoiler:

Code:

#include <stdio.h> int main(int argc, char ** argv) { unsigned int T, N, Q, i; sscanf(argv[1], "%u:%u:%u", &T, &N, &Q); unsigned int max = T; register unsigned char state = 0; for (i = 1; i <= max; i++) if (i % Q == 0) state = state ? 0 : 1; printf("T=%d\tQ=%d\tState=%s\n", T, Q, state ? "On" : "Off"); }

to compile:

Code:

gcc -o lights lights.c

run:

Code:

./lights T:N:Q

Here is my results:

Code:

(precise)phyrrus9@localhost:~$ time ./a.out 543210:4294967295:31 T=543210 Q=31 State=Off real 0m0.009s user 0m0.007s sys 0m0.001s

[Eclipse]

Windows:

1. https://www.python.org/downloads/
2. Download 2.7.x
3. Install
4. Open (IDLE)
5. Paste Code
6. Run (F5)

Linux:

1. You should have it installed already, if not, google it.
2:

Code:

python path/to/file.py

[phyrrus9]

Windows:

1. https://www.python.org/downloads/
2. Download 2.7.x
3. Install
4. Open (IDLE)
5. Paste Code
6. Run (F5)

Linux:

1. You should have it installed already, if not, google it.
2:

Code:

python path/to/file.py

ran for 31 seconds until I had to force kill it from memory overconsumption.

[Eclipse]

Here is my results:

Code:

(precise)phyrrus9@localhost:~$ time ./a.out 543210:4294967295:31 T=543210 Q=31 State=Off real 0m0.009s user 0m0.007s sys 0m0.001s

Holy fucking shit.

---

ran for 31 seconds until I had to force kill it from memory overconsumption.

I'm just going to delete it and start again from scratch. Bye.