codeforces 랭킹전 3

전송문
제면
A. Wormhole Sort time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Farmer John’s cows have grown tired of his daily request that they sort themselves before leaving the barn each morning. They have just completed their PhDs in quantum physics, and are ready to speed things up a bit.
This morning, as usual, Farmer John’s N cows (1≤N≤105), conveniently numbered 1…N, are scattered throughout the barn at N distinct locations, also numbered 1…N, such that cow i is at location pi. But this morning there are also M wormholes (1≤M≤105), numbered 1…M, where wormhole i bidirectionally connects location ai with location bi, and has a width wi (1≤ai,bi≤N,ai≠bi,1≤wi≤109).
At any point in time, two cows located at opposite ends of a wormhole may choose to simultaneously swap places through the wormhole. The cows must perform such swaps until cow i is at location i for 1≤i≤N.
The cows are not eager to get squished by the wormholes. Help them maximize the width of the least wide wormhole which they must use to sort themselves. It is guaranteed that it is possible for the cows to sort themselves.
Input The first line contains two integers, N and M.
The second line contains the N integers p1,p2,…,pN. It is guaranteed that p is a permutation of 1…N. For each i between 1 and M, line i+2 contains the integers ai, bi, and wi.
Output A single integer: the maximum minimal wormhole width which a cow must squish itself into during the sorting process. If the cows do not need any wormholes to sort themselves, output −1.
Examples inputCopy 4 4 3 2 1 4 1 2 9 1 3 7 2 3 10 2 4 3 outputCopy 9 inputCopy 4 1 1 2 3 4 4 2 13 outputCopy -1 Note The first example is one possible way to sort the cows using only wormholes of width at least 9:
Cow 1 and cow 2 swap positions using the third wormhole. Cow 1 and cow 3 swap positions using the first wormhole. Cow 2 and cow 3 swap positions using the third wormhole.
The second example is no wormholes are needed to sort the cows.
분석하다.
먼저 연결 블록 내부가 서로 도달할 수 있음을 알아야 한다. 벌레구멍을 통해order수조를 교환할 수 있다. 만약에 어떤 수가 그 번호와 다르면order[i]!=i는 i와order[i] 두 위치를 교환해야 한다는 것을 설명한다. 표시를 하고 가장자리를 너비에 따라 큰 순서에서 작은 순서로 배열하여 하나의 연결 블록을 유지하고 유지하며 끊임없이 가장자리를 이 연결 블록에 넣어야 한다. 연결 블록 안의 유효 원소 개수 ==cnt일 때 이 너비는 가장 작은 너비이다. 뿌리 노드의 값은 집합 개수를 대표하고 매번 합치면 두 뿌리의 값을 더해서 새로운 뿌리에 부여한다.
코드

#include
using namespace std;

const int INF=1e9;
const int MAX_N=1e5+5;
int order[MAX_N],Y[MAX_N],fa[MAX_N],n,m;

struct edge{ int x,y,wid; }a[MAX_N];
bool cmp(edge a,edge b){ return a.wid>b.wid; }

void init(){ for(int i=1;i<=n;i++) fa[i]=i; }
int get(int x){ return x==fa[x]? x:fa[x]=get(fa[x]); }

int main()
{
	scanf("%d%d",&n,&m); init();			//                   
	int cnt=0,ans=-1;
	for(int i=1;i<=n;i++) { 
		scanf("%d",&order[i]); 
		if(i!=order[i]) {
			if(!Y[i]) cnt++,Y[i]=1;//cnt                	Y                     
			if(!Y[order[i]]) cnt++,Y[order[i]]=1;
		}
	}
	for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].wid);
	if(cnt==0) { puts("-1"); return 0; }
	
	sort(a+1,a+1+m,cmp);
	
	for(int i=1;i<=m;i++){
		int x=get(a[i].x);
		int y=get(a[i].y);
		if(x!=y) { 
			fa[x]=y;  Y[y]+=Y[x]; //    (      )          
			if(Y[y]==cnt) { ans=a[i].wid; break; }
		}
	}
	printf("%d
",ans);
	
	return 0;
}

제면
D. Race time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Bessie is running a race of length K (1≤K≤109) meters. She starts running at a speed of 0 meters per second. In a given second, she can either increase her speed by 1 meter per second, keep it unchanged, or decrease it by 1 meter per second. For example, in the first second, she can increase her speed to 1 meter per second and run 1 meter, or keep it at 0 meters per second and run 0 meters. Bessie’s speed can never drop below zero.
Bessie will always run toward the finish line, and she wants to finish after an integer amount of seconds (ending either at or past the goal line at this integer point in time). Furthermore, she doesn’t want to be running too quickly at the finish line: at the instant in time when Bessie finishes running K meters, she wants the speed she has just been traveling to be no more than X (1≤X≤105) meters per second. Bessie wants to know how quickly she can finish the race for N (1≤N≤1000) different values of X.
Input The first line will contain two integers K and N.
The next N lines each contain a single integer X.
Output Output N lines, each containing a single integer for the minimum time Bessie needs to run K meters so that she finishes with a speed less than or equal to X.
Example inputCopy 10 5 1 2 3 4 5 outputCopy 6 5 5 4 4 Note When X=1, an optimal solution is:
Increase speed to 1 m/s, travel 1 meter Increase speed to 2 m/s, travel 2 meters, for a total of 3 meters Keep speed at 2 m/s, travel 5 meters total Keep speed at 2 m/s, travel 7 meters total Keep speed at 2 m/s, travel 9 meters total Decrease speed to 1 m/s, travel 10 meters total
When X=3, an optimal solution is:
Increase speed to 1 m/s, travel 1 meter Increase speed to 2 m/s, travel 3 meters total Increase speed to 3 m/s, travel 6 meters total Keep speed at 3 m/s, travel 9 meters total Keep speed at 3 m/s, travel 12 meters total
Note that the following is illegal when X=3:
Increase speed to 1 m/s, travel 1 meter Increase speed to 2 m/s, travel 3 meters total Increase speed to 3 m/s, travel 6 meters total Increase speed to 4 m/s, travel 10 meters total
This is because at the instant when Bessie has finished running 10 meters, her speed is 4 m/s.
분석하다.
모의 달리기 과정은 vx를 분류하여 토론할 때 균등하게 할 수 있고 줄일 수 있다. v>x와 v=x일 때 v+1~x는 전체 감속 과정의 노정을 구한다. 만약에 종점에 이르지 않으면 동일한 이치를 가속화할 수 있다. v~x의 감속 과정의 노정을 구하고 균등한 속도를 유지할 수 있는지 판단한다(그 중에서 v=x일 때 반드시 균등한 속도를 유지할 수 있다)
코드

#include 
using namespace std;
typedef long long ll;

const int INF=1E9;

int fsum(int l,int r){ return (l+r)*(r-l+1)/2; }

int main()
{	
	int k,n; scanf("%d%d",&k,&n);
	while(n--){
		ll x; scanf("%lld",&x);
		
		ll sum=0,cnt=0,v=1;
		while(sum<k){
			sum+=v; cnt++;			//vx       				
			
			if(v<x) { v++; continue; } //             3    
			
			if(sum+2*(v+1)+ fsum(x+1,v) < k ) v++;	//             		(v+t)*(v-t+1)/2
			else if( v==x || sum+ fsum(x+1,v) <k ) v=v;
			else v--;
			
		}
		printf("%lld
",cnt);
	}
	
	
	return 0; 
} 

제면
E. Word Processor time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Bessie the cow is working on an essay for her writing class. Since her handwriting is quite bad, she decides to type the essay using a word processor.
The essay contains N words (1≤N≤100), separated by spaces. Each word is between 1 and 15 characters long, inclusive, and consists only of uppercase or lowercase letters. According to the instructions for the assignment, the essay has to be formatted in a very specific way: each line should contain no more than K (1≤K≤80) characters, not counting spaces. Fortunately, Bessie’s word processor can handle this requirement, using the following strategy:
If Bessie types a word, and that word can fit on the current line, put it on that line.
Otherwise, put the word on the next line and continue adding to that line. Of course, consecutive words on the same line should still be separated by a single space. There should be no space at the end of any line.
Unfortunately, Bessie’s word processor just broke. Please help her format her essay properly!
Input The first line of input contains two space-separated integers N and K. The next line contains N words separated by single spaces. No word will ever be larger than K characters, the maximum number of characters on a line.
Output Bessie’s essay formatted correctly.
Example inputCopy 10 7 hello my name is Bessie and this is my essay outputCopy hello my name is Bessie and this is my essay Note Including “hello” and “my”, the first line contains 7 non-space characters. Adding “name” would cause the first line to contain 11>7 non-space characters, so it is placed on a new line.
분석하다.
매번 하나의 문자열의 길이를 더하면 길이가 k를 초과할 때 이전의 문자열을 출력하면 된다
코드

#include
using namespace std;
#include
#include
#include
#include
#include
#include
typedef long long ll;

const int INF=1E9;
const int MAX_N=105;
string str[MAX_N];

void print(int l,int r){
	cout<<str[l];
	for(int i=l+1;i<=r;i++) cout<<" "<<str[i]; cout<<endl;
}

int main()
{	
	int n,k; scanf("%d%d",&n,&k);
	
	int len=0 , l=1;	
	for(int i=1;i<=n;i++){
		cin>>str[i];
		if(len+str[i].size()<=k) len+=str[i].size();
		else {
			print(l,i-1);
			len=str[i].size(); 
			l=i;
		}
		
		if(i==n && len) print(l,n);
	}
	
	
	
	return 0; 
} 

제면
H. Photoshoot time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Farmer John is lining up his N cows (2≤N≤103), numbered 1…N, for a photoshoot. FJ initially planned for the i-th cow from the left to be the cow numbered ai, and wrote down the permutation a1,a2,…,aN on a sheet of paper. Unfortunately, that paper was recently stolen by Farmer Nhoj!
Luckily, it might still possible for FJ to recover the permutation that he originally wrote down. Before the sheet was stolen, Bessie recorded the sequence b1,b2,…,bN−1 that satisfies bi=ai+ai+1 for each 1≤i Based on Bessie’s information, help FJ restore the “lexicographically minimum” permutation a that could have produced b. A permutation x is lexicographically smaller than a permutation y if for some j, xi=yi for all i
Input The first line of input contains a single integer N. The second line contains N−1 space-separated integers b1,b2,…,bN−1. Output A single line with N space-separated integers a1,a2,…,aN. Example inputCopy 5 4 6 7 6 outputCopy 3 1 5 2 4 Note a produces b because 3+1=4, 1+5=6, 5+2=7, and 2+4=6.
분석하다.
각각 수조 a와 b에 대해 수조를 구하면 수조를 얻을 수 있다. 수조는 수조를 두 배(수미 두 원소를 빼면) 수미 두 원소의 합을 구할 수 있다. 이에 따라 작은 수조에서 큰 수조를 열거하고 b수조에 따라 a수조를 복원한다. (사전 순서가 가장 작음) a수조가 1~n의 한 배열인지 판단한다. 즉, a수조에서 한 번만 나타나는지 판단하고 크기는 1~n 사이이다.
물론 직접 폭력 매거수 요소도 ok
코드

#include
using namespace std;
#include
#include
#include
#include
#include
#include
typedef long long ll;

const int INF=1E9;
const int MAX_N=1e3+5;
ll a[MAX_N],b[MAX_N]; 
int Y[MAX_N];

int main()
{	
	int n; scanf("%d",&n);
	ll sum=0;
	for(int i=1;i<=n-1;i++) { scanf("%lld",&b[i]); sum+=b[i]; }
	
	int r=(1+n)*n - sum;
	int ok=1;
	for(int i=1;i<=r-1;i++){
		a[1]=i;
		ok=1;///
		memset(Y,0,sizeof(Y));
		
		for(int j=2;j<=n;j++){
			a[j]=b[j-1]-a[j-1];
			
			if(a[j]<=0 || a[j]>n || Y[ a[j] ] ) { ok=0; break; }
			
			Y[a[j]]=1;
		}
		
		if(a[n]!=r-a[1]) ok=0;///
		if(ok) break;
	}
	
	if(ok) for(int i=1;i<=n;i++) printf("%lld ",a[i]);
	
	return 0; 
}