30-06-2009, 12:01 AM

با سلام از اساتید و عزیزانی که جواب سوالات زیر را میدانند خواهشمندم تا مرا از طریق ایمیل زیر باخبر نمایند .

Davood.vahdati2009@gmail.com

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

Problem C -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 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.vahdati2009@gmail.com

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

Problem C -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 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

-------------------------------------------------------------------------------------------

**فایل(های) پیوست شده**

ACM.rar (اندازه: 47.18 KB / تعداد دفعات دریافت: 22)