a. dreamoon and stairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
dreamoon wants to climb up a stair of n steps. he can climb 1 or 2 steps at each move. dreamoon wants the number of moves to be a multiple of an integer m.
what is the minimal number of moves making him climb to the top of the stairs that satisfies his condition?
input
the single line contains two space separated integers n, m (0?a>>b; cout
d. dreamoon and sets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
dreamoon likes to play with sets, integers and . is defined as the largest positive integer that divides both a and b.
let s be a set of exactly four distinct integers greater than 0. define s to be of rank k if and only if for all pairs of distinct elements si, sj from s, .
given k and n, dreamoon wants to make up n sets of rank k using integers from 1 to m such that no integer is used in two different sets (of course you can leave some integers without use). calculate the minimum m that makes it possible and print one possible solution.
input
the single line of the input contains two space separated integers n, k (1?≤?n?≤?10?000,?1?≤?k?≤?100).
output
on the first line print a single integer ? the minimal possible m.
on each of the next n lines print four space separated integers representing the i-th set.
neither the order of the sets nor the order of integers within a set is important. if there are multiple possible solutions with minimal m, print any one of them.
sample test(s)
input
1 1
output
51 2 3 5
input
2 2
output
222 4 6 2214 18 10 16
note
for the first example it's easy to see that set {1,?2,?3,?4} isn't a valid set of rank 1 since .
规律，6×i+1 ， 6×i+2 ， 6×i+3 ， 6×i+5
#include #include #include #include using namespace std;int n,k;int main(){ scanf(%d%d,&n,&k); printf(%d\n,(6*(n-1)+5)*k); for(int i=0;i
e. dreamoon and strings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
dreamoon has a string s and a pattern string p. he first removes exactly x characters from s obtaining string s' as a result. then he calculates that is defined as the maximal number of non-overlapping substrings equal to p that can be found in s'. he wants to make this number as big as possible.
more formally, let's define as maximum value of over all s' that can be obtained by removing exactly x characters from s. dreamoon wants to know for all x from 0 to |s| where |s| denotes the length of string s.
input
the first line of the input contains the string s (1?≤?|s|?≤?2?000).
the second line of the input contains the string p (1?≤?|p|?≤?500).
both strings will only consist of lower case english letters.
output
print |s|?+?1 space-separated integers in a single line representing the for all x from 0 to |s|.
sample test(s)
input
aaaaaaa
output
2 2 1 1 0 0
input
axbaxxbab
output
0 1 1 2 1 1 0 0
note
for the first sample, the corresponding optimal values of s' after removal 0 through |s|?=?5 characters from s are {aaaaa, aaaa, aaa, aa,a, }.
for the second sample, possible corresponding optimal values of s' are {axbaxxb, abaxxb, axbab, abab, aba, ab, a, }.
dp
dp[i][j]再第一个串中前i个字符里删j个能得到的最大匹配数
cal(i)从第一个串第i个字符往前删至少删几个可以和第二个串匹配
dp[i][j]=max( dp[i-1][j],dp[i-cal(i)-len2][j-cal(i)] );
#include #include #include #include using namespace std;const int inf=0x3f3f3f3f;char s[2200],p[550];int dp[2200][2200],len1,len2;int cal(int x){ if(x