# 月度存档: 9月 2010

## SGU 118 解题报告

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

## 118. Digital Root

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

Let f(n) be a sum of digits for positive integer n. If f(n) is one-digit number then it is a digital root for n and otherwise digital root of n is equal to digital root of f(n). For example, digital root of 987 is 6. Your task is to find digital root for expression A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1.

### Input

Input file consists of few test cases. There is K (1 <=K <= 5) in the first line of input. Each test case is a line. Positive integer number N is written on the first place of test case (N<=1000). After it there are N positive integer numbers (sequence A). Each of this numbers is non-negative and not more than 109.

### Output

Write one line for every test case. On each line write digital root for given expression.

[……]

Continue

## SGU 133 解题报告

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

## 133. Border

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

Along the border between states A and B there are N defence outposts. For every outpost k, the interval [Ak,Bk] which is guarded by it is known. Because of financial reasons, the president of country A decided that some of the outposts should be abandoned.In fact, all the redundant outposts will be abandoned. An outpost i is redundant if there exists some outpost j such that Aj < Ai and Bi < Bj. Your task is to find the number of redundant outposts.

### Input

The first line of the input will contain the integer number N (1 <=N <= 16 000). N lines will follow, each of them containing 2 integers:Ak and Bk (0 <= Ak < Bk <= 2 000 000 000), separated by blanks. All the numbers Ak will be different. All the numbers Bk will be different.

### Output

You should print the number of redundant outposts.

[……]

Continue

## SGU 130 解题报告

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

## 130. Circle

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

On a circle border there are 2k different points A1, A2, …, A2k, located contiguously. These points connect k chords so that each of points A1, A2, …, A2k is the end point of one chord. Chords divide the circle into parts. You have to find N – the number of different ways to connect the points so that the circle is broken into minimal possible amount of parts P.

### Input

The first line contains the integer k (1 <= k <= 30).

### Output

The first line should contain two numbers N and P delimited by space.

[……]

Continue

## SGU 108 解题报告

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

## 108. Self-numbers 2

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

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), …. For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, … The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. Let the a[i] will be i-th self-number. There are thirteen self-numbers a[1]..a[13] less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97. (the first self-number is a[1]=1, the second is a[2] = 3, :, the thirteen is a[13]=97);

1949年,印度数学家D.R. Kaprekar 发现了一类数，称为自我数.对于任何一个正整数 n ,定义 d(n) 的值为 n 与 n的每一位数字之和.(d 叫做digitadition, 这个单词是Kaprekar创造的.) 例如,d(75) = 75 + 7 + 5 = 87. 给你任意正整数 n 作为起点，您可以构建无限增加的整数 n 序列,n, d(n), d(d(n)), d(d(d(n))),…. 例如,起点是33,则下一个数是 33 + 3 + 3 = 39,再下一个数是 39 + 3 + 9 = 51,然后是 51 + 5 + 1 = 57,这样由 33 生成的数列是 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141,… 这样我们称正整数 n 是 d(n)生成器.在刚才的序列中, 33 是 39 的生成器, 39 是 51 的生成器, 51 是 57 的生成器,等等.有些数有不止一个生成器,例如, 101 有两个生成器, 91 和 100.如果一个数没有生成器我们就称它为自我数.用 a[i] 表示第 i 个自我数.小于 100 有 13 个自我数:1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97.(第一个自我数是 a[1] = 1,第二个是 a[2] = 3,:,第十三个是 a[13] = 97);

### Input

Input contains integer numbers N, K, s1…sk. (1<=N<=107, 1<=K<=5000) delimited by spaces and line breaks.

### Output

At first line you must output one number – the quantity of self-numbers in interval [1..N]. Second line must contain K numbers – a[s1]..a[sk], delimited by spaces. It`s a gaurantee, that all self-numbers a[s1]..a[sk] are in interval [1..N]. (for example if N = 100, sk can be 1..13 and cannot be 14, because 14-th self-number a[14] = 108, 108 > 100)

[……]

Continue

## SGU 117 解题报告

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

## 117. Counting

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

Find amount of numbers for given sequence of integer numbers such that after raising them to the M-th power they will be divided by K.

### Input

Input consists of two lines. There are three integer numbers N, M, K (0

[……]

Continue

## 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