Monthly Archives: 3 月 2013

CH Adera 3(ZZB的数学作业-构造法初讲)

Posted on by

描述

把一个正整数M分成P个不超过K的正整数的和，满足分成的数不是N的倍数，并且P也不是N的倍数，求这样的P最小是多少？”

输入格式

一个测试点不超过10组数据，每行三个整数N、M、K代表一组数据，以EOF结尾。

输出格式

对于每组数据输出一行，一个整数，即最小的P。

样例输入

3 11 6
2 12 47

样例输出

4
-1

数据范围与约定

对于20%的数据，1<=N，M，K<=20。
对于60%的数据，1<=N，K<=10000。
对于另20%的数据，1<=K<=2。
对于100%的数据，1<=N，M，K<=10^9。

特判 

n=1 m%n肯定不行

n=2 m是偶数 奇数个奇数和≠偶数 不行

否则找最小的k

现在开始维护p，各种特判

由于最后多出来的一部分=k-1是不能合并 所以必须拆

最后维护p

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (1000000000)
int n,m,k;
int main()
{
	while (cin>>n>>m>>k)
	{
		if (n==1||n==2&&!(m%2))
		{
			puts("-1");continue;
		}
		while (!(k%n)) k--;
		if (k==1)
		{
			if (m%n) cout<<m<<endl;
			else puts("-1");
			continue;
		}
		int ans=(m-1)/k+1;
		if (ans==1&&!(m%n)) ans++;
		if (!((k-1)%n)&&m%k==k-1) ans++;
		if (!(ans%n)) ans++;
		cout<<ans<<endl;
	}
	return 0;
}

FZU 2100(排队-Treap维护队列最大值)

Posted on by
 Problem 2100 排队

Accept: 16    Submit: 160
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一些人在排队买车票，假设每个人都有不同的买票紧急程度，如果某个人的紧急程度比排在他前一个的人的紧急程度更大，则这个人可以和前一个人调换位置，并且假设每个人都有一个耐心值，若某人的耐心值为x，则他最多可以向前调换x次，当然前提是他之前x个人的紧急程度都比他小，若遇到前面一个人紧急程度比他大的他将停止往前调换。现假设有N个人，按顺序一个个进入队列，并且每进去一个人立即按照紧急程度和其耐心值向前进行调换，调换停止后下一个人才进入队列。给出这N个人的紧急程度和耐心值，问最终的排队情况。

Input

第一行输入一个整数T，表示数据组数。接下来T组数据，对于每组数据，第一行输入一个整数n (1<=n<=10^5)，接下来第2到n+1行每行输入两个整数a[i],c[i] (1<=a[i]<=n,0<=c[i]<=n)，分别表示第i个人的紧急程度在n个人种排第几及其耐心值，a[i]越大表示紧急程度越大。

Output

对于每组数据，请输出一行n个数，以一个空格隔开，表示最终队列的排队情况，第i个数表示最终排在第i个位置的人是第几个进入队列的。

Sample Input

152 31 44 33 15 2

Sample Output

3 1 5 4 2

Source

FOJ有奖月赛-2012年11月

这题因为把转移中的maxv打成v而Wa了一天（一天啊！）
言归正传，这题是要维护平衡树子树最大值，Treap的rotate是参考刘汝佳的写法。
就是insert时要根据左右子树的s(size)和maxv比大小

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
int t,n;
struct node
{
	int v,r,s,maxv,i;
	node *ch[2];
	node(int _v,int _i):s(1),r(rand()),v(_v),maxv(_v),i(_i){ch[0]=ch[1]=NULL;}
	bool operator<(const node &b){return r<b.r;}
	void maintain()
	{
		s=1;maxv=v;
		if (ch[0]!=NULL) {s+=ch[0]->s;maxv=max(maxv,ch[0]->maxv);}
		if (ch[1]!=NULL) {s+=ch[1]->s;maxv=max(maxv,ch[1]->maxv);}
	}
}*root=NULL;
void rotate(node *&o,int d)
{
	node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
	o->maintain();k->maintain();o=k;
}
void del(node *&o)
{
	if (o==NULL) return;
	del(o->ch[0]);
	del(o->ch[1]);
	delete o;
	o=NULL;
}
bool flag=1;
void print(node *&o)
{
	if (o->ch[0]!=NULL) print(o->ch[0]);
	if (flag) printf(" ");else flag=1;
	printf("%d",o->i);
	if (o->ch[1]!=NULL) print(o->ch[1]);
}
void insert(node *&o,int x,int k,int i)
{
	if (o==NULL){o=new node(x,i);return;	}
	int d;
	if (o->ch[1]==NULL)
	{
		if (k&&o->v<x) d=0;else d=1;
	}
	else if (o->ch[1]->s>=k||o->ch[1]->maxv>x||o->v>x) d=1;
	else d=0;
	if (d==0)
	{
		if (o->ch[1]!=NULL) k-=o->ch[1]->s;
		k--;
	}
	insert(o->ch[d],x,k,i);o->maintain();
	if (o->ch[d]<o) rotate(o,d^1);o->maintain();
}
int main()
{
//	freopen("fzu2100.in","r",stdin);
//	freopen("fzu2100.out","w",stdout);
	scanf("%d",&t);
	while (t--)
	{
		del(root);root=NULL;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			insert(root,x,y,i);
		}
		flag=0;print(root);printf("n");
	}
	return 0;
}

POJ 2704(Pascal's Travels-裸dp)

Posted on by
Language:
Pascal's Travels
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4821   Accepted: 2139

Description

An n x n game board is populated with integers, one nonnegative integer per square. The goal is to travel along any legitimate path from the upper left corner to the lower right corner of the board. The integer in any one square dictates how large a step away
from that location must be. If the step size would advance travel off the game board, then a step in that particular direction is forbidden. All steps must be either to the right or toward the bottom. Note that a 0 is a dead end which prevents any further
progress. 

Consider the 4 x 4 board shown in Figure 1, where the solid circle identifies the start position and the dashed circle identifies the target. Figure 2 shows the three paths from the start to the target, with the irrelevant numbers in each removed. 

Input

The input contains data for one to thirty boards, followed by a final line containing only the integer -1. The data for a board starts with a line containing a single positive integer n, 4 <= n <= 34, which is the number of rows in this board. This is followed
by n rows of data. Each row contains n single digits, 0-9, with no spaces between them.

Output

The output consists of one line for each board, containing a single integer, which is the number of paths from the upper left corner to the lower right corner. There will be fewer than 263 paths for any board. 

Sample Input

4
2331
1213
1231
3110
4
3332
1213
1232
2120
5
11101
01111
11111
11101
11101
-1

Sample Output

3
0
7

Hint

Brute force methods examining every path will likely exceed the allotted time limit. 64-bit integer values are available as long values in Java or long long values using the contest's C/C++ compilers.

Source

Mid-Central USA 2005

就是dp……

一开始忘打‘n’ wa了……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN (34+1)
int a[MAXN][MAXN],n;
long long f[MAXN][MAXN];
int main()
{
	while (scanf("%d",&n)&&n+1)
	{
		for (int i=1;i<=n;i++)
		{
			char s[MAXN];
			scanf("%s",s+1);
			for (int j=1;j<=n;j++) a[i][j]=s[j]-'0';
		}
		memset(f,0,sizeof(f));f[1][1]=1;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (a[i][j])
				{
					if (i+a[i][j]<=n) f[i+a[i][j]][j]+=f[i][j];
					if (j+a[i][j]<=n) f[i][j+a[i][j]]+=f[i][j];
				}
		printf("%lldn",f[n][n]);
	}
	return 0;
}


CH 白色情人节1(②第一天-KM算法)

Posted on by

背景

下过雨的夏天傍晚 我都会期待
唱歌的蝉 嘿 把星星都吵醒 月光晒了很凉快
就是这样回忆起来 第一次告白
尴尬的我 看 爱装得很哲学的你其实很可爱
你说活在明天 活在期待 不如活得今天很自在
我说我懂了 会不会太快 未来 第一天要展开

描述

时间回溯到男女主认识的第一天——女主同学举办的联谊会，男主迟到了那天的联谊会，而男主到达现场时女主也刚好没有男伴，这就是他们的第一次相遇。
男主回想起来不禁一阵感慨(为啥这么好的妹子你们都不搭讪呢)，突然男主想到，如果当时已经配对的n对男女好感值之和不是最大，会不会自己就遇不上女主了呢？

输入格式

第一行两个正整数n和queen，表示已有n对男女可以配对和女主的编号queen。(男编号为X1~Xn，女编号为Y1~Yn+1)
接下来n*(n+1)行，每行三个正整数Xi，Yi，Zi，表示男Xi女Yi之间的好感度为Zi，保证每对(Xi,Yi)没有重复，即两人的关系至多一条。
不存在男与男、女与女之间的好感度！

输出格式

前n行输出联谊会上n对男女的配对情况(会多出来一名女生)，每行两个正整数Xi和Yi(空格隔开)，任意一种符合条件的方案均可。
第n+1行，对于你输出的方案，如果女主未配对，输出"YES"(不含引号)，表示女主会遇到男主，否则输出"NO"(不含引号)。

样例输入

2 3
1 1 15
1 2 20
1 3 17
2 1 22
2 2 14
2 3 14

样例输出

1 2
2 1
YES

数据范围与约定

对于100%的数据，1leq nleq 520,1leq Z_{i}leq 201314。

样例解释

如图，已经配对的关系有是男1号女2号和男2号女1号。

来源

*****关系~

km算法

就是二分图匹配时维护lx[i],ly[i]

满足

1.对于任意边lx[i]+ly[i]>=w[i,j]

2.如果存在一组匹配，其中任意边满足lx[i]+ly[i]=w[i,j]，它一定是最大匹配（如果随意调换一边，必然出现lx[i]+ly[j]+lx[i']+ly[j']=w[i,j]+w[i',j']≥w[i,j']+w[i',j]

于是每次找出slock，表示对所有找过的i,不为0的min(lx[i]+ly[j]-w[i,j])

把slock的值从左移至右，既不改变原图能走的边，又能使图得到扩充。

//一开始应该把lx[i]设成max(w[i,j],0),ly[i]设成0

每次扩充必须保证图中的边满足lx[i]+ly[i]=w[i,j]，否则用slock扩充


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
using namespace std;
#define INF (100000000)
#define MAXN (520+10)
#define MAXWi (201314)
int n,m,yi,slack;
int w[MAXN][MAXN],lx[MAXN],ly[MAXN],a[MAXN];//a=?->yi
bool vx[MAXN],vy[MAXN];
bool find(int x)
{
	vx[x]=1;
	for (int i=1;i<=m;i++)
		if (!vy[i])
		{
			int t=lx[x]+ly[i]-w[x][i];
			if (t==0)
			{
				vy[i]=1;
				if (a[i]==0||find(a[i])) {a[i]=x;return 1;}
			}else slack=min(slack,t);
		}
	return 0;
}
int main()
{
//	freopen("input","r",stdin);
	scanf("%d%d",&n,&yi);m=n+1;
	memset(lx,0,sizeof(lx));
	memset(ly,0,sizeof(ly));
	memset(a,0,sizeof(a));
	for (int i=1;i<=n*(n+1);i++)
	{
		int u,v,wei;scanf("%d%d%d",&u,&v,&wei);w[u][v]=wei;
		lx[u]=max(lx[u],wei);
	}
	for (int i=1;i<=n;i++)
	{
		memset(vx,0,sizeof vx);
		memset(vy,0,sizeof vy);
		slack=INF;
		while (!find(i))
		{
			for (int j=1;j<=n;j++) if (vx[j]) lx[j]-=slack;
			for (int j=1;j<=m;j++) if (vy[j]) ly[j]+=slack;
			memset(vx,0,sizeof vx);
			memset(vy,0,sizeof vy);
			slack=INF;
		//	find(i);
		}
	}
	for (int i=1;i<=m;i++)
	{
		if (a[i]) printf("%d %dn",a[i],i);
	}
	if (a[yi]) printf("NOn");
	else printf("YESn");
	return 0;
}

CF 286C(Main Sequence-贪心括号匹配)

Posted on by
C. Main Sequence
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

As you know, Vova has recently become a new shaman in the city of Ultima Thule. So, he has received the shaman knowledge about the correct bracket sequences. The shamans of Ultima Thule have been using lots of different types of brackets since prehistoric times.
A bracket type is a positive integer. The shamans define a correct bracket sequence as follows:

  • An empty sequence is a correct bracket sequence.
  • If {a1, a2, ..., al} and {b1, b2, ..., bk} are
    correct bracket sequences, then sequence {a1, a2, ..., al, b1, b2, ..., bk} (their
    concatenation) also is a correct bracket sequence.
  • If {a1, a2, ..., al} —
    is a correct bracket sequence, then sequence  also is a correct bracket sequence, where v (v > 0) is
    an integer.

For example, sequences {1, 1,  - 1, 2,  - 2,  - 1} and {3,  - 3} are
correct bracket sequences, and {2,  - 3} is not.

Moreover, after Vova became a shaman, he learned the most important correct bracket sequence {x1, x2, ..., xn},
consisting of nintegers. As sequence x is the most
important, Vova decided to encrypt it just in case.

Encrypting consists of two sequences. The first sequence {p1, p2, ..., pn} contains
types of brackets, that is, pi = |xi| (1 ≤ i ≤ n).
The second sequence {q1, q2, ..., qt} contains t integers
— 这些地方必须取负数 {x1, x2, ..., xn}.

Unfortunately, Vova forgot the main sequence. But he was lucky enough to keep the encryption: sequences {p1, p2, ..., pn} and{q1, q2, ..., qt}.
Help Vova restore sequence x by the encryption. If there are multiple sequences that correspond to the encryption, restore any of them. If there are no
such sequences, you should tell so.

Input

The first line of the input contains integer n (1 ≤ n ≤ 106).
The second line contains n integers: p1, p2, ..., pn (1 ≤ pi ≤ 109).

The third line contains integer t (0 ≤ t ≤ n),
followed by t distinct integers q1, q2, ..., qt (1 ≤ qi ≤ n).

The numbers in each line are separated by spaces.

Output

Print a single string "NO" (without the quotes) if Vova is mistaken and a suitable sequence {x1, x2, ..., xn} doesn't
exist.

Otherwise, in the first line print "YES" (without the quotes) and in the second line print n integers x1, x2, ..., xn (|xi| = pi; xqj < 0).
If there are multiple sequences that correspond to the encrypting, you are allowed to print any of them.

Sample test(s)
input
2
1 1
0
output
YES
1 -1
input
4
1 1 1 1
1 3
output
YES
1 1 -1 -1
input
3
1 1 1
0
output
NO
input
4
1 2 2 1
2 3 4
output
YES
1 2 -2 -1

贪心，从后向前做，尽可能取左括号。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
using namespace std;
#define MAXN (1000000+10)
#define MAXP (1000000000+10)
int n,m,a[MAXN],ans[MAXN],tot;
bool b[MAXN];
int s[MAXN],size=0;
int main()
{
	memset(b,0,sizeof(b));
	scanf("%d",&n);tot=n+1;
	if (n%2) {printf("NOn");return 0;}
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		int p;
		scanf("%d",&p);
		b[p]=1;
	}
	for (int i=n;i;i--)
	{
		if (size==0||s[size]!=a[i]||b[i])
		{
			s[++size]=a[i];ans[--tot]=-a[i];
		}
		else ans[--tot]=s[size--];
	}
	if (size) printf("NOn");
	else
	{
		printf("YESn");
		for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%dn",ans[n]);
	}

	return 0;
}

圈地(斜率排序+坐标系旋转)

Posted on by

Problem 2 圈地(land.cpp/c/pas)

【题目描述】

2维平面上有n个木桩，你有一次圈地的机会并得到圈到的土地，为了体现你的高风亮节，你要使你圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形，多边形的顶点就是一个木桩，圈得的土地就是这个多边形内部的土地。

 

【输入格式】

第一行一个整数n，表示木桩个数。
　　接下来n行，每行2个整数表示一个木桩的坐标，坐标两两不同。

【输出格式】

仅一行，表示最小圈得的土地面积，保留2位小数。

【样例输入】

样例1：
3

0 0

0 1

1 0

样例2：
4

0 0

0 1

0 2

1 1

【样例输出】

样例1：
0.50
样例2：
0.00
【数据范围】

    对于10%的数据，n<=100；
　对于30%的数据，n<=300；
　对于50%的数据，n<=500；
　对于100%的数据，n<=1000。

显然这题的多边形一定是三角形。

首先求出所有边，按k排序（必须先求出来，不能直接在排序的时候求）

然后考虑这些边，会发现正好是绕坐标系旋转一圈。

也就是说如果按照以这边为y轴从左至右排序，那么每转移一条边，只需要调换该边2个点的位置

这题没给范围，但是必须用long long

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN (1000+10)
#define INF (1000000000)
#define eps 1e-10
struct P
{
	int x,y;
	long long operator*(const P &b)
	{
		return (long long)x*b.y-(long long)b.x*y;
	}
	friend bool operator<(P a,P b){if (a.x^b.x)	return a.x<b.x;return a.y<b.y;}
}a[MAXN];
long long abs2(long long x){if (x>0) return x;return -x;}
int n,h[MAXN];
struct E
{
	int i,j;
	double k;
	E(){}
	E(int _i,int _j):i(_i),j(_j){if (a[i].x==a[j].x) k=1e10;else k=(double)(a[i].y-a[j].y)/(a[i].x-a[j].x);}
	friend bool operator<(E a,E b){return a.k<b.k;	}
}e[MAXN*MAXN/2];
long long S2(P A,P B,P C)
{
	return abs2(A*B+B*C+C*A);
}
int size=0;
int main()
{
	freopen("land.in","r",stdin);
	freopen("land.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	long long ans=(long long)1<<60;
	/*
	for (int i=1;i<=n-2;i++)
		for (int j=i+1;j<n;j++)
			for (int k=j+1;k<=n;k++)
				ans=min(ans,abs2(a[i]*a[j]+a[j]*a[k]+a[k]*a[i]));
	*/

	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) h[i]=i;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			e[++size]=E(i,j);
		}

	sort(e+1,e+1+size);

	for (int i=1;i<=size&&ans;i++)
	{
		if (h[e[i].i]>1&&h[e[i].i]<n) ans=min(ans,S2(a[h[e[i].i]-1],a[h[e[i].i]],a[h[e[i].i]+1]));
		if (h[e[i].j]>1&&h[e[i].j]<n) ans=min(ans,S2(a[h[e[i].j]-1],a[h[e[i].j]],a[h[e[i].j]+1]));
		swap(a[h[e[i].i]],a[h[e[i].j]]);
		swap(h[e[i].i],h[e[i].j]);
	}

	printf("%.2lf",(double)ans/2);
	return 0;
}


CF 286B(Shifting-deque)

Posted on by
B. Shifting
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

John Doe has found the beautiful permutation formula.

Let's take permutation p = p1, p2, ..., pn.
Let's define transformation f of this permutation:

 k (k > 1) 是每段长度, r 是最大满足 rk ≤ n 的整数
 把 r
段和尾剩余部分（如果有）左移.

求序列 f(f( ... f(p = [1, 2, ..., n], 2) ... , n - 1), n) .

Input

一行 n (2 ≤ n ≤ 106).

Output

Print n distinct space-separated integers from 1 to n —
a beautiful permutation of size n.

Sample test(s)
input
2
output
2 1
input
3
output
1 3 2
input
4
output
4 2 3 1
Note

A note to the third test sample:

  • f([1, 2, 3, 4], 2) = [2, 1, 4, 3]
  • f([2, 1, 4, 3], 3) = [1, 4, 2, 3]
  • f([1, 4, 2, 3], 4) = [4, 2, 3, 1]
这题我是用WJMZBMR的神模拟过的。
先普及一下deque< >
deque<int> deq;   //建立双端队列
deq.push_back(x) 
deq.push_front(x) 
deq.pop_back(x) 
deq.pop_back(x) 
然后可以模拟了，每次把每段的最后搬上来。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define MAXN (1000000+10)
deque<int> deq;
int n;
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) deq.push_back(i);
	for (int i=2;i<=n;i++)
	{
		int l=(n-1)/i*i;deq.push_back(deq[l]);
		while (l-i>=0)
		{
			deq[l]=deq[l-i];
			l-=i;
		}
		deq.pop_front();
	}
	for (int i=0;i<deq.size();i++) cout<<deq[i]<<' ';
	return 0;
}

CF 286A(Lucky Permutation-数列找规律)

Posted on by
A. Lucky Permutation
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A permutation p of size n is the sequence p1, p2, ..., pn,
consisting of n distinct integers, each of them is from 1 to n (1 ≤ pi ≤ n).

A lucky permutation is such permutation p, that any integer i (1 ≤ i ≤ n) meets
this condition ppi = n - i + 1.

You have integer n. Find some lucky permutation p of
size n.

Input

The first line contains integer n (1 ≤ n ≤ 105)
— the required permutation size.

Output

Print "-1" (without the quotes) if the lucky permutation p of size n doesn't
exist.

Otherwise, print n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) after
a space — the required permutation.

If there are multiple answers, you can print any of them.

Sample test(s)
input
1
output
1
input
2
output
-1
input
4
output
2 4 1 3
input
5
output
2 5 3 1 4

找规律

如图所示



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
using namespace std;
int n;
int main()
{
	cin>>n;
	if (n%4>1)
	{
		cout<<"-1n";
		return 0;
	}
	for (int i=1;i<=n/2;i++)
	{
		if (i%2) cout<<i+1<<' ';
		else cout<<(n-i+2)<<' ';
	}
	int m=n/2;
	if (n%4==1)
	{
		cout<<m+1;
		if (m+1<n) cout<<' ';
		m++;
	}
	for (int i=m+1;i<n;i++)
	{
		if ((i-m)%2) cout<<n-i<<' ';
		else cout<<i-1<<' ';
	}
	if (m+1<n) cout<<(n-1);
	cout<<endl;
	return 0;
}

CF 287B(Pipeline-二分)

Posted on by
B. Pipeline
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vova, the Ultimate Thule new shaman, wants to build a pipeline. As there are exactly n houses in Ultimate Thule, Vova wants the city to have exactly n pipes,
each such pipe should be connected to the water supply. A pipe can be connected to the water supply if there's water flowing out of it. Initially Vova has only one pipe with flowing water. Besides, Vova has several splitters.

A splitter is a construction that consists of one input (it can be connected to a water pipe) and x output pipes. When a splitter is connected to a water
pipe, water flows from each output pipe. You can assume that the output pipes are ordinary pipes. For example, you can connect water supply to such pipe if there's water flowing out from it. At most one splitter can be connected to any water pipe.


The figure shows a 4-output splitter

Vova has one splitter of each kind: with 2, 3, 4,
..., k outputs. Help Vova use the minimum number of splitters to build the required pipeline or otherwise state that it's impossible.

Vova needs the pipeline to have exactly n pipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.

Input

The first line contains two space-separated integers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 109).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams
or the %I64dspecifier.

Output

Print a single integer — the minimum number of splitters needed to build the pipeline. If it is impossible to build a pipeline with the given splitters, print -1.

Sample test(s)
input
4 3
output
2
input
5 5
output
1
input
8 4
output
-1

这题显然优先找大的

直到找不下去了，判断无解或者拿个与需要的分水器相等的（显然有）

因为一个k的分水器只能增加k-1条通道

所以列方程


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (1000000000000000000)
#define MAXK (1000000000)
long long n,k;
long long bin_s(long long l,long long r)
{
	if (n==1) return 0;
	while (r-l>1)
	{
		long long  m=(l+r)/2;
		if ((m+k-1)*(k-m)>2*(n-1)) l=m;
		else r=m;
	}
	if ((l+k-1)*(k-l)>2*(n-1)) l=r;
	if ((l+k-1)*(k-l)<2*(n-1)) l--;

	if (l==0) return -1;
	return k-l;
}
int main()
{
	cin>>n>>k;
	cout<<bin_s(1,k-1)<<endl;


	return 0;
}

CF 287A(IQ Test-枚举3个字符相等的矩阵)

Posted on by
A. IQ Test
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

In the city of Ultima Thule job applicants are often offered an IQ test.

The test is as follows: the person gets a piece of squared paper with a 4 × 4 square painted on it. Some of the square's cells are painted black and others are painted
white. Your task is to repaint at most one cell the other color so that the picture has a 2 × 2 square,
completely consisting of cells of the same color. If the initial picture already has such a square, the person should just say so and the test will be completed.

Your task is to write a program that determines whether it is possible to pass the test. You cannot pass the test if either repainting any cell or no action doesn't result in a 2 × 2 square,
consisting of cells of the same color.

Input

Four lines contain four characters each: the j-th character of the i-th
line equals "." if the cell in the i-th row and the j-th
column of the square is painted white, and "#", if the cell is black.

Output

Print "YES" (without the quotes), if the test can be passed and "NO"
(without the quotes) otherwise.

Sample test(s)
input
####
.#..
####
....
output
YES
input
####
....
####
....
output
NO
Note

In the first test sample it is enough to repaint the first cell in the second row. After such repainting the required 2 × 2 square is on the intersection of the 1-st
and 2-nd row with the 1-st and 2-nd
column.

枚举看是否有一个矩形有3个字符相等
一开始居然把4个判断打错了？《上午也是……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
using namespace std;
#define MAXLen (4+10)
char a[MAXLen][MAXLen];
bool flag=0;
int main()
{
	for (int i=1;i<=4;i++) scanf("%s",a[i]+1);
	for (int i=1;i<4;i++)
		for (int j=1;j<4;j++)
		{
			if (a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j]) flag=1;
			if (a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j+1]) flag=1;
			if (a[i][j]==a[i+1][j]&&a[i][j]==a[i+1][j+1]) flag=1;
			if (a[i+1][j]==a[i][j+1]&&a[i+1][j]==a[i+1][j+1]) flag=1;

		}
	if (flag) printf("YESn");
	else printf("NOn");
	return 0;
}