Azret's blog

By Azret, history, 4 years ago, In English,

Hello CF!

I think many of you, in particular IOI participants, can not find a good, clear solutions of IOI problems, so I decided to create a blog where we will publish a problem then find solution for it and start to solve next problem (like on AOPS).

Let me begin — IOI 2006 B. Pyramid.

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

By Azret, history, 4 years ago, translation, In English,
Add Participant View Participants
Name CF Handle Country Previous IOIs
Román Castellarin ponysalvaje Argentina 2013 2014
Ariel Nowik ariel.nowik Argentina No Participation
Martin Mirakyan Martin97 Armenia No Participation
Mushegh Shahinyan Mushegh Armenia 2014 S
Albert Gevorgyan albertg Armenia No Participation
Eduard Grigoryan edogrigqv2 Armenia 2010, 2011, 2013, 2014 S
Florian Leimgruber fleimgruber Austria 2014 B
Gary Ye gdisastery Austria 2013 B, 2014 B
Peter Ralbovsky peto159 Austria 2013, 2014
Simon Lehner-Dittenberger Austria No Participation
Nur Muhammad Shafiullah LamePrince Bangladesh 2012
Hasib Al Muhaimin hasib Bangladesh 2013 2014
Labib Rashid Labib666 Bangladesh 2013 2014
Imran Hasan Sherlock221b Bangladesh No Participation
Nikita Sazanovich Nik_storm_2010 Belarus No Participation
Alex Vistyazh netman Belarus 2014 S
Barbara Kuskova kuskova Belarus 2014 B
Ilya Medyanikov ferathorn Belarus No Participation
Mattéo Couplet phixyma Belgium No Participation
Damien Galant damien_g Belgium 2014
Robin Jadoul Belgium No Participation
Nico Ekkart nicoekkart Belgium No Participation
Marcelo Zeballos marcelozeballos Bolivia No Participation
Ronaldo Franco Jaldin rony Bolivia 2014
Arthur Pratti Dadalto arthurpd Brazil 2014 S
Mateus Bezrutchka m_bezrutchka Brazil 2014 S
Lucca Morais de Arruda Siaudzionis luccasiau Brazil No Participation
Murilo Corato Zanarella murilocz Brazil No Participation
Hristo Venev mustrumr Bulgaria 2012 S ,2013 G, 2014 G
Encho Mishinev Enchom Bulgaria 2013 S 2014 G
Daniel Atanasov Bulgaria No Participation
Kristian Tsaklev krisits Bulgaria No Participation
Farbod Yadegarian FarbodY Canada No Participation
Yikuan (Timothy) Li FatalEagle Canada 2014 B
Ben Zhang Kuroba Canada 2014
Jacob Jackson zxqfl Canada 2014 G
Yanyi Liu lyy China No Participation
Xiaochen Lu Ruchiose China No Participation
Yuhao Du toosimple China No Participation
Hengjie Zhang zhj China No Participation
Juan Sebastian Chaves AdamantWharf Colombia 2014
Domagoj Bradac Dbradac Croatia No Participation
Tonko Sabolcec tonkosi Croatia No Participation
Mihael Liskij Mihaell Croatia No Participation
Ivan Lazaric IvL Croatia 2013 B
Alexander Bestard Rivera bestard Cuba No Participation
Michael Gonzáles mjgonzales Dominican Republic No Participation
Manuel David Sánchez Suero tecnomaster999 Dominican Republic No Participation
Alejandra Martínez Jiménez alejandra_244 Dominican Republic No Participation
Sami Kalliomäki Scintillo Finland 2012, 2013 B, 2014 S
Tuukka Korhonen Laakeri Finland No Participation
Henrik Lievonen Hennkka Finland 2013, 2014 B
Kalle Luopajärvi zscefn Finland 2013 B, 2014 S
Alexander Tskhovrebov alexandre Georgia No Participation
Georgy Skhirtladze gskhirtladze Georgia 2014 B
Elene Machaidze emachaidze Georgia 2014 B
Giorgi Kldiashvili giorgikldiashvili Georgia No Participation
Aristofanis Rontogiannis mentalist Greece 2014 B
Panagiotis Kostopanagiotis infinity Greece 2013
Konstantinos Agiannis Greece No Participation
Emanuel Mihalainas Greece No Participation
Tanay Kothari Tanay1998 India No Participation
Malvika Raj Joshi a06 India 2014 S
Arjun P Superty India No Participation
Kushagra Juneja India No Participation
Muhammad Ayaz Dzulfikar azure97 Indonesia No Participation
Michael Wibawa M_W Indonesia No Participation
Agus Sentosa Hermawan aguss787 Indonesia No Participation
Stacia Edina Johanna Indonesia No Participation
Francesco Milizia fram Italy 2014 S
Marco Donadoni mark03 Italy No Participation
Filippo Baroni Delfad0r Italy No Participation
Peiman Jabbarzade JeBeK Iran No Participation
Ali Haghani Haghani Iran No Participation
Ali Bahjati alib Iran No Participation
Amir Keivan Mohtashami matrix Iran No Participation
Sami Daoud daoudsammy1 Jordan No Participation
Aleksejs Zajakins Alex_2oo8 Latvia 2014 S
Kristaps Čivkulis kristapuciitis Latvia 2014 S
Ingus Jānis Pretkalniņš Ingugugus Latvia 2014
Aleksejs Popovs popoffka Latvia 2011, 2012 B, 2013 B, 2014 S
Azret Kenzhaliev exm_kg Kyrgyzstan No Participation
Kadyrbek Narmamatov SEFI Kyrgyzstan 2014
Erkin Matkaziev Erkin97 Kyrgyzstan 2014
Zarlyk Jusubaliev heavenly_phoenix Kyrgyzstan No Participation
Kliment Serafimov Macedonia 2012 2013 2014 B
Hristijan Gjorshevski Macedonia No Participation
Mihail Denkovski Macedonia No Participation
Juan Carlos Sigler Priego Juanito98 Mexico No Participation
Carlos Galeana Hernandez charlyhlms Mexico No Participation
Angel David Ortega Ramirez blak_dragon Mexico No Participation
Emmanuel Antonio Cuevas EmmanuelAC Mexico No Participation
Marcel Bezdrighin yosei-san Moldova 2014
Mihail Tarigradschi thatmathguy Moldova No participation
Chihai Mihai mihai_chihai Moldova No participation
Motroi Valeriu Djok Moldova No participation
Dejan Todorovic zele.zeka Montenegro 2014
Velibor Dosljak nnMan Montenegro No Participation
Maciej Hołubowicz znirzejskwarka Poland No Participation
Jarosław Kwiecień rudy102 Poland 2014 G
Przemysław Jakub Kozłowski Poland No Participation
Konrad Jan Paluszek Poland No Participation
Gonçalo Paredes gonP Portugal 2014
José Correia jrcc Portugal No Participation
João Lago joaolago Portugal No Participation
Fábio Colaço fabioiuri Portugal No Participation
Hanpil Kang HYEA Republic of Korea No Participation
Jaehyun Koo koosaga Republic of Korea No Participation
Jeehak Yoon cubelover Republic of Korea 2014 G
Seunghyun Joe ainta Republic of Korea 2014 S
Alexandru Velea plus2CircletOfNobility Romania 2014 S
Rares Buhai rares.buhai Romania 2012 G, 2013 G, 2014 G
Andrei Popa AndreiNet Romania No Participation
Valentin Harsan valih10 Romania No Participation
Mikhail Ipatov LHiC Russia No participation
Vladislav Makeev overtroll Russia No participation
Mikhail Putilin SpyCheese Russia No participation
Nikolay Budin BudAlNik Russia No participation
Marko Stanković MeinKraft Serbia 2013 S, 2014 S
Dimitrije Erdeljan didins Serbia 2013 B, 2014 S
Dušan Živanović zDule98 Serbia No Participation
Nikola Jovanović randomusername Serbia No Participation
Teo Por Loong Singapore No Participation
Feng Jiahai Singapore 2014 G
Pang Wen Yuen pwypeanut Singapore No Participation
Howe Choong Yin Singapore No Participation
Eduard Batmendijn Baklazan Slovakia 2012 G, 2013 G, 2014 S
Bui Truc Lam Slovakia 2014 S
Pavel Madaj Slovakia No Participation
Samuel Sládek samo98 Slovakia No Participation
David Wärn Sweden No Participation
Aleksandar Abas Alex7 Syria 2014
Joud Zouzou joudzouzou Syria 2014
Besher Massri besher Syria No Participation
Mohammad Dwik dwik Syria No Participation
Pochang Chen johnchen902 Taiwan 2014 S
Po Jui Chen a00012025 Taiwan No Participation
Mekhrubon Turaev Ximera Tajikistan 2013,2014
Nodir Daminov Nodir.Daminov Tajikistan No Participation
Doro Umarov DARIUS_XIX Tajikistan 2013,2014
Suhaylii Bakhoduri Suhaylee Tajikistan No Participation
Muhammed İkbal Kazar ikbal Turkey No Participation
Muhammed Emin Ayar eminayar Turkey 2014 S
Abdullah Enes ÖNCÜ enesoncu Turkey 2014 B
Kayacan Vesek kayacanv Turkey No Participation
Bayram Berdiyev bayram Turkmenistan 2014
Silap Aliyev silap-aliyev Turkmenistan 2013 2014
Allanur Shiriyev allanur_tkm Turkmenistan No Participation
Gunesh Purchekov Turkmenistan No Participation
Moakher Mohamed moakhey Tunisia No Participation
Shevchenko Ilya Scorpy Ukraine 2013 B 2014 S
Aslandukov Matvey BigBag Ukraine No Participation
Kachur Roman Maestr0 Ukraine No Participation
Mikhno Mark CbI4 Ukraine No Participation
Rowan Lee Rowan.Lee United Kingdom No Participation
Daniel Chiu waterfalls USA No Participation
Demi Guo DemiGuo USA No Participation
Alexander Wei yummy USA No Participation
Andrew He ecnerwal USA 2014 G
Andrew Li ParanoidAndroid Uzbekistan No Participation
Raif Akhmedshin Zardos Uzbekistan No Participation
Abdulla Axmadaliyev a1549a Uzbekistan No Participation
Ulugbek Sobirov BEK97 Uzbekistan No Participation
Nguyen Tien Trung Kien kien_coi_1997 Vietnam 2014 B
Pham Van Hanh skyvn97 Vietnam No Participation
Nguyen Viet Dung Alpha_purple Vietnam No Participation
Phan Duc Nhat Minh minh141198 Vietnam No Participation

Please feel free to post the participants here too, so that there will be something to discuss :)

Congratulations! To those who qualified for IOI 2015 :)

Read more »

 
 
 
 
  • Vote: I like it
  • +156
  • Vote: I do not like it

By Azret, 5 years ago, In Russian,

Доброго времени суток!

Не так давно начал прорешивать задачи на жадные алгоритмы и ДП. Очень часто затрудняюсь доказывать оптимальность своих решений.

Собственно вопрос: Существует ли общая схема построения доказательства жадных алгоритмов и решений ДП?

Заранее спасибо. :)

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By Azret, 5 years ago, translation, In English,

Hello everyone!

So, the problem is to find all prime numbers on segment N .. N+M where 1010 <= N <= 1011 and 1 <= M <= 105.

My algorithm with O(M * sqrt(K)) asymptotic, where K — is the number that we are testing for primality exceeds TL.

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By Azret, history, 5 years ago, In Russian,

Доброго времени суток!

Предлагаю обсудить задачи прошедшей олимпиады. По ходу буду добавлять разборы.

Разбор задач.

Задача A.

Разбор от Alex_2oo8.

Всегда существует оптимальное решение следующего вида — разобьем всю последовательность на отрезочки и сначала заберем все числа из первого отрезочка (внутри отрезочка берем числа в обратном порядке), потом из второго отрезочка и так далее. К примеру, если мы разбили последовательность на отрезки вот так: [a1a2a3][a4a5][a6a7a8a9], то забирать числа будем в порядке a3, a2, a1, a5, a4, a9, a8, a7, a6. Доказывать это сейчас не буду.

Дальше получается довольно простое ДП: f(k) -  -  максимальная сумма, которую можно получить убрав префикс длины k. Переход будет такой:

  • f(k) = f(k - 1) + ak + 1, если последний отрезочек будет длины 1;

  •  , если последний отрезочек — [j, k].

  • Замечаем, что второй переход можно записать вот так:

 , где S — префиксные суммы и получаем константный переход.

Задача C.

Решение от EXM_KG.

После долгих размышлений я увидел закономерность. Итог:

int s[][5] = {
    {1, 2, 3, 4, 5},
    {4, 5, 1, 2, 3},
    {2, 3, 4, 5, 1},
    {5, 1, 2, 3, 4},
    {3, 4, 5, 1, 2},
};
int main() {
    freopen(NAME".in", "r", stdin);
    freopen(NAME".out", "w", stdout);

    int n, i, j, m, a[111][111];

    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i ++)
        for(j = 0; j < m; j ++)
            a[i][j] = s[i % 5][j % 5];

    for(i = 0; i < n; i ++){
        for(j = 0; j < m; j ++)
            printf("%d ", a[i][j]);
        printf("\n");
    }

    return 0;
}

Задача D.

Разбор от heavenly_phoenix.

Код.

Задача E.

Разбор от SEFI.

Простая динамика, не требует объяснения.

int main(){
    cnt [0] = 1;
    for (i =  1; n >= i ; i++){
        cnt[i] += cnt[i - 1];cnt[i]%=md;
        for (j =  i - 1; j>=1 ; j--){if(a[j] > a[j + 1])break;cnt[i] += cnt[j - 1];cnt[i]%=md;}
        for (j =  i - 1; j>=1 ; j--){if(a[j] < a[j + 1])break;cnt[i] += cnt[j - 1];cnt[i]%=md;}
        long long inter = 0;
        for (j =  i - 1; j>=1 ; j--){
            if(a[j] != a[j + 1])break;
            inter += cnt[j - 1];
        }
        cnt [i] -= inter;
        cnt [i] = (cnt[i] + md) % md;
    }
    cout << cnt[ n ] << endl;
 
    return 0;
}

Задача G.

Разбор от EXM_KG.

Простой жадный алгоритм. На каждом этапе будем уравнивать предыдущий уровень с текущим пока это возможно. Если в конце остались лишние кубики (обозначим их как OST), то ответом будет текущая высота стены + OST / N.

Для лучшего понимания выкладываю код.

Задача I.

Разбор от heavenly_phoenix.

Код.

Задача L.

Разбор от pva701.

  • Первый факт — рассмотрим два возможных отрезка (произвольных длин), кандидатов на ответ, для которых выполнено условие, они либо не пересекаются, либо один вкладывается в другой, потому что если они как-то пересекаются, то у этих отрезков концевые элементы равны — поэтому можем просто взять один отрезок большей длины, таким образом увеличив длину.

  • Т.е можем разбить весь массив на непересекающиеся подряд идущие отрезки. если запрос был просто на массиве — нам нужно было выбрать максимальный из этих отрезков.

  • Посчитаем для каждого i, такой максимальный индекс f[i] (f[i] >= i), что отрезок [i..f[i]] удовлетворяет условию.

  • Теперь, когда приходит запрос, начнем в l, перейдем в f[l] + 1, затем в f[f[l] + 1] + 1, и т.д, т.е будем прыгать на элемент после правой границы отрезка [i..f[i]], сохраняя максимум среди длин всех отрезков, по которым прошли. рано или поздно наступит следующее: либо мы просто придем в r (вернее, на следующий после r) — тогда все, максимум найден, либо следующий прыжок из i будет за правую границу, т.е f[i] > r, отметим, что в этом случае a[i] будет больше либо равен всех элементов на суффиксе [i..r]. тогда начнем ту же самую процедуру с r (мы так же заранее для всех j посчитали массив g[j] — минимальный индекс, такой что [g[j]..j] удовлетворяет условию). рано или поздно, g[j] станет меньше, чем l. тогда a[j] = a[i], т.к. если бы они были неравны, то мы могли перейти из j не за l (g[j] был бы больше l), т.к. a[i] был бы больше a[j] (как мы ранее отметили). Т.е. остается один отрезок, который нельзя никак уже разбить [i..j], учитываем его в нашем ответе.

  • Последний шаг — все вот эти переходы (f[i], g[j]) предподсчитаем в массив двоичных подъемов, и будем делать наши прыжки за log N.

Асимптотика —

Задача J.

Разбор от netman.

Сначала очень просто можно узнать, какое максимальное число вхождений у нас может быть. Просто возьмем и посчитаем, какое максимальное кол-во вхождений какой-нибудь буквы мы имеем. Назовем это кол-во вхождений need.

Давайте научимся проверять какую-нибудь длину len. Проверять длину len — значит узнать, есть ли у нас такая подстрока длины len, что она имеет need непересекающихся вхождений.

Это можно делать за используя полиноминальные хэши. Посчитаем хэш всех подстрок длины len. Выпишем такие пары (hash, position) — хэш подстроки и позиция подстроки. Теперь давайте для каждого уникального hash выпишем все его position в возрастающем порядке. Теперь, зная все position для фиксированного hash не составляет труда посчитать максимальную подпоследовательность из этих позиций, что разница между соседними элементами подпоследовательности больше либо равна len (это условие нужно, потому что мы ищем непересекающиеся вхождения). Это можно легко подсчитать используя ДП:

Пусть a — это подпоследовательность, в которой нужно найти максимальную подпоследовательность, чтобы соседние элементы различались не меньше чем на len. Напоминаю, что все числа в этой последовательности в возрастающем порядке.

Теперь можно просто считать следующее ДП:

fi — максимальная длина подпоследовательности из префикса a длины i. Понятно, что f0 = 0.

Подсчет данного ДП ведется так:

fi = max(fj, f0) + 1, где j — такая максимальная позиция, что ai - aj ≥ len. Если такой позиции нет, то j = 0. Найти такое j можно бинарным поиском.

Как говорилось выше: давайте для каждого уникального hash выпишем все его позиции и запустим на них вышеописанное ДП. И возьмем максимум среди всех результатов запуска ДП. Это и будет максимальное кол-во непересекающихся вхождений строки, имеющей длину len. Теперь легко проверить подходит длина len или нет.

Также надо заметить, что если подходит длина len, то и длина len — 1 тоже подходит, значит можно использовать бинарный поиск, чтобы найти максимальное len, которое подходит.

Итоговая асимптотика решения:

Для лучшего понимания выкладываю код.

Решение от izban.

Есть решение проще.

Сначала найдем need. Теперь фиксируем первую букву ответа (26 вариантов), и перебираем длину ответа, добавляя новый символ — суммарно будет сделано не больше n операций для каждой буквы. Итого, решение за 26n. Код.

P.S. Осталось немного, отписывайтесь.

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

By Azret, 5 years ago, In Russian,

Доброго времени суток!

Задача А.

Реализация.

Задача B.

Ладей можно было расставлять по диагоналям.

Задача С.

Пусть города уже отсортированы по возрастанию пары (население, цена). Для простоты будем считать, что у всех городов разное население (при допуске совпадений к доказательству прибавится лишь немного незначительных подробностей).

  • Можно считать, что сперва мы вербуем людей, а потом завоёвываем города. Пусть из i-того города завербовано xi людей в лучшем ответе.
  • Города лучше всего захватывать в порядке ai - xi (очевидно).
  • В одном из лучших ответов города надо захватывать в порядке ai. Пусть это не так. Тогда если мы сперва захватили i, прямо следуюшим j и ai > aj, то xj = 0 (зачем нам кого-то нанимать, если можно весь город захватить бесплатно). "Перекинем" часть закупок из i-того города в j-тый. Противоречие. (см. пункт 5))
  • Пусть теперь в последнем городе мы закупили солдат больше, чем надо для победы (а в каком-то меньше (иначе мы уже потратили не меньше денег, чем в построенном ответе)). Перекинем одного из закупленных солдат в какой-то город, в котором не закупили всех. Тогда мы всё равно присоединим последний город.
  • Каждая операция, описанная в решении не увеличивает число потраченных денег и перекидывает покупки в более дешёвые города, то есть проблем с зацикливанием нет.

Решение.

Задача D.

Решение от king_of_hakers.

Будем обрабатывать запросы в оффлайн. Для каждого участка будем за O(n) обновлять его высоту. Если номер этого участка - начало порыва ветра чётное число то добавляем соответствующую высоту к этому участку, иначе отнимаем.

Задача Е.

Решение от Anuar.

Обозначения:

  • А — множество столбиков на которые Петя может закинуть кольца
  • B — множество столбиков на которые Петя может закинуть кольца
  • C — множество столбиков на которые и Петя и Вася могут закинуть кольца

|x| -> размер некоторого множества x Так как они играют оптимально оба вначале кидают по очереди кольца в множество С. После этого они кидают в свои множества (т.е Петя в А, Вася в В).

Их очки можно выразить такой формулой:

  • Очки Пети: min( |A| — |C| + ceil(|C| / 2) , ceil(m / 2) )
  • Очки Васи: min( |B| — |C| + floor(|C| / 2) , floor(m / 2) )

Код решения

Задача F.

Решение от Na2a.

Перебираем делителей a * b и ищем такие x, y что x * y = a * b && gcd(x, y) == gcd(a, b) обновляем ответ. Делитель a * b = делитель a * делитель b. Работает за (количество делителей a) * (количество делителей b). Решение.

Задача G.

Решение от Zharaskhan.

Сначала отсортируем массив. Берем самый максимальный сосуд, переливаем и разбиваем пока средняя арифметическая сумма будет меньше чем максимальный элемент.

int ans = 0;
for (int i = n; i >= 1; i--) {
    if (double(sum / double(i)) >= double(a[i])) {
        break;
    }
    ans++;
}

Задача H.

Решение от Zharaskhan.

Посчитаем сколько раз встречается первое и второе слово каждой строки через map Если первое слово встречается больше одного раза тогда это слово Имя, значить упорядочим строку. После этого отсортируем массив.

pair <string, pair <string, string> > a[n];
map <string, int> cnt;
for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second.first >> a[i].second.second;
    cnt[a[i].first]++;
    cnt[a[i].second.first]++; 
}
for (int i = 1; i <= n; i++) {
    if (cnt[a[i].first] > 1) {
      swap(a[i].first, a[i].second.second);
      swap(a[i].second.first, a[i].second.second);
    }
}
sort(a + 1, a + 1 + n);

Задача I.

Решение от Alex_2oo8.

Сведем задачу к кратчайшему пути в графе. Вершинами графа будут состояния (l1, l2, dir), означающие, что мы находимся на перекрестке прямых l1 и l2 и смотрим в данный момент либо по направлению прямой l1 (dir = 0), либо против него (dir = 1). Также добавим две вершины — старт и финиш.

Ребра будут трех типов:

  • Мы можем продолжить движение по прямой до следующего перекрестка. То есть из состояния (l1, l2, dir) в (l1, l3, dir), если пересечение прямых l1 и l3 находится в нужном направлении от пересечения l1 и l2 (или они совпадают). Стоимость таких ребер — 0, так как поворачивать нам не нужно

  • Либо на как-то перекрестке мы можем повернуть — то есть добавляем ребро из (l1, l2, dir) в (l2, l1, new_dir), стоимость такого ребра — угол между данными векторами.

  • И последний вид ребер — это ребра из старта (достаточно добавить два ребра с ценой 0) и аналогично два ребра в финиш.

Как и во всех геометрических задачах, реализация всего этого куда сложнее идеи (по крайней мере для нас). Стоит не забыть, что прямые могут быть параллельными, некоторые из данных точек могут совпадать. Геометрическая составляющая — это нахождение точки пересечения двух прямых и угла между двумя векторами. Для последнего мы использовали скалярное произведение и арккосинус.

Задача J.

Решение от SEFI.

Решение.

Задача K.

Решение от Na2a.

Добавляем по несколько клеток слева, справа, сверху и снизу (я добавил 20 клеток) и отмечаем их '.'. Напишем функцию win(ch) => количество позиций что если в них поставить ch (X или 0), то можно выиграть.

  • Если win('X') > 0 то первый игрок может выиграть сразу, следовательно ответ равен win('X').

  • Иначе, смотрим win('0'). Если позиций, где второй игрок выиграет, больше одного, то мы проиграем в любом случае. (Мы закроем одну позицию, но следующий ход он выиграет).

  • Если win('0') равен одному, то мы закрываем эту позицию, а следующий ход второй игрок не может выиграть. Ему будет оптимальнее закрыть один наш выигрышный ход, следовательно ответ win('X') — 1.

  • Иначе, перебираем клетку куда мы ставим 'X'. Если после того, как мы поставили Х на эту клетку, на поле выигрышных клеток стало больше одного, то увеличиваем ответ.

Функию win(ch) надо реализовать не на всем поле, а на каком то подпрямоугольнике. Решение.

UPD 2. Код решения может не совпадать с идеей, так как был взят от другого пользователя.

Read more »

 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

By Azret, 5 years ago, In Russian,

Привет всем!

"Где я могу найти задачи и решения IOI ?" — частый и актуальный вопрос, который вы хоть раз себе задавали. Я долго не мог найти для него ответ. Долгие поиски все же навели меня ссылки, которыми хочу с вами поделиться.

http://www.ioinformatics.org/locations/ioi**/contest/ -> Здесь можно найти условия задач и решения в текстовом виде. Вместо звёздочек вписываете последние цифры года ( пример : http://www.ioinformatics.org/locations/ioi13/contest/ ).

http://informatics.mccme.ru/course/view.php?id=31 -> Наверняка вы знали, это так, на всякий случай.

UPD Ещё можно обратиться к yeputons по этому вопросу.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it