分类存档: sgu

SGU 276 解题报告

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

276. Andrew’s Troubles

time limit per test: 1 sec.
memory limit per test: 65536 KB

Famous Berland ACM-ICPC team Anisovka consists of three programmers: Andrew, Michael and Ilya. A long time ago, during the first few months the team was founded, Andrew was very often late to the trainings and contests. To stimulate Andrew to be more punctual, Ilya and Andrew decided to introduce a new rule for team participants. If somebody is late (i.e. comes at least one second after appointed time) he owes a cup of tea to other team members. If he is late for 5 minutes, he owes two cups of tea. If he is late for 15 minutes, he owes three cups of tea. And if he is late for 30 minutes or more, he owes 4 cups of tea.

著名的 Berland ACM-ICPC 团队 Anisovka 包含三名成员:Andrew, Michael and Ilya.在团队刚建立的几个月里,Andrew 经常在比赛和训练中迟到.为了激励 Andrew 更加准时, Ilya 和 Andrew 决定在团队训练中引入一条新规则.如果有人迟到(即至少比约定的时间晚一秒) 则他欠团队其他成员一杯茶.如果他迟到5 分钟,他将欠 2 杯茶.如果他迟到 15 分钟,他将欠 3 杯茶.如果迟到 15 分钟惠更多,他将欠 4 杯茶.

The training starts at the time S (counted in seconds, from some predefined moment of time) and Andrew comes at the time P (also in seconds, counted from the same moment of time).

训练开始的时间是 S (以秒作为计时单位) Andrew到达的时间是 P (同样以秒作为计时单位).

Your task is to find how many cups of tea Andrew owes.

你的任务是计算出 Andrew 一共欠多少杯茶.

[……]

Continue

SGU 222 解题报告

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

222. Little Rooks

time limit per test: 1 sec.
memory limit per test: 65536 KB

Inspired by a “Little Bishops” problem, Petya now wants to solve problem for rooks.

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move horizontally and vertically from its current position and two rooks attack each other if one is on the path of the other.

Given two numbers n and k, your job is to determine the number of ways one can put k rooks on an n × n chessboard so that no two of them are in attacking positions.

受小主教问题的启发, Petya现在决定解决一个关于车的问题.

车是国际象棋中的一种棋子,只能在水平和垂直方向移动,如果在一个移动方向上有两个车,他们就会互相攻击.

给定两个数n和k,你的工作是要计算出在n× n的棋盘中放置K个车,使他们不会相互攻击的方案数量.

Input

The input file contains two integers n (1 ≤ n ≤ 10) and k (0 ≤ k ≤ n2).

Output

Print a line containing the total number of ways one can put the given number of rooks on a chessboard of the given size so that no two of them are in attacking positions.

Sample Input

4 4

Sample Output

24

[……]

Continue

SGU 304 解题报告

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

302. BHTML 1.0

Time limit per test: 2 second(s)
Memory limit: 65536 kilobytes

The hypertext markup language BHTML 1.0 has only two paired tags. They are <UP> </UP> and <DOWN> </DOWN>. The <UP> </UP> tag capitalizes all letters inside its body (between an open tag and a close one), and <DOWN> </DOWN> makes all inside the body letters lowercase. You are given the text consisting of latin letters and tags. Your task is to write the text right as it will be shown in the Bernet Explorer browser window. Tags in the text are arranged correctly, i.e. they form correct bracket sequence. If a letter lays inside several tags, its case is defined by the most inner tag.

Input

The input contains the string S with the text. The length of the string is a natural number not exceeding 1000. Tags are always written in uppercase.

Output

Write to the output text after the processing.

Example(s)

sample input sample output
Thi<UP>sIs<DOWN>EaSY</DOWN>Pr<UP>O</UP>ble</UP>m ThiSISeasyPROBLEm

[……]

Continue

SGU 114 解题报告

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

114. Telecasting station

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

Every city in Berland is situated on Ox axis. The government of the country decided to build new telecasting station. After many experiments Berland scientists came to a conclusion that in any city citizens displeasure is equal to product of citizens amount in it by distance between city and TV-station. Find such point on Ox axis for station so that sum of displeasures of all cities is minimal.

Input

Input begins from line with integer positive number N (0<N<15000) – amount of cities in Berland. Following N pairs (X, P) describes cities (0<X, P<50000), where X is a coordinate of city and P is an amount of citizens. All numbers separated by whitespace(s).

Output

Write the best position for TV-station with accuracy 10-5.

Sample Input

4
1 3
2 1
5 2
6 2

Sample Output

3.00000

[……]

Continue

SGU 144 解题报告

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

144. Meeting

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

Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between X o’clock and Y o’clock. Because they never get anywhere on time (they were late even on the day of the regional contest), they did not set an exact time when they will meet. However, they decided that the one who gets first at the meeting point will not wait more than Z minutes for the other one (they calculated that, if the other one will not come within Z minutes from the arrival of the first of them, then it is very probable that he will not show up at all).
Knowing that, in the end, both of them will show up at some time between X o’clock and Y o’clock (not necessarily after an integer number of minutes), compute which is the probability that they will actually meet.

Input

The input will contain 2 integer numbers X and Y (0<=X<Y<=24) and one real number Z ( 0 < Z <= 60*(Y-X) ).

Output

You should output the required probability with 7 decimal digits (rounded according to the 8th decimal digit).

[……]

Continue

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.

设 f(n) 表示十进制正整数 n 的各位数字之和。如果 f(n) 是一个1位数那么他就是 n 的数根。否则的话 f(n) 的数根就是 n 的数根。举例说明:987的数根是 6(9+8+7=24 2+4=6)。你的任务是算出这样的数的数根: 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.

输入包含K个测试点.在第一行会给出 K (1 <= K <= 5).每个测试点一行.首先是一个正整数N (N <= 1000). 接着N个非负整数 (序列 A). 均不超过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.

在 A 和 B 的边界出有 N 个前哨站.对于每一个前哨站 k,他的管辖范围 [Ak,Bk] 是已知的.由于经济原因,A 国总统决定减少一些前哨站.多余的前哨站都会被抛弃.我们定义 i 号前哨站是多余的如果存在另一个前哨战 j 满足 Aj < Ai 且 Bi < Bj.你的任务是计算多余的前哨站个数.

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.

第一行是整数N (1 <=N <= 16 000).接下来N行每行包含2个整数: Ak 和 Bk (0 <= Ak < Bk <= 2 000 000 000),空格隔开.所有的 Ak 都是不同的,所有的 Bk 也是不同的.

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.

在圆上有 2k 个不重合的点 A1, A2, …, A2k, 通过这些点可以作k条弦,使得每个点都恰好属于一条弦。这样我们就把这个圆分成了很多区域,你要求出 N 个方案数,使这些弦将圆划分的区域数量最小。

Input

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

输入 K.

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.

输入数据包含整数 N, K, s1…sk. (1<=N<=107, 1<=K<=5000) 用空格或回车隔开。

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)

第一行输出 [1..N]范围内自我数的数量.第二行包含 K 个数 – a[s1]..a[sk], 用空格隔开.必须满足所有自我数 a[s1]..a[sk] 是在[1..N]范围内.(例如,如果 N =100,sk可以是 1..13 但不能是 14,因为 第 14 个自我数 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.

给出一系列数,统计出其中 M 次幂能被 K 整除的个数.

Input

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

输入包含两行.第一行有三个整数 N, M, K (0

Output

Write answer for given task.

输出结果.

[……]

Continue