Monthly Archives: February 2011

SGU 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 一共欠多少杯茶.


Read more »

SGU 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个车,使他们不会相互攻击的方案数量.


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


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


Read more »

SGU 304 解题报告

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.


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.


Write to the output text after the processing.


sample input
sample output


Read more »

ZJU 1109 解题报告

Language of FatMouse

Time Limit: 10 Seconds Memory Limit: 32768 KB

We all know that FatMouse doesn't speak English. But now he has to be prepared since our nation will join WTO soon. Thanks to Turing we have computers to help him.

Input Specification

Input consists of up to 100,005 dictionary entries, followed by a blank line, followed by a message of up to 100,005 words. Each dictionary entry is a line containing an English word, followed by a space and a FatMouse word. No FatMouse word appears more than once in the dictionary. The message is a sequence of words in the language of FatMouse, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.

Output Specification

Output is the message translated to English, one word per line. FatMouse words not in the dictionary should be translated as "eh".

Sample Input

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

Output for Sample Input



Read more »