Encuentre una disposición de M colores para N índices tal que no haya dos índices adyacentes que tengan el mismo color y cada color se pueda usar como máximo K veces. Si no existe tal arreglo, salida -1.
Ejemplos:
Entrada: N = 6, M = 4, K = 2
Salida: 1 2 3 4 1 2
Explicación: El color 1 se asigna al primer índice.
El color 2 se asigna al 2º índice, el color 3 al 3º índice,
el color 4 al 4º índice.
De nuevo, el color 1 se asigna al índice 5 y el color 2 al índice 6.Entrada: N = 20, M = 6, K = 3
Salida: -1
Explicación: No existe tal disposición en la que se puedan asignar 6 colores a un máximo de 3 índices.
Enfoque: Observe los siguientes puntos:
- Si el número de colores es solo 1 y el número de índices es mayor que 1, entonces no puede existir tal asignación.
- Si el número total de índices es mayor que lo que se puede colorear con los colores disponibles ( M * K ), entonces no existe tal asignación.
Siga los pasos a continuación para resolver el problema anterior:
- Si el número de colores es 1 y el número de índices es mayor que 1, la salida es -1.
- Si el número total de colores es mayor que lo que se puede colorear con los colores disponibles ( M * K ), entonces genera -1.
- Si las dos condiciones anteriores no se cumplen, entonces:
- Inicialice la variable x con 1.
- Ejecute un ciclo hasta N y dentro del ciclo, genere x . Incremente x y verifique si x es mayor que M . Si x se vuelve mayor que M , establezca x = 1.
- Cuando x se establece en 1, el ciclo nuevamente comienza a imprimir el número de colores desde 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find the required
// arrangement of colors to indices
void findAssignment(int N, int M, int K)
{
// If number of colors is 1
// and number of indices is more than 1
if (M == 1 && N > 1) {
// Output -1
cout << -1;
}
// If number of indices is more than
// what can be colored
// by the available colors
else if (N > M * K) {
// Output -1
cout << -1;
}
else {
// Initialize x with 1
int x = 1;
// Loop to print
// the required arrangement
for (int i = 0; i < N; ++i) {
// Output the number of colors
cout << x << " ";
// Increment the number of colors
x++;
// If x exceeds the total number
// of available colors
if (x > M) {
// Set x to 1
x = 1;
}
}
}
}
// Driver Code
int main()
{
// Given input
int N = 6, M = 4, K = 2;
// Function Call
findAssignment(N, M, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find the required
// arrangement of colors to indices
static void findAssignment(int N, int M, int K)
{
// If number of colors is 1
// and number of indices is more than 1
if (M == 1 && N > 1) {
// Output -1
System.out.print("-1");
}
// If number of indices is more than
// what can be colored
// by the available colors
else if (N > M * K) {
// Output -1
System.out.print("-1");
}
else {
// Initialize x with 1
int x = 1;
// Loop to print
// the required arrangement
for (int i = 0; i < N; ++i) {
// Output the number of colors
System.out.print(x + " ");
// Increment the number of colors
x++;
// If x exceeds the total number
// of available colors
if (x > M) {
// Set x to 1
x = 1;
}
}
}
}
// Driver Code
public static void main (String[] args)
{
// Given input
int N = 6, M = 4, K = 2;
// Function Call
findAssignment(N, M, K);
}
}
// This code is contributed by hrithikgarg03188
Python3
# Python code for the above approach # Function to find the required # arrangement of colors to indices def findAssignment(N, M, K): # If number of colors is 1 # and number of indices is more than 1 if (M == 1 and N > 1): # Output -1 print(-1) # If number of indices is more than # what can be colored # by the available colors elif (N > M * K) : # Output -1 print(-1) else: # Initialize x with 1 x = 1; # Loop to print # the required arrangement for i in range(N): # Output the number of colors print(x, end= " "); # Increment the number of colors x += 1 # If x exceeds the total number # of available colors if (x > M): # Set x to 1 x = 1; # Driver Code # Given input N = 6 M = 4 K = 2 # Function Call findAssignment(N, M, K); # This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the required
// arrangement of colors to indices
static void findAssignment(int N, int M, int K)
{
// If number of colors is 1
// and number of indices is more than 1
if (M == 1 && N > 1) {
// Output -1
Console.Write(-1);
}
// If number of indices is more than
// what can be colored
// by the available colors
else if (N > M * K) {
// Output -1
Console.Write(-1);
}
else {
// Initialize x with 1
int x = 1;
// Loop to print
// the required arrangement
for (int i = 0; i < N; ++i) {
// Output the number of colors
Console.Write(x + " ");
// Increment the number of colors
x++;
// If x exceeds the total number
// of available colors
if (x > M) {
// Set x to 1
x = 1;
}
}
}
}
// Driver Code
public static void Main()
{
// Given input
int N = 6, M = 4, K = 2;
// Function Call
findAssignment(N, M, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the required
// arrangement of colors to indices
function findAssignment(N, M, K)
{
// If number of colors is 1
// and number of indices is more than 1
if (M == 1 && N > 1) {
// Output -1
document.write(-1)
}
// If number of indices is more than
// what can be colored
// by the available colors
else if (N > M * K) {
// Output -1
document.write(-1)
}
else {
// Initialize x with 1
let x = 1;
// Loop to print
// the required arrangement
for (let i = 0; i < N; ++i) {
// Output the number of colors
document.write(x + " ");
// Increment the number of colors
x++;
// If x exceeds the total number
// of available colors
if (x > M) {
// Set x to 1
x = 1;
}
}
}
}
// Driver Code
// Given input
let N = 6, M = 4, K = 2;
// Function Call
findAssignment(N, M, K);
// This code is contributed by Potta Lokesh
</script>
Producción
1 2 3 4 1 2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA