Разбор добавил Роман Атангулов

Понятно, что неподходящими (точно врущими) являются все те черепахи, у которых не выполняется хотя бы одно из условий \(a_i,b_i\geq 0\), \(a_i+b_i=N-1\). Таких черепах не будем рассматривать вообще.

Кроме того, если у каких-то черепах совпадают числа \(a\), то правду может говорить только одна. Тоже и для чисел \(b\). Понятно, что если у каких-то двух черепах из рассматриваемых совпадают \(a\), то совпадают и \(b\), и наоборот. Это значит, что достаточно проверить равенство по \(a\).

Таким образом, алгоритм состоит в следующем: сначала уберём всех неподходящих черепах, а потом посчитаем количество различных из оставшихся. Это количество и будет ответом.

Сложность алгоритма зависит от реализации. Убрать всех неподходящих черепах из массива можно за \(O(N)\) (а можно их просто не добавлять ;). Количество различных черепах можно посчитать, например, отсортировав массив оставшихся за \(O(N\cdot \log N)\). Тогда общая сложность будет \(O(N\cdot \log N)\).

Но можно и достичь асимптотики \(O(N)\), правда, с выделением \(O(N)\) дополнительной памяти. Нужно просто хранить, сколько было подходящих черепах с \(a_i\) для каждого \(a_i\) от 0 до 9999.

По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня a_i черепах, а позади меня b_i черепах”. Ваша задача определить самое большее количество черепах, которые могут говорить правду.