Алгоритм по поиску перестановки одной пары элементов массива, чтобы на четных местах стояли четные элементы, а на нечетных - нечетные
Подскажите, пожалуйста, как решить задачу из Тинькофф.Контест. У меня уже есть свое решение, но проверяющая система оценивает его, как частичное. Уже тестировал на многих массивах, везде выдает правильный ответ. Не могу понять, что не так.
Условие задачи: Дан массив из n натуральных чисел (2 ≤ n ≤ 1000). Нужно найти и вывести в консоль единственную пару индексов i, j (1 ≤ i, j ≤ n, i != j), такую, что переставив элементы, которые стоят на этих индексах, массив примет вид "четный индекс - четное значение, нечетный индекс - нечетное значение". Если ответов несколько — разрешается вывести любой. Если не существует способа поменять только два элемента местами — вывести -1 -1.
Пример:
Я написал вот такой код:
using System;
using System.Linq;
public class HelloWorld
{
public static long[] GetNumericalInput()
{
var parametrs = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
return parametrs;
}
public static Tuple<int, int> Task6(int n, long[] array)
{
int i = -1, j = -1;
long iValue = 0;
bool isPossible = true;
for (int index = 0; index < n; index++)
{
// Если на i-ом месте все правильно, то двигаемся дальше
if (array[index] % 2 - (index + 1) % 2 == 0)
continue;
else
{
// Если мы уже нашли пару элементов, которую нужно поменять,
// то одной единственной перестановки не хватит и можно останавливать цикл
if (i != -1 && j != -1)
{
isPossible = false;
break;
}
if (i == -1)
{
i = index + 1;
// Запоминаем, что за число стоит на неправильно позиции
iValue = array[index];
}
else
{
// Если текущее число, стоящее в неправильной позиции, противоположно по четности ранее найденному числу,
// то мы нашли пару для перестановки
if (iValue % 2 - array[index] % 2 != 0)
j = index + 1;
}
}
}
if (i == -1 || j == -1 || i == j || !isPossible)
i = j = -1;
return Tuple.Create(i, j);
}
public static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
long[] array = GetNumericalInput();
var result = Task6(n, array);
Console.WriteLine(result.Item1.ToString() + " " + result.Item2.ToString());
}
}
Ответы (2 шт):
Для списка 1 2 3 4 ваша программа ответит -1 -1. Хотя годятся ответы 1 3 и 2 4.
Когда все числа уже на своих местах, можно менять числа одинаковой чётности. В программе ниже в этой ситуации всегда меняются индексы 1 и 3.
Примеры:
1 2 -> -1 -1 # все на местах, но список короткий 1 2 3 -> 1 3 # все на местах, меняем первый и третий 1 2 3 4 -> 1 3 # ... 1 2 3 5 -> -1 -1 # один не на месте, ничего нельзя сделать 1 2 4 3 -> 3 4 # два разной чётности не на месте 4 3 2 1 -> -1 -1 # три или больше не на месте, ничего нельзя сделать
using System;
using System.Linq;
public class Temp {
public static void Main(string[] args) {
int n = int.Parse(Console.ReadLine());
int[] indices = Console.ReadLine()
// "11 12 14 15 16 17"
.Split(' ')
// "11", "12", "14", "15", "16", "17"
.Select((w, i) => (i + 1, long.Parse(w)))
// (1, 11), (2, 12), (3, 14), (4, 15), (5, 16), (6, 17)
.Where(t => t.Item1 % 2 != t.Item2 % 2)
// (3, 14), (4, 15), (5, 16), (6, 17)
.Take(3) // optimization
// (3, 14), (4, 15), (5, 16)
.Select(t => t.Item1)
// 3, 4, 5
.ToArray()
;
switch (indices.Length) {
case 0 : Console.WriteLine((n < 3) ? "-1 -1" : "1 3"); break;
case 2 : Console.WriteLine(String.Join(' ', indices)); break;
default: Console.WriteLine("-1 -1" ); break;
}
}
}
$ csc -nologo Temp.cs $ echo -e "2\n1 2" | mono Temp.exe -1 -1 $ echo -e "3\n1 2 3" | mono Temp.exe 1 3 $ echo -e "4\n1 2 3 4" | mono Temp.exe 1 3 $ echo -e "4\n1 2 3 5" | mono Temp.exe -1 -1 $ echo -e "4\n1 2 4 3" | mono Temp.exe 3 4 $ echo -e "4\n4 3 2 1" | mono Temp.exe -1 -1
Тоже мучился с этой задачкой. Весь день мучился с этим заданием. Вот написал этот код, но тесты также не проходили. Наткнулся на твой такой же вопрос и в коде выше увидел эту проверку:
case 0 : Console.WriteLine((n < 3) ? "-1 -1" : "1 3"); break;
Добавил это в свой код.
if (oddOnEven == 0 && evenOnOdd == 0)
{
Console.WriteLine((n < 3) ? "-1 -1" : "1 3");
}
И все тесты были пройдены.
int quantity = int.Parse(Console.ReadLine()!);
string[] input = Console.ReadLine()!.Split(" ",
StringSplitOptions.RemoveEmptyEntries);
if (quantity < 2 || quantity > 1000)
{
throw new ArgumentOutOfRangeException($"{nameof(quantity)} must be between 2 and 1000.");
}
int[] students = new int[quantity ];
for (int i = 0; i < quantity; i++)
{
var height = int.Parse(input[i]);
if (height < 1 || height > Math.Pow(10, 9))
{
throw new ArgumentOutOfRangeException($"Element {i} must be integer number between 1 and 10^9.");
}
students[i] = height;
}
int evenOnOdd = 0, oddOnEven = 0, evenIndex = 0, oddIndex = 0;
for (int i = 0; i < quantity; i++)
{
//Чётный рост на нечётном месте
if ((i + 1) % 2 != 0 && students[i] % 2 == 0)
{
//Запоминает индекс студента и добавляет в счётчик (чётный на нечётном)
oddIndex = i + 1;
evenOnOdd++;
}
//Нечётный рост на чётном месте
else if ((i + 1) % 2 == 0 && students[i] % 2 != 0)
{
//Запоминает индекс студента и добавляет в счётчик (нечётный на чётном)
evenIndex = i + 1;
oddOnEven++;
}
}
// согласно условиям если есть только одна пара учеников которые должны поменяться местами чтобы шеренга стала валидной, то выводим номера этих учеников на экран
if (oddOnEven == 1 && evenOnOdd == 1)
{
Console.WriteLine($"{oddIndex} {evenIndex}");
}
//Если нету пар которые должны поменяться местами и в шеренге итак все норм
else if (oddOnEven == 0 && evenOnOdd == 0)
{
Console.WriteLine((quantity < 3) ? "-1 -1" : "1 3");
}
// Если нужно поменять местами больше одной пары, либо шеренга не валидна
else
{
Console.WriteLine("-1 -1");
}