Домино
вася установил на телефон игру, где в каждой клетке полоски размером 2×n записано целое число. цель игры состоит в том, чтобы накрыть часть клеток доминошками размерами 2×1 так, чтобы сумма чисел на не покрытых доминошками клетках была минимальной.
доминошки можно поворачивать горизонтально или вертикально, они не могут накладываться. обязательно использовать все имеющиеся доминошки.
формат входных данных
в первой строке вводится два числа n и k (1 ≤ n ≤ 2×105, 0 ≤ k ≤ 2×105, 0 ≤ n × k ≤ 2 × 105, n ≥ k) — размер полоски и количество имеющихся доминошек.
в следующих n строках вводятся по 2 целых числа, записанных на полоске. числа не превосходят 109 по модулю.
формат результата
выведите n строк по 2 числа в каждой — описание расположения доминошек на полоске. каждая клетка должна описываться либо числом от 1 до k — номером доминошки, которой она накрыта, либо числом 0, в случае, если она не накрыта доминошкой.
если ответов несколько — выведите любой из них.
// Поскольку о работе с комплексными числами не говорилось, написал метод для решения квадратного уравнения в вещественных числах (d >= 0).
// Solve -- метод, обеспечивающий решение.
using System;
namespace ConsoleApp1
{
internal class Program
{
private static void Main(string[] args)
{
double a, b, c;
Console.Write("a = ");
a = double.Parse(Console.ReadLine());
Console.Write("b = ");
b = double.Parse(Console.ReadLine());
Console.Write("c = ");
c = double.Parse(Console.ReadLine());
if (a == 0)
{
Console.WriteLine("incorrect data");
return;
}
Console.WriteLine();
Solve(a, b, c);
Console.ReadLine();
}
private static void Solve(double a, double b, double c)
{
double d = b * b - 4 * a * c;
if (d < 0)
{
Console.WriteLine("No solutions");
return;
}
double sd = Math.Sqrt(d);
double x1 = (-b + sd) / (2 * a);
double x2 = (-b - sd) / (2 * a);
if (d == 0)
{
Console.WriteLine($"x = {x1}");
return;
}
Console.WriteLine($"x1 = {x1}");
Console.WriteLine($"x2 = {x2}");
}
}
}