标签归档:code jam

Code Jam 2019 Qualification Round

离开了这么久,感觉还是做题纯粹有意思….上周看了看World Final,感觉还是想念之前做题的时光….真是岁月催人老,我也什么都不会写了…..

新的一年的Code Jam已经开始了,不知道能走到哪一步,简单写写…吐槽一下,今年界面比去年界面更好看了,但是感觉没有之前打code jam时候的特色了,给我一种计蒜客的感觉…..而且我也没找到有什么办法可以下到数据啊,有没有大佬告诉我….

A

水题没啥好说的,听说叉姥爷和韩司机一行py….

 

B

水题没啥好说的,听说叉姥爷和韩司机一行py….

C

找第一个相邻数不同的位置然后算gcd,之后做n次除法即可。。。结果我有个地方把//打成了/,mdzz。。。

D

唯一一道感觉有意思的题目:有n个电脑,其中坏掉了b个,让你在f次内找到。f为5且b不超过15。

比赛的时候想到的思路是肯定可以通过分成16个为一段来解决,比如第一次询问一半0一半1,然后就可以知道每一段有几个错误了,然后继续往下分段,这样递归下去就可以了。但是这种思路感觉太麻烦了,不会写= =。看了题解才发现这样分段的好处是如果我们把所有f次的返回01序列拼起来,竖着看可以得到一个0-15的序列(详情官方题解)。。。瞬间好写了。。。

感觉这道题妙啊,能不能给个机会面试学弟考考啊。。。

 

Kickstart Round A 2017 做题记录

Problem A. Square Counting

Problem

Mr. Panda has recently fallen in love with a new game called Square Off, in which players compete to find as many different squares as possible on an evenly spaced rectangular grid of dots. To find a square, a player must identify four dots that form the vertices of a square. Each side of the square must have the same length, of course, but it does not matter what that length is, and the square does not necessarily need to be aligned with the axes of the grid. The player earns one point for every different square found in this way. Two squares are different if and only if their sets of four dots are different.

Mr. Panda has just been given a grid with R rows and C columns of dots. How many different squares can he find in this grid? Since the number might be very large, please output the answer modulo 109 + 7 (1000000007).

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line has two integers R and C: the number of dots in each row and column of the grid, respectively.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of different squares can be found in the grid.

Limits

1 ≤ T ≤ 100.

Small dataset

2 ≤ R ≤ 1000.
2 ≤ C ≤ 1000.

Large dataset

2 ≤ R ≤ 109.
2 ≤ C ≤ 109.

Sample

Input Output

The pictures below illustrate the grids from the three sample cases and a valid square in the third sample case.

题目大意:给出n*m个点阵,求出其中有多少个不同的正方形。n,m<=1e9.

比赛的时候推了半天。然后只推出个两重循环的式子,然后过了小数据后也没有想着优化,以为大数据肯定可以跑完,然而本机跑得太慢了直接GG了,后来想出来优化发现也没法交了。sad,根本不熟悉这种赛制啊。。

比赛的时候自己推得方式太复杂了,是把正的正方形和斜的正方形分开考虑的。后来看见别人的方法非常好:链接

公式大概这个样子吧。。。

Problem B. Patterns Overlap

Problem

Alice likes reading and buys a lot of books. She stores her books in two boxes; each box is labeled with a pattern that matches the titles of all of the books stored in that box. A pattern consists of only uppercase/lowercase English alphabet letters and stars (*). A star can match between zero and four letters. For example, books with the titles GoneGirl and GoneTomorrow can be put in a box with the pattern Gone**, but books with the titles TheGoneGirl, and GoneWithTheWind cannot.

Alice is wondering whether there is any book that could be stored in either of the boxes. That is, she wonders if there is a title that matches both boxes’ patterns.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of two lines; each line has one string in which each character is either an uppercase/lowercase English letter or *.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is TRUE if there is a string that matches both patterns, or FALSE if not.

Limits

1 ≤ T ≤ 50.

Small dataset

1 ≤ the length of each pattern ≤ 200.
Each pattern contains at most 5 stars.

Large dataset

1 ≤ the length of each pattern ≤ 2000.

Sample

Input Output

In sample case #1, the title It matches both patterns. Note that it is possible for a * to match zero characters.

In sample case #2, the title Shakespeare matches both patterns.

In sample case #3, there is no title that matches both patterns. Shakespeare, for example, does not work because the * at the start of the *peare pattern cannot match six letters.

题意:给出两个字符串,其中字符串有一些字符是*,一个*可以代替0到4个字符,问最后能否匹配这两个串。字符串长度小于2000

很明显dp,但是比赛的时候各种挂,最后弃疗了。。。考虑把每个字符*换成4个$,那么就变成了每个$只能替换一个字符或者不替换,这样转移的时候就很简单了。dp[i][j]表示第一个串匹配到了i第二个串匹配到了j的情况是否存在。需要考虑可能根本不发生替换的情况,以及要注意好初始化,如果某个字符串的开头就是一个*的话,那么插入$的字符后字符串就变成了开头四个$。那么这四个位置是都可以认为和另一个字符串的0位置匹配(也就是不发生替换的情况。)比如:T….和$$$$T这样一个例子。。。画一画就好了。

C不大会,待补。。。

Kickstart Practice Round 2017做题记录

大概是之前的APAC的题目。

Problem A. Country Leader

Problem

The Constitution of a certain country states that the leader is the person with the name containing the greatest number of different alphabet letters. (The country uses the uppercase English alphabet from A through Z.) For example, the name GOOGLE has four different alphabet letters: E, G, L, and O. The name APAC CODE JAM has eight different letters. If the country only consists of these 2 persons, APAC CODE JAM would be the leader.

If there is a tie, the person whose name comes earliest in alphabetical order is the leader.

Given a list of names of the citizens of the country, can you determine who the leader is?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with an interger N, the number of people in the country. Then N lines follow. The i-th line represents the name of the i-th person. Each name contains at most 20 characters and contains at least one alphabet letter.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the name of the leader.

Limits

1 ≤ T ≤ 100.
1 ≤ N ≤ 100.

Small dataset

Each name consists of at most 20 characters and only consists of the uppercase English letters A through Z.

Large dataset

Each name consists of at most 20 characters and only consists of the uppercase English letters A through Z and ‘ ‘(space).
All names start and end with alphabet letters.

Sample

Input Output

In sample case #1, JOHNSON contains 5 different alphabet letters(‘H’, ‘J’, ‘N’, ‘O’, ‘S’), so he is the leader.

Sample case #2 would only appear in Large data set. The name DEF contains 3 different alphabet letters, the name A AB C also contains 3 different alphabet letters. A AB C comes alphabetically earlier so he is the leader.

字符串模拟一下咯。。。

Problem B. Vote

Problem

A and B are the only two candidates competing in a certain election. We know from polls that exactly N voters support A, and exactly M voters support B. We also know that N is greater than M, so A will win.

Voters will show up at the polling place one at a time, in an order chosen uniformly at random from all possible (N + M)! orders. After each voter casts their vote, the polling place worker will update the results and note which candidate (if any) is winning so far. (If the votes are tied, neither candidate is considered to be winning.)

What is the probability that A stays in the lead the entire time — that is, that A will always be winning after every vote?

Input

The input starts with one line containing one integer T, which is the number of test cases. Each test case consists of one line with two integers N and M: the numbers of voters supporting A and B, respectively.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the probability that A will always be winning after every vote.

y will be considered correct if y is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

1 ≤ T ≤ 100.

Small dataset

0 ≤ M < N ≤ 10.

Large dataset

0 ≤ M < N ≤ 2000.

Sample

Input Output

In sample case #1, there are 3 voters. Two of them support A — we will call them A1 and A2 — and one of them supports B. They can come to vote in six possible orders: A1 A2 B, A2 A1 B, A1 B A2, A2 B A1, B A1 A2, B A2 A1. Only the first two of those orders guarantee that Candidate A is winning after every vote. (For example, if the order is A1 B A2, then Candidate A is winning after the first vote but tied after the second vote.) So the answer is 2/6 = 0.333333…

In sample case #2, there is only 1 voter, and that voter supports A. There is only one possible order of arrival, and A will be winning after the one and only vote.

题意:现在有n个1和m个0,这n+m个数字的合法排序方案是到任意一个位置1的个数都要比0大,求合法序列产生的概率。

这道题当时不会。。。然后学习了一下。考虑合法的方案数,那么合法的方案第一局一定是放1(也就是A胜利)。然后就转化成了一个经典的问题了。合法的方案数就是这么多:,再除以个(n+m)!就好了,化简一下就是(n-m)/(n+m)。

Problem C. Sherlock and Parentheses

Problem

Sherlock and Watson have recently enrolled in a computer programming course. Today, the tutor taught them about the balanced parentheses problem. A string S consisting only of characters ( and/or ) is balanced if:

  • It is the empty string, or:
  • It has the form (S), where S is a balanced string, or:
  • It has the form S1S2, where S1 is a balanced string and S2 is a balanced string.

Sherlock coded up the solution very quickly and started bragging about how good he is, so Watson gave him a problem to test his knowledge. He asked Sherlock to generate a string S of L + R characters, in which there are a total of L left parentheses ( and a total of R right parentheses ). Moreover, the string must have as many different balanced non-empty substrings as possible. (Two substrings are considered different as long as they start or end at different indexes of the string, even if their content happens to be the same). Note that S itself does not have to be balanced.

Sherlock is sure that once he knows the maximum possible number of balanced non-empty substrings, he will be able to solve the problem. Can you help him find that maximum number?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with two integers: L and R.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the answer, as described above.

Limits

1 ≤ T ≤ 100.

Small dataset

0 ≤ L ≤ 20.
0 ≤ R ≤ 20.
1 ≤ L + R ≤ 20.

Large dataset

0 ≤ L ≤ 105.
0 ≤ R ≤ 105.
1 ≤ L + R ≤ 105.

Sample

Input Output

In Case 1, the only possible string is (. There are no balanced non-empty substrings.
In Case 2, the optimal string is (). There is only one balanced non-empty substring: the entire string itself.
In Case 3, both strings ()()( and (()() give the same optimal answer.
For the case ()()(, for example, the three balanced substrings are () from indexes 1 to 2, () from indexes 3 to 4, and ()() from indexes 1 to 4.

贪心的想,假设L和R的最小值为min的话,那么我们可以弄出来min对括号匹配。那么要匹配的方案最多,肯定是()()要好过(())这样的了。因为如果只是嵌套的话,配对还只是局限于min对,而如果相邻放的话,相邻的匹配括号也可以互相组成。然后就是1+2+3+..n了。