1 Тема від Eff1c Востаннє редагувалося Eff1c (14.04.2019 16:26:24)

  • Eff1c
  • Eff1c
  • Користувач
  • Поза форумом
  • Звідки: Луцьк
  • Дата реєстрації: 15.01.2018
  • Повідомлень: 448
    • Репутація: 91

Тема: задачка з олімпіади

https://replace.org.ua/uploads/images/7323/5c73a1936f42179e0dad018bc976d1c7.jpg UI
Доброго дня.
Прошу допомогти мені розв'язати мені задачку з вчорашньої олімпіаду.
Вчора я не встиг її доробити, але ради цікавості - доробив сьогодні.
Але є одна проблема - я розумію, що при певних тестах мій розв'язок не пройде.
Умова на фотографії (вибачте за якість, в кращій ніяк не можу загрузити).
Ось мій код:

import math
out = []       # масив для виводу
n  = int(input())
arr = list(map(int, input().split()))
for i in range(n * 2 - 1):   # кількість команд - 1 (бо далі ми будемо перевіряти даний і наступний елемент масиву, отже, останній не потрібно)
  if arr[i] == arr[i + 1]:   # якщо даний елемент = наступному
    out.append(i + 1)        # то добавляємо його порядковий номер ( + 1, бо потрібно, щоб був відлік від 1) в масив для виводу
print(math.ceil(len(out) / 2))  # рахує кількість хвилин (перестановок) по кількості елементів масиву і виводить
for i in range(1, math.ceil(len(out) / 2) + 1):  # виконуємо цикл по кількості перестановок, але з відліком від одного (тому, що далі у нас буде спосіб обчислення порядкового номеру масиву неприйнчтний для 0)
  try:
    print(str(out[i * 2 - 2]) + " " + str(out[i * 2 - 1])) # якщо є 2 команди, то міняємо їх місцями
  except:
    print(str(out[i * 2 - 2]) + " 1")    # якщо залишилась лише 1 команда то міняємо її з 1шою

Розумію, код сильно заплутаний  *SCRATCH*  і мабуть є набагато простіший спосіб це зробити, але тому я сюди і пишу - щоб ви мені допомогли.
На рахунок тестів, які він не пройде - ось приклад:
Вхідні дані:

2
1 1 2 2

Вихідні:

1
1 3

Тобто, якщо у тест-кейсі буде іти підряд 2 пари одинакових чисел, які потрібно переставити місцями - тест провалиться.
А ще коли потрібно буде переставити місцями перший елемент масиву і, потім, після всіх перестановок залишиться якийсь один елемент, який потрібно буде переставити і він по замовчуванні буде переставлений з 1м

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 620
    • Репутація: 13331

Re: задачка з олімпіади

1. Знаходимо всі пари, хай їх буде p; кількість обмінів - (p+1)//2. В принципі, це можна пропустити, але так одразу маємо перше число відповіді
2. Для кожної пари знаходимо у наступній елемент, що не межує із цією парою.
3. Якщо лишилася одна пара, знаходимо перший елемент, що це межує із цією парою і не рівний сусідньому із нею числу. Обмінюємо.

Подякували: Eff1c1

koala вебсайт

3 Відповідь від koala Востаннє редагувалося koala (14.04.2019 20:14:48)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 620
    • Репутація: 13331

Re: задачка з олімпіади

Якось так вийшло:

n = int(input())
arr = [int(x) for x in input().split()]

answer = []
for i in range(2*n-1):
    if arr[i]==arr[i+1]:
        if len(answer)%2 == 0: #no previous elements to change
            print(f'will change {arr[i]}')
            answer.append(i)
        else:
            print(f'will change to {arr[i+1]}')
            answer.append(i+1) #we always may change first in left pair and second in right pair
print(f'answer now is {answer}')
if len(answer)%2==1: #last change is not done
    for i in range(2*n):
        if (    (i==0              or arr[answer[-1]]  !=arr[i-1])
            and (i==2*n-1          or arr[answer[-1]]  !=arr[i+1])
            and (answer[-1]==0     or arr[answer[-1]-1]!=arr[i])
            and (answer[-1]==2*n-1 or arr[answer[-1]+1]!=arr[i])
                ):
            answer.append(i)
            break
print(len(answer)//2)
print(' '.join(str(x+1) for x in answer)) #answer uses 0-base numeration
Подякували: Eff1c, shabaranskij2

koala вебсайт