Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
英大文字からなる長さ の文字列 が与えられます。 が ACE
、BDF
、CEG
、DFA
、EGB
、FAC
、GBD
のいずれかと等しいとき Yes
を、そうでないとき No
を出力してください。
给出一个由大写字母 组成的 长度字符串。 打印 when 等于 ACE
Yes
, CEG
DFA
EGB
FAC
GBD
BDF
当 不等于 No
时打印。
制約
- は英大文字からなる長さ の文字列
是由大写字母组成的长度字符串
入力
入力は以下の形式で標準入力から与えられる。 输入从标准输入给出,格式如下:
出力
が ACE
、BDF
、CEG
、DFA
、EGB
、FAC
、GBD
のいずれかと等しいとき Yes
を、そうでないとき No
を出力せよ。
打印 when 等于 ACE
Yes
, CEG
DFA
EGB
FAC
GBD
BDF
当 不等于 No
时打印。
入力例 1
ABC
出力例 1
No
ABC
のとき、 は ACE
、BDF
、CEG
、DFA
、EGB
、FAC
、GBD
のいずれとも等しくないので No
を出力します。
ABC
, ACE
BDF
CEG
DFA
EGB
FAC
GBD
No
入力例 2
FAC
出力例 2
Yes
入力例 3
XYX
出力例 3
No
Score : points 成绩 : points
Problem Statement 问题陈述
Given a length- string consisting of uppercase English letters, print Yes
if equals one of ACE
, BDF
, CEG
, DFA
, EGB
, FAC
, and GBD
; print No
otherwise.
给定一个由大写英文字母组成的长度字符串 ,如果等于 、 BDF
、 CEG
、 DFA
、 EGB
和 FAC
之一 ACE
,则 打印 Yes
GBD
;否则打印 No
。
Constraints 约束
- is a length- string consisting of uppercase English letters.
是由大写英文字母组成的长度 字符串。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
Print Yes
if equals one of ACE
, BDF
, CEG
, DFA
, EGB
, FAC
, and GBD
; print No
otherwise.
如果等于 、 BDF
、 CEG
、 DFA
、 EGB
和 FAC
之一 ACE
,则打印 GBD
Yes
; 否则打印 No
。
Sample Input 1 示例输入 1
ABC
Sample Output 1 示例输出 1
No
When ABC
, does not equal any of ACE
, BDF
, CEG
, DFA
, EGB
, FAC
, and GBD
, so No
should be printed.
当 ABC
、 不等于 、 BDF
、 、 CEG
DFA
、 EGB
FAC
GBD
和 的任何 、 ACE
、 时, No
应打印 。
Sample Input 2 示例输入 2
FAC
Sample Output 2 示例输出 2
Yes
Sample Input 3 示例输入 3
XYX
Sample Output 3 示例输出 3
No
B - TaK 代码
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
高橋君は 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
高桥先生设计了 尺寸代码 TaK 代码。 TaK 代码满足以下所有条件:
- 縦 マス 横 マスの領域である
垂直质量是水平 质量的面积 - 左上及び右下の縦 マス 横 マスの領域に含まれる計 マスは全て黒である
左上角和右下 角垂直和水平 像元区域中的总 像元都是黑色的。 - 左上及び右下の縦 マス 横 マスの領域に八方位で隣接する計 マスは全て白である
在八个方向上与质量区域相邻的左上角和右下角的垂直 和水平 方块都是白色的。
TaK Code を回転させることはできません。
TaK 代码不能轮换。
縦 マス、横 マスのグリッドがあります。
グリッドの状態は 個の長さ の文字列 で与えられ、上から 行目左から 列目のマスは の 文字目が #
のとき黒、.
のとき白です。
有一个垂直和水平 正方形的网格。 网格的状态以长度字符串 的形式给出 ,当 字符为 时,从顶部 开始的行和从左 到右的列中的单元格为 黑色 .
,当字符为 #
时为白色。
グリッドに完全に含まれる縦 マス横 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
找到完全包含在网格中且符合 TaK 代码条件的垂直 和水平 正方形的所有区域。
制約
- は整数である 是一个整数
- は
.
および#
のみからなる長さ の文字列である
是一个长度仅由.
和#
组成的字符串
入力
入力は以下の形式で標準入力から与えられる。 输入从标准输入给出,格式如下:
出力
上から 行目左から 列目のマスを左上とする縦 マス 横 マスの領域が TaK Code の条件を満たす の組全てを辞書順の昇順で 行に 組ずつ、 をこの順に空白区切りで出力せよ。
从上到下, 所有垂直和水平 单元格的集合,从左 到左上角 的列单元格满足 TaK Code 的条件 ,应按字典顺序升序输出, 一一排,用空格分隔 。
の組の辞書順の昇順とは、 の昇順、 が等しい組は の昇順にすることである。
集合的词典顺序的升序是 的升序 和 的升序。
入力例 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
出力例 1
1 1 1 10 7 7 10 2
TaK Code は以下のものです。#
が黒マス、.
が白マス、?
が白黒どちらでもよいマスを表します。
TaK代码如下: #
表示黑色方块, .
表示白色方块, ?
表示黑白方块。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
入力で与えられたグリッドの上から マス目左から 列目のマスを左上とする縦 マス 横 マスの領域は以下のようになっており、TaK Code の条件を満たします。
从输入中给出的网格顶部开始,从 列单元格的左上角到左上角 的垂直 和水平 方块的面积如下,并且满足 TaK 代码的条件。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
入力例 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
出力例 2
1 1
入力例 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
出力例 3
TaK Code の条件を満たす箇所が つもないこともあります。
在某些情况下,不满足 任何 TaK 代码条件。
Score : points 成绩 : points
Problem Statement 问题陈述
Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:
高桥发明了Tak Code,一种二维码。TaK 代码满足以下所有条件:
- It is a region consisting of nine horizontal rows and nine vertical columns.
它是一个由九个水平行和九个垂直列组成的区域。 - All the cells in the top-left and bottom-right three-by-three regions are black.
左上角和右下角 3×3 区域中的所有 单元格均为黑色。 - All the cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
与左上角或右下角 3×3 区域相邻(水平、垂直或对角线)的所有 单元格均为白色。
It is not allowed to rotate a TaK Code.
不允许旋转 TaK 代码。
You are given a grid with horizontal rows and vertical columns.
The state of the grid is described by strings, , and , each of length . The cell at the -th row from the top and -th column from the left is black if the -th character of is #
, and white if it is .
.
您将获得一个包含 水平行和 垂直列的网格。网格的状态由 字符串 、 和 来描述,每个字符串的长度 都是 。如果 的 第 -th 个字符为 #
,则从顶部开始的 第 -行和 从左侧开始的第 --列的单元格为黑色,如果 的字符为 .
,则为白色。
Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
查找满足 TaK 代码条件的所有 9×9 区域,这些区域完全包含在网格中。
Constraints 约束
- and are integers.
和 是整数。 - is a string of length consisting of
.
and#
.
是由.
和#
组成的长度 字符串。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
For all pairs such that the nine-by-nine region, whose top-left cell is at the -th row from the top and -th columns from the left, satisfies the conditions of a TaK Code, print a line containing , a space, and in this order.
对于所有对 ,使其左上角单元格位于顶部的第 -行和 左起的第 - 列的 9×9 区域满足 TaK 代码的条件,请 按此顺序打印包含 、空格的行。
The pairs must be sorted in lexicographical ascending order; that is, must be in ascending order, and within the same , must be in ascending order.
这些对必须按词典升序排序;也就是说, 必须按升序排列,并且在同一 范围内, 必须按升序排列。
Sample Input 1 示例输入 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
Sample Output 1 示例输出 1
1 1 1 10 7 7 10 2
A TaK Code looks like the following, where #
is a black cell, .
is a white cell, and ?
can be either black or white.
TaK 代码如下所示,其中 #
是黑色单元格, .
是白色单元格, ?
可以是黑色或白色。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
In the grid given by the input, the nine-by-nine region, whose top-left cell is at the -th row from the top and -nd column from the left, satisfies the conditions of a TaK Code, as shown below.
在输入给出的网格中,9×9 区域(其左上角单元格位于顶部的第 -行, 左侧的 -nd 列)满足 TaK 代码的条件,如下所示。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
Sample Input 2 示例输入 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
Sample Output 2 示例输出 2
1 1
Sample Input 3 示例输入 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
Sample Output 3 示例输出 3
There may be no region that satisfies the conditions of TaK Code.
可能没有满足 TaK Code 条件的区域。
C - 看不见的手
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
りんご市場に 人の売り手と 人の買い手がいます。
在苹果市场上,有人卖家, 也有 人买家。
番目の売り手は、 円以上でならりんごを売ってもよいと考えています。
第二个卖家认为苹果卖超过 一日元是可以的。
番目の買い手は、 円以下でならりんごを買ってもよいと考えています。
第二个买家认为以低于 日元的价格购买苹果是可以的。
次の条件を満たすような最小の整数 を求めてください。
求满足以下条件的最小整数:
条件:りんごを 円で売ってもよいと考える売り手の人数が、りんごを 円で買ってもよいと考える買い手の人数以上である。
条件:愿意以 日元出售苹果的卖家数量大于愿意以 日元购买苹果的买家数量。
制約
- 入力は全て整数である 所有输入均为整数
入力
入力は以下の形式で標準入力から与えられる。 输入从标准输入给出,格式如下:
出力
答えを出力せよ。 打印出答案。
入力例 1
3 4 110 90 120 100 80 120 10000
出力例 1
110
りんごを 円で売ってもよいと考える売り手は 番目の 人であり、りんごを 円で買ってもよいと考える買い手は 番目の 人であるため、 は条件を満たします。
满足条件,因为认为可以卖 苹果换日元的卖家是 第二 人,认为可以买 苹果换日元的买家是 第二 人。
未満の整数が条件を満たすことはないため、これが答えです。
这就是答案,因为小于的整数永远不会满足条件。
入力例 2
5 2 100000 100000 100000 100000 100000 100 200
出力例 2
201
入力例 3
3 2 100 100 100 80 120
出力例 3
100
Score : points 成绩 : points
Problem Statement 问题陈述
There are sellers and buyers in an apple market.
苹果市场上有 卖家和 买家。
The -th seller may sell an apple for yen or more (yen is the currency in Japan).
第-个卖家可以以 日元或更高的价格出售一个苹果(日元是日本的货币)。
The -th buyer may buy an apple for yen or less.
第-个买家可以以日元或更低的价格 购买苹果。
Find the minimum integer that satisfies the following condition.
求满足以下条件的最小整数 。
Condition: The number of people who may sell an apple for yen is greater than or equal to the number of people who may buy an apple for yen.
条件:可以以 日元出售苹果的人数大于或等于可以以 日元购买苹果的人数。
Constraints 约束
- All input values are integers.
所有输入值均为整数。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
Print the answer. 打印答案。
Sample Input 1 示例输入 1
3 4 110 90 120 100 80 120 10000
Sample Output 1 示例输出 1
110
Two sellers, the -st and -nd, may sell an apple for yen; two buyers, the -rd and -th, may buy an apple for yen. Thus, satisfies the condition.
两个卖家,- st 和 -nd,可以卖一个苹果换 日元;两个买家,- rd 和 -th,可以用 日元购买一个苹果。因此, 满足条件。
Since an integer less than does not satisfy the condition, this is the answer.
由于小于 的整数不满足条件,这就是答案。
Sample Input 2 示例输入 2
5 2 100000 100000 100000 100000 100000 100 200
Sample Output 2 示例输出 2
201
Sample Input 3 示例输入 3
3 2 100 100 100 80 120
Sample Output 3 示例输出 3
100
D - 计数括号序列
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
空でない文字列 が与えられます。 の各文字は (
, )
, ?
のいずれかです。
提供非空字符串 。 每个字符都是 (
、 、 )
之一。 ?
に含まれる ?
の個数を とすると、?
を (
あるいは )
に置き換えて新しい文字列を作る方法は 通りありますが、このうち新しくできた文字列が括弧列となるような置き換え方の数を で割った余りを求めてください。
如果 包含 的 数 ?
目, ?
(
)
则有一种 方法可以用 或 替换来创建新字符串,但要找到替换次数的余数,其中新创建的字符串是括号序列除 以 。
ただし、括弧列とは以下のいずれかの条件を満たす文字列のことです。
但是,括号列是满足下列条件之一的字符串:
- 空文字列
- ある括弧列 が存在して、
(
, ,)
をこの順に連結した文字列
一个字符串,其中存在括号序列 ,并(
)
按该顺序连接 。 - ある空でない括弧列 が存在して、 をこの順に連結した文字列
一个字符串,其中存在一个非空括号列 ,并 按以下顺序连接
制約
- は長さ 以下の
(
,)
,?
からなる空でない文字列
是由(
、)
和 长度?
组成的非空字符串
入力
入力は以下の形式で標準入力から与えられる。 输入从标准输入给出,格式如下:
出力
答えを出力せよ。 打印出答案。
入力例 1
(???(?
出力例 1
2
を ()()()
あるいは (())()
に置き換えると括弧列となります。
用 ()()()
或 (())()
形成括号列。
他の置き換え方で新しくできた文字列が括弧列となることはないので、 を出力します。
由于由其他替换方法创建的新字符串不会成为括号序列, 因此它输出 。
入力例 2
)))))
出力例 2
0
入力例 3
??????????????(????????(??????)?????????(?(??)
出力例 3
603032273
で割った余りを出力してください。
输出余数除以 。
Score : points 成绩 : points
Problem Statement 问题陈述
You are given a non-empty string consisting of (
, )
, and ?
.
您将获得一个由 (
、 )
和 ?
组成的非空字符串 。
There are ways to obtain a new string by replacing each ?
in with (
and )
, where is the number of occurrences of ?
in . Among them, find the number, modulo , of ways that yield a parenthesis string.
有一些 方法可以通过将每个 ?
in 替换为 (
和 )
来获取新字符串,其中 ?
是 in 的出现次数。其中,找到产生括号字符串的方式的数、模 数。
A string is said to be a parenthesis string if one of the following conditions is satisfied.
如果满足以下条件之一,则称字符串为括号字符串。
- It is an empty string.
它是一个空字符串。 - It is a concatenation of
(
, , and)
, for some parenthesis string .
它是(
、 和)
的串联,用于某些括号字符串 。 - It is a concatenation of and , for some non-empty parenthesis strings and .
它是 和 的串联,用于一些非空括号字符串 和 。
Constraints 约束
- is a non-empty string of length at most consisting of
(
,)
, and?
.
是一个长度最多 由(
、)
和?
组成的非空字符串。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
Print the answer. 打印答案。
Sample Input 1 示例输入 1
(???(?
Sample Output 1 示例输出 1
2
Replacing with ()()()
or (())()
yields a parenthesis string.
替换 为 ()()()
或 (())()
生成括号字符串。
The other replacements do not yield a parenthesis string, so should be printed.
其他替换不产生括号字符串,因此 应打印。
Sample Input 2 示例输入 2
)))))
Sample Output 2 示例输出 2
0
Sample Input 3 示例输入 3
??????????????(????????(??????)?????????(?(??)
Sample Output 3 示例输出 3
603032273
Print the count modulo .
打印计数模 。
E - 长方体的切线
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
次元空間内に 個の直方体があります。
直方体同士は重なっていません。厳密には、相異なるどの つの直方体の共通部分の体積も です。
番目の直方体は、 点 を結ぶ線分を対角線とし、辺は全ていずれかの座標軸に平行です。
各直方体について、他のいくつの直方体と面で接しているか求めてください。
厳密には、各 に対し、 かつ である のうち、 番目の直方体の表面と 番目の直方体の表面の共通部分の面積が正であるものの個数を求めてください。
制約
- 直方体同士は体積が正の共通部分を持たない
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1
4 0 0 0 1 1 1 0 0 1 1 1 2 1 1 1 2 2 2 3 3 3 4 4 4
出力例 1
1 1 0 0
番目の直方体と 番目の直方体は、 点 を結ぶ線分を対角線とする長方形を共有しています。
番目の直方体と 番目の直方体は、点 を共有していますが、面で接してはいません。
入力例 2
3 0 0 10 10 10 20 3 4 1 15 6 10 0 9 6 1 20 10
出力例 2
2 1 1
入力例 3
8 0 0 0 1 1 1 0 0 1 1 1 2 0 1 0 1 2 1 0 1 1 1 2 2 1 0 0 2 1 1 1 0 1 2 1 2 1 1 0 2 2 1 1 1 1 2 2 2
出力例 3
3 3 3 3 3 3 3 3
Score : points 成绩 : points
Problem Statement 问题陈述
There are rectangular cuboids in a three-dimensional space.
在三维空间中有 矩形长方体。
These cuboids do not overlap. Formally, for any two different cuboids among them, their intersection has a volume of .
这些长方体不重叠。从形式上讲,对于它们之间的任意两个不同的长方体,它们的交点的体积为 。
The diagonal of the -th cuboid is a segment that connects two points and , and its edges are all parallel to one of the coordinate axes.
第 -th 个长方体的对角线是连接两点 和 的线段,其边都平行于其中一个坐标轴。
For each cuboid, find the number of other cuboids that share a face with it.
对于每个长方体,找到与其共享面的其他长方体的数量。
Formally, for each , find the number of with and such that the intersection of the surfaces of the -th and -th cuboids has a positive area.
形式上,对于每个 ,求 和 的个数, 使得 第 -th 个和 -th 个长方体的表面的交点具有正面积。
Constraints 约束
- Cuboids do not have an intersection with a positive volume.
长方体没有与正体积的交点。 - All input values are integers.
所有输入值均为整数。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
Print the answer. 打印答案。
Sample Input 1 示例输入 1
4 0 0 0 1 1 1 0 0 1 1 1 2 1 1 1 2 2 2 3 3 3 4 4 4
Sample Output 1 示例输出 1
1 1 0 0
The -st and -nd cuboids share a rectangle whose diagonal is the segment connecting two points and .
-st 和 -nd 长方体共享一个矩形,其对角线是连接两点 和 的线段。
The -st and -rd cuboids share a point , but do not share a surface.
-st 和 -rd 长方体共享一个点 ,但不共享一个曲面。
Sample Input 2 示例输入 2
3 0 0 10 10 10 20 3 4 1 15 6 10 0 9 6 1 20 10
Sample Output 2 示例输出 2
2 1 1
Sample Input 3 示例输入 3
8 0 0 0 1 1 1 0 0 1 1 1 2 0 1 0 1 2 1 0 1 1 1 2 2 1 0 0 2 1 1 1 0 1 2 1 2 1 1 0 2 2 1 1 1 1 2 2 2
Sample Output 3 示例输出 3
3 3 3 3 3 3 3 3
F - 罐头和开瓶器
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
個の品物があります。
これらはそれぞれ、缶切りが不要な缶・缶切りが必要な缶・缶切りのいずれかです。
個目の品物は、整数の組 により次のように表されます。
- ならば、 個目の品物は缶切りが不要な缶で、入手すると満足度 を得る。
- ならば、 個目の品物は缶切りが必要な缶で、入手した上で缶切りを使うと満足度 を得る。
- ならば、 個目の品物は缶切りで、 個までの缶に対して使用できる。
個の品物から 個を選んで入手するとき、得られる満足度の合計としてあり得る最大値を求めてください。
制約
- は のいずれか
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを整数として出力せよ。
入力例 1
8 4 0 6 0 6 1 3 1 5 1 15 2 1 2 10 2 100
出力例 1
27
個目の品物を入手し、 個目の品物である缶切りを 個目の品物に対して使用すると、満足度 を得ます。
満足度が 以上になる品物の入手方法は存在しませんが、上記の例において 個目の品物のかわりに 個目の品物や 個目の品物を選んでも満足度 を得ることができます。
入力例 2
5 5 1 5 1 5 1 5 1 5 1 5
出力例 2
0
入力例 3
12 6 2 2 0 1 0 9 1 3 1 5 1 3 0 4 2 1 1 8 2 1 0 1 0 4
出力例 3
30
Score : points 成绩 : points
Problem Statement 问题陈述
There are items.
有 项目。
Each of these is one of a pull-tab can, a regular can, or a can opener.
这些都是拉片罐、普通罐或开罐器之一。
The -th item is described by an integer pair as follows:
第 -th 项由整数对 描述,如下所示:
- If , the -th item is a pull-tab can; if you obtain it, you get a happiness of .
如果 ,则第 -th 项是拉片罐;如果你得到它,你就会得到一种幸福 。 - If , the -th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of .
如果 , 则第 -th 项是常规罐;如果你得到它并使用开罐器来对付它,你会得到一种幸福 。 - If , the -th item is a can opener; it can be used against at most cans.
如果 ,则第 -th 项是开罐器;它可以用于大多数 罐头。
Find the maximum total happiness that you get by obtaining items out of .
找到你通过获得 物品获得的最大总幸福 感。
Constraints 约束
- is , , or .
是 、 或 。 - All input values are integers.
所有输入值均为整数。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
Print the answer as an integer.
将答案打印为整数。
Sample Input 1 示例输入 1
8 4 0 6 0 6 1 3 1 5 1 15 2 1 2 10 2 100
Sample Output 1 示例输出 1
27
If you obtain the -st, -nd, -th, and -th items, and use the -th item (a can opener) against the -th item, you will get a happiness of .
如果你获得 -st、 -nd、 -th 和 -th 项,并使用 第 -th 项(开罐器)来对抗 第 -th 项,你将获得 的 幸福。
There are no ways to obtain items to get a happiness of or greater, but you can still get a happiness of by obtaining the -th or -th items instead of the -th in the combination above.
没有办法获得获得幸福 或更大的幸福的物品,但你仍然 可以通过获得 -th 或 -th 物品而不是上面组合中的 -th 来获得幸福。
Sample Input 2 示例输入 2
5 5 1 5 1 5 1 5 1 5 1 5
Sample Output 2 示例输出 2
0
Sample Input 3 示例输入 3
12 6 2 2 0 1 0 9 1 3 1 5 1 3 0 4 2 1 1 8 2 1 0 1 0 4
Sample Output 3 示例输出 3
30
G - 避免直线
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
頂点の木が与えられます。頂点には から までの番号がついており、 番目の辺は頂点 と頂点 を結んでいます。
以下の条件を満たす整数の組 の個数を求めてください。
- 与えられた木には頂点 をすべて含む単純パスは存在しない
制約
- 与えられるグラフは木
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1
5 1 2 2 3 2 4 1 5
出力例 1
2
の つが条件を満たします。
入力例 2
6 1 2 2 3 3 4 4 5 5 6
出力例 2
0
入力例 3
12 1 6 3 4 10 4 5 9 3 1 2 3 7 2 2 12 1 5 6 8 4 11
出力例 3
91
Score : points 成绩 : points
Problem Statement 问题陈述
You are given a tree with vertices. The vertices are numbered from through , and the -th edge connects vertex and vertex .
你会得到一棵带有 顶点的树。顶点从 到 编号 , 第 -th 条边连接顶点 和顶点 。
Find the number of tuples of integers such that:
求整数元组的数目, 使得:
- ; and ;和
- the given tree does not contain a simple path that contains all of vertices , , and .
给定的树不包含包含所有顶点 、 和 的简单路径。
Constraints 约束
- The given graph is a tree.
给定的图形是一棵树。 - All input values are integers.
所有输入值均为整数。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
Print the answer. 打印答案。
Sample Input 1 示例输入 1
5 1 2 2 3 2 4 1 5
Sample Output 1 示例输出 1
2
Two tuples satisfy the conditions: .
两个元组满足以下条件: 。
Sample Input 2 示例输入 2
6 1 2 2 3 3 4 4 5 5 6
Sample Output 2 示例输出 2
0
Sample Input 3 示例输入 3
12 1 6 3 4 10 4 5 9 3 1 2 3 7 2 2 12 1 5 6 8 4 11
Sample Output 3 示例输出 3
91
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制:2 秒 / 内存限制:1024 MB
配点 : 点
問題文
高橋君は人 の 人のあだ名を決めることになりました。
人 はあだ名を にしてほしいと思っています。複数人に同じあだ名をつけるのを避けるため、高橋君は次の手順で 人のあだ名を決めることにしました。
- の順に、以下の操作により人 のあだ名を決める
- 変数 を とする。
- 「 を 回繰り返した文字列」がすでに誰かのあだ名である間、 を 増やすことを繰り返す。
- 「 を 回繰り返した文字列」を人 のあだ名とする。
人のあだ名を決めた後の を求めてください。
制約
- は英小文字のみからなる、長さ 以上の文字列
- の長さの総和は 以下
入力
入力は以下の形式で標準入力から与えられる。
出力
問題文中の操作により 人のあだ名を決めた後の をこの順に空白区切りで出力せよ。
入力例 1
3 snuke snuke rng
出力例 1
1 2 1
- まず人 のあだ名を決めます。
- とします。
- を 回繰り返した文字列
snuke
は誰のあだ名でもないので、人 のあだ名はsnuke
になります。
- 次に人 のあだ名を決めます。
- とします。
- を 回繰り返した文字列
snuke
はすでに人 のあだ名なので、 を 増やして とします。 - を 回繰り返した文字列
snukesnuke
は誰のあだ名でもないので、人 のあだ名はsnukesnuke
になります。
- 最後に人 のあだ名を決めます。
- とします。
- を 回繰り返した文字列
rng
は誰のあだ名でもないので、人 のあだ名はrng
になります。
以上により、 はそれぞれ となります。
入力例 2
4 aa a a aaa
出力例 2
1 1 3 2
- 人 のあだ名は
aa
になります。 - 人 のあだ名は
a
になります。 - 人 のあだ名は、
a
,aa
がすでに他の人のあだ名なので、aaa
になります。 - 人 のあだ名は、
aaa
がすでに他の人のあだ名なので、aaaaaa
になります。
入力例 3
5 x x x x x
出力例 3
1 2 3 4 5
Score : points 成绩 : points
Problem Statement 问题陈述
Takahashi is going to decide nicknames of people, person .
高桥要决定 人的昵称,人 .
Person wants a nickname . To avoid giving the same nickname to multiple people, he is going to decide their nicknames as follows:
人 想要一个昵称 。为了避免给多个人起同一个昵称,他将决定他们的昵称如下:
- For each in order, decide person 's nickname as follows:
按顺序确定每个人 的昵称,如下所示:- Initialize a variable with .
使用 初始化变量。 - Repeatedly increment by one while the -time repetition of is someone's nickname.
重复 递增 1,而 -time 重复是 某人的昵称。 - Let person 's nickname be the -time repetition of .
设 person's 昵称是 的 -time 重复。
- Initialize a variable with .
Find , and after deciding nicknames of the people.
找到 ,并在 决定 人们的昵称之后。
Constraints 约束
- is a string of length at least consisting of lowercase English letters.
是长度至少 由小写英文字母组成的字符串。 - The sum of lengths of is at most .
的 长度之和最多 为 。
Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:
Output 输出
Print , and resulting from deciding the nicknames of the people by the procedure in the problem statement.
打印 ,并 根据问题陈述中的程序确定 人们的昵称。
Sample Input 1 示例输入 1
3 snuke snuke rng
Sample Output 1 示例输出 1
1 2 1
- First, he decides person 's nickname.
首先,他决定一个人 的昵称。- Let . 让 .
- The -time repetition of is
snuke
, which is nobody's nickname, so person 's nickname is set tosnuke
.
的 -time 重复是snuke
,这是 nobody's 昵称,所以 person 的昵称设置为snuke
。
- Next, he decides person 's nickname.
接下来,他决定一个人 的昵称。- Let . 让 .
- The -time repetition of is
snuke
, which is already a nickname of person , so increment by one to make it .
的 -time 重复 是snuke
,这已经是人的 昵称了,所以 递增 1 即可 。 - The -time repetition of is
snukesnuke
, which is nobody's nickname, so person 's nickname is set tosnukesnuke
.
的 -time 重复是snukesnuke
,这是 nobody's 昵称,所以 person 的昵称设置为snukesnuke
。
- Finally, he decides person 's nickname.
最后,他决定一个人 的昵称。- Let . 让 .
- The -time repetition of is
rng
, which is nobody's nickname, so person 's nickname is set torng
.
的 -time 重复是rng
,这是 nobody's 昵称,所以 person 的昵称设置为rng
。
Thus, , , and result in , , and , respectively.
因此, 、 和 分别产生 、 和 。
Sample Input 2 示例输入 2
4 aa a a aaa
Sample Output 2 示例输出 2
1 1 3 2
- Person 's nickname is set to
aa
.
人员 的昵称设置为aa
。 - Person 's nickname is set to
a
.
人员 的昵称设置为a
。 - Person 's nickname is set to
aaa
, becausea
andaa
are already nicknames of someone else.
人的 昵称设置为aaa
,因为a
和aa
已经是其他人的昵称。 - Person 's nickname is set to
aaaaaa
, becauseaaa
is already a nickname of someone else.
Person 的昵称设置为aaaaaa
,因为aaa
已经是其他人的昵称。
Sample Input 3 示例输入 3
5 x x x x x
Sample Output 3 示例输出 3
1 2 3 4 5