AXYZ


Submit solution

Points: 100 (partial)
Time limit: 0.2s
Memory limit: 32M

Author:
Problem type
Allowed languages
C++, Python

Descripción

Considere los números naturales A (formado por dos o tres dígitos, todos distintos y sin numerar) y X (formado por N dígitos, todos sin numerar).

A partir del número X, utilizando todas sus N cifras, construya el mayor número natural Y estrictamente menor que X. Por ejemplo, para X = 121621 construir Y = 121612.

También a partir del número X, se puede obtener el número A suprimiendo algunas cifras de la grafía de X y uniendo las restantes, sin cambiar su orden. Por ejemplo, si X = 121621 y A = 12, hay Z = 3 posibilidades distintas de obtener el número A a partir de X, son: 1) 121621; 2) 121621; 3) 121621. Los que no están en negrita son los que se eliminan.

Tarea

Conociendo los números A, N y las N cifras de X, determinar:

  1. el mayor número natural Y, estrictamente menor que X, que se puede obtener reordenando los dígitos de X;

  2. el máximo número Z de posibilidades distintas por las que se puede obtener el número A a partir del número X suprimiendo algunas cifras y uniendo las restantes sin cambiar su orden.

Entrada

La entrada contiene:

  • en la primera línea, un número natural p; para todas las pruebas de entrada, el número p sólo puede tener el valor 1 o el valor 2;
  • en la segunda línea, el número A, con el significado dado en el enunciado;
  • en la tercera línea, el número de dígitos del número X;
  • en la cuarta línea, una cadena de N dígitos, separados por un espacio, que representan los dígitos del número X, en ese orden.

Salida

  • Si el valor de p es 1, sólo se resolverá el requisito 1. En este caso, la salida contendrá en la primera línea una cadena de dígitos que representan el número natural Y determinado (la respuesta al requisito 1).
  • Si el valor de p es 2, sólo se resolverá el requisito 2. En este caso, la salida contendrá en la primera línea un número natural que representa el número Z determinado (la respuesta al requisito 2).

Restricciones y aclaraciones

  • 12 ≤ A ≤ 987
  • 10 ≤ N ≤ 30000
  • Para todos los datos de la prueba, los números Y y A pueden obtenerse a partir del número X
  • Las respuestas correctas al requisito 1 reciben el 30% de la puntuación y las respuestas correctas al requisito 2 reciben el 70% de la puntuación.

Ejemplo #1 de Entrada

1
12
6
1 2 1 6 2 1

Ejemplo #1 de Salida

121612

Explicación del Ejemplo #1

El requisito 1 está resuelto. A = 12, N = 6, X = 121621 El mayor número Y estrictamente menor que X es: Y = 121612

Ejemplo #2 de Entrada

2
12
6
1 2 1 6 2 1

Ejemplo #2 de Salida

3

Explicación del Ejemplo #2

Resuelve el requisito 2. A = 12, N = 6, X = 121621 Existen Z = 3 posibilidades distintas por las que se obtiene el número A a partir de X: 1) 121621; 2) 121621; 3) 121621


Comments

There are no comments at the moment.