Написання програми, яка грає в гру "Нім" і, по можливості, виграє (Завдання другого туру X Всеукраїнської олiмпiади з iнформатики)

X Всеукраїнська олiмпiада з iнформатики

2 тур

Нім

В гру Нім грають двоє. Є N (2 £ N £ 100) купок камінців. Гравці по черзі беруть камінці з купок. Виграє той, хто візьме останній камінець. На кожному ході гравець може брати камінці не більше ніж з K (1 £ K £ N) купок, але повинен взяти хоча б один камінець. На початку гри в кожній купці 0 < H[i] < 1000000000 камінців.

Завдання. Напишіть програму, яка буде грати в Нім та, по можливості, вигравати.

Технічні умови. Під час перевірки до Вашої програми буде приєднано (linked) модуль перевірки, який називається CHECK.* (PAS, C чи CPP). Цей модуль містить 3 функції: InitGame, JudgeTurn, PartTurn.

Функція InitGame використовується для зчитування вхідних даних з тестового файлу. Вона має 4 вихідних параметри: N та K - кількості купок, масив H - кількості камінців в купках, First - хто перший ходить. Після виклику цієї функції N та K отримають відповідні значення, в перших N елементах масиву H будуть кількості камінців в купках, а First приймає значення 0, якщо першою ходить програма перевірки (журі), та 1, якщо першою ходить програма учасника. Зверніть увагу, що Ваша програма не повинна самостійно читати вхідні дані, це треба робити тільки за допомогою функції InitGame.

Функцію JudgeTurn Ваша програма буде викликати коли їй потрібно буде отримати черговий хід журі. Єдиний вихідний параметр цієї функції - масив T, перші N елементів якого містять кількості камінців, що перевіряюча програма бере з купок. Відповідність ходу умовам гри гарантується.

Функцію PartTurn Ваша програма буде викликати щоб повідомити перевіряючій програмі свій хід. Запишіть свій хід в перші N  елементів масиву T. 

Кожна з цих функцій повертає 1, якщо все гаразд, або 0, якщо виникла помилка, і Ваша програма може припиняти роботу.

На отриманій Вами дискеті буде модуль перевірки (CHECK.*) та головний модуль (NIM_KBD.*). Вони надаються тільки для того, щоб Ви могли швидко почати роботу над розв’язком, не втрачаючи час на технічні проблеми. Модуль CHECK виконує зчитування даних з клавіатури, перевірку ходів учасника та послідовності викликів функції, але дуже погано грає. Журі при перевірці буде використовувати інший. Модуль NIM_KBD викликає функції модуля CHECK в потрібній послідовності, але замість обчислення наступного ходу учасника читає його з клавіатури. Ваша задача і полягає в тому, щоб функція MakeTurn обчислювала наступний хід. Журі не наполягає на використанні означених файлів, але Ваш розв’язок повинен коректно взаємодіяти з модулем CHECK.

Примітка.При перевірці серед тестів будуть такі часткові випадки:

1) N = 2, K = 1; 2) N = 3, K = 1; 3) N > 3, K = 1.

Програма-розв’язок - NIM.PAS, NIM.CPP чи NIM.C.

Приклад

N = 4, K = 2, First = 1, H = (3,4,5,6).

Учасник:         (1,1,0,0), залишилось (2,3,5,6)

Журі:               (0,0,1,1), залишилось (2,3,4,5)

Учасник:         (0,0,1,1), залишилось (2,3,3,4)

Журі:               (1,1,0,0), залишилось (1,2,3,4)

Учасник:         (0,0,0,4), залишилось (1,2,3,0)

Журі:               (0,0,1,0), залишилось (1,2,2,0)

Учасник:         (1,2,0,0), залишилось (0,0,2,0)

Журі:               (0,0,2,0), залишилось (0,0,0,0)

Виграло журі (але учасник мав шанс !!!)