شما وارد انجمن نشده‌اید، در اینصورت از تمامی امکانات سایت نمی‌توانید استفاده کنید. برای رفع این مشکل وارد شوید یا ثبت‌نام کنید.

ارسال پاسخ 
 
امتیاز موضوع:
  • 2 رأی - میانگین امیتازات : 5
  • 1
  • 2
  • 3
  • 4
  • 5
سوالات اولین acm دانشگاه در ترم جدید
abbasi
مهمان

 
سپاس ها
سپاس شده بار در ارسال
۲۷-مهر-۱۳۸۹, ۰۸:۰۳ عصر
0سوالات اولین acm دانشگاه در ترم جدید | ارسال: #1

اولین acm  دانشگاه در پنج شنبه 15/7/89   در سایت دانشکده فنی با حضور 4 گروه سه نفره و یک گروه 2 نفره از ساعت 9:30 تا 2:30 برگزار شد که از میان این گروه ها تنها گروه آقای کوشا حقیری (علوم کامپیوتر88) موفق به حل سوال maximum sumشدند.

Background

Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level.

This problem deals with computing quantities relating to part of Fermat's Last Theorem: that there are no integer solutions of for n > 2.

The Problem

Given a positive integer N, you are to write a program that computes two quantities regarding the solution of

where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x<y< z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values such that p is not part of any triple (not just relatively prime triples).

The Input

The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file.

The Output

For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is ). The second number is the number of positive integers that are not part of any triple whose components are all . There should be one output line for each input line.

Sample Input

10

25

100

Sample Output

1 4

4 9

16 27

 

 

 

 

 Maximum Sum 

Background

A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.

The Problem

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

is in the lower-left-hand corner:

and has the sum of 15.

Input and Output

The input consists of an array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by integers separated by white-space (newlines and spaces). These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [-127, 127].

The output is the sum of the maximal sub-rectangle.

Sample Input

4

0 -2 -7  0 9  2 -6  2

-4  1 -4  1 -1

8  0 -2

Sample Output

15

 

 

 

 

 

 

 

 

 

 

 

 

 

 Il Gioco dell'X 

The game `Il Gioco dell' X' is played on a N by N board ( ). The object of both players, say Black and White, is to join opposite sides of the board by placing in turn their pawns on the board in such a way that a path is made from one side to the other by adjacent (neighboring) pawns of their own color. Although the board is it is not a square but rather diamond-shaped. Let us denote the field on the board in row i and column j by . The neighbors of (i, j) are:

                       ( i-1 , j-1 ) , ( i-1 ,  j  )

                       (  i  , j-1 ) , (  i  , j+1 )

                       ( i+1 ,  j  ) , ( i+l , j+1 )

provided these fields do not fall outside the board.

Black tries to join row 1 with row N, while White tries to join column 1 with column N.

lt is a Deep Mathematical Result that this game cannot end in a draw (that is, without winner). As we will present to you only full boards, there will always be a winner. It may, however, be difficult to see who has won, so some computer assistance would be appreciated.

Examples:

Example 1 Example 2

این سوال یه تصویر داره که تو فایل زیر موجود است 

In example 1 White has won, and in example 2 Black has won.

Input

The input is a textfile containing a number of games. Each game is given by: one line containing an integer N, being the number of rows. (N can he any number between 2 and 200). This line is followed by N lines, each consisting of a row of N characters from the set {`b',`w'} denoting the pawns of Black and White respectively. The numbers of black and white pawns will differ by at most one. Note that all positions on the board are filled with pawns. The list of games ends with a single zero on a line of its own. (Of course, this is not a game for which a winner has to be determined.)

Output

The output will be a textfile containing one line for each game. This line should contain the number of the game (starting at 1) followed by a space, and followed by an uppercase `B' if Black did win, or followed by an uppercase `W' if White did win.

Sample Input

4

bbwb

wwbw

bbwb

bwww

4

bbwb

wwbw

bwwb

wwbb

0

Sample Output

1 W

2 B

 

 

 

 

 

 

 

 

 Roman Digititis 

Many persons are familiar with the Roman numerals for relatively small numbers. The symbols ``i", ``v", ``x", ``l", and ``c" represent the decimal values 1, 5, 10, 50, and 100 respectively. To represent other values, these symbols, and multiples where necessary, are concatenated, with the smaller-valued symbols written further to the right. For example, the number 3 is represented as ``iii", and the value 73 is represented as ``lxxiii". The exceptions to this rule occur for numbers having units values of 4 or 9, and for tens values of 40 or 90. For these cases, the Roman numeral representations are ``iv" (4), ``ix" (9), ``xl" (40), and ``xc" (90). So the Roman numeral representations for 24, 39, 44, 49, and 94 are ``xxiv", ``xxxix", ``xliv", ``xlix", and ``xciv", respectively.

The preface of many books has pages numbered with Roman numerals, starting with ``i" for the first page of the preface, and continuing in sequence. Assume books with pages having 100 or fewer pages of preface. How many ``i", ``v", ``x", ``l", and ``c" characters are required to number the pages in the preface? For example, in a five page preface well use the Roman numerals ``i", ``ii", ``iii", ``iv", and ``v", meaning we need 7 ``i" characters and 2 ``v" characters.

Input

The input will consist of a sequence of integers in the range 1 to 100, terminated by a zero. For each such integer, except the final zero, determine the number of different types of characters needed to number the prefix pages with Roman numerals.

Output

For each integer in the input, write one line containing the input integer and the number of characters of each type required. The examples shown below illustrate an acceptable format.

Sample Input

1

2

20

99

0

Sample Output

1: 1 i, 0 v, 0 x, 0 l, 0 c

2: 3 i, 0 v, 0 x, 0 l, 0 c

20: 28 i, 10 v, 14 x, 0 l, 0 c

99: 140 i, 50 v, 150 x, 50 l, 10 c

 

نقل قول این ارسال در یک پاسخ
abbasi
مهمان

 
سپاس ها
سپاس شده بار در ارسال
۲۷-مهر-۱۳۸۹, ۰۸:۱۴ عصر
0RE: سوالات اولین acm دانشگاه در ترم فعلی | ارسال: #2

سوالات اولین 89  acm دانشگاه ذر ترم جدید



فایل (های) پیوست شده
First-89.docx
نوع فایل .docx
دفعات دانلود 215
اندازه 34.27 KB

نقل قول این ارسال در یک پاسخ
آفلاین
nvdcmptr
Programmer
*****
ثبت‌نام‌شده

ارسال ها: 1,300
تاریخ عضویت: فروردين ۱۳۸۹
اعتبار: 15
سپاس ها 25
سپاس شده 12 بار در 9 ارسال
۲۸-مهر-۱۳۸۹, ۰۵:۵۳ عصر
0RE: سوالات اولین acm دانشگاه | ارسال: #3
این مسابقه اولین ACM داشگاه نبوده!
nvdcmptr[تصویر: 1402658063_4_ce9cca802e.PNG]
یافتن تمامی ارسال های این کاربر
نقل قول این ارسال در یک پاسخ
abbasi
مهمان

 
سپاس ها
سپاس شده بار در ارسال
۲۸-مهر-۱۳۸۹, ۱۰:۵۸ عصر
0RE: سوالات اولین acm دانشگاه در ترم جدید | ارسال: #4

{# }منظورم تو ترم جدید بود تا جایی که من میدونم این اولین acm ترم جدید بوده شایدم نبوده؟

نقل قول این ارسال در یک پاسخ
ارسال پاسخ 


موضوع های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  عدم حمایت مسئولان از تیم دانشجویی ACM دانشگاه صنعتی شریف sarostad 2 1,635 ۲۵-دي-۱۳۸۹ ۱۱:۳۳ عصر
آخرین ارسال: morteza
  سوالات سومین acm abbasi 2 1,301 ۳۰-آبان-۱۳۸۹ ۰۲:۵۴ عصر
آخرین ارسال: abbasi
  سوالات دومین acm abbasi 0 795 ۱-آبان-۱۳۸۹ ۰۲:۲۲ عصر
آخرین ارسال: abbasi
  راهنمایی اولین مسابقه acm دانشگاه در ترم جدید abbasi 2 1,857 ۲۸-مهر-۱۳۸۹ ۱۱:۲۸ عصر
آخرین ارسال: abbasi
  دومین acm دانشگاه abbasi 0 657 ۲۷-مهر-۱۳۸۹ ۰۸:۱۹ عصر
آخرین ارسال: abbasi

پرش به انجمن:


کاربرانِ درحال بازدید از این موضوع: