Тема: Допоможіть з завданням будь-ласка

Зеник отримав Марсiанську перестановку p iз чисел вiд 1 до n у подарунок вiд Iлони. Чи-
сло k називається щасливим, якщо Зеник може посортувати отриману перестановку виконавши
довiльну кiлькiсть раз таку операцiю: вибрати i та помiняти мiсцями pi та pi+k.
Допоможiть Зенику визначити усi натуральнi числа, якi є щасливими.
Вхiднi данi:
У першому рядку задано одне цiле число n - розмiр перестановки.
У другому рядку задано n цiлих чисел pi -перестановка.
Вихiднi данi:
У першому рядку виведiть одне цiле число m - кiлькiсть щасливих чисел.
У другому рядку виведiть m цiлих чисел - щасливi числа у порядку зростання.
Обмеження
2 ≤ n ≤105,
1 ≤ pi ≤n,
iснує такий iндекс i, що pi 6= i,
для 60% тестiв виконується додаткове обмеження: n ≤2000.
Приклади:
Вхiднi данi:                                       Вихідні дані:
3                                                     2
3 2 1                                                1 2

7                                                     1
7 5 3 6 2 4 1                                      1

Ось моя спроба:

import random
n  = int(input())
p = input()
pl = p.split()
pl = [int(item) for  item in pl]
x = 0
for i in range(n):
    if pl[i]:
        pl[i] = pl[i+random.randint(1,n)]
        x += 1
        break

print(pl[i])

2

Re: Допоможіть з завданням будь-ласка

перше що помітив, у вас в перемінні n та p можуть попасти дані які будуть порушувати уммову
далі, на виход має бути 2 рядки, у вас - 1

print(pl[i])

незрозумів, чому. вас просять вивести кiлькiсть щасливих чисел, а ви виводите число з масиву

може я трішки тупенький, але навіщо перемінна х?

if pl[i]: #теж нерозумію навіщо

ви свій код на прикладах тестували? там якщо спробувати 2 приклад вибиваєтся помилка

3

Re: Допоможіть з завданням будь-ласка

Ваш код - дурня, і ви це знаєте. if pl[i] буде виконуватися завжди для ненульових pl[i], а нулів там немає; значить, цикл завжди буде виконуватися один раз при i=0 і не потрібний, і весь код після введення - це просто
print(pl[random.randint(1,n)])

Очевидно, що 1 буде "щасливим" завжди, бульбашкове сортування так і працює.
Для k>1 сортування можливе, якщо все елементи, що мають остачу від ділення на k, скажімо, r, знаходяться на місцях, звідки вони можуть потрапити на своє місце, тобто на місцях, номери яких (нумеруємо з 1) мають таку саме остачу r.

Для прикладу №1: 3 та 1 знаходяться на місцях 1 і 3, всі остачі від ділення дорівнюють 1, їх можна обміняти; 2 на своєму місці.
Складніше питання: що робити, якщо послідовність вже відсортована? Довільне число тоді буде щасливим, а в умові нічого про це не сказано.

105 - це мається на увазі 105? Якщо так, то може знадобитися оптимізація, але це вже коли хоч трохи робочий код напишете.
І так, я не зрозумів, що означає "pi 6= i".

4

Re: Допоможіть з завданням будь-ласка

mamkin haker написав:

перше що помітив, у вас в перемінні n та p можуть попасти дані які будуть порушувати уммову
далі, на виход має бути 2 рядки, у вас - 1

print(pl[i])

незрозумів, чому. вас просять вивести кiлькiсть щасливих чисел, а ви виводите число з масиву

може я трішки тупенький, але навіщо перемінна х?

if pl[i]: #теж нерозумію навіщо

ви свій код на прикладах тестували? там якщо спробувати 2 приклад вибиваєтся помилка

Я просто не розумію як в цьому завданні рухатися. Ніби не розумію самої умови, звідси і не можу придумати рішення

А змінну x я забув вивести, але в ній я хотів рахувати кількість щасливих чисел.
Щодо

if pl[i]:

, я не можу придумати як перевіряти на щасливе число

5 Востаннє редагувалося mamkin haker (30.10.2021 14:51:49)

Re: Допоможіть з завданням будь-ласка

hamster.ostap написав:

я не можу придумати як перевіряти на щасливе число

після того як просортируєте масив (використовуюче те число) виконайте оцю функцію

def function(arr) -> bool:
    for i in range(len(arr) - 1):
            if arr[i] > arr[i+1]:
                return False
    return True

якщо Fasle - не щасливе
якщо True - щасливе

звісно у функцію потрібно запихнути відсортований масив

6

Re: Допоможіть з завданням будь-ласка

Хакере, там немає завдання сортувати. Лише визначити, чи є така можливість.

7 Востаннє редагувалося mamkin haker (30.10.2021 16:51:30)

Re: Допоможіть з завданням будь-ласка

ну тоді ось моя спроба, яка теж не вдала =(

import random

def check_index(pi) -> bool:
    for i in range(len(pi)):
        if pi[i] == i+1:
            return False
    return True

def get_chance() -> bool:
    return 60 <= random.randint(1, 101)

def check_arr(pi) -> bool:
    for j in range(len(pi) - 1):
            if pi[j] > pi[j+1]:
                return False
    return True

def main() -> None:
    n_min = 2
    n_max = 10**5
    n_max_chance = 2000
    min_len_pi = 1

    n = int(input("Введіть n: "))

    if get_chance():
        n_max = n_max_chance

    if not(n_min <= n <= n_max):
        if n_max == n_max_chance and n > n_max_chance:
            print("Вам непощастило! Спробуйте ввести n наступного разу!")
        else:
            print("Введіть коректне n!")
        return

    pi = input("Введіть pi: ").split()
    len_pi = len(pi)

    if not(min_len_pi <= len_pi <= n):
        print("Введіть коректне pi!")
        return

    temp_pi = []
    lucky_numbers = []

    for i in range(len_pi):
        temp_pi.append(int(pi[i]))

    if check_index(temp_pi):
        print("Немає такого індекса щоб від був рівним числу під ним!")
        return

    for k in range(len_pi):
        for i in range(len_pi):
            pi[i] = temp_pi[i]

        for _ in range(len_pi):
            for j in range(len_pi):

                if j+k >= len_pi:
                    break
                elif pi[j] > pi[j+k]:
                    temp = pi[j]
                    pi[j] = pi[j+k]
                    pi[j+k] = temp

        if check_arr(pi):
            lucky_numbers.append(k)

    print(len(lucky_numbers))

    for i in range(len(lucky_numbers)):
        print(lucky_numbers[i], end=" ")
    print()

if __name__ == '__main__':
    main()

C:\Users\777\Desktop>python main.py
Введіть n: 3
Введіть pi: 3 2 1
2
1 2

C:\Users\777\Desktop>python main.py
Введіть n: 7
Введіть pi: 7 5 3 6 2 4 1
1
1

8

Re: Допоможіть з завданням будь-ласка

[k for k in range(1,n+1) if all((x-i)%k==0 for i, x in enumerate(pl,1))]

Оформлюйте самостійно.

Подякували: mamkin haker1

9

Re: Допоможіть з завданням будь-ласка

0_0, як :D?
піду гуглити функції all та enumerate :D

але викладач таке напевно не прийме :D

10 Востаннє редагувалося mamkin haker (30.10.2021 18:38:00)

Re: Допоможіть з завданням будь-ласка

koala написав:
[k for k in range(1,n+1) if all((x-i)%k==0 for i, x in enumerate(pl,1))]

Оформлюйте самостійно.

lucky_numbers = []
for k in range(1, n+1):
    for i in range(1, len(pl)):
        if not((pl[i-1] - i) % k == 0):
            break
    
    if i == len(pl) - 1:
        lucky_numbers.append(k)

???