El grupo de Programación Competitiva Pu++ esta formado por alumnos de varias licenciaturas de la F. Ciencias (Abierto a la Comunidad de CU) con el principal objetivo de participar en concursos ACM. En este blog se encuentra algo de Teoria y Problemas con los que anteriormente hemos trabajado.
lunes, 24 de septiembre de 2012
lunes, 10 de septiembre de 2012
Concurso Fes Acatlán
Les dejo el enlace para que vean los detalles: http://cimac.acatlan.unam.mx/?m=concurso#
quien este interesado en participar comuniquelo a los demas.
Raggedy, Raggedy Regional 2011 North America Mid Atlantic
Consider the problem of laying out text in lines of a fixed maximum width L (a.k.a., ``line filling'').
If you do a poor job,
the ends of the lines are unnecessarily
ragged - like
this paragraph. Now,
by convention, we allow the last line of a paragraph to be arbitrarily ragged. We don't mind if that final line contains just a few characters, but we expect the earlier lines to be of approximately uniform length, filling up the column in which we are setting the text.
See if we care.could be laid out in L = 6 like this:
See if we care.That layout is, arguably, not as visually pleasing as
See if we care.Define a ``word'' as any sequence of non-whitespace characters bounded by a line start or end or by a blank. The legal ``whitespace characters'' in this problem are blanks and the line terminator characters.
Given a sequence of N words of width w1, w2,..., wN, and a maximum line width L, with the guarantee that for all i, wi
Then we can define the raggedness of a line containing words i though j as
r(i, j) = (L - w(i, j))2
Write a program to read paragraphs of text and to lay them out in a
way that no line contains more than L characters, for a specified
L, and so that you minimize the total raggedness added up over all
lines except the last one. (The final line of a paragraph can be
arbitrarily shorter then the lines above it.) Line terminator
characters are not counted as part of the line width.
Input
Input will consist of one or more datasets.Each dataset begins with a line containing one integer, L, denoting the maximum line width (not counting line terminator characters). You are guaranteed that 0 < L
The remainder of the dataset consists of up to 250 lines containing a paragraph of text, terminated by an empty line. Paragraphs may contain from 1 to 500 words, where a word is any consecutive sequence of non-whitespace characters.
No line of text will contain a word of length greater than L.
Output
Print each paragraph laid out optimally as described above. After each paragraph print a line containing ``==='' (three equal signs).If there is more than one way to fill a paragraph with the optimal raggedness, any such layout may be printed.
Sample Input
6 See if we care. 25 Raggedy, raggedy are we. Just as raggedy as raggedy can be. We don't get nothin' for our labor. So raggedy, raggedy are we. - P Seeger 0
Sample Output
See if we care. === Raggedy, raggedy are we. Just as raggedy as raggedy can be. We don't get nothin' for our labor. So raggedy, raggedy are we. - P Seeger ===
jueves, 2 de agosto de 2012
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:
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) = x2 + 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?
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| Digital 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
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) = x2 + 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
107, 0
M
105).
- The second line contains an integer k, the grad of the polynomial P (
0
k
10).
- The third line contains k + 1 integers
a0, a1,..., ak separated by blanks, indicating the integer coefficients
that define the polynomial P, i.e.,
P(x) = akxk + ... + a1x + a0. You can assume that
0
ai
N for each 0
i
k. If k > 0 then you may assume that ak
0.
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
jueves, 21 de junio de 2012
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
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
Suscribirse a:
Entradas (Atom)
