ZOJ Monthly, October 2010 ABEFI

ZOJ 3406	Another Very Easy Task

#include <cstdio>
#include <cstring>
const int N = 100005;
char s[N];
int main() {
	bool f = 0;
	int size = 0;
	char ch;
	while(scanf("%c", &ch)!=EOF) {
		if( !(ch >= 'a' && ch <='z') && !(ch >='A' && ch <= 'Z')) {
			if(size <= 2) {
				s[size] = '';
				printf("%s", s);
			} else {
				printf("%c%d%c", s[0], size-2, s[size-1]);
			}
			size = 0;
			printf("%c", ch);
		} else {
			s[size++] = ch;
		}
	}
	return 0;
}

ZOJ 3407	Doraemon's Cake Machine

ZOJ 3407

Doraemon's Cake Machine

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int Rand(int l,int r){
	int ans = rand()%r+1;
	while(ans<l) ans = rand()%r+1;
	return ans;
}
int main() {
//	freopen("b.txt","w+",stdout);
	int T;
	scanf("%d", &T);
	ll n, m;
	while(T -- > 0) {
		cin >> n >> m;
//		n = Rand(1,6000000), m = Rand(0,10000);
		if(m == 0) {
			if(n == 1) puts("0");
			else puts("-1");
			continue;
		}
		if(m >= n) {
			puts("-1");
		}else {
			ll d = 2 * (n-m) - 1;
			ll ans = -1;
			ans = 2 * m - n;// shu
			if(ans < 0) ans = -1;
			if(n==m+1)ans = 0; // heng
			for(ll i = 1; i * i <= d; i += 2) {
				if( d % i == 0 ) {
					ll a = (i + 1) / 2;
					ll b = (d / i - 1) / 2;
					ll c = m - a - b;
					if(c < 0) continue;
					if(ans == -1 || ans>c ){
					//	printf("%I64d %I64d %I64d %I64d
", d, a, b, c);
						ans = c;
					}
				}
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

ZOJ 3410	Layton's Escape

ZOJ 3410

Layton's Escape

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <iostream>
#include <algorithm>
/*
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

int main() {
	return 0;
}
*/
typedef long long ll;
const ll Inf = (ll)(1e15);
const int N = 25000 + 10;
const int M = 5000 + 10;
struct node {
	int cos, lim;
};

node a[N];
ll d[2][M];
std::priority_queue<int> Q;

bool cmp(const node& i, const node& j) {
	return i.lim < j.lim;
}

int main() {
	int n, K, cnt;
	while (~scanf("%d%d", &n, &K)) {
		for (int i = 0; i < n; ++i)
			scanf("%d%d", &a[i].cos, &a[i].lim);
		std::sort(a, a + n, cmp);
		while (!Q.empty())
			Q.pop();
		cnt = 0;
		ll sum = 0;
		for (int i = 0; i < n; ++i) {
			sum += a[i].cos;
			Q.push(a[i].cos);
			while (sum > a[i].lim && !Q.empty()) {
				sum -= Q.top();
				++cnt;
				Q.pop();
			}
			if (sum > a[i].lim || cnt >= K) {
				cnt = -1;
				break;
			}
		}

		printf("%d
", cnt);
	}
	return 0;
}

ZOJ 3411	Special Special Judge

ZOJ 3411

Special Special Judge

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {
	BigInteger gcd(BigInteger a, BigInteger b) {
		BigInteger tmp;
		while(a.equals(BigInteger.ZERO)==false){
			b = b.mod(a);
			tmp = b;
			b = a;
			a = tmp;
		}
		return b;
	}
	
	public void work() {
		int n, m, a, b, x;
		BigInteger[][] d = new BigInteger[55][55];
		BigInteger up, down, v;
		
		while (cin.hasNext()) {
			n = cin.nextInt();
			m = cin.nextInt();
			a = cin.nextInt();
			b = cin.nextInt();
			v = BigInteger.valueOf(b - a + 1);
			for (int i = 0; i <= n; ++i)
				for (int j = 0; j <= m; ++j)
					d[i][j] = BigInteger.ZERO;
			d[0][0] = BigInteger.ONE;
			for (int i = 0; i < n; ++i) {
				x = cin.nextInt();
				for (int j = 0; j <= m; ++j)
					if (d[i][j].compareTo(BigInteger.ZERO) > 0)
						for (int z = a; z <= b; ++z)
							if (Math.abs(x - z) + j <= m) {
								d[i + 1][Math.abs(x - z) + j] = d[i + 1][Math
										.abs(x - z) + j].add(d[i][j]);
							}
			}
			up = BigInteger.ZERO;
			for (int i = 0; i <= m; ++i)
				up = up.add(d[n][i]);
			down = BigInteger.ONE;
			for (int i = 1; i <= n; ++i)
				down = down.multiply(v);
			v = gcd(up, down);
			up = up.divide(v);
			down = down.divide(v);
			out.println(up + "/" + down);
		}
		out.close();
	}

	Main() {
		cin = new Scanner(System.in);
		out = new PrintWriter(System.out);
	}

	public static void main(String[] args) {
		Main e = new Main();
		e.work();
	}

	public Scanner cin;
	public PrintWriter out;

}

ZOJ 3414	Trail Walk

ZOJ 3414

Trail Walk

#include <cstdio>
#include <cstring>
#include <math.h>
#include <iostream>
using namespace std;
#define eps (1e-8)
const int N = 100005;
bool Is0(double x){
	return (x>0?x:-x)<eps;
}
struct node{
	double x,y;
	void put(){
		printf("(%.3f, %.3f)
",x,y);
	}
}a[N], last;
double dis(node aa,node bb){
	return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}
int n,m;
int main() {
	int i,j,Cas = 1;
	while(~scanf("%d %d",&n,&m)) {
		m++;
		printf("Route %d
",Cas++);
		a[0].x=a[0].y=0;
		double len = 0;
		for(i=1;i<=n;i++) {
			scanf("%lf %lf",&a[i].x,&a[i].y);
			len += dis(a[i],a[i-1]);
		}
		double now = len/(double)m;
	//	cout<<"len:"<<len<<"now: "<<now<<endl;
		int num = 1;
		last = a[0];
		for(i = 1; i <= n; i++) {
			if(num>=m)break;
		//	last.put();
			double t = dis(last, a[i]);
			if(t<now && !Is0(t-now)) {
			//	puts("1");
				now -= t;
				last = a[i];
				continue;
			}
			else if(Is0(t-now))
			{
			//	puts("2");
				printf("CP%d: ",num++);
				last = a[i];
				now = len/(double)m;
				a[i].put();
			}
			else {
			//	puts("3");
				printf("CP%d: ",num++);
				double b = now/t;
				double x = a[i].x-last.x, y = a[i].y-last.y;
				node tmp = last;
				tmp.x += b*x; tmp.y += b*y;
				
				tmp.put();
				last = tmp;
				now = len/(double)m;
				i--;
			}
		}
	}
	return 0;
}
/*
5.8863495173726744416200360616723
1.4715873793431686104050090154181


*/