/* Задача А1. ИГРА Лист хартия е разграфен на мрежа от еднакви квадратчета. Всяко квадратче се определя с номерата на реда и стълба, в които се намира. Номерирането на редовете и стълбовете започва от 1. Върху едно от квадрачета е поставена пионка. Двама играчи играят с последователно редуващи се ходове игра, при която на всеки ход съответният играч премества пионката. При поредния ход тя трябва да бъде преместена така, че да остане или в същия ред, като номерът на стълба й се намали с число, което е точен квадрат, или да остане в същия стълб, като номерът на реда й се намали с число, което е точен квадрат. Това означава, че ако пионката се намира в ред i и стълб j, т.е. в позиция (i, j), то тя може да бъде преместена в някоя от позициите (i, j – 1), (i, j – 4), (i, j – 9) и т.н., или в някоя от позициите (i – 1, j), (i – 4, j), (i – 9, j) и т.н., като винаги трябва да остане в рамките на игралното поле. Играта печели този играч, който след като изиграе своя ход, постави пионката в позиция (1, 1). Една позиция (i, j) се нарича печеливша, ако при поставена върху нея пионка, играчът, който започва играта, може да организира действията си така, че да спечели, независимо от начина на игра на противника му. Напишете програма GAME.EXE, която въвежда четири цели числа i1, j1, i2, j2, всяко с възможна стойност измежду числата 0, 1, 2, ..., 500 и i1 < j1, i2 < j2, която пресмята броя на печелившите позиции (i, j), за които е изпълнено, че i1 < i < i2 и j1 < j < j2. Входните данни се въвеждат от един ред на стандартния вход като четири цели числа i1, j1, i2, j2, разделени с по един интервал. Резултатът трябва да бъде изведен на стандартния изход като едно цяло число. ПРИМЕР Вход: 0 0 2 2 Изход: 0 Решение на задача A1 – Игра От Иван Анев Дадената игра попада в класа игри, при които броят на различните ситуации е достатъчно малък, за да съберем в паметта информация за всяка ситуация. За нашата игра ситуация или позиция е двойка числа (x, y), който дефинират клетка от игралната дъска. Всяка позиция има две стойности печеливша и губеща. Като всяка стойност показва дали играчът, който е на ход, попаднал в дадената позиция може да спечели играта независимо от играта на противника и дали ще загуби ако противника играе оптимално. Друга важна характеристика на играта е, че тя е нециклична и крайна. Тоест ако от една позиция може да се стигне до друга, то не може от втората да се стигне до първата. Освен това играта ще свърши след краен брой ходове, независимо как играят играчите. Това лесно ни помага да видим, че дали една позиция е печеливша или губеща зависи от това какви са позициите, до който може да достигнем от нея. А именно, ако от една позиция може с един ход да се достигне до губеща позиция, то текущата позиция е печеливша. Ако няма губеща позиция, до която може да се достигне с един ход (всички достижими позиции са печеливши), то позицията е губеща. Забелязваме също, че една позиция зависи само от позиции с по-малки числа x и y. Следователно, за да изчислим стойността на една позиция е достатъчно да сме изчислили позициите с по-малки индекси x и y. Това показва, че един добър подход за изчисляване на позициите е в ред на нарастване на индексите. Остава да определим базова позиция, от която да произлизат всички останали. Това очевидно е позицията (1,1) и освен това тя е губеща, защото играч попаднал в нея вече е загубил играта. Реализацията на описаното решение е сравнително лесно и пряка реализация на идеята. Първо изчисляваме стойността на всички позиции за x и y в интервала [1;i2)x[1;j2). Това става с 3 вложени цикъла. Един по x, един по y и трети, който ще обхожда квадратите на числата 1, 2, 3 и т.н. След това ще обходим таблицата в интервалите (i1;i2)x(j1;j2) и ще преброим печелившите позиции. */ /* NAME: Ivan Anev PROG: game LANG: C */ #include <stdio.h> #undef max #define MAXN 512 #define MAXS 32 int i1, j1, i2, j2; int sq[MAXS], a[MAXN][MAXN]; int ans; void readf(void); void solve(void); void writef(void); int main(void) { readf(); solve(); writef(); return 0; } void readf(void) { scanf("%d%d%d%d", &i1, &j1, &i2, &j2); } void solve(void) { int i, j, k; int max(int a, int b); for (i = 0; i < MAXS; ++i) sq[i] = (i + 1) * (i + 1); for (i = 1; i < i2; ++i) for (j = 1; j < j2; ++j) { for (k = 0; i - sq[k] >= 1 && a[i-sq[k]][j]; ++k) ; if (i - sq[k] >= 1) a[i][j] = 1; else { for (k = 0; j - sq[k] >= 1 && a[i][j-sq[k]]; ++k) ; if (j - sq[k] >= 1) a[i][j] = 1; } } for (i = i1 + 1; i < i2; ++i) for (j = j1 + 1; j < j2; ++j) ans += a[i][j]; } void writef(void) { printf("%d\n", ans); } int max(int a, int b) { return ((a > b) ? a : b); }