月度存档: 九月 2010 - 第2页

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.

在第一行有两个整数N和M,(1<=N<=200,1<=m<=30000)N代表可选择的考试的科目数,M代表学生的人数。下面的M行中分别代表一个学生选择的考试项目数。

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

如果安排方法存在,在第一行写”yes”,在第二行输出在第一天必须安排的考试项目的数量,在第三行输出考试项目的项目数。如果存在多个安排方法,输出其中一个就可以了。如果安排方法不存在,输出”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.

第一行是自然数 K (0 < K < 255) 每页最多有多少行。第二行是自然数 N (0 < N < 8000) 提供的电话记录总数。 接下来的N行每行包括 4 个数字的电话号码。它们是随机顺序给出的,保证不会有重复的情况。

Output

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

输出P – 最少需要多少页。

[……]

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