/* Задача 1.2 ИГРА Двама играчи A и B играят с редуващи се ходове игра, при която целите числа от 1 до N включително са написани в една редица и играчите ги задраскват съгласно следните правила: Когато A е на ход (независимо дали е първи или втори), той трябва да избере едно четно число, което дотогава не е било задраскано, да го задраска и да задраска още всички делители на избраното число (вкл. и числото 1), които не са задраскани. Когато B е на ход, той трябва да задраска избрано от него нечетно число, което дотогава не е било задраскано и аналогично да задраска още всички делители на това избрано число, които не са задраскани. Играта губи този играч, който не може да направи ход, когато е негов ред, а другият играч печели. Напишете програма GAME.EXE, която играе за играча A срещу програма на журито, играеща за играча B. Програмата трябва да може да играе, както когато играчът A започва пръв, така и когато започва втори. Данните за едно текущо състояние на играта програмата ще получи на файл чрез стандартния си вход. Входният файл съдържа цялото положително число N < 100 и след един интервал във файла са записани слято един до друг знаци A, B или O (главни латински букви, общо N броя), всеки в съответствие с поредното цяло число в редицата 1, 2, 3, ..., N. Буквата A означава, че числото на мястото, на което е тя – е задраскано от играча A при някой негов предишен ход, буквата B означава, че съответното число е било задраскано от играча B, а буквата O означава, че числото все още не е задраскано. Числото N не се променя по време на една игра. Вашата програма трябва да изведе на стандарния си изход едно цяло число, показващо избраното от играча A за текущия му ход. Пример 1. При N = 9, ако играчът A започва пръв, Вашата програма ще получи при първото извикване входни данни: 9 OOOOOOOOO. Пример 2. Ако играчът A е започнал втори, тогава възможни входни данни, които може да получи Вашата програма след третия ход на B са 9 BABAOOBAB, като това може да стане, ако Вашата програма е играла така, че на първия си ход е избрала числото 2, а на втория си ход – числото 8. По време на една игра програмата Ви ще бъде извиквана многократно, като всеки път ще получава данни, отразяващи текущото състояние след поредния ход на играча B. Програмата на журито играе винаги коректно и детерминирано. Вашата програма винаги ще получава коректни входни данни, отразяващи точно протичането на играта. Не е разрешено програмата Ви да чете или записва други файлове, освен стандартния вход и изход. При победа получавате 10 т., а при загуба или при некоректен ход – 0 т. Всяка игра ще бъде разигравана с програмата повече от веднъж. При различни резултати в отделните разигравания получавате 0 т. РЕШЕНИЕ от Иван Анев Когато играе играч A, той задрасква едно четно число и после задрасква всичките му делители, които могат да бъдат четни и нечетни числа. Когато играе играч B, той задрасква нечетно число и неговите делители, които са само нечетни числа. Тоест докато играч A може да намалява броят на свободните позиции за игра на играч B, обратното не е изпълнено. Това ни дава една лесна стратегия, за игра на играч A. Разглеждаме всички възможни позиции за игра (всички не задраскани четни числа) и преброяваме броят на четните и нечетните не задраскани делители на всяка позиция и избираме това, при което разликата между нечетните и четните не задраскани делители е най-голяма – в полза на нечетните. Ще прилагаме тази стратегия до края на играта. */ /* NAME: Ivan Anev PROG: game LANG: C */ #include <stdio.h> #define MAXN 128 int n, ans; char s[MAXN]; int a[MAXN]; void readf(void); void solve(void); void writef(void); int main(void) { readf(); solve(); writef(); return 0; } void readf(void) { scanf("%d%s", &n, s); } void solve(void) { int i, j, best, wb, cc; for (i = 1; i <= n; ++i) a[i] = ((s[i-1] == 'O') ? 0 : 1); best = -1; for (i = 2; i <= n; i += 2) { if (a[i] == 0) { cc = 0; for (j = 1; j < i; ++j) if (i % j == 0 && a[j] == 0) if (j % 2) ++cc; else --cc; if (cc > best) { wb = i; best = cc; } } } ans = wb; } void writef(void) { printf("%d\n", ans); }