Colocación de Sudo[1.3] | Jugando con pilas

Tiene 3 pilas, A (Pila de entrada), B (Pila auxiliar) y C (Pila de salida). Inicialmente, la pila A contiene números del 1 al N, debe transferir todos los números de la pila A a la pila C en orden ordenado, es decir, al final, la pila C debe tener el elemento más pequeño en la parte inferior y el más grande en la parte superior. Puede usar la pila B, es decir, en cualquier momento también puede empujar/abrir elementos para apilar B. En la pila final A, B debe estar vacía.

Ejemplos:

Entrada: A = {4, 3, 1, 2, 5} 
Salida: Sí 7 

Entrada: A = {3, 4, 1, 2, 5} 
Salida: No

Enfoque: Iterar desde la parte inferior de la pila dada. Se requiere inicializar como el elemento más inferior en stackC al final, es decir, 1. Siga el algoritmo que se proporciona a continuación para resolver el problema anterior. 

• si el elemento de la pila es igual al elemento requerido, entonces el número de transferencias será uno, que es el recuento de transferencias de A a C.
• si no es igual al elemento requerido, compruebe si es posible transferirlo comparándolo con el elemento superior de la pila. 
  1. Si el elemento superior en stackC es mayor que el elemento stackA[i], entonces no es posible transferirlo de forma ordenada,
  2. de lo contrario, empuje el elemento a stackC e incremente la transferencia.
• Iterar en la pila C y extraer el elemento superior hasta que sea igual al requerido e incrementarlo y transferirlo en cada paso.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program for
// Sudo Placement | playing with stacks
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// count the number of steps
void countSteps(int sa[], int n)
{
 
    // Another stack
    stack<int> sc;
 
    // variables to count transfers
    int required = 1, transfer = 0;
 
    // iterate in the stack in reverse order
    for (int i = 0; i < n; i++) {
 
        // if the last element has to be
        // inserted by removing elements
        // then count the number of steps
        if (sa[i] == required) {
            required++;
            transfer++;
        }
        else {
            // if stack is not empty and top element
            // is smaller than current element
            if (!sc.empty() && sc.top() < sa[i]) {
                cout << "NO";
                return;
            }
            // push into stack and count operation
            else {
 
                sc.push(sa[i]);
                transfer++;
            }
        }
        // stack not empty, then pop the top element
        // pop out all elements till is it equal to required
        while (!sc.empty() && sc.top() == required) {
            required++;
            sc.pop();
            transfer++;
        }
    }
 
    // print the steps
    cout << "YES " << transfer;
}
 
// Driver Code
int main()
{
    int sa[] = { 4, 3, 1, 2, 5 };
    int n = sizeof(sa) / sizeof(sa[0]);
    countSteps(sa, n);
    return 0;
}

// Java program for Sudo
// Placement | playing with stacks
import java.util.*;
 
class GFG
{
 
    // Function to check if it is possible
    // count the number of steps
    static void countSteps(int sa[], int n)
    {
 
        // Another stack
        Stack<Integer> sc = new Stack<Integer>();
 
        // variables to count transfers
        int required = 1, transfer = 0;
 
        // iterate in the stack in reverse order
        for (int i = 0; i < n; i++)
        {
 
            // if the last element has to be
            // inserted by removing elements
            // then count the number of steps
            if (sa[i] == required)
            {
                required++;
                transfer++;
            }
            else
            // if stack is not empty and top element
            // is smaller than current element
            if (!sc.empty() && sc.peek() < sa[i])
            {
                System.out.print("NO");
                return;
            }
             
            // push into stack and count operation
            else
            {
 
                sc.push(sa[i]);
                transfer++;
            }
            // stack not empty, then pop the top element
            // pop out all elements till is it equal to required
            while (!sc.empty() && sc.peek() == required)
            {
                required++;
                sc.pop();
                transfer++;
            }
        }
 
        // print the steps
        System.out.println("YES " + transfer);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int sa[] = {4, 3, 1, 2, 5};
        int n = sa.length;
        countSteps(sa, n);
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 program for
# Sudo Placement | playing with stacks
from typing import List
 
# Function to check if it is possible
# count the number of steps
def countSteps(sa: List[int], n: int) -> None:
     
    # Another stack
    sc = []
 
    # Variables to count transfers
    required = 1
    transfer = 0
     
    # Iterate in the stack in reverse order
    for i in range(n):
         
        # If the last element has to be
        # inserted by removing elements
        # then count the number of steps
        if (sa[i] == required):
            required += 1
            transfer += 1
             
        else:
             
            # If stack is not empty and top element
            # is smaller than current element
            if (sc and sc[-1] < sa[i]):
                print("NO")
                return
 
            # push into stack and count operation
            else:
                sc.append(sa[i])
                transfer += 1
 
        # stack not empty, then pop the top
        # element pop out all elements till
        # is it equal to required
        while (sc and sc[-1] == required):
            required += 1
            sc.pop()
            transfer += 1
 
    # Print the steps
    print("YES {}".format(transfer))
 
# Driver Code
if __name__ == "__main__":
 
    sa = [ 4, 3, 1, 2, 5 ]
    n = len(sa)
     
    countSteps(sa, n)
 
# This code is contributed by sanjeev2552

// C# program for Sudo
// Placement | playing with stacks
using System;
using System.Collections.Generic;   
     
public class GFG
{
  
    // Function to check if it is possible
    // count the number of steps
    static void countSteps(int []sa, int n)
    {
  
        // Another stack
        Stack<int> sc = new Stack<int>();
  
        // variables to count transfers
        int required = 1, transfer = 0;
  
        // iterate in the stack in reverse order
        for (int i = 0; i < n; i++)
        {
  
            // if the last element has to be
            // inserted by removing elements
            // then count the number of steps
            if (sa[i] == required)
            {
                required++;
                transfer++;
            }
            else
            // if stack is not empty and top element
            // is smaller than current element
            if (sc.Count!=0 && sc.Peek() < sa[i])
            {
                Console.Write("NO");
                return;
            }
              
            // push into stack and count operation
            else
            {
  
                sc.Push(sa[i]);
                transfer++;
            }
            // stack not empty, then pop the top element
            // pop out all elements till is it equal to required
            while (sc.Count!=0 && sc.Peek() == required)
            {
                required++;
                sc.Pop();
                transfer++;
            }
        }
  
        // print the steps
        Console.WriteLine("YES " + transfer);
    }
  
    // Driver Code
    public static void Main(String[] args)
    {
        int []sa = {4, 3, 1, 2, 5};
        int n = sa.Length;
        countSteps(sa, n);
    }
}
// This code has been contributed by 29AjayKumar

<script>
// Javascript program for Sudo
// Placement | playing with stacks
 
// Function to check if it is possible
// count the number of steps
function countSteps(sa, n)
{
 
    // Another stack
        let sc = [];
  
        // variables to count transfers
        let required = 1, transfer = 0;
  
        // iterate in the stack in reverse order
        for (let i = 0; i < n; i++)
        {
  
            // if the last element has to be
            // inserted by removing elements
            // then count the number of steps
            if (sa[i] == required)
            {
                required++;
                transfer++;
            }
            else
             
            // if stack is not empty and top element
            // is smaller than current element
            if (sc.length!=0 && sc[sc.length-1] < sa[i])
            {
                document.write("NO");
                return;
            }
              
            // push into stack and count operation
            else
            {
  
                sc.push(sa[i]);
                transfer++;
            }
             
            // stack not empty, then pop the top element
            // pop out all elements till is it equal to required
            while (sc.length!=0 && sc[sc.length-1] == required)
            {
                required++;
                sc.pop();
                transfer++;
            }
        }
  
        // print the steps
        document.write("YES " + transfer+"<br>");
}
 
// Driver Code
let sa=[4, 3, 1, 2, 5];
let n = sa.length;
countSteps(sa, n);
 
// This code is contributed by rag2127
</script>

YES 7