这是用户在 2024-5-28 9:58 为 https://atcoder.jp/contests/abc312/tasks_print 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？
A - Chord A - 和弦

Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB

配点 : 100100 点

問題文

英大文字からなる長さ 33 の文字列 SS が与えられます。SS が ACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれかと等しいとき Yes を、そうでないとき No を出力してください。
给出一个由大写字母 SS 组成的 33 长度字符串。 SS 打印 when 等于 ACE Yes ， CEG DFA EGB FAC GBD BDF 当 不等于 No 时打印。

制約

  • SS は英大文字からなる長さ 33 の文字列
    SS 是由大写字母组成的长度字符串 33

入力

入力は以下の形式で標準入力から与えられる。 输入从标准输入给出，格式如下： 

SS

出力

SS が ACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれかと等しいとき Yes を、そうでないとき No を出力せよ。
SS 打印 when 等于 ACE Yes ， CEG DFA EGB FAC GBD BDF 当 不等于 No 时打印。

入力例 1

ABC

出力例 1

No

S=S = ABC のとき、SS は ACE、BDF、CEG、DFA、EGB、FAC、GBD のいずれとも等しくないので No を出力します。
S=S = ABC ， SS ACE BDF CEG DFA EGB FAC GBD No

入力例 2

FAC

出力例 2

Yes

入力例 3

XYX

出力例 3

No

Score : 100100 points 成绩 ： 100100 points

Problem Statement 问题陈述

Given a length-33 string SS consisting of uppercase English letters, print Yes if SS equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.
给定一个由大写英文字母组成的长度字符串 33 SS ，如果等于 、 BDF 、 CEG 、 DFA 、 EGB 和 FAC 之一 ACE ，则 SS 打印 Yes GBD ;否则打印 No 。

Constraints 约束

  • SS is a length-33 string consisting of uppercase English letters.
    SS 是由大写英文字母组成的长度 33 字符串。

Input 输入

The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：

SS

Output 输出

Print Yes if SS equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.
如果等于 、 BDF 、 CEG 、 DFA 、 EGB 和 FAC 之一 ACE ，则打印 GBD Yes ; SS 否则打印 No 。

Sample Input 1 示例输入 1

ABC

Sample Output 1 示例输出 1

No

When S=S = ABC, SS does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.
当 S=S = ABC 、 SS 不等于 、 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 Code
B - TaK 代码

Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB

配点 : 200200 点

問題文

高橋君は 22 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
高桥先生设计了 22 尺寸代码 TaK 代码。 TaK 代码满足以下所有条件：

  • 縦 99 マス 横 99 マスの領域である
    99 垂直质量是水平 99 质量的面积
  • 左上及び右下の縦 33 マス 横 33 マスの領域に含まれる計 1818 マスは全て黒である
    左上角和右下 33 角垂直和水平 33 像元区域中的总 1818 像元都是黑色的。
  • 左上及び右下の縦 33 マス 横 33 マスの領域に八方位で隣接する計 1414 マスは全て白である
    在八个方向上与质量区域相邻的左上角和右下角的垂直 33 1414 和水平 33 方块都是白色的。

TaK Code を回転させることはできません。
TaK 代码不能轮换。

縦 NN マス、横 MM マスのグリッドがあります。 グリッドの状態は NN 個の長さ MM の文字列 S1,…,SNS_1,\ldots,S_N で与えられ、上から ii 行目左から jj 列目のマスは SiS_i の jj 文字目が # のとき黒、. のとき白です。
NN 有一个垂直和水平 MM 正方形的网格。 网格的状态以长度字符串 NN 的形式给出 S1,…,SNS_1,\ldots,S_N ，当 jj 字符为 时，从顶部 ii 开始的行和从左 jj 到右的列中的单元格为 SiS_i 黑色 . ，当字符为 # 时为白色。 MM

グリッドに完全に含まれる縦 99 マス横 99 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
找到完全包含在网格中且符合 TaK 代码条件的垂直 99 和水平 99 正方形的所有区域。

制約

  • 9≤N,M≤1009 \leq N,M \leq 100
  • N,MN,M は整数である  N,MN,M 是一个整数
  • SiS_i は . および # のみからなる長さ MM の文字列である
    SiS_i 是一个长度仅由 . 和 # 组成的字符串 MM

入力

入力は以下の形式で標準入力から与えられる。 输入从标准输入给出，格式如下： 

NN MM
S1S_1
⋮\vdots
SNS_N

出力

上から ii 行目左から jj 列目のマスを左上とする縦 99 マス 横 99 マスの領域が TaK Code の条件を満たす (i,j)(i,j) の組全てを辞書順の昇順で 11 行に 11 組ずつ、i,ji,j をこの順に空白区切りで出力せよ。
从上到下， ii 所有垂直和水平 99 单元格的集合，从左 jj 到左上角 99 的列单元格满足 TaK Code 的条件 (i,j)(i,j) ，应按字典顺序升序输出， 11 11 一一排，用空格分隔 i,ji,j 。
(i,j)(i,j) の組の辞書順の昇順とは、ii の昇順、ii が等しい組は jj の昇順にすることである。
(i,j)(i,j) 集合的词典顺序的升序是 的升序 ii 和 ii jj 的升序。

入力例 1

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

出力例 1

1 1
1 10
7 7
10 2

TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。
TaK代码如下： # 表示黑色方块， . 表示白色方块， ? 表示黑白方块。

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

入力で与えられたグリッドの上から 1010 マス目左から 22 列目のマスを左上とする縦 99 マス 横 99 マスの領域は以下のようになっており、TaK Code の条件を満たします。
从输入中给出的网格顶部开始，从 22 列单元格的左上角到左上角 1010 的垂直 99 和水平 99 方块的面积如下，并且满足 TaK 代码的条件。

###......
###......
###......
.........
..##.....
..##.....
......###
......###
......###

入力例 2

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

出力例 2

1 1

入力例 3

18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

出力例 3



TaK Code の条件を満たす箇所が 11 つもないこともあります。
在某些情况下，不满足 11 任何 TaK 代码条件。






Score : 200200 points 成绩 ： 200200 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 1818 cells in the top-left and bottom-right three-by-three regions are black.
    左上角和右下角 3×3 区域中的所有 1818 单元格均为黑色。
    • 

  • All the 1414 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
    与左上角或右下角 3×3 区域相邻（水平、垂直或对角线）的所有 1414 单元格均为白色。
    • 



It is not allowed to rotate a TaK Code.
不允许旋转 TaK 代码。


You are given a grid with NN horizontal rows and MM vertical columns.
The state of the grid is described by NN strings, S1,…S_1,\ldots, and SNS_N, each of length MM.  The cell at the ii-th row from the top and jj-th column from the left is black if the jj-th character of SiS_i is #, and white if it is ..
您将获得一个包含 NN 水平行和 MM 垂直列的网格。网格的状态由 NN 字符串 S1,…S_1,\ldots 、 和 SNS_N 来描述，每个字符串的长度 MM 都是 。如果 jj 的 SiS_i 第 -th 个字符为 # ，则从顶部开始的 ii 第 -行和 jj 从左侧开始的第 --列的单元格为黑色，如果 的字符为 . ，则为白色。


Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
查找满足 TaK 代码条件的所有 9×9 区域，这些区域完全包含在网格中。











Constraints 约束
    

  • 9≤N,M≤1009 \leq N,M \leq 100
    • 

  • NN and MM are integers.
     NN 和 MM 是整数。
    • 

  • SiS_i is a string of length MM consisting of . and #.
     SiS_i 是由 . 和 # 组成的长度 MM 字符串。
    • 
















Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：


NN MM
S1S_1
⋮\vdots
SNS_N












Output 输出
For all pairs (i,j)(i,j) such that the nine-by-nine region, whose top-left cell is at the ii-th row from the top and jj-th columns from the left, satisfies the conditions of a TaK Code, print a line containing ii, a space, and jj in this order.
对于所有对 (i,j)(i,j) ，使其左上角单元格位于顶部的第 ii -行和 jj 左起的第 - 列的 9×9 区域满足 TaK 代码的条件，请 jj 按此顺序打印包含 ii 、空格的行。

The pairs must be sorted in lexicographical ascending order; that is, ii must be in ascending order, and within the same ii, jj must be in ascending order.
这些对必须按词典升序排序;也就是说， ii 必须按升序排列，并且在同一 ii 范围内， jj 必须按升序排列。















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 1010-th row from the top and 22-nd column from the left, satisfies the conditions of a TaK Code, as shown below.
在输入给出的网格中，9×9 区域（其左上角单元格位于顶部的第 1010 -行， 22 左侧的 -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 - Invisible Hand
C - 看不见的手
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB


			

				


配点 : 300300 点







問題文
りんご市場に NN 人の売り手と MM 人の買い手がいます。
在苹果市场上，有人卖家， MM 也有 NN 人买家。


ii 番目の売り手は、AiA_i 円以上でならりんごを売ってもよいと考えています。
 ii 第二个卖家认为苹果卖超过 AiA_i 一日元是可以的。


ii 番目の買い手は、BiB_i 円以下でならりんごを買ってもよいと考えています。
 ii 第二个买家认为以低于 BiB_i 日元的价格购买苹果是可以的。


次の条件を満たすような最小の整数 XX を求めてください。
 XX 求满足以下条件的最小整数：


条件：りんごを XX 円で売ってもよいと考える売り手の人数が、りんごを XX 円で買ってもよいと考える買い手の人数以上である。
条件：愿意以 XX 日元出售苹果的卖家数量大于愿意以 XX 日元购买苹果的买家数量。











制約
    

  • 1≤N,M≤2×1051 \leq N,M \leq 2\times 10^5
    • 

  • 1≤Ai,Bi≤1091\leq A_i,B_i \leq 10^9
    • 

  • 入力は全て整数である 所有输入均为整数 
    • 
















入力
入力は以下の形式で標準入力から与えられる。 输入从标准输入给出，格式如下： 


NN MM
A1A_1 …\ldots ANA_N
B1B_1 …\ldots BMB_M












出力
答えを出力せよ。   打印出答案。 















入力例 1
3 4
110 90 120
100 80 120 10000












出力例 1
110



りんごを 110110 円で売ってもよいと考える売り手は 1,21,2 番目の 22 人であり、りんごを 110110 円で買ってもよいと考える買い手は 3,43,4 番目の 22 人であるため、110110 は条件を満たします。
满足条件，因为认为可以卖 110110 苹果换日元的卖家是 1,21,2 第二 22 人，认为可以买 110110 苹果换日元的买家是 3,43,4 第二 22 人。 110110 


110110 未満の整数が条件を満たすことはないため、これが答えです。
 110110 这就是答案，因为小于的整数永远不会满足条件。













入力例 2
5 2
100000 100000 100000 100000 100000
100 200












出力例 2
201














入力例 3
3 2
100 100 100
80 120












出力例 3
100







Score : 300300 points 成绩 ： 300300 points







Problem Statement 问题陈述
There are NN sellers and MM buyers in an apple market.
苹果市场上有 NN 卖家和 MM 买家。


The ii-th seller may sell an apple for AiA_i yen or more (yen is the currency in Japan).
 ii 第-个卖家可以以 AiA_i 日元或更高的价格出售一个苹果（日元是日本的货币）。


The ii-th buyer may buy an apple for BiB_i yen or less.
 ii 第-个买家可以以日元或更低的价格 BiB_i 购买苹果。


Find the minimum integer XX that satisfies the following condition.
求满足以下条件的最小整数 XX 。


Condition: The number of people who may sell an apple for XX yen is greater than or equal to the number of people who may buy an apple for XX yen.
条件：可以以 XX 日元出售苹果的人数大于或等于可以以 XX 日元购买苹果的人数。











Constraints 约束
    

  • 1≤N,M≤2×1051 \leq N,M \leq 2\times 10^5
    • 

  • 1≤Ai,Bi≤1091\leq A_i,B_i \leq 10^9
    • 

  • All input values are integers.
    所有输入值均为整数。
    • 
















Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：


NN MM
A1A_1 …\ldots ANA_N
B1B_1 …\ldots BMB_M












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 11-st and 22-nd, may sell an apple for 110110 yen; two buyers, the 33-rd and 44-th, may buy an apple for 110110 yen.  Thus, 110110 satisfies the condition.
两个卖家，- 11 st 和 22 -nd，可以卖一个苹果换 110110 日元;两个买家，- 33 rd 和 44 -th，可以用 110110 日元购买一个苹果。因此， 110110 满足条件。


Since an integer less than 110110 does not satisfy the condition, this is the answer.
由于小于 110110 的整数不满足条件，这就是答案。













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 - Count Bracket Sequences
D - 计数括号序列
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB


			

				


配点 : 400400 点







問題文
空でない文字列 SS が与えられます。SS の各文字は (, ), ? のいずれかです。
提供非空字符串 SS 。 SS 每个字符都是 ( 、 、 ) 之一。 ? 

SS に含まれる ? の個数を xx とすると、? を ( あるいは ) に置き換えて新しい文字列を作る方法は 2x2^x 通りありますが、このうち新しくできた文字列が括弧列となるような置き換え方の数を 998244353998244353 で割った余りを求めてください。
 SS 如果 包含 的 xx 数 ? 目， ? ( ) 则有一种 2x2^x 方法可以用 或 替换来创建新字符串，但要找到替换次数的余数，其中新创建的字符串是括号序列除 998244353998244353 以 。


ただし、括弧列とは以下のいずれかの条件を満たす文字列のことです。
但是，括号列是满足下列条件之一的字符串： 


    

  • 空文字列
    • 

  • ある括弧列 AA が存在して、(, AA, ) をこの順に連結した文字列
    一个字符串，其中存在括号序列 AA ，并 ( AA ) 按该顺序连接 。
    • 

  • ある空でない括弧列 A,BA, B が存在して、A,BA, B をこの順に連結した文字列
    一个字符串，其中存在一个非空括号列 A,BA, B ，并 A,BA, B 按以下顺序连接
    • 












制約
    

  • SS は長さ 30003000 以下の (, ), ? からなる空でない文字列
     SS 是由 30003000 ( 、 ) 和 长度 ? 组成的非空字符串
    • 
















入力
入力は以下の形式で標準入力から与えられる。 输入从标准输入给出，格式如下： 


SS












出力
答えを出力せよ。 打印出答案。 















入力例 1
(???(?












出力例 1
2



SS を ()()() あるいは (())() に置き換えると括弧列となります。
 SS 用 ()()() 或 (())() 形成括号列。

他の置き換え方で新しくできた文字列が括弧列となることはないので、22 を出力します。
 由于由其他替换方法创建的新字符串不会成为括号序列， 22 因此它输出 。













入力例 2
)))))












出力例 2
0














入力例 3
??????????????(????????(??????)?????????(?(??)












出力例 3
603032273



998244353998244353 で割った余りを出力してください。
 998244353998244353 输出余数除以 。






Score : 400400 points 成绩 ： 400400 points







Problem Statement 问题陈述
You are given a non-empty string SS consisting of (, ), and ?.
您将获得一个由 ( 、 ) 和 ? 组成的非空字符串 SS 。

There are 2x2^x ways to obtain a new string by replacing each ? in SS with ( and ), where xx is the number of occurrences of ? in SS.  Among them, find the number, modulo 998244353998244353, of ways that yield a parenthesis string.
有一些 2x2^x 方法可以通过将每个 ? in SS 替换为 ( 和 ) 来获取新字符串，其中 xx ? 是 in SS 的出现次数。其中，找到产生括号字符串的方式的数、模 998244353998244353 数。


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 (, AA, and ), for some parenthesis string AA.
    它是 ( 、 AA 和 ) 的串联，用于某些括号字符串 AA 。
    • 

  • It is a concatenation of AA and BB, for some non-empty parenthesis strings AA and BB.
    它是 AA 和 BB 的串联，用于一些非空括号字符串 AA 和 BB 。
    • 












Constraints 约束
    

  • SS is a non-empty string of length at most 30003000 consisting of (, ), and ?.
     SS 是一个长度最多 30003000 由 ( 、 ) 和 ? 组成的非空字符串。
    • 
















Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：


SS












Output 输出
Print the answer. 打印答案。















Sample Input 1 示例输入 1
(???(?












Sample Output 1 示例输出 1
2



Replacing SS with ()()() or (())() yields a parenthesis string.
替换 SS 为 ()()() 或 (())() 生成括号字符串。

The other replacements do not yield a parenthesis string, so 22 should be printed.
其他替换不产生括号字符串，因此 22 应打印。













Sample Input 2 示例输入 2
)))))












Sample Output 2 示例输出 2
0














Sample Input 3 示例输入 3
??????????????(????????(??????)?????????(?(??)












Sample Output 3 示例输出 3
603032273



Print the count modulo 998244353998244353.
打印计数模 998244353998244353 。






			


			
		

	
		

		

			E - Tangency of Cuboids 
E - 长方体的切线
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB


			

				


配点 : 500500 点







問題文
33 次元空間内に NN 個の直方体があります。


直方体同士は重なっていません。厳密には、相異なるどの 22 つの直方体の共通部分の体積も 00 です。


ii 番目の直方体は、22 点 (Xi,1,Yi,1,Zi,1),(Xi,2,Yi,2,Zi,2)(X_{i,1},Y_{i,1},Z_{i,1}), (X_{i,2},Y_{i,2},Z_{i,2}) を結ぶ線分を対角線とし、辺は全ていずれかの座標軸に平行です。


各直方体について、他のいくつの直方体と面で接しているか求めてください。

厳密には、各 ii に対し、1≤j≤N1\leq j \leq N かつ j≠ij\neq i である jj のうち、ii 番目の直方体の表面と jj 番目の直方体の表面の共通部分の面積が正であるものの個数を求めてください。











制約
    

  • 1≤N≤1051 \leq N \leq 10^5
    • 

  • 0≤Xi,1<Xi,2≤1000 \leq X_{i,1} < X_{i,2} \leq 100
    • 

  • 0≤Yi,1<Yi,2≤1000 \leq Y_{i,1} < Y_{i,2} \leq 100
    • 

  • 0≤Zi,1<Zi,2≤1000 \leq Z_{i,1} < Z_{i,2} \leq 100
    • 

  • 直方体同士は体積が正の共通部分を持たない
    • 

  • 入力は全て整数である
    • 
















入力
入力は以下の形式で標準入力から与えられる。


NN
X1,1X_{1,1} Y1,1Y_{1,1} Z1,1Z_{1,1} X1,2X_{1,2} Y1,2Y_{1,2} Z1,2Z_{1,2}
⋮\vdots
XN,1X_{N,1} YN,1Y_{N,1} ZN,1Z_{N,1} XN,2X_{N,2} YN,2Y_{N,2} ZN,2Z_{N,2}












出力
答えを出力せよ。  















入力例 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



11 番目の直方体と 22 番目の直方体は、22 点 (0,0,1),(1,1,1)(0,0,1),(1,1,1) を結ぶ線分を対角線とする長方形を共有しています。

11 番目の直方体と 33 番目の直方体は、点 (1,1,1)(1,1,1) を共有していますが、面で接してはいません。













入力例 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 : 500500 points 成绩 ： 500500 points







Problem Statement 问题陈述
There are NN rectangular cuboids in a three-dimensional space.
在三维空间中有 NN 矩形长方体。


These cuboids do not overlap.  Formally, for any two different cuboids among them, their intersection has a volume of 00.
这些长方体不重叠。从形式上讲，对于它们之间的任意两个不同的长方体，它们的交点的体积为 00 。


The diagonal of the ii-th cuboid is a segment that connects two points (Xi,1,Yi,1,Zi,1)(X_{i,1},Y_{i,1},Z_{i,1}) and (Xi,2,Yi,2,Zi,2)(X_{i,2},Y_{i,2},Z_{i,2}), and its edges are all parallel to one of the coordinate axes.
第 ii -th 个长方体的对角线是连接两点 (Xi,1,Yi,1,Zi,1)(X_{i,1},Y_{i,1},Z_{i,1}) 和 (Xi,2,Yi,2,Zi,2)(X_{i,2},Y_{i,2},Z_{i,2}) 的线段，其边都平行于其中一个坐标轴。


For each cuboid, find the number of other cuboids that share a face with it.
对于每个长方体，找到与其共享面的其他长方体的数量。

Formally, for each ii, find the number of jj with 1≤j≤N1\leq j \leq N and j≠ij\neq i such that the intersection of the surfaces of the ii-th and jj-th cuboids has a positive area.
形式上，对于每个 ii ，求 jj 和 1≤j≤N1\leq j \leq N 的个数， j≠ij\neq i 使得 ii 第 -th 个和 jj -th 个长方体的表面的交点具有正面积。











Constraints 约束
    

  • 1≤N≤1051 \leq N \leq 10^5
    • 

  • 0≤Xi,1<Xi,2≤1000 \leq X_{i,1} < X_{i,2} \leq 100
    • 

  • 0≤Yi,1<Yi,2≤1000 \leq Y_{i,1} < Y_{i,2} \leq 100
    • 

  • 0≤Zi,1<Zi,2≤1000 \leq Z_{i,1} < Z_{i,2} \leq 100
    • 

  • 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:
输入从标准输入中给出，格式如下：


NN
X1,1X_{1,1} Y1,1Y_{1,1} Z1,1Z_{1,1} X1,2X_{1,2} Y1,2Y_{1,2} Z1,2Z_{1,2}
⋮\vdots
XN,1X_{N,1} YN,1Y_{N,1} ZN,1Z_{N,1} XN,2X_{N,2} YN,2Y_{N,2} ZN,2Z_{N,2}












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 11-st and 22-nd cuboids share a rectangle whose diagonal is the segment connecting two points (0,0,1)(0,0,1) and (1,1,1)(1,1,1).
 11 -st 和 22 -nd 长方体共享一个矩形，其对角线是连接两点 (0,0,1)(0,0,1) 和 (1,1,1)(1,1,1) 的线段。

The 11-st and 33-rd cuboids share a point (1,1,1)(1,1,1), but do not share a surface.
 11 -st 和 33 -rd 长方体共享一个点 (1,1,1)(1,1,1) ，但不共享一个曲面。













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 - Cans and Openers
F - 罐头和开瓶器
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB


			

				


配点 : 500500 点







問題文
NN 個の品物があります。

これらはそれぞれ、缶切りが不要な缶・缶切りが必要な缶・缶切りのいずれかです。

ii 個目の品物は、整数の組 (Ti,Xi)(T_i, X_i) により次のように表されます。  


    

  • Ti=0T_i = 0 ならば、ii 個目の品物は缶切りが不要な缶で、入手すると満足度 XiX_i を得る。
    • 

  • Ti=1T_i = 1 ならば、ii 個目の品物は缶切りが必要な缶で、入手した上で缶切りを使うと満足度 XiX_i を得る。
    • 

  • Ti=2T_i = 2 ならば、ii 個目の品物は缶切りで、XiX_i 個までの缶に対して使用できる。
    • 



NN 個の品物から MM 個を選んで入手するとき、得られる満足度の合計としてあり得る最大値を求めてください。











制約
    

  • 1≤M≤N≤2×1051 \leq M \leq N \leq 2 \times 10^5
    • 

  • TiT_i は 0,1,20,1,2 のいずれか
    • 

  • 1≤Xi≤1091 \leq X_i \leq 10^9
    • 

  • 入力される値はすべて整数
    • 
















入力
入力は以下の形式で標準入力から与えられる。


NN MM
T1T_1 X1X_1
T2T_2 X2X_2
⋮\vdots
TNT_N XNX_N












出力
答えを整数として出力せよ。















入力例 1
8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100












出力例 1
27



1,2,5,71, 2, 5, 7 個目の品物を入手し、77 個目の品物である缶切りを 55 個目の品物に対して使用すると、満足度 6+6+15=276 + 6 + 15 = 27 を得ます。

満足度が 2828 以上になる品物の入手方法は存在しませんが、上記の例において 77 個目の品物のかわりに 66 個目の品物や 88 個目の品物を選んでも満足度 2727 を得ることができます。













入力例 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 : 500500 points 成绩 ： 500500 points







Problem Statement 问题陈述
There are NN items.
有 NN 项目。

Each of these is one of a pull-tab can, a regular can, or a can opener.
这些都是拉片罐、普通罐或开罐器之一。

The ii-th item is described by an integer pair (Ti,Xi)(T_i, X_i) as follows:  
 ii 第 -th 项由整数对 (Ti,Xi)(T_i, X_i) 描述，如下所示：


    

  • If Ti=0T_i = 0, the ii-th item is a pull-tab can; if you obtain it, you get a happiness of XiX_i.
    如果 Ti=0T_i = 0 ii ，则第 -th 项是拉片罐;如果你得到它，你就会得到一种幸福 XiX_i 。
    • 

  • If Ti=1T_i = 1, the ii-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of XiX_i.
    如果 Ti=1T_i = 1 ， ii 则第 -th 项是常规罐;如果你得到它并使用开罐器来对付它，你会得到一种幸福 XiX_i 。
    • 

  • If Ti=2T_i = 2, the ii-th item is a can opener; it can be used against at most XiX_i cans.
    如果 Ti=2T_i = 2 ii ，则第 -th 项是开罐器;它可以用于大多数 XiX_i 罐头。
    • 



Find the maximum total happiness that you get by obtaining MM items out of NN.
找到你通过获得 MM 物品获得的最大总幸福 NN 感。











Constraints 约束
    

  • 1≤M≤N≤2×1051 \leq M \leq N \leq 2 \times 10^5
    • 

  • TiT_i is 00, 11, or 22.
     TiT_i 是 00 、 11 或 22 。
    • 

  • 1≤Xi≤1091 \leq X_i \leq 10^9
    • 

  • All input values are integers.
    所有输入值均为整数。
    • 
















Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：


NN MM
T1T_1 X1X_1
T2T_2 X2X_2
⋮\vdots
TNT_N XNX_N












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 11-st, 22-nd, 55-th, and 77-th items, and use the 77-th item (a can opener) against the 55-th item, you will get a happiness of 6+6+15=276 + 6 + 15 = 27.
如果你获得 11 -st、 22 -nd、 55 -th 和 77 -th 项，并使用 77 第 -th 项（开罐器）来对抗 55 第 -th 项，你将获得 的 6+6+15=276 + 6 + 15 = 27 幸福。

There are no ways to obtain items to get a happiness of 2828 or greater, but you can still get a happiness of 2727 by obtaining the 66-th or 88-th items instead of the 77-th in the combination above.
没有办法获得获得幸福 2828 或更大的幸福的物品，但你仍然 2727 可以通过获得 66 -th 或 88 -th 物品而不是上面组合中的 77 -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 - Avoid Straight Line
G - 避免直线
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB


			

				


配点 : 550550 点







問題文
NN 頂点の木が与えられます。頂点には 11 から NN までの番号がついており、ii 番目の辺は頂点 AiA_i と頂点 BiB_i を結んでいます。

以下の条件を満たす整数の組 (i,j,k)(i,j,k) の個数を求めてください。  


    

  • 1≤i<j<k≤N1 \leq i < j < k \leq N
    • 

  • 与えられた木には頂点 i,j,ki,j,k をすべて含む単純パスは存在しない
    • 












制約
    

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
    • 

  • 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N
    • 

  • 与えられるグラフは木
    • 

  • 入力される値はすべて整数 
    • 
















入力
入力は以下の形式で標準入力から与えられる。


NN
A1A_1 B1B_1
⋮\vdots
AN−1A_{N-1} BN−1B_{N-1}












出力
答えを出力せよ。















入力例 1
5
1 2
2 3
2 4
1 5












出力例 1
2



(i,j,k)=(1,3,4),(3,4,5)(i,j,k) = (1,3,4),(3,4,5) の 22 つが条件を満たします。













入力例 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 : 550550 points 成绩 ： 550550 points







Problem Statement 问题陈述
You are given a tree with NN vertices.  The vertices are numbered from 11 through NN, and the ii-th edge connects vertex AiA_i and vertex BiB_i.
你会得到一棵带有 NN 顶点的树。顶点从 11 到 编号 NN ， ii 第 -th 条边连接顶点 AiA_i 和顶点 BiB_i 。

Find the number of tuples of integers (i,j,k)(i,j,k) such that:  
求整数元组的数目， (i,j,k)(i,j,k) 使得：


    

  • 1≤i<j<k≤N1 \leq i < j < k \leq N; and  1≤i<j<k≤N1 \leq i < j < k \leq N ;和
    • 

  • the given tree does not contain a simple path that contains all of vertices ii, jj, and kk.
    给定的树不包含包含所有顶点 ii 、 jj 和 kk 的简单路径。
    • 












Constraints 约束
    

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
    • 

  • 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N
    • 

  • The given graph is a tree.
    给定的图形是一棵树。
    • 

  • All input values are integers.
    所有输入值均为整数。
    • 
















Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：


NN
A1A_1 B1B_1
⋮\vdots
AN−1A_{N-1} BN−1B_{N-1}












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: (i,j,k)=(1,3,4),(3,4,5)(i,j,k) = (1,3,4),(3,4,5).
两个元组满足以下条件： (i,j,k)=(1,3,4),(3,4,5)(i,j,k) = (1,3,4),(3,4,5) 。













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







			


			
		

	
		

		

			Ex - snukesnuke
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB
时间限制：2 秒 / 内存限制：1024 MB


			

				


配点 : 600600 点







問題文
高橋君は人 1,…,N1,\ldots,N の NN 人のあだ名を決めることになりました。


人 ii はあだ名を SiS_i にしてほしいと思っています。複数人に同じあだ名をつけるのを避けるため、高橋君は次の手順で NN 人のあだ名を決めることにしました。


    

  • i=1,…,Ni=1,\ldots,N の順に、以下の操作により人 ii のあだ名を決める
      

    • 変数 kik_i を 11 とする。
      • 

    • 「SiS_i を kik_i 回繰り返した文字列」がすでに誰かのあだ名である間、kik_i を 11 増やすことを繰り返す。
      • 

    • 「SiS_i を kik_i 回繰り返した文字列」を人 ii のあだ名とする。
      • 

    

    • 



NN 人のあだ名を決めた後の k1,…,kNk_1,\ldots,k_N を求めてください。











制約
    

  • N≥1N \geq 1
    • 

  • SiS_i は英小文字のみからなる、長さ 11 以上の文字列
    • 

  • SiS_i の長さの総和は 2×1052\times 10^5 以下
    • 
















入力
入力は以下の形式で標準入力から与えられる。


NN
S1S_1
⋮\vdots
SNS_N












出力
問題文中の操作により NN 人のあだ名を決めた後の k1,…,kNk_1,\ldots,k_N をこの順に空白区切りで出力せよ。















入力例 1
3
snuke
snuke
rng












出力例 1
1 2 1



    

  • まず人 11 のあだ名を決めます。
      

    • k1=1k_1=1 とします。
      • 

    • S1S_1 を k1k_1 回繰り返した文字列 snuke は誰のあだ名でもないので、人 11 のあだ名は snuke になります。
      • 

    

    • 

  • 次に人 22 のあだ名を決めます。
      

    • k2=1k_2=1 とします。
      • 

    • S2S_2 を k2k_2 回繰り返した文字列 snuke はすでに人 11 のあだ名なので、k2k_2 を 11 増やして 22 とします。
      • 

    • S2S_2 を k2k_2 回繰り返した文字列 snukesnuke は誰のあだ名でもないので、人 22 のあだ名は snukesnuke になります。
      • 

    

    • 

  • 最後に人 33 のあだ名を決めます。
      

    • k3=1k_3=1 とします。
      • 

    • S3S_3 を k3k_3 回繰り返した文字列 rng は誰のあだ名でもないので、人 33 のあだ名は rng になります。
      • 

    

    • 



以上により、k1,k2,k3k_1,k_2,k_3 はそれぞれ 1,2,11,2,1 となります。













入力例 2
4
aa
a
a
aaa












出力例 2
1 1 3 2



    

  • 人 11 のあだ名は aa になります。
    • 

  • 人 22 のあだ名は a になります。
    • 

  • 人 33 のあだ名は、a, aa がすでに他の人のあだ名なので、aaa になります。
    • 

  • 人 44 のあだ名は、aaa がすでに他の人のあだ名なので、aaaaaa になります。
    • 














入力例 3
5
x
x
x
x
x












出力例 3
1 2 3 4 5







Score : 600600 points 成绩 ： 600600 points







Problem Statement 问题陈述
Takahashi is going to decide nicknames of NN people, person 1,…,N1,\ldots,N.
高桥要决定 NN 人的昵称，人 1,…,N1,\ldots,N .


Person ii wants a nickname SiS_i.  To avoid giving the same nickname to multiple people, he is going to decide their nicknames as follows:
人 ii 想要一个昵称 SiS_i 。为了避免给多个人起同一个昵称，他将决定他们的昵称如下：


    

  • For each i=1,…,Ni=1,\ldots,N in order, decide person ii's nickname as follows:
     i=1,…,Ni=1,\ldots,N 按顺序确定每个人 ii 的昵称，如下所示：
      

    • Initialize a variable kik_i with 11.
       kik_i 使用 11 初始化变量。
      • 

    • Repeatedly increment kik_i by one while the kik_i-time repetition of SiS_i is someone's nickname.
      重复 kik_i 递增 1，而 kik_i -time 重复是 SiS_i 某人的昵称。
      • 

    • Let person ii's nickname be the kik_i-time repetition of SiS_i.
      设 person's ii 昵称是 kik_i 的 SiS_i -time 重复。
      • 

    

    • 



Find k1,…k_1,\ldots, and kNk_N after deciding nicknames of the NN people.
找到 k1,…k_1,\ldots ，并在 kNk_N 决定 NN 人们的昵称之后。











Constraints 约束
    

  • N≥1N \geq 1
    • 

  • SiS_i is a string of length at least 11 consisting of lowercase English letters.
     SiS_i 是长度至少 11 由小写英文字母组成的字符串。
    • 

  • The sum of lengths of SiS_i is at most 2×1052\times 10^5.
    的 SiS_i 长度之和最多 2×1052\times 10^5 为 。
    • 
















Input 输入
The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：


NN
S1S_1
⋮\vdots
SNS_N












Output 输出
Print k1,…k_1,\ldots, and kNk_N resulting from deciding the nicknames of the NN people by the procedure in the problem statement.
打印 k1,…k_1,\ldots ，并 kNk_N 根据问题陈述中的程序确定 NN 人们的昵称。















Sample Input 1 示例输入 1
3
snuke
snuke
rng












Sample Output 1 示例输出 1
1 2 1



    

  • First, he decides person 11's nickname.
    首先，他决定一个人 11 的昵称。
      

    • Let k1=1k_1=1. 让 k1=1k_1=1 .
      • 

    • The k1k_1-time repetition of S1S_1 is snuke, which is nobody's nickname, so person 11's nickname is set to snuke.
      的 k1k_1 S1S_1 -time 重复是 snuke ，这是 nobody's 昵称，所以 person 11 的昵称设置为 snuke 。
      • 

    

    • 

  • Next, he decides person 22's nickname.
    接下来，他决定一个人 22 的昵称。
      

    • Let k2=1k_2=1. 让 k2=1k_2=1 .
      • 

    • The k2k_2-time repetition of S2S_2 is snuke, which is already a nickname of person 11, so increment k2k_2 by one to make it 22.
      的 k2k_2 S2S_2 -time 重复 是 snuke ，这已经是人的 11 昵称了，所以 k2k_2 递增 1 即可 22 。
      • 

    • The k2k_2-time repetition of S2S_2 is snukesnuke, which is nobody's nickname, so person 22's nickname is set to snukesnuke.
      的 k2k_2 S2S_2 -time 重复是 snukesnuke ，这是 nobody's 昵称，所以 person 22 的昵称设置为 snukesnuke 。
      • 

    

    • 

  • Finally, he decides person 33's nickname.
    最后，他决定一个人 33 的昵称。
      

    • Let k3=1k_3=1. 让 k3=1k_3=1 .
      • 

    • The k3k_3-time repetition of S3S_3 is rng, which is nobody's nickname, so person 33's nickname is set to rng.
      的 k3k_3 S3S_3 -time 重复是 rng ，这是 nobody's 昵称，所以 person 33 的昵称设置为 rng 。
      • 

    

    • 



Thus, k1k_1, k2k_2, and k3k_3 result in 11, 22, and 11, respectively.
因此， k1k_1 、 k2k_2 和 k3k_3 分别产生 11 、 22 和 11 。













Sample Input 2 示例输入 2
4
aa
a
a
aaa












Sample Output 2 示例输出 2
1 1 3 2



    

  • Person 11's nickname is set to aa.
    人员 11 的昵称设置为 aa 。
    • 

  • Person 22's nickname is set to a.
    人员 22 的昵称设置为 a 。
    • 

  • Person 33's nickname is set to aaa, because a and aa are already nicknames of someone else.
    人的 33 昵称设置为 aaa ，因为 a 和 aa 已经是其他人的昵称。
    • 

  • Person 44's nickname is set to aaaaaa, because aaa is already a nickname of someone else.
    Person 44 的昵称设置为 aaaaaa ，因为 aaa 已经是其他人的昵称。
    • 














Sample Input 3 示例输入 3
5
x
x
x
x
x












Sample Output 3 示例输出 3
1 2 3 4 5