Две минуты стереозаписи занимают на диске 1,3 Мб, количество уровней кодирования звука 8. С какой частотой дискретизации записан звук? ответ переведите в килоГерцы и округлите до целых.

Первая - прямой перебор, но хорошо оптимизированный: с целочисленным вычислением корня для короткой схемы на квадратах. У меня на компьютере работает впритык, за 2.8 для 100k. Если бы не питон - укладывалось бы, но лень переписывать. На тестовом сервере скорее всего не уложится в таймлимит, просто для информации, что так тоже можно:

def prime_count(N):

   primes = [2, 3]

   i, s, s2 = 5, 3, 9

   while len(primes) < N:

       while s2 <= i:

           s += 1

           s2 = s*s

       flag = True

       for p in primes:

           if p > s+1:

               break

           if i % p == 0:

               flag = False

               break

       if flag:

           primes.append(i)

       i += 2

   return primes[N-1]

print(prime_count(int(input(

Вторая: обычное решето Эратосфена. Сравни, насколько короче получилось =) Число 13 выведено эмпирически, для K<=100000 оно подходит, но потом будет маленьким. В общем случае там должна стоять величина log2(N) с каким-то множителем по теореме о плотности простых чисел. Для 100k работает раз в 15 быстрее, так что в лимит уложится точно:

def eratosthenes(N):

   i, numbers = 0, [True] * (13 * N)

   for index in range(N):

       while not numbers[i]: i += 1

       numbers[i::i+2] = [False] * len(numbers[i::i+2])

   return i+2

print(eratosthenes(int(input(

(см. объяснение)

Объяснение:

Решим задачу с Python 3:

k = 0

for x1 in range(2):

   for x2 in range(2):

       for x3 in range(2):

           for x4 in range(2):

               for x5 in range(2):

                   for x6 in range(2):

                       for x7 in range(2):

                           for x8 in range(2):

                               for x9 in range(2):

                                   for x10 in range(2):

                                       if (((x1 == x2) and (x3 == x4)) or (

                                               not (x1 == x2) and not (x3 == x4)) == 0) and (

                                               ((x3 == x4) and (x5 == x6)) or (

                                               not (x3 == x4) and not (x5 == x6)) == 0) and (

                                               ((x5 == x6) and (x7 == x8)) or (

                                               not (x5 == x6) and not (x7 == x8)) == 0) and (

                                               ((x7 == x8) and (x9 == x10)) or (

                                               not (x7 == x8) and not (x9 == x10)) == 0):

                                           k += 1

print(k)

Результат работы программы: 416.

Задание выполнено!