Problema de la UVA 12318

Recientemente elegimos este problema para trabajar con él. Básicamente, te dan un polinomio de grado k menor o igual a 10 y la idea es averiguar cuantos resultados distintos modulo n+1 (con n menor o igual a 10 000 000) podemos obtener evaluándolo con los enteros del 0 al m menor o igual a 100 000 . Todos los coeficientes del polinomio son mayores o iguales a 0 y menores o iguales a n. Creo que lo primero es ver cómo evaluar rápidamente el polinomio módulo n+1 y después ver cómo averiguar cuántos resultados fueron diferentes. El límite de tiempo es de 4 segundos, y el problema es multicasos. La descripción del problema es la siguiente:

Digital Roulette

John is developing a videogame that allows players to bet in a wall roulette. Players may bet for integer numbers from 0 to N, for some N 0 that represents the maximum number in the roulette.

Of course, the roulette behaves digitally. As a matter of fact, John designed its way to choose a value in the interval 0..N (the result of spinning the roulette) with a digital trigger that moves the roulette with a force that depends on an integer value x randomly chosen in the interval 0..M, where M 0 (M is the maximal appliable force). The roulette turns around a distance equivalent to P(x), where P is a polynomial with integer coefficients. One distance unit represents a displacement of one roulette number, counting clockwise.


It is clear that some result values may be produced by different chosen force values. Also, depending on the mechanism parameters, some numbers in the roulette may be not attainable regardless of the force value. For example, if N = 7, M = 5 and P(x) = x² + 1, the mechanism can generate only three different results:

John wants to know how many different result values may be attained by his mechanism. Can you help him?

Input 

There are several cases to analyze. Each case is described by three lines:

• The first line contains two non-negative integer numbers N and M, separated by a blank ( 1 N 10⁷, 0 M 10⁵).
• The second line contains an integer k, the grad of the polynomial P ( 0 k 10).
• The third line contains k + 1 integers a₀, a₁,..., a_k separated by blanks, indicating the integer coefficients that define the polynomial P, i.e., P(x) = a_kx^k + ^... + a₁x + a₀. You can assume that 0 a_i N for each 0 i k. If k > 0 then you may assume that a_k 0.

The last test case is followed by a line containing two zeros.

Output 

For each case, print one line indicating how many different numbers are attainable by John's mechanism.

Sample Input 

7 5
2
1 0 1
99 10
0
5
99 10
1
5 25
99 10
1
3 29
99 10
2
3 29 31
0 0

Sample Output 

3
1
4
11
10

Duda libreria iostream

Hola,

que saben acerca del uso de la libreria iostream?
del hecho de que deba ponerse.h o no para declarla?
que se deba poner using namespace std; o std:: antes de cada objeto o funcion?

Yo intente usar << de cout, sin poner using namespace std; y no lo compilaba bien codeblocks

Problema de esta semana: COJ 1500 an express taxi

1500 - An Express Taxi

Descripción

In a long street the traffic of express taxies is organized in the following way: There is a taxi stop every one kilometer. An express taxi drives along the street from each stop 1, 2, 3, ... or 10 kilometers without a stop. For each of the ten distances a separate price is fixed and marked in the table, e.g. 1 12 2 21 3 31 4 40 5 49 6 58 7 69 8 79 9 90 10 101 A passenger wants to travel n (1 <= n <= 100) kilometers. Can you write a program to helping on that. Which driving distances does the passenger have to choose so that the journey would be the cheapest, and what is the total price of the journey.

Especificación de entrada

The input has two lines. The first line contains ten space separated integer numbers which are prices for driving 1, 2, 3, ... , 10 kilometers. The last line contains the number of kilometers (n) which the passenger has to travel.

Especificación de salida

Each line except the last one should contain two numbers which are the length of the route and the price of the ticket. The total price of the journey should be written in the last line of the output. If several solutions are possible, choose one of them where tickets (in ascending ordered by the distance) are minimum.

Ejemplo de entrada

12 21 31 40 49 58 69 79 90 101
15

Ejemplo de salida

3 31
6 58
6 58
147

Problemas del Concurso del Politecnico

Resultados del concurso de hoy en el Politécnico

Quedamos en segundo lugar. ¡El próximo tenemos que ir por el primero! El score final fue el siguiente: