N개의 주머니에 공이 A1,A2,...,AN개 있을때 다음과 같은 연산중 1개를 할 수 있음
1) 비어있지 않은 주머니 1개를 골라서 주머니에서 원하는 만큼 공을 뺌. 이때 공을 빼내서 주머니가 비게되면 보상으로 토큰 1개를 얻음
2) 가지고 있는 토큰 1개를 제거함
Alice와 Bob이 위 연산을 반복함. 행동 못하는 쪽이 짐. N과 A1~AN이 주어져있을때 Alice가 이기는지 Bob이 이기는지 구하시오
예) N=1, A1= 3 => Alice 승 (처음에 3개를 다가져가면 되니까)
예) N=2, A1=1, A2=1 => Bob 승(Bob이 Alice가 하는걸 그대로 따라하면 Alice는 할게 없음)
진짜 좋은 문제여서 가지고와봄
+) 링크
게이야 링크는 어디 팔아먹고 왔노????????????
일본어 읽을줄 앎?
해당 댓글은 삭제되었습니다.
토큰은 개인소유
처음 시작한 사람이 공 다 빼는거 반복해서 토큰을 최대한 얻으면 이기거나 비기지 않음? 문제를 잘못 이해하고있나 - dc App
비기는 경우는 없음.
그럼 n이 홀수면 이기고 짝수면 지는거 아녀? - dc App
N=2, A1=1, A2=2인경우 Alice가 A2에서 1개 가져가고 그뒤로 Bob이 하는걸 그대로 따라하면 Bob은 아무것도 못하므로, Alice가 이김
각 사람 선택지가 공의 개수를 다 가져가거나 1개남기거나 2개남기는거 같은데 dp안되려나 난 못풀겠다 - dc App
Alice가 이미 A2에서 공1개를 가져갔는데 밥이 A2에서 어떻게 공 2개를 꺼냄. 원본 문제가 일본어라 그냥 링크 안가져왔는데 링크 가져올테니 정 헷갈리면 번역기 돌려서 확인해봐
그런디정리 안쓰고 풀리는문제임? - dc App