| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 7685 |
| 문제명 | Nim |
| 레벨 | 플래티넘 4 |
| 분류 |
스프라그-그런디 정리 |
| 시간복잡도 | O(T*n) |
| 인풋사이즈 | T<=?, n<=1000 |
| 사용한 언어 | Python |
| 제출기록 | 30840KB / 88ms |
| 최고기록 | 88ms |
| 해결날짜 | 2022/07/13 |
"""Solution code for "BOJ 7685. Nim".
- Problem link: https://www.acmicpc.net/problem/7685
- Solution link: http://www.teferi.net/ps/problems/boj/7685
Tags: [Sprague-Grundy]
"""
import sys
def main():
while (n := int(sys.stdin.readline())) != 0:
k = [int(x) for x in sys.stdin.readline().split()]
grundy = 0
for k_i in k:
grundy ^= k_i
answer = sum(1 for k_i in k if grundy ^ k_i < k_i)
print(answer)
if __name__ == '__main__':
main()