В
Все
Б
Биология
Б
Беларуская мова
У
Українська мова
А
Алгебра
Р
Русский язык
О
ОБЖ
И
История
Ф
Физика
Қ
Қазақ тiлi
О
Окружающий мир
Э
Экономика
Н
Немецкий язык
Х
Химия
П
Право
П
Психология
Д
Другие предметы
Л
Литература
Г
География
Ф
Французский язык
М
Математика
М
Музыка
А
Английский язык
М
МХК
У
Українська література
И
Информатика
О
Обществознание
Г
Геометрия
777кошка777
777кошка777
15.04.2020 10:09 •  Информатика

На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да a, b, c, d, e, f, g, h, i, j. по каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да а в город j?

Показать ответ
Ответ:
mlizim
mlizim
15.04.2022 02:08

#include <iostream>

using namespace std;

int main() {

    int N, count=0;

    long long max;

    // создаем и заполняем массив

    cin>>N;

    long long* array=new long long[N];

    for(int i=0; i<N; i++)

        cin>>array[i];

    //находим максимальный элемент

    for(int i=0; i<N; i++)

    {

        if(i==0)

            max=array[i];

        else if(array[i]>max)

            max=array[i];

    }

    //считаем элементы, равные максимальному

    for(int i=0; i<N; i++)

        if(array[i]==max)

            count++;

    //выводим результат

    cout<<max<<" "<<count;

}

0,0(0 оценок)
Ответ:
faas1501
faas1501
07.05.2021 16:20

Первая - прямой перебор, но хорошо оптимизированный: с целочисленным вычислением корня для короткой схемы на квадратах. У меня на компьютере работает впритык, за 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(

0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота