# Category Archives: 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.

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).

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

......

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

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

`4 4`

`24`

## 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` `ThisIsEaSYPrOblem ` `ThiSISeasyPROBLEm `

......

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

......

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

......

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

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