没有合适的资源?快使用搜索试试~ 我知道了~
首页Codeforces 题库 101-200
Codeforces 题库 101-200
4星 · 超过85%的资源 需积分: 0 26 下载量 186 浏览量
更新于2023-03-16
评论 1
收藏 4.52MB PDF 举报
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
资源详情
资源评论
资源推荐
CODEFORCES PROBLEMSET
#101-#200
2013-4-11
Sorted by Jerry Xu in Shanghai
Codeforces (c) Copyright 2010-2013 Mike Mirzayanov
Codeforces is a Russian website dedicated to competitive programming. It was created and
is currently maintained by group of sportsmen from Saratov State University led by Mikhail
Mirzayanov.
Codeforces provides to all users following main services:
Participation in the short (2-hours) contests, so-called "Codeforces Rounds", held about
once a week;
Ability to solve problems from previous contests for training purposes;
"Polygon" for creating and testing problems;
Kind of social-networking by using of internal public blogs.
Contestants are rated by system similar to ELO. There are usually no prizes for winners,
though 100 winners of 100-th Codeforces Round received a T-Shirt. Some bigger contests
(mostly country internal) are hosted on Codeforces base, among them "Yandex Algorithm
2011", provided by Yandex - one of biggest Russian IT-companies.
Website: Codeforces.com
101A. Homework
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Once when Gerald studied in the first year at school, his teacher gave the class the
following homework. She offered the students a string consisting of n small Latin
letters; the task was to learn the way the letters that the string contains are written.
However, as Gerald is too lazy, he has no desire whatsoever to learn those letters.
That's why he decided to lose some part of the string (not necessarily a connected
part). The lost part can consist of any number of segments of any length, at any
distance from each other. However, Gerald knows that if he loses more than k
characters, it will be very suspicious.
Find the least number of distinct characters that can remain in the string after no
more than k characters are deleted. You also have to find any possible way to
delete the characters.
Input
The first input data line contains a string whose length is equal to n (1 ≤ n ≤ 10
5
).
The string consists of lowercase Latin letters. The second line contains the number
k (0 ≤ k ≤ 10
5
).
Output
Print on the first line the only number m — the least possible number of different
characters that could remain in the given string after it loses no more than k
characters.
Print on the second line the string that Gerald can get after some characters are
lost. The string should have exactly m distinct characters. The final string should be
the subsequence of the initial string. If Gerald can get several different strings with
exactly m distinct characters, print any of them.
Sample test(s)
Input
aaaaa
4
Output
1
aaaaa
Input
abacaba
4
Output
1
aaaa
Input
abcdefgh
10
Output
0
Note
In the first sample the string consists of five identical letters but you are only allowed
to delete 4 of them so that there was at least one letter left. Thus, the right answer is
1 and any string consisting of characters "a" from 1 to 5 in length.
In the second sample you are allowed to delete 4 characters. You cannot delete all
the characters, because the string has length equal to 7. However, you can delete
all characters apart from "a" (as they are no more than four), which will result in the
"aaaa" string.
In the third sample you are given a line whose length is equal to 8, and k = 10, so
that the whole line can be deleted. The correct answer is 0 and an empty string.
101B. Buses
time limit per test
2 seconds
memory limit per test
265 megabytes
input
standard input
output
standard output
Little boy Gerald studies at school which is quite far from his house. That's why he
has to go there by bus every day. The way from home to school is represented by a
segment of a straight line; the segment contains exactly n + 1 bus stops. All of them
are numbered with integers from 0 to n in the order in which they follow from
Gerald's home. The bus stop by Gerald's home has number 0 and the bus stop by
the school has number n.
There are m buses running between the house and the school: the i-th bus goes
from stop s
i
to t
i
(s
i
< t
i
), visiting all the intermediate stops in the order in which they
follow on the segment. Besides, Gerald's no idiot and he wouldn't get off the bus
until it is still possible to ride on it closer to the school (obviously, getting off would
be completely pointless). In other words, Gerald can get on the i-th bus on any stop
numbered from s
i
to t
i
- 1 inclusive, but he can get off the i-th bus only on the bus
stop t
i
.
Gerald can't walk between the bus stops and he also can't move in the direction
from the school to the house.
Gerald wants to know how many ways he has to get from home to school. Tell him
this number. Two ways are considered different if Gerald crosses some segment
between the stops on different buses. As the number of ways can be too much, find
the remainder of a division of this number by 1000000007 (10
9
+ 7).
Input
The first line contains two space-separated integers: n and m
(1 ≤ n ≤ 10
9
, 0 ≤ m ≤ 10
5
). Then follow m lines each containing two integers s
i
, t
i
.
They are the numbers of starting stops and end stops of the buses (0 ≤ s
i
< t
i
≤ n).
Output
Print the only number — the number of ways to get to the school modulo
1000000007 (10
9
+ 7).
Sample test(s)
Input
2 2
0 1
1 2
Output
1
Input
3 2
0 1
1 2
Output
0
Input
5 5
0 1
0 2
0 3
0 4
0 5
Output
16
Note
The first test has the only variant to get to school: first on bus number one to the bus
stop number one; then on bus number two to the bus stop number two.
In the second test no bus goes to the third bus stop, where the school is positioned.
Thus, the correct answer is 0.
In the third test Gerald can either get or not on any of the first four buses to get
closer to the school. Thus, the correct answer is 2
4
= 16.
101C. Vectors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
剩余814页未读,继续阅读
fei960922
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 数据结构1800题含完整答案详解.doc
- 医疗企业薪酬系统设计与管理方案.pptx
- 界面与表面技术界面理论与表面技术要点PPT学习教案.pptx
- Java集合排序及java集合类详解(Collection、List、Map、Set)讲解.pdf
- 网页浏览器的开发 (2).pdf
- 路由器原理与设计讲稿6-交换网络.pptx
- 火电厂锅炉过热汽温控制系统设计.doc
- 企业识别CIS系统手册[收集].pdf
- 物业管理基础知识.pptx
- 第4章财务预测.pptx
- 《集成电路工艺设计及器件特性分析》——实验教学计算机仿真系.pptx
- 局域网内共享文件提示没有访问权限的问题借鉴.pdf
- 第5章网络营销策略.pptx
- 固井质量测井原理PPT教案.pptx
- 毕业实习总结6篇.doc
- UGNX建模基础篇草图模块PPT学习教案.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1