usaco-camp

Short, concise solutions for problems from the USACO camp

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	char s[10] = "MMOOMO";
	int K;
	cin >> K;
	if (K == 5) {
		cout << "impossible";
		return 0;
	}
	if (K == 1) { cout << "O"; return 0; }
	if (K == 2) { cout << "MO"; return 0; }
	if (K == 3) { cout << "MM";	return 0; }
	if (K == 7) { cout << "MMMO"; return 0; }
	if (K == 9) { cout << "MOMOM"; return 0; }
	if (K % 2 == 0 && K / 2 <= 1e5) {
		for (int i = 0; i <= K / 2; ++i) cout << s[i % 6];
		return 0;
	}
	ll sq = sqrt(8ll * K + 1) + 0.5;
	if (sq * sq == 8ll * K + 1) {
		int t = (sq - 1) / 2;
		for (int i = 0; i < t; ++i) cout << "O";
		return 0;
	}
	/*if (K > 1e8 && K % 2 == 1) {
		cout << "M";
		--K;
	}*/
	int t = sqrt(2 * K);
	while ((((K - t * (t + 1) / 2) - 2) % 2) || K - t * (t + 1) / 2 - 2 < 6) --t;
	for (int i = 0; i < t; ++i) cout << "O";
	int ans = t;
	//cout << t << '\n';
	K += - t * (t + 1) / 2 - 2;
	for (int i = 0; i <= K / 2; ++i) cout << s[i % 6];
	ans += K / 2;
	assert(ans <= 1e5);
	//cout << ans << '\n';
}