enunciado 113 El poder de la criptografia

Poder de la Criptografía

Fondo

 El trabajo actual en la criptografía implica (entre otras cosas) grandes números primos y cálculo de potencias de números modulo funciones de estos números primos. El trabajo en esta área se ha traducido en la utilización práctica de los resultados de la teoría de números y otras ramas de las matemáticas, una vez que se consideran de interés sólo teórico.

Este problema está relacionado con el cómputo eficiente de las raíces enteras de números.

El Problema

Dado un número entero   (n>=1) y un entero   (p>=1) usted es escribir un programa que determina (raíz n de p), lo positivo  raíz de p . En este problema, dado tales enteros n y p , p siempre será de la forma (k^n) de un número entero k (este entero es lo que el programa debe encontrar).

La entrada

La entrada consiste en una secuencia de pares de números enteros n y p con cada número entero en una línea por sí mismo. Para todos los pares ,  (1<=n<=200,1<=p<=10^101)y existe un entero k ,  (1<=k<=10^9)tal que (k^n=p=).

La Salida

Para cada par de enteros n y p el valor  debe ser impreso, es decir, el número k de tal manera que .

 Ejemplo de entrada

2

16

 3

27

7

4357186184021382204544

Ejemplo de salida

4

3

1234

El poder de la criptografia

enunciado 10071 Volviendo a la fisica de la escuela

Una partícula tiene velocidad y la aceleración iniciales. Si su velocidad después de cierto tiempo es “v” entonces ¿cuál será su desplazamiento sea en el doble de ese tiempo?

entrada

La entrada contendrá dos números enteros en cada línea. Cada línea tiene un conjunto de entrada. Estos dos enteros denotan el valor de v (-100 ≤ v ≤ 100) y t (0 ≤ t ≤ 200) (t significa el tiempo que las partículas ganan velocidad)

salida

Para cada línea de entrada imprimir un solo entero en una línea que indica el desplazamiento en el doble de ese tiempo.

Ejemplo de entrada

0 0

5 12

Ejemplo de salida

0

120

enunciado 386 cubos perfectos

Durante cientos de años el último teorema de Fermat, que declaró simplemente que para n> 2 no existen números enteros a, b, c mayores que 1,  tal que a^n = b^n + c^n, ha permanecido esquiva sin probar. (Una prueba reciente se cree que es correcta, aunque todavía está en control.) Es posible, sin embargo, para encontrar números enteros mayores que 1 que satisfacen la ecuación del cubo perfecto (a^3 = b^3+c^3+d^3) (por ejemplo, un cálculo rápido mostrará que el 12^3 = 6^3 + 8^3 + 10^3 ecuación es cierto). Este problema requiere que escriba un programa para encontrar todos los conjuntos de números {a, b, c, d} que satisfacen esta ecuación para a menor o igual 200.

Salida

La salida debe aparecer como se muestra a continuación, un cubo perfecto por línea, con el fin de una (es decir, las líneas deben ser ordenados por sus valores a) no decreciente. Los valores de b, c, y d también deben ser listadas en orden no decreciente en la propia línea. Sí existen varios valores de una que puede ser producido a partir de múltiples conjuntos distintos de b, c, d y triples. En estos casos, los triples con los valores de b menores se deben enumerar en primer lugar.

La primera parte de la salida se muestra aquí:

Cubo = 6, Triple = (3,4,5)

Cubo = 12, Triple = (6,8,10)

Cubo = 18, Triple = (2,12,16)

Cubo = 18, Triple = (9,12,15)

Cubo = 19, Triple = (3,10,18)

Cubo = 20, Triple = (7,14,17)

Cubo = 24, Triple = (12,16,20)

Nota: necesitará El programador que preocuparse por una implementación eficiente. El límite de tiempo oficial para este problema es de 2 minutos, y de hecho es posible escribir una solución a este problema que se ejecuta en menos de 2 minutos en una máquina 80386 33 MHz. Debido a la naturaleza distribuida del concurso en esta región, los jueces han recibido instrucciones para hacer el límite de tiempo oficial en su sitio la mayor de 2 minutos o dos veces el tiempo empleado por la solución del juez en la máquina que se utiliza para juzgar a este problema.

enunciado 108 suma maxima

FONDO

Un problema que es simple de resolver en una dimensión a menudo es mucho más difícil de resolver en más de una dimensión. Considere la posibilidad de satisfacer una expresión booleana en forma normal conjuntiva en el que cada conjunto se compone de exactamente 3 disyuntos. Este problema (3-SAT) es NP-completo. El problema 2-SAT se resuelve de forma eficiente, sin embargo. En contraste, algunos problemas pertenecen a la misma clase de complejidad independientemente de la dimensionalidad del problema.

El problema

Dada una matriz de 2 dimensiones de los números enteros positivos y negativos, encontrar el sub-rectángulo con la suma más grande. La suma de un rectángulo es la suma de todos los elementos de ese rectángulo. En este problema, el sub-rectángulo con la suma más grande se conoce como la máxima sub-rectángulo. Un sub-rectángulo es cualquier sub-matriz contigua de tamaño 1x1 o superior situado dentro de toda la gama. Como ejemplo, la máxima sub-rectángulo de la matriz:

0             -2            -7            0

9             2             -6            2

-4            1             -4            1

-1            8             0             -2

se encuentra en la esquina inferior izquierda:

9             2

-4            1

-1            8

y tiene la suma de 15.

Entrada y Salida

La entrada consiste en una matriz de NxN enteros. La entrada comienza con un único entero positivo n en una línea por sí mismo lo que indica el tamaño de la plaza matriz bidimensional. Esto es seguido por N^2 enteros separados por espacios en blanco (saltos de línea y espacios). Estos N^2 enteros constituyen la matriz en orden de las filas (es decir, todos los números de la primera fila, de izquierda a derecha, y luego todos los números de la segunda fila, de izquierda a derecha, etc.). N puede ser tan grande como 100. Los números en la matriz estará en la gama de [-127, 127].

La salida es la suma de la máxima sub-rectángulo.

Ejemplo de entrada

4

0 -2 0 -7 -6 9 2 2

-4 1 -4 -1 1

8 0 -2

Ejemplo de salida

15

enunciado 12342 Calculador de taxas

La gente de un país determinado tienen un poco de interés en el pago de impuestos. Este no es el caso de que no aman el país o que no quieren obedecer la ley, pero el problema es que los complejos cálculos de impuesto a pagar. La mayoría de las personas no entienden la regla y algunos abogados toman altos cargos para ayudar a (?) Ellos. Así, la mayoría de las personas simplemente evitar pagar impuestos. Consciente de esto, el Gobierno decidió automatizar el sistema de pago de impuestos y usted nombró para programar una calculadora de impuestos que tiene un ingreso anual de personas como entrada y calcular el impuesto a pagar por él. Esta es la regla para calcular el impuesto a pagar para una persona:

1. Los primeros 180,000 / - del ingreso es libre de impuestos.

2. Los siguientes 300000 / - tendrá 10% de impuestos.

3. Los siguientes 400000 / - tendrá 15% de impuestos.

4. Los siguientes 300000 / - tendrá 20% de impuestos.

5. El resto tendrá un 25% de impuestos.

6. El impuesto mínimo a pagar será de 2.000 / -. Esto es, si algun impuesto está por debajo de 2000 / - (pero por supuesto mayor que cero) debe pagar 2.000 / -

7. El impuesto a pagar debe ser un entero. Si el impuesto calculado es un punto flotante, entonces debe ser reemplazado por el menor entero mayor que el impuesto a pagar.

Entrada

La primera línea de entrada contendrá un número entero T (T ≤ 5000), que indica el número de casos de prueba.

Cada una de las siguientes líneas de T contiene un entero k (1 ≤ k ≤ 109).

Salida

Para cada línea de salida de entrada el número de caso y un entero que es el impuesto por pagar por el ingreso dado.

Cantidad de Impuesto Tasa

180 000 0% 0

300 000 10% 30 000

135.000 15% 20.250

50250 total

Ejemplo de entrada

3

180001

12345

615000

Ejemplo de salida

Caso 1: 2000

Caso 2: 0

Caso 3: 50.250

UVA

Explicacion propia del ejercicio:

Las taxas inferiores a 180000 no pagan impuestos.

si pasas de ahi el impuesto minimo son 2000 (monedas).

a partir de los 180000 (monedas) se empieza a calcular el impuesto.

Los "primeros" 300000 se calculan con un 10% de impuesto, por ejemplo:

             A 200000 se le restarian los 180000 libres de impuesto y se hacia el 10% de 20000.    

A partir de los 480000 (180000+300000) a los siguientes 400000  (monedas) se le aplica el 15% de impuesto, como en el caso anterior.

Luego (880000 monedas) se aplica un 20% durante 300000  (monedas).

Por ultimo, a lo restante (la parte de ingresos mayor a 1180000 monedas ) se le aplica un impuesto de 25%.

10055 – Hashmat, el guerrero valiente

  Hashmat es un guerreo valiente con un grupo de jóvenes soldados que se desplazan de un lugar a otro para luchar contra sus oponentes. Antes de luchar calculan la diferencia entre su número de soldados y el número de soldados de sus oponentes, Dependiendo de esta diferencia deciden si luchar o no. El número de soldados de Hashmat nunca es mejor que el de su oponente.

Entrada                                                                                                                                                      

Consiste en dos números enteros en cada línea. Estos dos números denotan el número de soldados de Hashmat y de su oponente respectivamente. Los enteros no podrán ser mayores de 2 elevado a 32.

Salida

Para cada línea de la entrada se imprime la diferencia entre el número de soldados de Hashmat y el número de soldados de su oponente. Cada salida se imprime en una línea diferente.

Ejemplo Entrada

10 12
10 14
100 200

Ejemplo Salida

2
4
100

enunciado 11799 Horror Dash

Es esa época del año otra vez! Globos y banderas de colores brillantes se extienden a lo largo de todo tu vecindario por sólo esta una ocasión. Es la fiesta anual del payaso en tu escuela local. Por primera vez en su vida, los estudiantes prueban sus dotes para ser el mejor payaso. Algunos caminan en largos zancos, otros tratan de hacer reir a la multitud en el escenario, mientras que otros aún tratan de hacer su primer acto de malabarismo - algunos "maestros payasos 'incluso enseñan estos trucos a los visitantes en el festival.

Como parte del festival, hay un evento único que se conoce como el "Guion de terror". En este caso, N (1≤N≤100) estudiantes vestidos con los trajes más aterradores posibles empiezan una carrera para coger un pobre payaso que se ejecuta en la misma pista. El payaso tropieza, pierde su mente, y hace todo tipo de actos cómicos mientras es perseguido en la pista. Para mantener el evento  el mayor tiempo posible, el payaso debe correr lo suficientemente rápido para no ser capturado por cualquiera de las criaturas de miedo. Sin embargo, para mantener al público al borde de sus asientos, el payaso tampoco debe correr demasiado rápido. Aquí es donde se debe ayudar.

Dada la velocidad de todas las criaturas de miedo, se debe averiguar la velocidad mínima que el payaso debe mantener para que no se deje atrapar incluso si siguen corriendo siempre.

entrada

La primera línea de entrada contiene un único entero T (T≤50), el número de casos de prueba. Esta línea es seguida por los T casos de entrada. Cada caso de entrada es en una sola línea de números enteros separados por espacios. El primero de estos enteros es N, el número de estudiantes que actúan como criaturas de miedo. El resto de la línea tiene más N números enteros, c0, c1, ..., cn, cada uno representando la velocidad de una criatura en metros por segundo (1≤ci≤10000 para cada i). Usted puede asumir que siempre están corriendo en la misma dirección en la pista.

salida

Debe haber una sola línea de salida para cada caso de prueba, con el formato "Caso c: s". Aquí, c representa el número de serie de la caja de entrada, empezando por 1, mientras que s representa la velocidad requerida del payaso, en metros por segundo.

Sample Input	Sample Output
2 5 9 3 5 2 6 1 2	Case 1: 9 Case 2: 2

UVA

453 - Intersecting Circles(La intersección de los círculos)

La ecuación de un círculo con radio r y centro es

Escriba un programa que compare dos círculos para ver si se cruzan y, si lo hacen, calcular los puntos de intersección. (Puede haber 1, 2, o un número infinito de tales puntos).

Entrada

La entrada a este programa consistirá en un número par de líneas. Cada dos líneas representan un problema de intersección. Cada línea contendrá 3 números reales que constituyen los parámetros  ,   y r de un círculo.

Salida

Para cada problema, la salida debe ser las palabras “No hay intersección” si los círculos no tienen intersección.

Cuando tienen un número infinito de puntos de intersección, la salida debe ser las palabras "Los círculos son iguales".

Si hay intersección en 1 o 2 puntos, la salida debe ser una línea con, respectivamente,  uno o dos pares de números reales que dan las coordenadas X e Y de cualquier punto de intersección. Los pares deben ser ordenados primero por su coordenada X, y cuando éstas son iguales por su coordenada Y.

Entrada ejemplo

0.0 0.0 1.0

3.0 0.0 1.0

0.0 0.0 1.0

0.0 0.0 1.0

0.0 0.0 1.0

1.0 0.0 1.0

Salida ejemplo

No hay intersección

Los círculos son iguales

(0.500,-0.866)(0.500,0.866)

Enunciado original:

Fuente

enunciado 11777 automatizar los grados

11777 Automatizar los Grados

Los profesores de una escuela ubicada en la región occidental de Sylhet, sigue actualmente un sistema manual de clasificación de sus estudiantes. El proceso manual es muy lento y propenso a errores. Desde el próximo semestre que han decidido comprar algunas computadoras para que todo el proceso de clasificación pueden ser automatizadas. Y sí, lo has adivinado - que le han contratado para escribir un programa que hará el trabajo. La clasificación de cada curso se basa en la siguiente escala ponderada:

• Plazo 1 - 20%

• Plazo 2-20%

• Final - 30%

• Asistencia - 10%

• Clase - Pruebas de 20%

Las calificaciones con letras se hacen según la puntuación total obtenida por un estudiante y se muestra a continuación:

• A = 90%

• B = 80% y <90%

• C = 70% y <80%

• D = 60% y <70%

• F <60%

Plazo 1 y Plazo 2 son exámenes de 20 cada uno como nota maxima, Final es de 30 y Asistencia es de 10. Se hacen 3 pruebas por semestre con sus respectivas notas, la media de las 2 mejores se valoran con hasta 20 puntos.

Ejemplo: Di Tara obtuvo notas de 15, 18, 25 y 8 en el Trimestre 1, Trimestre 2, final y Asistencia

respectivamente. Sus marcas de la prueba 3 de clase son 15, 12 y 17. Desde será contado promedio de sus 2 mejores , su marca de prueba clase será igual a (15 + 17) / 2 = 16. Por lo tanto, las marcas totales = 15 + 18 + 25 + 8 + 16 = 82 y ella va a obtener una B.

entrada

La primera línea de entrada es un número entero T (T <100) que indica el número de casos de prueba. Cada caja contiene 7 enteros en una línea en el orden:

• trimestre 1
• trimestre 2
• Final
• Asistencia
• test1
• test2
• test3

Todos estos enteros estarán en el rango [0, puntuación total posible para el ensayo].

salida

Para cada caso, la salida el número de caso primero seguido de la letra de grado {ABCDF}.

Ejemplo de entrada

3

15 18 25 8 15 17 12

20 20 30 10 20 20 20

20 20 30 10 18 0 0

Ejemplo de salida

Caso 1: B

Caso 2: A

Caso 3: B

UVA

Enunciado 11727 Recortes

La Empresa XYZ se ha visto muy afectada por la recesión y está teniendo una gran cantidad de medidas de reducción de costes. Algunas de estas medidas incluyen renunciar a espacio de oficinas, pasando de código abierto, lo que reduce los incentivos, recortando en lujos y la emisión de cartas de despido.

Tienen tres (3) empleados que trabajan en el departamento de contabilidad y se va a despedir a dos (2) de ellos. Después de una serie de reuniones, que han decidido desalojar a la persona que recibe la mayor sueldo y el que obtenga el menor. Esta suele ser la tendencia general durante crisis como esta

Se le dará los salarios de estos 3 empleados que trabajan en el departamento de contabilidad. Usted tiene que averiguar el sueldo de la persona que sobrevive.

entrada

La primera línea de entrada es un número entero T (T <20) que indica el número de casos de prueba. Cada caso consiste en una línea con 3 números enteros positivos distintos. Estos 3 enteros representan los sueldos de los tres empleados. Todos estos serán números enteros en el rango [1000, 10000]

salida

Para cada caso, la salida el número de caso seguido por el sueldo de la persona que sobrevive.

Ejemplo de entrada

  3

  1000 2000 3000

  3000 2500 1500

1500 1200 1800

  Ejemplo de salida

  Caso 1: 2000

Caso 2: 2500

  Caso 3: 1500

UVA

136 Numeros feos

Los números feos son números cuyos únicos divisores primos son 2, 3 ó 5. La secuencia

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

muestra los primeros 11 números feos. Por convención, 1 incluido.

Escriba un programa para encontrar e imprimir el número feo 1500'th.

Entrada y Salida

No hay ninguna entrada para este programa. La salida debe constar de una sola línea como se muestra a continuación, con <número> reemplazado por el número calculado.

Ejemplo de salida

El número feo 1500'th es <número>.

UVA

Traducido por Santiago

UVA 101 El problema de los bloques

BACKGROUND

Muchas áreas de la Informática utilizan dominios simples y abstractos para los estudios analíticos y empíricos. Por ejemplo, un estudio inicial AI de la planificación y la robótica (tiras) utiliza un mundo de bloques en el que un brazo de robot lleva a cabo las tareas que implican la manipulación de bloques.

En este problema va a modelar un mundo simple bloque bajo ciertas reglas y limitaciones. En lugar de determinar la forma de lograr un estado especificado, debes programar un brazo robótico para responder a un conjunto limitado de comandos.

EL PROBLEMA

El problema es analizar una serie de comandos que instruyen a un brazo de robot en la forma de manipular bloques que se encuentran sobre una mesa plana. Inicialmente hay n bloques en la mesa (numeradas de 0 a n-1) con el bloque b_i adyacente para bloquear b_(i + 1) para todo 0<=i<n , como se muestra en el siguiente diagrama:

Diagrama

Los comandos válidos para el brazo robot que manipula bloques son:

Poner A sobre de B “move a onto b”

donde a y b son números de bloque, poner “a” encima de  “b” y regresar cualquier bloque que estubiese encima superior de los bloques A y B a sus posiciones iniciales.

poner a encima b “move a over b”

donde “a” y “b” son números de bloque, poner “a” encima de la pila de bloque de contención b, después de regresar de cualquier bloque que se apilan en la parte superior del bloque “a” a sus posiciones iniciales.

colocar a sobre b “pile a onto b”

donde a y b son números de bloque, poner la pila “a” sobre “b”, Todos los bloques en la parte superior del bloque B se mueven a sus posiciones iniciales antes de adoptar pila lugar.

apilar a sobre b “pile a over b”

donde a y b son números de bloqueas, apilar la fila “a” sobre la fila “b”. Los bloques apilados encima de un bloque conservan su orden original cuando se mueven.

dejar

termina manipulaciones en el mundo de bloques.

Cualquier comando en el que “a” sea igual a “b”  o “a” y “b” estean en la misma pila de bloques es una orden ilegal. Todos los comandos ilegales deben ser ignorados y no deben tener ningún efecto en la configuración de los bloques.

ENTRADA

La entrada comienza con un entero n en una línea por sí mismo que representa el número de bloques en el mundo bloque. Usted puede asumir que 0 <n <25.

El número de bloques es seguido por una secuencia de comandos de bloque, un comando por línea. Su programa debe procesar todos los comandos hasta que se encuentra el comando quit.

Usted puede asumir que todos los comandos serán de la forma indicada anteriormente. No habrá comandos sintácticamente incorrectos.

SALIDA

La salida debe consistir en el estado final del mundo de los bloques. Cada posición debloque original numerado i (0<=i<n donde n es el número de bloques) debe aparecer seguido inmediatamente por dos puntos. Si hay al menos un bloque en él, los “:” deben ser seguido por un espacio, seguido por una lista de bloques que aparecen apilados en esa posición con cada número de bloque separado de otros números de bloque por un espacio. No ponga ningún espacio final de una línea.

Debe haber una línea de salida para cada posición del bloque (es decir, n líneas deproducción donde n es el número entero en la primera línea de la entrada).

Sample Input 

10

move 9 onto 1

move 8 over 1

move 7 over 1

move 6 over 1

pile 8 over 6

pile 8 over 5

move 2 over 1

move 4 over 9

quit

Sample Output 

 0: 0

 1: 1 9 2 4

 2:

 3: 3

 4:

 5: 5 8 7 6

 6:

 7:

 8:

 9:

TRADUCIDO POR: Santiago

UVA: LINK UVA

138 Numeros de calle

Un programador de ordenadores vive en una calle con casas numeradas consecutivamente que empiezan en el numero 1 por un lado de la calle. Todas las noche ella anda con su perro sobre salir de su casa, girar a un lado al azar, caminar hasta el final de la calle y volver. Una noche ella suma los números de las calles por las que ella pasa, excluyendo la suya. La próxima vez ella anda en la otra dirección haciendo lo mismo y descubre, para su asombro, que las dos sumas dan lo mismo. Esto esta determinado en parte por el numero de su casa y en parte por el numero de viviendas en la calle. Sin embargo, es un detalle que le gusta y decide que todas sus casas posteriores deben compartirlo.

Escribe un programa que busque pares de números que satisfagan esta condición. Para empezar tu lista, los primeros pares de números son: (numero de casa, ultimo numero)

         6         8

        35        49

ENTRADA Y SALIDA

No hay una entrada para el programa. La salida consiste en 10 líneas que contengan pares de números, cada uno contenido en un espacio de 10 caracteres, como se muestra arriba

FUENTE: http://uva.onlinejudge.org/

TRADUCTORES: Amanda Álvarez  y Santiago Gómez.