# 分类存档: sgu - 第2页

## SGU 101 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=101

## 101. Domino

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The blocks usually are called bones, dominoes, or pieces and sometimes men,stones, or even cards.
The face of each piece is divided, by a line or ridge, into two squares, each of which is marked as would be a pair of dice…

The principle in nearly all modern dominoes games is to match one end of a piece to another that is identically or reciprocally numbered.

ENCYCLOPÆDIA BRITANNICA

–––––– 《大英百科全书》

Given a set of domino pieces where each side is marked with two digits from 0 to 6. Your task is to arrange pieces in a line such way, that they touch through equal marked sides. It is possible to rotate pieces changing left and right side.

### Input

The first line of the input contains a single integer N (1 ≤ N ≤ 100) representing the total number of pieces in the domino set. The following N lines describe pieces. Each piece is represented on a separate line in a form of two digits from 0 to 6 separated by a space.

### Output

Write “No solution” if it is impossible to arrange them described way. If it is possible, write any of way. Pieces must be written in left-to-right order. Every of N lines must contains number of current domino piece and sign “+” or “-“ (first means that you not rotate that piece, and second if you rotate it).

[……]

Continue

## SGU 126 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=126

## 126. Boxes

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

There are two boxes. There are A balls in the first box, and B balls in the second box (0 < A + B < 2147483648). It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box.

### Input

The first line contains two integers A and B, delimited by space.

### Output

First line should contain the number N – the number of moves which are required to move all balls into one box, or -1 if it is impossible.

[……]

Continue

## SGU 175 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=175

## 175.Encoding

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Let phi(W) is the result of encoding for algorithm:
1.If the length of W is 1 then phi(W) is W;
2.Let coded word is W = w1w2…wN and K = N / 2 (rounded down);
3.phi(W) = phi(wNwN-1…wK+1) + phi(wKwK-1…w1).
For example, phi(‘Ok’) = ‘kO’, phi(‘abcd’) = ‘cdab’.
Your task is to find position of letter wq in encoded word phi(W).

1、如果W长度为1，那么phi(W)就是W
2、设W=w1 w2 …… wN 且 K=N/2 （向下取整）
3、phi(W)=phi(wN wN-1 …… wK+1)+phi(wK wK-1 …… w1)

### Input

Given integers N, q (1 <= N <= 10^9; 1<= q <= N), where N is the length of word W.

### Output

Write position of letter wq in encoded word phi(W).

[……]

Continue

## SGU 104 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=104

## 104. Little shop of flowers

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.

Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.

 V A S E S 花瓶 1 2 3 4 5 Bunches 花束 1 (azaleas 杜鹃花) 7 23 -5 -24 16 2 (begonias 秋海棠) 5 21 -4 10 23 3 (carnations 康乃馨) -21 5 -4 -20 20

According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.

To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.

ASSUMPTIONS

• 1 ≤ F ≤ 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
• FV ≤ 100 where V is the number of vases.
• -50 Aij 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.
• 1 ≤ F ≤ 100 表示花的种数。
• FV ≤ 100 表示花瓶数。
• -50 Aij 50 表示i号花束放入j号花瓶产生的美学价值。

### Input

• The first line contains two numbers:F, V.
• The following F lines: Each of these lines contains V integers,so that Aij is given as thej th number on the (j+1) st line of the input file.
• 第一行: F, V.
• 接下来F行每行V个数，其中Aij第(i+1) 行j 列 。

### Output

• The first line will contain the sum of aesthetic values for your arrangement.
• The second line must present the arrangement as a list of F numbers, so that the k’th number on this line identifies the vase in which the bunch k is put.
• 第一行包括一个整数表示最大美学价值。
• 第二行从左到右F个数表示最优方案的每个花束放在哪一个花瓶里，数据用空格隔开。

[……]

Continue

## SGU 184 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=184

## 184.Patties

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Petya is well-known with his famous cabbage patties. Petya’s birthday will come very soon, and he wants to invite as many guests as possible. But the boy wants everybody to try his specialty of the house. That’s why he needs to know the number of the patties he can cook using the stocked ingredients. Petya has P grams of flour, M milliliters of milk and C grams of cabbage. He has plenty of other ingredients. Petya knows that he needs K grams of flour, R milliliters of milk and V grams of cabbage to cook one patty. Please, help Petya calculate the maximum number of patties he can cook.

### Input

The input file contains integer numbers P, M, C, K, R and V, separated by spaces and/or line breaks (1 <= P, M, C, K, R, V <= 10000).

### Output

Output the maximum number of patties Petya can cook.

[……]

Continue

## SGU 172 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=172

## 172.eXam

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

In Russia school pupils must do some exams before leaving school. Among others, they must do two “selective” exams. This means that school provides a list of available subjects; each pupil selects two different subjects from this list and is going to do this exams. According to rules, pupil isn’t allowed to do both exams at the same day, so the school must schedule the exams, i.e. provide some days when pupils will be able to do exams.

One school does not want to warn teachers too much. They want to schedule all the exams into two days in such way that exams on some subjects are on the first day, and exams on all other (and only on them) are on second. You are to write a program, which will determine, if it is possible to schedule exams in this way so that all pupils will be able to do all their selected exams.

### Input

On the first line of input there are two integers N and M (1<=N<=200, 1<=M<=30000) - the number of available subjects and the number of pupils. Then M lines follows; on i-th of them there are two integers - the numbers of exams, which were selected by i-th pupil. Exams are numerated from 1 to N.

### Output

If the solution exists, write on the first line of output only one word “yes”. On the second line write the total number of exams, which must be held on first day, and on the third line – the numbers of subjects of this exams. If there exist several solutions, output any. If no solution exists, write to output only one word “no”.

[……]

Continue

## SGU 127 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=127

## 127. Telephone directory

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

CIA has decided to create a special telephone directory for its agents. The first 2 pages of the directory contain the name of the directory and instructions for agents, telephone number records begin on the third page. Each record takes exactly one line and consists of 2 parts: the phone number and the location of the phone. The phone number is 4 digits long. Phone numbers cannot start with digits 0 and 8. Each page of the telephone directory can contain not more then K lines. Phone numbers should be sorted in increasing order. For the first phone number with a new first digit, the corresponding record should be on a new page of the phone directory. You are to write a program, that calculates the minimal number P pages in the directory. For this purpose, CIA gives you the list of numbers containing N records, but since the information is confidential, without the phones locations.

CIA（中央情报局）决定为它的代理商做一份特殊的电话号码簿。号码簿的前两页是一些使用说明和人名等一些乱七八糟的内容，从第三页开始记录电话号码。每一个电话记录都只有一行，它包括两个部分：电话号码和电话位置。电话号码长度是4，电话号码不能以0或8开头。电话号码簿的每一页不能超过K行。电话号码应该按照字典序排序。第一位的数字不同的电话号码不能出现在同一页。所以当电话号码第一位改变时，应该另起一页。你需要编写一个程序，计算最少需要的页数 P。为此，CIA已经给你了一份有N条电话记录的表格，但由于工作机密，CIA没有告诉你电话的位置，所以你不用考虑电话位置。

### Input

The first line contains a natural number K (0 < K < 255) – the maximum number of lines that one page can contain. The second line contains a natural N (0 < N < 8000) – number of phone numbers supplied. Each of following N lines contains a number consisting of 4 digits – phone numbers in any order, and it is known, that numbers in this list cannot repeat.

### Output

First line should contain a natural number P – the number of pages in the telephone directory.

[……]

Continue

## SGU 180 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=180

## 180. Inversions

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<= i < j <= N and A[i]>A[j].

### Input

The first line of the input contains the number N. The second line contains N numbers A1…AN.

### Output

Write amount of such pairs.

[……]

Continue

## SGU 111 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=111

## 111. Very simple problem

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

You are given natural number X. Find such maximum integer number that it square is not greater than X.

### Input

Input file contains number X (1≤X≤101000).

### Output

Write answer in output file.

[……]

Continue