Codeforces Round #147 (Div. 2)

Codeforces Round #147 (Div. 2)

​

A. Free Cash

time limit per test

memory limit per test

input

output

n people will visit his cafe. For each person we know the arrival time: the i-th person comes exactly at hi hours mi

n

Help Valera count the minimum number of cashes to work at his cafe next day, so that they can serve all visitors.

Input

n (1 ≤ n ≤ 105), that is the number of cafe visitors.

n lines has two space-separated integers hi and mi (0 ≤ hi ≤ 23; 0 ≤ mi, representing the time when the i-th person comes into the cafe.

chronological

Output

Print a single integer — the minimum number of cashes, needed to serve all clients next day.

Examples

input

4 8 0 8 10 8 10 8 45

output

2

input

3 0 12 10 11 22 22

output

1

Note

In the first sample it is not enough one cash to serve all clients, because two visitors will come into cafe in 8:10. Therefore, if there will be one cash in cafe, then one customer will be served by it, and another one will not wait and will go away.

In the second sample all visitors will come in different times, so it will be enough one cash.

【题意】每组输入客户到来的时间：h,m,主人提供咖啡馆为客户服务，服务时间不能冲突，求满足条件的最小咖啡馆数目。 【分析】模拟。 【代码】

/** Problem: Codeforces Round #147 (Div. 2) A. Free Cash* Running time: 62MS* Complier: G++* Author: herongwei* Create Time: 18:18 2016/4/6*/#include #include #include using namespace std;typedef long long LL;const int maxn = 1e5+10;const LL MOD = 999999997;int a[maxn];int main(){ // freopen("1.txt","r",stdin); int n; while(~scanf("%d",&n)){ memset(a,0,sizeof(a)); int h,m,maxx=0; for(int i=1; i<=n; ++i){ scanf("%d %d",&h,&m); int hh=h*60+m; /*防止冲突，统一转化时间*/ a[hh]++; maxx= max(a[hh],maxx); } printf("%d\n",maxx); } return 0;}/*input48 08 108 108 45output2input30 1210 1122 22output1*/

B. Young Table

time limit per test

memory limit per test

input

output

a, consisting of n rows, numbered from 1 to n. The i-th line of table a contains ci cells, at that for all i (1 < i ≤ n) holds ci ≤ ci - 1.

s as the total number of cells of table a, that is,

. We know that each cell of the table contains a single integer from 1 tos, at that all written integers are distinct.

i-th row of table a are numbered from 1 to ci, then let's denote the number written in the j-th cell of the i-th row asai, j. Your task is to perform several swap operations to rearrange the numbers in the table so as to fulfill the following conditions:

i,j(1 ai- 1,j;i,j(1 ≤i≤n; 1 ai,j- 1.

In one swap operation you are allowed to choose two different cells of the table and swap the recorded there numbers, that is the number that was recorded in the first of the selected cells before the swap, is written in the second cell after it. Similarly, the number that was recorded in the second of the selected cells, is written in the first cell after the swap.

s. You do not have to minimize the number of operations.

Input

n (1 ≤ n ≤ 50) that shows the number of rows in the table. The second line contains n space-separated integers ci (1 ≤ ci ≤ 50; ci ≤ ci - 1)

n lines contain table а. The i-th of them contains ci space-separated integers: the j-th integer in this line represents ai, j.

ai, j are positive and do not exceed s. It is guaranteed that all ai, j

Output

m (0 ≤ m ≤ s), representing the number of performed swaps.

m lines print the description of these swap operations. In the i-th line print four space-separated integers xi, yi, pi, qi(1 ≤ xi, pi ≤ n; 1 ≤ yi ≤ cxi; 1 ≤ qi ≤ cpi). The printed numbers denote swapping the contents of cells axi, yi and api, qi. Note that a swap operation can change the contents of distinct

Examples

input

33 2 1 4 3 5 6 1 2

output

21 1 2 2 2 1 3 1

input

14 4 3 2 1

output

21 1 1 4 1 2 1 3

【题意】：给你一个初始矩阵，可以任意交换两个矩阵元素，求得到行列均递增的目标矩阵的（最小）交换次数，PS：题目不需求最小。

看清题意很重要，不难得出，按第一行放1,2,3...如此顺序放即可满足条件

【代码】：

/** Problem: Codeforces Round #147 (Div. 2) B. Young Table* Running time: 46MS* Complier: G++* Author: herongwei* Create Time: 18:18 2016/4/6 */#include #include #include using namespace std;typedef long long LL;const int maxn = 1e6+10;const int maxm = 55;const LL MOD = 999999997;inline LL read(){ int c=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} return c*f;}int c[maxm],Map[maxm][maxm],Save[maxm*maxm][4];int main(){ int n,m; //freopen("1.txt","r",stdin); while(~scanf("%d",&n)) { memset(c,0,sizeof(c)); memset(Map,0,sizeof(c)); memset(Save,0,sizeof(c)); for(int i=1; i<=n; ++i){ scanf("%d",&c[i]); } for(int row=1; row<=n; ++row){ for(int col=1; col<=c[row]; ++col){ scanf("%d",&Map[row][col]); } } int diff_num=0,tot=1; /*记录交换次数，枚举放的元素，从1开始*/ for(int Row=1; Row<=n; ++Row){ for(int Col=1; Col<=c[Row]; ++Col,++tot){ if(Map[Row][Col] == tot) continue; /*恰好对应元素*/ for(int row=Row; row<=n; ++row){ bool flag=0; /*标记第二次循环已经找到要按顺序放的元素*/ for(int col=1; col<=c[row]; ++col){ if(Map[row][col] == tot){ flag=1; Save[diff_num][0]=Row; /*分别记录两个元素的位置*/ Save[diff_num][1]=Col; Save[diff_num][2]=row; Save[diff_num++][3]=col; swap(Map[Row][Col],Map[row][col]); /*记得交换*/ break; } } if(flag) break; } } } printf("%d\n",diff_num); for(int i=0; i

C. Primes on Interval

time limit per test

memory limit per test

input

output

You've decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors.

a, a + 1, ..., b (a ≤ b). You want to find the minimum integer l (1 ≤ l ≤ b - a + 1) such that for any integer x(a ≤ x ≤ b - l + 1) among l integers x, x + 1, ..., x + l - 1 there are at least k

l. If no value l

Input

a, b, k (1 ≤ a, b, k ≤ 106; a ≤ b).

Output

l. If there's no solution, print -1.

Examples

input

2 4 2

output

3

input

6 13 1

output

4

input

1 4 3

output

-1

x, x + 1, ..., x + l - 1 至少存在k个素数。

【分析】考虑到先筛出素数，然后用一个a数组前缀累加素数的个数，这个数组的作用是求区间内素数个数，用前缀和比较方便，然后我们就可以知道既然小区间的长度固定为L，在【a,b-L+1】判断素数个数是否满足条件（即是否大于K个）即可，然后二分枚举答案就可以了。注意区间没有素数输出-1.

【代码】：

/** Problem: Codeforces Round #147 (Div. 2) C. Primes on Interval* Running time: 31MS* Complier: G++* Author: herongwei* Create Time: 18:18 2016/4/6*/#include #include #include using namespace std;typedef long long LL;const int maxn = 1e6+10;const int maxp = 1e6+10;const int maxm = 55;const LL MOD = 999999997;int prime[maxn];bool vis[maxn];int a[maxn];int n,m,k;void init(){ /// find prime !!! memset(vis,true,sizeof(vis)); int num_prime=0; for(int i=2; i<=maxp; ++i){ if(vis[i]){ prime[++num_prime]=i; } for (int j = 1; ((j <= num_prime) && (i * prime[j] <= maxp)); ++j){ vis[i * prime[j]] = false; if(i % prime[j] == 0) break; } } for(int i=0; i<=num_prime; ++i) a[prime[i]]=1; for(int i=2; i< maxp; ++i) a[i]+=a[i-1]; a[0]=0; ///!!!!}bool Check(int x){ /// find the value of x,the length is x for(int i=n; i<=m-x+1; ++i){ if(a[i+x-1]-a[i-1]>1; if(Check(mid)){ ret=mid; Right=mid-1; ///the required minimum L!!! } else Left=mid+1; } printf("%d\n",ret); } return 0;}/*input2 4 2output3input6 13 1output4input1 4 3output-1*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。