c++ Source Code for acm 2004-2005 problems

Discussion in 'Python' started by Davood Vahdati, Jul 12, 2009.

  1. Dear Sirs And Madams :

    it is an Acm programming competition Questions in year 2004-2005 .
    could you please solve problems is question ? I Wan't C++ Source Code
    program About this questions OR Problems . thank you for your prompt
    attention to this matter

    your faithfully.
    -----------------------------------------
    29th ACM International Collegiate
    Sponsored by
    Programming Contest, 2004-2005
    Sharif Preliminary Contest
    Sharif University of Technology, 28 Oct. 2004

    Problem B
    (Program filename: B.CPP, B.DPR, B.PAS or B.java)

    Parallelogram Counting
    There are n distinct points in the plane, given by their integer
    coordinates. Find the number of parallelograms whose
    vertices lie on these points. In other words, find the number of 4-
    element subsets of these points that can be written as
    {A, B, C, D} such that AB || CD, and BC || AD. No four points are in a
    straight line.
    Input (filename: B.IN)
    The first line of the input file contains a single integer t (1 £ t £
    10), the number of test cases. It is followed by the input

    data for each test case.
    The first line of each test case contains an integer n (1 £ n £ 1000).
    Each of the next n lines, contains 2 space-separated
    integers x and y (the coordinates of a point) with magnitude (absolute
    value) of no more than 1000000000.

    Output (Standard Output)
    Output should contain t lines.
    Line i contains an integer showing the number of the parallelograms as
    described above for test case i.

    Sample Input
    2
    6
    0 0
    2 0
    4 0
    1 1
    3 1
    5 1
    7
    -2 -1
    8 9
    5 7
    1 1
    4 8
    2 0
    9 8

    Sample Output
    5
    6
    ----------------------------------------------------------------------------------------------------------------------
    Problem B-Page 1 of 1

    28th ACM International Collegiate
    Sponsored by
    Programming Contest, 2003-2004
    Sharif Preliminary Contest
    Sharif University of Technology, 14 Nov. 2003

    Problem C
    (Program filename: C.CPP or C.PAS or C.DPR or C.java)

    Toy Storage
    Mom and dad have a problem: their child, Reza, never puts his toys
    away when he is finished playing with them.
    They gave Reza a rectangular box to put his toys in. Unfortunately,
    Reza is rebellious and obeys his parents by simply
    throwing his toys into the box. All the toys get mixed up, and it is
    impossible for Reza to find his favorite toys anymore.
    Reza's parents came up with the following idea. They put cardboard
    partitions into the box. Even if Reza keeps
    throwing his toys into the box, at least toys that get thrown into
    different partitions stay separate. The box looks like this
    from the top:

    We want for each positive integer t, such that there exists a
    partition with t toys, determine how many partitions
    have t, toys.
    Input (filename: C.IN)
    The input consists of a number of cases. The first line consists of
    six integers n, m, x1, y1, x2, y2. The number of
    cardboards to form the partitions is n (0< n £ 1000) and the number of
    toys is given in m (0<m £ 1000). The
    coordinates of the upper-left corner and the lower-right corner of the
    box are (x1, y1) and (x2, y2), respectively. The
    following n lines each consists of two integers Ui Li, indicating that
    the ends of the ith cardboard is at the coordinates
    (Ui, y1) and (Li, y2). You may assume that the cardboards do not
    intersect with each other. The next m lines each consists
    of two integers Xi Yi specifying where the ith toy has landed in the
    box. You may assume that no toy will land on a
    cardboard.
    A line consisting of a single 0 terminates the input.
    Output (filename: C.OUT)
    For each box, first provide a header stating “Box”
    on a line of its own. After that, there will be one line of output
    per
    count (t> 0) of toys in a partition. The value t will be followed by a
    colon and a space, followed the number of
    partitions containing t toys. Output will be sorted in ascending order
    of t for each box.
    Sample Input
    4 10 0 10 100 0
    20 20
    80 80
    60 60
    40 40
    5 10
    15 10
    95 10
    25 10
    65 10
    75 10
    35 10
    45 10
    55 10
    85 10
    5 6 0 10 60 0

    4 3
    15 30
    3 1
    6 8
    10 10
    2 1
    2 8
    1 5
    5 5
    40 10
    7 9
    0

    Sample Output
    Box

    2: 5
    Box
    1: 4
    2: 1
    ----------------------------------------------------------------------
    29th ACM International Collegiate
    Sponsored by
    Programming Contest, 2004-2005
    Sharif Preliminary Contest
    Sharif University of Technology, 28 Oct. 2004

    Problem D
    (Program filename: D.CPP, D.DPR, or D.java)

    Software Company
    A software developing company has been assigned two programming
    projects. As
    both projects are within the same contract, both must be handed in at
    the same
    time. It does not help if one is finished earlier.

    This company has n employees to do the jobs. To manage the two
    projects more
    easily, each is divided into m independent subprojects. Only one
    employee can
    work on a single subproject at one time, but it is possible for two
    employees to
    work on different subprojects of the same project simultaneously.

    Our goal is to finish the projects as soon as possible.

    Input (filename: D.IN)
    The first line of the input file contains a single integer t (1 £ t £
    11), the
    number of test cases, followed by the input data for each test case.
    The first
    line of each test case contains two integers n (1 £ n £ 100), and m (1
    £ m £
    100). The input for this test case will be followed by n lines. Each
    line
    contains two integers which specify how much time in seconds it will
    take for
    the specified employee to complete one subproject of each project. So
    if the
    line contains x and y, it means that it takes the employee x seconds
    to complete
    a subproject from the first project, and y seconds to complete a
    subproject from
    the second project.
    Output (Standard Output)
    There should be one line per test case containing the minimum amount
    of time in
    seconds after which both projects can be completed.

    Sample Input
    1
    3 20
    1 1
    2 4
    1 6

    Sample Output
    18

    Problem D -Page 1 of 1

    29th ACM International Collegiate
    Sponsored by
    Programming Contest, 2004-2005
    Sharif Preliminary Contest
    Sharif University of Technology, 28 Oct. 2004
    ----------------------------------------------------------------------
    Problem F
    (Program filename: F.CPP, F.DPR, or F.java)

    Median Weight Bead
    There are N beads which of the same shape and size, but with different
    weights.
    N is an odd number and the beads are labeled as 1, 2, ..., N. Your
    task is to
    find the bead whose weight is median (the ((N+1)/2)th among all
    beads). The
    following comparison has been performed on some pairs of beads:
    A scale is given to compare the weights of beads. We can determine
    which one is
    heavier than the other between two beads. As the result, we now know
    that some
    beads are heavier than others. We are going to remove some beads which
    cannot
    have the medium weight.

    For example, the following results show which bead is heavier after M
    comparisons where M=4 and N=5.

    1. Bead 2 is heavier than Bead 1.
    2. Bead 4 is heavier than Bead 3.
    3. Bead 5 is heavier than Bead 1.
    4. Bead 4 is heavier than Bead 2.
    From the above results, though we cannot determine exactly which is
    the median
    bead, we know that Bead 1 and Bead 4 can never have the median weight:
    Beads 2,
    4, 5 are heavier than Bead 1, and Beads 1, 2, 3 are lighter than Bead
    4.
    Therefore, we can remove these two beads.
    Write a program to count the number of beads which cannot have the
    median
    weight.

    Input (filename: F.IN)
    The first line of the input file contains a single integer t (1 £ t £
    11), the
    number of test cases, followed by the input data for each test case.
    The input
    for each test case will be as follows:
    The first line of input data contains an integer N (1=N=99) denoting
    the number
    of beads, and M denoting the number of pairs of beads compared. In
    each of the
    next M lines, two numbers are given where the first bead is heavier
    than the
    second bead.
    Output (Standard Output)
    There should be one line per test case. Print the number of beads
    which can
    never have the medium weight.

    Sample Input Sample Output
    1 2
    5 4
    2 1
    4 3
    5 1
    4 2
    Problem F -Page 1 of 2
     
    Davood Vahdati, Jul 12, 2009
    #1
    1. Advertisements

  2. Davood Vahdati

    Paul McGuire Guest

    <huge chunk of OT content snipped>

    looking for the Python content in this post...

    mmmmm, nope, didn't find any...

    I guess the OP tried on a C++ newsgroup and got told to do his own
    homework, so he came here instead?
     
    Paul McGuire, Jul 12, 2009
    #2
    1. Advertisements

  3. En Sun, 12 Jul 2009 19:24:57 -0300, Davood Vahdati
    Not C++ code but Python: A brute force approach to the first problem.
    class Point:
    def __init__(self, x, y): self.x, self.y = x, y
    def __repr__(self): return 'Point(%d,%d)' % (self.x, self.y)

    class Segment:
    def __init__(self, p0, p1): self.p0, self.p1 = p0, p1
    def is_parallel(self, other):
    return ((self.p1.x-self.p0.x) * (other.p1.y-other.p0.y) -
    (self.p1.y-self.p0.y) * (other.p1.x-other.p0.x) == 0)

    points = [
    Point(-2,-1),
    Point(8,9),
    Point(5,7),
    Point(1,1),
    Point(4,8),
    Point(2,0),
    Point(9,8)]

    n = 0
    for i,A in enumerate(points):
    for B in points[i+1:]:
    AB = Segment(A,B)
    for C in points:
    if C in (A,B): continue
    BC = Segment(B,C)
    for D in points:
    if D in (A,B,C): continue
    CD = Segment(C,D)
    if AB.is_parallel(CD) and BC.is_parallel(Segment(A,D)):
    print A,B,C,D
    n += 1

    n /= 4 # ABCD,BCDA,CDAB,DABC ## BACD etc already removed
    print n
     
    Gabriel Genellina, Jul 13, 2009
    #3
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.