fork(1) download
copy 
  1. //Aakash Jain - SPOOKY
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. bool subset[500][100001]; //dynamic programming store
  6. int divisors[500];
  7.  
  8. bool isSpooky(int n) {
  9. 	int i, j, limit = sqrt(n),
  10. 		numDivs = 0, //number of divisors
  11. 		sumDivs = 1; //sum of divisors
  12. 	divisors[numDivs++] = 1; //add 1 to divisors
  13. 	for(i = 2; i <= limit; i++)
  14. 		if(n%i == 0) {
  15. 			//add i and n/i to divisors
  16. 			j = n/i;
  17. 			divisors[numDivs++] = i;
  18. 			divisors[numDivs++] = j;
  19. 			sumDivs += i+j;
  20. 		}
  21. 	if(i*i == n) {
  22. 		//if n is a perfect square, its square root would be added twice
  23. 		//so remove the duplicate occurrence
  24. 		numDivs--;
  25. 		sumDivs -= i;
  26. 	}
  27. 	if(sumDivs <= n)
  28. 		return false; //check first condition
  29.  
  30. 	//subset sum problem
  31. 	for(i = 0; i <= numDivs; i++)
  32. 		subset[i][0] = true;
  33. 	for(i = 1; i <= n; i++)
  34. 		subset[0][i] = false;
  35. 	for(i = 1; i <= numDivs; i++)
  36. 		for(j = 1; j <= n; j++)
  37. 			if(j >= divisors[i-1])
  38. 				subset[i][j] = subset[i-1][j] || subset[i-1][j - divisors[i-1]];
  39. 			else
  40. 				subset[i][j] = subset[i-1][j];
  41.  
  42. 	return !subset[numDivs][n];//check second condition
  43. }
  44.  
  45. int main() {
  46. 	int t, n;
  47. 	cin >> t;
  48. 	while(t--) {
  49. 		cin >> n;
  50. 		if(isSpooky(n))
  51. 			cout << "SPOOKY\n";
  52. 		else
  53. 			cout << "OK\n";
  54. 	}
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 51976KB
comments ()
stdin
copy 
2
20
70
stdout
copy 
OK
SPOOKY
https://ideone.com/BSqZdI
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!