1

Подскажите, пожалуйста, как решить задачу из Тинькофф.Контест. У меня уже есть свое решение, но проверяющая система оценивает его, как частичное. Уже тестировал на многих массивах, везде выдает правильный ответ. Не могу понять, что не так.

Условие задачи: Дан массив из 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
  • Вообще-то если вопрос именно разбивки на 2 команды, то расстановка к четным на четных местах, а нечетным на нечетных, как и расстановка четным на нечетных местах, а нечетных на четных, приводят к главному - требуемому разбиению на 2 команды. Хотя второе и противоречит пояснению "Иначе говоря, он хочет получить такой порядок, при котором все ученики с четным ростом стоят на четных позициях, а с нечетным — на нечетных.". Но чем черт не шутит - а попробуйте допустить и второй вариант расстановки, вдруг он годится :)
    – Harry
    2 мар в 13:13
  • Если все элементы стоят на верных местах это не повод выдавать -1, -1. Вы можете вернуть любую пару индексов одинаковой четности. 3 мар в 22:59

2 ответа 2

0

Для списка 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
6
  • Спасибо за ответ. Исправил программу. Количество пройденных тестов увеличилось, но система все также показывает "частичное решение"
    – ByMyKolaps
    4 мар в 13:52
  • Дайте ссылку на задачу. Покажите код. 4 мар в 14:01
  • Создал репозиторий на гитхабе: github.com/ByMyKolaps/Task6_Tinkoff Там полное условие, код и юнит-тесты. Для доступа к самой проверяющей системе, придется зарегистрироваться на сайте, что может быть не очень удобно, но на всякий случай, оставлю ссылку: edu.tinkoff.ru/selection/76378fbd-1998-48fa-944e-eb736d321f11/…
    – ByMyKolaps
    4 мар в 16:51
  • Там проблемы с чтением входа. Я создал дефект в репозитории. 4 мар в 17:11
  • Исправил, но это не помогло
    – ByMyKolaps
    5 мар в 11:35
0

Тоже мучился с этой задачкой. Весь день мучился с этим заданием. Вот написал этот код, но тесты также не проходили. Наткнулся на твой такой же вопрос и в коде выше увидел эту проверку:

    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");
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.