akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
using ll = long long;
using P = pair<int, int>;

const int mod = 1000000007;
struct mint {
  ll x; 
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};

mint f(int n){ 
  if(n == 0)return 1;
  mint x = f(n / 2); 
  x *= x; 
  if(n % 2 == 1)x *= 2;
  return x;
}

mint choose(int n, int a){
  mint x = 1, y = 1;
  for(int i = 0; i < a; ++i){
    x *= n - i;
    y *= i + 1;
  }
  return x / y;
}

mint fact[2000200];
mint inv_fact[2000200];
void init(){
	fact[0] = 1;
	for(int i = 1; i < 2000200; ++i){
		fact[i] = fact[i - 1] * i;
	}

	inv_fact[2000200 - 1] = fact[2000200 - 1].inv();
	for(int i = 2000200 - 1; i >= 1; --i){
		inv_fact[i - 1] = inv_fact[i] * i;
	}
}

mint comb(ll n, ll k){
	if(n < k)return 0;
	else return fact[n] * inv_fact[n - k] * inv_fact[k];
}

mint g(int r, int c){
	mint ret = 0;
	for(int i = 1; i <= c + 1; ++i){
		ret += comb(r + i, i);
	}
	return ret;
}

int main(){
  init();
  int r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;

  mint ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1);
  cout << ans.x << endl;
  return 0;
}


Measured memory_bytes: 31488
#coding:utf-8
#1_5_D 2015.4.1
#This program outputs multiples of 3 or any numbers with 3 under n. In this program, n is int(input()).

for i in range(int(input())):
    if (i + 1) % 3 == 0 or '3' in str(i + 1):
        print(' ' + str(i + 1), end = '')
print()

Measured memory_bytes: 6736
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <utility>
#include <climits>
#include <iomanip>
using namespace std;
#define MAXSIZE 100005
#define MAXL 100
#define MOD_CONST 1000000007
typedef long long int lli;

// vector<int> input_vector(const int &num){
//     vector<int> res(num);
//     for(int i = 0; i < num; ++i){
//         cin >> res[i];
//     }
//     return res;
// }

// int get_ans(int &point, const int &x, const vector<int> &l_vec){
//     int cnt = 1;
//     for(int i : l_vec){
//         point += i;
//         if(point <= x){
//             cnt++;
//         }
//     }
//     return cnt;
// }

int main(){
    int w, h, x, y;
    cin >> w >> h >> x >> y;

    double ans = 0.5 * w * h;
    bool multi;
    if(w % 2 == 0 && h % 2 == 0){
        multi = (x == w / 2 && y == h / 2);
    }else{
        multi = false;
    }
    printf("%.12f", ans);
    cout << " " << multi << endl;
    return 0;
}

Measured memory_bytes: 888
N = int(input())
a = list(map(int, input().split()))

over_3200 = 0
colors = {}
for x in a:
    if 1 <= x and x <= 399:
        colors.setdefault("grey", 0)
        colors["grey"] += 1
    elif 400 <= x and x <= 799:
        colors.setdefault("brown", 0)
        colors["brown"] += 1
    elif 800 <= x and x <= 1199:
        colors.setdefault("green", 0)
        colors["green"] += 1
    elif 1200 <= x and x <= 1599:
        colors.setdefault("sky", 0)
        colors["sky"] += 1
    elif 1600 <= x and x <= 1999:
        colors.setdefault("blue", 0)
        colors["blue"] += 1
    elif 2000 <= x and x <= 2399:
        colors.setdefault("yellow", 0)
        colors["yellow"] += 1
    elif 2400 <= x and x <= 2799:
        colors.setdefault("orange", 0)
        colors["orange"] += 1
    elif 2800 <= x and x <= 3199:
        colors.setdefault("red", 0)
        colors["red"] += 1
    else:
        over_3200 += 1

print(max(1, len(colors)), len(colors) + over_3200)


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
typedef complex< double > Point;
typedef vector< Point > Polygon;
namespace std{
    bool operator < ( Point a, Point b){
        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
};
const double INF = 1e12;
const double EPS = 1e-8;
Point NextPoint(){
    Point P;
    cin>>P.real() >> P.imag();
    return P;
}
struct Line : Polygon{
    Line(){};
    Line(Point p, Point q){push_back(p);push_back(q);}
};
 
struct Circle{
    Point p;
    double r;
    Circle();
    Circle(Point a, double s){p = a,r = s;}
};
double cross(Point p, Point q){
    return imag(conj(p)*q);
}
double dot(Point p,Point q){
    return real(conj(p)*q);
}
int ccw(Point a,Point b,Point c){
    b -= a,c -= a;
    if(cross(b,c) > 0)return 1;
    if(cross(b,c) < 0)return -1;
    if(dot(b,c) < 0 )return 2;
    if(norm(b) < norm(c))return -2;
    return 0;
}
Point projection(Line l,Point p){
    double t = dot(p - l[0],l[0]-l[1]) / norm(l[0]-l[1]);
    return l[0] + t * (l[0]-l[1]);
}
bool intersectSP(Line s,Point p){
    return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS;
}
double distanceSP(Line s,Point p){
    const Point r = projection(s,p);
    if(intersectSP(s,r))return abs(r-p);
    return min(abs(s[0] - p),abs(s[1] - p));
}
int main(){
    int r,n;
    while(cin>>r>>n,r){
        int sc[60] = {};
        for(int i = 0;i < n;i++){
            int l,r,h;
            cin>>l>>r>>h;
            l+=30,r+=30;
            for(int j = l;j < r;j++){
                sc[j] = max(sc[j],h);
            }
        }
        Polygon G;
        G.push_back(Point(-100,0));
        G.push_back(Point(0,0));
        for(int i = 0;i < 55;i++){
             
            if(i != 0){
                if(sc[i] != sc[i-1])
                    G.push_back(Point(i,sc[i]));
                 
                G.push_back(Point(i+1,sc[i]));
            }
        }
        G.push_back(Point(100,0));
 
        for(int i = 0;i < G.size();i++){
            //cout<<G[i].real()<<" "<<G[i].imag()<<endl;
        }
 
        double low = -100,high = 100;
        int D = 100;
        //cout<<sc[20]<<endl;
        while(D--){
            double mid = (low+high)/2;
            Circle C = Circle(Point(30,mid),r);
            double mi = INF;
            for(int i = 0;i < G.size()-1;i++){
                double dist = distanceSP(Line(G[i],G[i+1]),C.p);
                mi = min(mi,dist);
            }
            //cout<<mid<<" "<<mi<<" "<<mid+r<<endl;
            if(mi < r)high = mid;
            else if(sc[30] < mid+r)high = mid;
            else low = mid;
        }
        printf("%.4lf\n",low+r);
    }
}

Measured memory_bytes: 1256
#include"bits/stdc++.h"
using namespace std;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())

int main() {
	int N;
	cin >> N;
	if (N % 10 == 3) {
		puts("bon");
	}
	else if (N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8) {
		puts("pon");
	}
	else {
		puts("hon");
	}
	return 0;
}

Measured memory_bytes: 3624
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(input())

score = {
  'r': r,
  's': s,
  'p': p
}

win_map = {
  'r': 'p',
  's': 'r',
  'p': 's'
}

lose_map = {
  'r': 's',
  's': 'p',
  'p': 'r'
}

result = [''] * n
result_num = 0
for j in range(n):
  if j >= k and result[j - k] == win_map[t[j]]:
    if j + k < n and t[j] == win_map[t[j + k]]:
      result[j] = lose_map[t[j]]
    else:
      result[j] = t[j]
  else:
    result[j] = win_map[t[j]]
    result_num += score[win_map[t[j]]]


print(result_num)

Measured memory_bytes: 4796
#include <bits/stdc++.h>
#define rep(i, to) for (int i = 0; i < (to); ++i)
#define repf(i, from, to) for (int i = (from); i < (to); ++i)
#define unless(cond) if (!(cond))
using namespace std;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

int count_two_factor(int num) {
  int count = 0;
  while(num % 2 == 0) {
    count++;
    num /= 2;
  }

  return count;
}

int main() {
  int n;

  cin >> n;

  int max_count = 0;
  int max_num = 1;
  repf(i, 1, n + 1) {
    int current_count = count_two_factor(i);

    if(current_count > max_count) {
      max_count = current_count;
      max_num = i;
    }
  }
  cout << max_num << endl;
}


Measured memory_bytes: 3592
import java.util.*;

public class Main {
	static final long MODULO = 1_000_000_000 + 7;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int C = sc.nextInt() - 1;
		int T = sc.nextInt();
		int[] a = new int[K];
		int[] b = new int[K];
		int[] t = new int[K];
		for (int i = 0; i < K; ++i) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			t[i] = sc.nextInt();
		}
		// dp[t]=A[1]dp[t-1]+A[2]dp[t-2]+A[3]dp[t-3]
		long[][][] A = new long[6][N][N];
		for (int i = 0; i < K; ++i) {
			for (int j = 0; j < b[i]; ++j) {
				A[t[i]][j][(a[i] - 1) + j] += 1;
			}
			for (int j = 0; j < a[i] - 1; ++j) {
				A[t[i]][b[i] + j][j] += 1;
			}
			for (int j = a[i] + b[i] - 1; j < N; ++j) {
				A[t[i]][j][j] += 1;
			}
		}
		long[][] dp = new long[6][N];
		dp[0][C] = 1;
		for (int i = 1; i <= 5; ++i) {
			for (int j = 0; j < i; ++j) {
				dp[i] = addVec(dp[i], mulVec(A[i - j], dp[j]));
			}
		}
		long[] v = new long[N * 5];
		for (int i = 0; i < 5; ++i) {
			for (int j = 0; j < N; ++j) {
				v[j + i * N] = dp[i][j];
			}
		}
		long[][] mx = new long[5 * N][5 * N];
		for (int i = N; i < 5 * N; ++i) {
			mx[i - N][i] = 1;
		}
		for (int i = 1; i <= 5; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < N; ++k) {
					mx[4 * N + j][N * (5 - i) + k] = A[i][j][k];
				}
			}
		}

		v = mulVec(pow(mx, T), v);
		System.out.println(v[0]);
	}

	static long[][] mul(long[][] a, long[][] b) {
		int n = a.length;
		long[][] ret = new long[n][n];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				for (int k = 0; k < n; ++k) {
					ret[i][j] += a[i][k] * b[k][j] % MODULO;
					ret[i][j] %= MODULO;
				}
			}
		}
		return ret;
	}

	static long[] mulVec(long[][] a, long[] v) {
		int n = v.length;
		long[] ret = new long[n];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				ret[i] += a[i][j] * v[j] % MODULO;
				ret[i] %= MODULO;
			}
		}
		return ret;
	}

	static long[] addVec(long[] a, long[] b) {
		int n = a.length;
		long[] ret = new long[n];
		for (int i = 0; i < n; ++i) {
			ret[i] = (a[i] + b[i]) % MODULO;
		}
		return ret;
	}

	static long[][] pow(long[][] a, long n) {
		int len = a.length;
		long[][] ret = new long[len][len];
		for (int i = 0; i < len; ++i)
			ret[i][i] = 1;
		for (; n > 0; n >>= 1, a = mul(a, a)) {
			if (n % 2 == 1) {
				ret = mul(ret, a);
			}
		}
		return ret;
	}

	static void showMatrix(long[][] a) {
		int n = a.length;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				System.out.print(a[i][j] + " ");
			}
			System.out.println();
		}
	}

	static void showVec(long[] a) {
		for (int i = 0; i < a.length; ++i) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 44164
#include<bits/stdc++.h>

#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define INF (1 << 29)

using namespace std;

int main(){
	int x;
	cin >> x;
	if(x >= 30){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	return 0;
}



Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;

int main(){
	int k,a,b;
	cin>>k>>a>>b;
	for(int i=a;i<=b;i++){
		if(i%k==0){
			cout<<"OK"<<endl;
			return 0;
		}
	}
	cout<<"NG\n";
	return 0;
}

Measured memory_bytes: 3492
from sys import stdin
n, x = map(int, input().split())
l = [int(x) for x in stdin.readline().rstrip().split()]
cnt =[]
c=0
cnt.append(0)
for i in range(n):
	cnt.append(cnt[i]+l[i])


for i in range(n+1):
	if cnt[i] <= x:
		c+=1
print(c)

Measured memory_bytes: 3060
n,x,m = map(int,input().split())

a = x
r = [True for _ in range(m)]
s = []
while(r[a]):
  r[a] = False
  s.append(a)
  a = pow(a,2,m)
ai = s.index(a)
c = (n-len(s))//(len(s)-ai)
d = (n-len(s))-(len(s)-ai)*c
# print(i,ai,c,d)
ans = sum(s)+sum(s[ai:])*c+sum(s[ai:ai+d])
print(ans)

Measured memory_bytes: 75604
import math

while True:
    n = int(input())
    if n == 0:
        break;
    s = list(map(int, input().split()))
    sum = 0

    for i in range(n):
        sum += s[i]
    average = sum / n

    sum = 0
    for i in range(n):
        sum += (s[i] - average) ** 2
    print('{:.10f}'.format(math.sqrt(sum / n)))


Measured memory_bytes: 5708
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

template <typename QvQ> inline QvQ Min(QvQ a,QvQ b){if(a<b) return a;return b;}
template <typename QvQ> inline QvQ Max(QvQ a,QvQ b){if(a>b) return a;return b;}

#define inf 2147483647
#define dinf 0x3f3f3f3f
#define llinf 0x7f7f7f7f7f7f7f7f

#define ll long long
#define rei register int
#define inv inline void
#define ull unsigned long long
#define il inline

#define bl putchar(' ')
#define ed putchar('\n')
#define test cout<<"this:" 

#define read2(a,b) read(a),read(b)
#define write2(a,b) write(a),bl,write(b)
#define read3(a,b,c) read(a),read(b),read(c)
#define write3(a,b,c) write(a),bl,write(b),bl,write(c)

template <typename QvQ>inv read(QvQ &x){
	x=0;int f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=x*f;
}
template <typename QvQ>inv write(QvQ x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+48);
}
using namespace std;
int n,a[1000];
int main()
{
	read(n);
	for(rei i=1;i<=n;++i) read(a[i]);
	ll sum=0;
	for(rei i=1;i<=n;++i)
	for(rei j=i+1;j<=n;++j)
	 sum+=a[i]*a[j];
	write(sum);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

#define ll long long

#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = n - 1; i >= 0; i--)
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define debug(x) cout<<#x<<": "<<x<<endl

#define ld double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define INF 1000000000000000000

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long double pi= 3.14159265358979323846;
    ll n,k;
    cin>>n>>k;
    ll h[n+1];
    rep(i,n)
    {
        cin>>h[i+1];
    }
    ll dp[n+1]={0};
    dp[0]=INF;
    
    rep(i,n+1)
    {
        dp[i]=INF;
    }dp[1]=0; 
    for(ll i=2;i<=n;i++)
    {
        // debug(i);
        for(ll j=1;j<=k;j++)
        {
            if(i-j<1)
            {
                break;
            }
            // debug(dp[i-j]+abs(h[i]-h[i-j]));
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
        }
    }
    cout<<dp[n];
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g;}E;
typedef struct graph{
	int vcnt,ecnt;
	E  e[400010];//適宜変える(ecnt)
	int id[100010];//適宜変える(vcnt)
}G;
G g;

int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}
void readgraph(){
	//適宜変える
	ll n,m;
	scanf("%lld%lld",&n,&m);
	rep(i,0,m){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		g.e[2*i].s=x;
		g.e[2*i].g=y;
		g.e[2*i+1].s=y;
		g.e[2*i+1].g=x;
	}
	g.vcnt=n+1;
	g.ecnt=2*m;
	qsort(g.e,g.ecnt,sizeof(E),esort);

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//番兵
}

int ans[100010];
int que[100010],cnt;
int main(){
	readgraph();
	que[cnt++]=1;
	ans[1]=-1;
	rep(pos,0,cnt){
		int v=que[pos];
		rep(i,g.id[v],g.id[v+1]){
			int u=g.e[i].g;
			if(!ans[u]){
				ans[u]=v;
				que[cnt++]=u;
			}
		}
	}
	puts("Yes");
	rep(i,2,g.vcnt)printf("%d\n",ans[i]);
}


Measured memory_bytes: 13904
#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define li int64_t

int main()
{
	int n;
	cin>>n;
	if(n%1000 == 0){
		cout<<0<<endl;
	}	
	else
	{
		cout<< 1000 - (n%1000);
	}
}

Measured memory_bytes: 3588
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
N = int(input())

a = a + b + c

list = []

for i in range(N):
    b = int(input())
    list.append(b)

b = [0,0,0,0,0,0,0,0,0]

for i in range(len(a)):
    for j in range(len(list)):
        if a[i] == list[j]:
            b[i] = 1

sum = 0
for i in range(len(b)):
    sum = sum + b[i]

if sum == 0:
    print("No")
elif b[2]+b[4]+b[6] ==3:
    print("Yes")
elif b[0]+b[1]+b[2] ==3:
    print("Yes")
elif b[3]+b[4]+b[5] ==3:
    print("Yes")
elif b[6]+b[7]+b[8] ==3:
    print("Yes")
elif b[0]+b[4]+b[8] ==3:
    print("Yes")
elif b[2]+b[5]+b[8] ==3:
    print("Yes")
elif b[1]+b[4]+b[7] ==3:
    print("Yes")
elif b[0]+b[3]+b[6] ==3:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	int q; cin >> q;
	for (int i = 0; i < q; i ++) {
		long long a, b; cin >> a >> b;
		long long root = sqrt(a*b);
		long long ans = root + (a*b-1)/root-1;
//		if ((a*b-1)/root >= a) ans --;
//		if ((a*b-1)/root >= b) ans --;
        if(a!=b)--ans;
		cout << ans << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {

  int N;
  cin >> N;
  string S;
  cin >> S;

  int LCP[5001][5001] = {{}};
  for(int i = S.size() - 1; i >= 0; i--) {
    for(int j = S.size() - 1; j >= 0; j--) {
      LCP[i][j] = S[i] == S[j] ? LCP[i + 1][j + 1] + 1 : 0;
    }
  }

  int ret = 0;
  for(int i = 0; i < S.size(); i++) {
    for(int j = i + 1; j < S.size(); j++) {
      chmax(ret, min(j - i, LCP[i][j]));
    }
  }

  cout << ret << endl;
}





Measured memory_bytes: 98048
#include <bits/stdc++.h>

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

// =============================
// union by size + path having
// =============================
class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int S[410][410];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int H, W;
  cin >> H >> W;

  string s;
  rep(i, H){
    cin >> s;
    rep(j, W){
      if(s[j] == '.'){
        S[i][j] = 0;
      }else{
        S[i][j] = 1;
      }
    }
  }

  UnionFind uf(H*W);

  rep(i, H){
    rep(j, W){
      if(i+1!=H){
        if(S[i][j] != S[i+1][j]){
          uf.merge(i*W+j, (i+1)*W+j);
        }
      }

      if(j+1==W) continue;

      if(S[i][j] != S[i][j+1]){
        uf.merge(i*W+j, i*W+j+1);
      }
    }
  }

  map<int, pair<ll, ll>> mp;
  rep(i, H){
    rep(j, W){
      if(S[i][j] == 0){
        mp[uf.root(i*W+j)].first++;
      }else{
        mp[uf.root(i*W+j)].second++;
      }
    }
  }

  ll ans = 0;
  for(auto itr = mp.begin(); itr != mp.end(); itr++){
    ans += itr->second.first * itr->second.second;
  }

  cout << ans << endl;








  return 0;
}


Measured memory_bytes: 11776
#include<stdio.h>
int main(){
  int n,x,i;
  int cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&x);
      if(sosu(x))cnt++;
    }
  printf("%d\n",cnt);


  return 0;
}



int sosu(int x)
{
  int i;
  if(x<2)return 0;
  else if(x==2)return 1;
  if(x%2==0)return 0;
  for(i=3;i*i<=x;i+=2)
    {
      if(x%i==0)return 0;
    }
  return 1;
}

Measured memory_bytes: 596
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>

using namespace std;

int main() {

	int N;
	string S;
	cin >> N >> S;
	for (int i = 0; i < S.size(); ++i) {
		S[i] += N;
		if (S[i] > 'Z')S[i] -= 26;
	}
	cout << S << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdbool.h>
#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N],col[N],dpos[2*N-1],dneg[2*N-1];

bool X[N][N];

void initialize(){
  int i;
  for(i=0;i<N;i++){
    row[i]=FREE;
    col[i]=FREE;
  }
  for(i=0;i<2*N-1;i++){
    dpos[i]=FREE;
    dneg[i]=FREE;
  }
}

void printBoard(){
  int i,j;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(X[i][j]){
	if(row[i]!=j) return;
      }
    }
  }
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      printf("%s",((row[i]==j)?"Q":"."));
    }
    printf("\n");
  }
}

void recursive(int i){
  int j;
  if(i==N){
    printBoard(); return;
  }

  for(j=0;j<N;j++){
    if(NOT_FREE == col[j] || NOT_FREE == dpos[i+j] || NOT_FREE == dneg[i-j+N-1]) continue;

    row[i]=j;
    col[j]=dpos[i+j]=dneg[i-j+N-1]=NOT_FREE;
    recursive(i+1);
    row[i]=col[j]=dpos[i+j]=dneg[i-j+N-1]=FREE;
  }
}

int main(){
  int i,j,k,r,c;
  initialize();

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      X[i][j]=false;
    }
  }

  scanf("%d",&k);

  for(i=0;i<k;i++){
    scanf("%d%d",&r,&c);
    X[r][c]=true;
  }

  recursive(0);

  return 0;
}
    
	     



Measured memory_bytes: 2108
N = int(input())
A = input()
B = input()
C = input()

count = 0
for i in range(N):
  if not A[i] == B[i] == C[i]:
    if A[i] == B[i] or A[i] == C[i] or B[i] == C[i]:
      count += 1
    else: count += 2

print(count)


Measured memory_bytes: 3060
#include<stdio.h>

int main() {
	int n, m, c, b[20], i, j, a[20][20], out[20], cnt;
	scanf("%d%d%d", &n, &m, &c);
	for (i = 0; i < m; i++) scanf("%d", &b[i]);
	for (i = 0; i < n; i++) for (j = 0; j < m; j++) scanf("%d", &a[i][j]);
	for (i = 0; i < n; i++) out[i] = c;
	for (i = 0; i < n; i++) for (j = 0; j < m; j++) out[i] += a[i][j] * b[j];
	cnt = 0;
	for (i = 0; i < n; i++) if (out[i] > 0) cnt++;
	printf("%d", cnt);
	return 0;
}

Measured memory_bytes: 128
N, M, X = map(int, input().split())
A = list(map(int, input().split()))
a = 0
b = 0

for i in range(X):
    if i in A:
        a += 1

for i in range(X+1, N+1):
    if i in A:
        b += 1

print(min(a, b))

Measured memory_bytes: 3060
# AOJ GRL_3_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A

import sys

sys.setrecursionlimit(100000)

V, E = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for _ in range(0, E)]

ord = [0 for _ in range(0, V)]
low = [0 for _ in range(0, V)]
used = [False for _ in range(0, V)]
articulation = []

G = [ [] for _ in range(0, V)]
for s, t in Edge:
    G[s] += [t]
    G[t] += [s]

def dfs(s, p, k):
    global articulation
    used[s] = True
    ord[s] = k
    low[s] = ord[s]
    k += 1
    c = 0
    for t in G[s]:
        if used[t] == False:
            c += 1
            dfs(t, s, k)
            low[s] = min(low[s], low[t])
            if p != -1 and ord[s] <= low[t]:
                articulation += [s]
        elif t != p:
            low[s] = min(low[s], ord[t])
    if p == -1 and c >= 2:
        articulation += [s]
 
for s in range(0, V): 
    if used[s] == False:
        dfs(s, -1, 0)

answer = list(set(articulation))
answer.sort()
if len(articulation) > 0:
    print("\n".join(list(map(str, answer))))





Measured memory_bytes: 24596
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define endl '\n'
#define ld long double
#define FOR(i,a,n) for (ll i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
#define FI(i,n) for (ll i=0; i<(n); ++i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define MINUS(a) memset((a),-1,sizeof((a)))
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }
 
/*
░░░░░░░░░░░░░░░░░░░░░░░░░
░░█▀▀▄░░░░░░░░░░░▄▀▀█░░░░
░░█░░░▀▄░▄▄▄▄▄░▄▀░░░█░░░░
░░░▀▄░░░▀░░░░░▀░░░▄▀░░░░░
░░░░░▌░▄▄░░░▄▄░▐▀▀░░░░░░░
░░░░▐░░█▄░░░▄█░░▌▄▄▀▀▀▀█░
░░░░▌▄▄▀▀░▄░▀▀▄▄▐░░░░░░█░
░▄▀▀▐▀▀░▄▄▄▄▄░▀▀▌▄▄▄░░░█░
░█░░░▀▄░█░░░█░▄▀░░░░█▀▀▀░
░░▀▄░░▀░░▀▀▀░░▀░░░▄█▀░░░░
░░░░█░░░░░░░░░░░▄▀▄░▀▄░░░
░░░░█░░░░░░░░░▄▀█░░█░░█░░
░░░░█░░░░░░░░░░░█▄█░░▄▀░░
░░░░█░░░░░░░░░░░████▀░░░░
░░░░▀▄▄▀▀▄▄▀▀▄▄▄█▀░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░
*/
 
// I want to be the very best, like no one ever was, I will battle everyday to claim my rightful place
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
// I am questioning life and universe and 
// everything else after looking at this

void solve(){
    ll n; cin>>n;

    ll odd = n/2 + (n%2 != 0);
    ld ans = odd;
    ans = ans/(ld)n;

    cout<<fixed<<setprecision(10)<<ans<<endl;
}
 
signed main(){
 
   FastRead;    
 

    ll t;
    t = 1; 
    // cin>>t;
    FOR(i,1,t){
        // cout<<"Case #"<<i<<": ";
        solve();
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
//const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  int H, W, N;
  cin >> H >> W >> N;
  cout << min((N + H - 1) / H, (N + W - 1) / W) << endl;


}

Measured memory_bytes: 1020
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

h,n = mii()
ab = llint(n)

dp = [float("inf")] * (h+1)

dp[h] = 0

for i in range(h,-1,-1):
    for j in range(n):
        tmp = max(0,i-ab[j][0])
        dp[tmp] = min(dp[tmp], dp[i]+ab[j][1])

print(dp[0])




Measured memory_bytes: 68936
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
using namespace std;
using ll=long long;
using ld=long double;
#define ssort(n) sort((n).begin(),(n).end())
typedef pair<int,int> P;

int main()
{
    int N;
    cin >> N;
    vector<int> h(N);
    rep(i,N)cin >> h[i];

    int count=0;
    int max=0;
    rep(i,N){
        if(max<h[i]){
            max=h[i];
        }
    }
    bool flag=false;
    rep(i,max){
        rep(j,N){
            if(h[j]>0&&!flag){
                flag=true;
                h[j]--;
            }else if(h[j]>0&&flag){
                h[j]--;
            }else if(h[j]==0&&flag){
                count++;
                flag=false;
            }if(j==N-1&&flag){
                count++;
                flag=false;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
@count = 0

def merge_sort(arr)
  return arr if arr.size == 1
  mid = arr.size / 2
  left, right = arr.slice(0, mid), arr.slice(mid, arr.size)
  merge(merge_sort(left), merge_sort(right))
end

def merge(arr1, arr2)
  ret = []
  until arr1.empty? || arr2.empty?
    @count += 1
    if arr1.first < arr2.first
      ret << arr1.shift
    else
      ret << arr2.shift
    end
  end

  until arr1.empty?
    @count += 1
    ret << arr1.shift
  end

  until arr2.empty?
    @count += 1
    ret << arr2.shift
  end

  ret
end

n = gets.to_i
arr = gets.split.map(&:to_i)
puts merge_sort(arr).join("\s")
puts @count

Measured memory_bytes: 74572
N = int(input())
TA = [map(int,input().split()) for _ in range(N)]

pret,prea = TA[0]
for i in range(1,N):
  t,a = TA[i]
  if pret == t and prea == a:
    continue
  elif pret <= t and prea <= a:
    pret,prea = t,a
  else:
    if (pret+t-1)//t > (prea+a-1)//a:
      pret = (pret+t-1)//t * t
      prea = pret // t * a
    else:
      prea = (prea+a-1)//a * a
      pret = prea // a * t
print(pret+prea)

Measured memory_bytes: 38896
H,W=map(int,input().split())
L=[]
for i in range (H):
	T=input()
	L.append(T)
A="#"*(W+2)
for i in range (H+2):
	if i==0 or i==H+1:
		print(A)
	else:
		print("#",end="")
		print(L[i-1],end="")
		print("#")

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main{
 public static void main(String[] args) {
   Scanner kbd =new Scanner(System.in);
   int n=kbd.nextInt();
   int a=n/1000;
   if(a!=0&&n%(a*1000)==0){
     System.out.println(0);
   }else{
   System.out.println(1000*(a+1)-n);
}
}
}



Measured memory_bytes: 35688
n, m = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
c = [0] * m
d = [0] * m
for i in range(m):
    c[i], d[i] = map(int, input().split())

for i in range(n):
    ans = 0
    mincp = 100000000000
    for j in range(m):
        dist = abs(a[i]-c[j])+abs(b[i]-d[j])
        if dist < mincp:
            ans = j+1
            mincp = dist
    print(ans)


Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>

using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+9
#define EPS 1e-9
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < (k); i++)
typedef long long ll;
char num[256];
char decode[][7] = {{0,0,0,0,0},
                   {0,'a','b','c','d','e'},
                   {0,'f','g','h','i','j'},
                   {0,'k','l','m','n','o'},
                   {0,'p','q','r','s','t'},
                   {0,'u','v','w','x','y'},
                   {0,'z','.','?','!',' '}};
string change(){
    if(strlen(num)%2 == 1)return "NA";
    string ans = "";
    for(int i = 0; i < strlen(num); i+=2){
        if('0' < num[i] && num[i] < '7' && '0' < num[i+1] && num[i+1] < '6')ans += decode[num[i]-48][num[i+1]-48];
        else return "NA";        
    }
    return ans;
}
int main(){
    while(~scanf("%s",num)){
        cout << change() << endl;
    }
    return 0;
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

int main(){
    int k;
    cin>>k;
    int r=0;
    bool b[k]={};
    for(int i=1;;++i){
        r=(10*r+7)%k;
        if(r==0){
            cout<<i<<endl;
            return 0;
        }
        else if(b[r]){
            cout<<-1<<endl;
            return 0;
        }
        b[r]=true;
    }
}


Measured memory_bytes: 4612
#include<stdio.h>
#include<math.h>

double disCal(int p, int dim, int *vect1, int *vect2){
	int i;
	double dis_pre;
	double distance;
	int *vc1_res, *vc2_res;
	
	dis_pre = 0;
	vc1_res = vect1;
	vc2_res = vect2;
	
	distance = 0;
	
	for(i=0; i<dim; i++){
		switch (p){
			case 1:
				distance += fabs( *vect1 - *vect2);
				break;
			case 2:
				distance += pow( fabs(*vect1 - *vect2), 2.0);
				break;
			case 3:
				distance += pow( fabs(*vect1 - *vect2), 3.0);
				break;
			case 4:
				dis_pre = fabs( *vect1 - *vect2 );
				if( distance < dis_pre){
					distance = dis_pre;
				}
				break;
			default:
				printf("異常な値です。\n");
				break;
		}
		vect1++;
		vect2++;
	}
	switch (p){
		case 2:
			distance = sqrt(distance);
			break;
		case 3:
			distance = pow(distance, 1.0/3.0);
			break;
	}
	vect1 = vc1_res;
	vect2 = vc2_res;
	
	return distance;
	
/*	switch (p){
		case 1:
			for(i=0; i<dem; i++){
				distance += sqrt( pow(*vect1 -*vect2, 2.0));
				vect1++;
				vect2++;
			}
			break;
		case 2:
			for(i=0; i<dem; i++){
				distance += pow(*vect1 -*vect2, 2.0);
				vect1++;
				vect2++;
			}
			distance = sqrt(distance);
			break;
		case 3:
			for(i=0; i<dem; i++){
				distance += pow(*vect1 -*vect2, 3.0);
				vect1++;
				vect2++;
			}
			distance = cbrt(distance);
			break;
		case 4:
			for(i=0; i<dem; i++){
				dis_pre = sqrt( pow( *vect1 - *vect2, 2.0) );
				if( distance < dis_pre){
					distance = dis_pre;
				}
				vect1++;
				vect2++;
			}
			break;
		default:
			printf("異常な数値です\n");
	}*/

}

int main(){
	
	int i;
	int vect1[1001],vect2[1001];	/*vector*/
	int dim;			/*dimension*/
	int clsNum, score;
	
	/*値セット[次元数、ベクトルA、ベクトルB]*/
	scanf("%d", &dim);
	for(i=0; i<dim; i++)	scanf("%d",&vect1[i]);
	for(i=0; i<dim; i++)	scanf("%d",&vect2[i]);
	
	
	for(i=1; i<5; i++){
		printf("%f\n", disCal(i, dim, vect1, vect2) );
	}
	
	
	return 0;
}




Measured memory_bytes: 2140
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> p;
typedef long long ll;
typedef pair<ll,ll> pll;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e9;
const ll MOD=1e9+7;
struct edge{
    int to;
    int cost;
};
int main(){
    int N;cin>>N;
    string S;cin>>S;
    int Q;cin>>Q;
    vector<set<int> > st(26);
    for(int i=0;i<N;++i){
        st[S[i]-'a'].insert(i);
    }
    for(int i=0;i<26;++i) st[i].insert(INF);
    while(Q--){
        int t;cin>>t;
        if(t==1){
            int i;
            char c;
            cin>>i>>c;i--;
            st[S[i]-'a'].erase(i);
            S[i]=c;
            st[S[i]-'a'].insert(i);
        }else{
            int l,r;cin>>l>>r;l--;r--;
            int ans=0;
            for(int i=0;i<26;++i){
                int j=*st[i].lower_bound(l);
                if(j<=r) ans++;
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 27232
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

ll n, m;

int main(){
	while (cin >> n >> m&&n + m){
		ll p[10000];
		fill(p, p + 10000, -1);
		REP(i, n)cin >> p[i];
		sort(p, p + 10000, greater<int>());
		ll sum = 0;
		REP(i, n){
			if ((i+1)%m != 0)sum += p[i];
		}
		cout << sum << endl;
	}
}

Measured memory_bytes: 1248
sx,sy,tx,ty=map(int,input().split())

x=tx-sx
y=ty-sy

for i in range(x):
    print("R",end="")

for i in range(y):
    print("U",end="")


for i in range(x):
    print("L",end="")

for i in range(y):
    print("D",end="")
#iki
print("D",end="")
for i in range(x+1):
    print("R",end="")

for i in range(y+1):
    print("U",end="")
print("L",end="")




print("U",end="")
for i in range(x+1):
    print("L",end="")

for i in range(y+1):
    print("D",end="")
print("R",end="")

Measured memory_bytes: 4468
#include <stdio.h>

int main(){
    int S,h,m,s;
    scanf("%d", &S);
    h = S / 3600;
    m = (S - h*3600) / 60;
    s = S - h*3600 - m*60;
    printf("%d:%d:%d\n", h, m, s);

    return 0;
}

Measured memory_bytes: 592
#include<iostream>
#include<map>
#include<vector>
#include<sstream>
using namespace std;
#define DIR 1
#define FILE 2
#define ARB 3
#define REP(i,b,e) for(int i=b;i<e;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(),(c).end()
class Tree{
public:
  int type;
  string myname;
  map<string,Tree* > M;
  Tree(){type=DIR;M.clear();myname="";}
};

void get_path(string a,vector<string>&b){
  rep(i,a.size())if (a[i]=='/')a[i]=' ';
  stringstream sin(a);
  while(sin>>a)b.push_back(a);
}

void get_query(string a,vector<pair<string,int> > & b){
  REP(i,1,a.size()){
    string t;
    while(i<a.size() && a[i] != '/')t+=a[i++];
    b.push_back(make_pair(t,DIR) );
  }
  if ( b.size() == 0)return;
  if ( a[a.size()-1]=='/')b.push_back(make_pair("index.html",FILE) );
  else b[b.size()-1].second =ARB;
}

void make_tree(Tree *a,vector<string>&b,int &p){
  if (b.size()==p){return;}
  Tree *next=a->M[b[p]];
  if ( next == 0){
    next = new Tree;
    next->myname=b[p];
    a->M[b[p]]=next;
    if ( p+1 ==b.size())next->type=FILE;
    else next->type=DIR;
    make_tree(next,b,++p);
  }else make_tree(next,b,++p);
  
}

Tree* Find_Page(Tree *a,vector<pair<string,int> >&b,int &p,Tree *prev){
  //if ( b.size() ==p)return a;
  Tree *ret=a;
  while(p < b.size()){
    if (b[p].first == "."){p++;continue;}
    else if ( b[p].first ==".."){p++;return prev;}
    //exceptional case "index.html"
    Tree *next = a->M[b[p].first];
    if ( next == 0 || (next->type&b[p].second )==0  )return NULL;
    ret = Find_Page(next,b,++p,a);
    if ( ret == NULL)return NULL;
  }

  if (ret->type == FILE)return ret;
  ret = ret->M["index.html"];
  if ( ret == 0 || ret->type !=FILE){
    return NULL;
  }

  return ret;
}

void solve(string *q,Tree *root){
  Tree *data[2];
  rep(i,2){
    vector<pair<string,int> > a;
    int p=0;
    data[i]=NULL;
    get_query(q[i],a);
    data[i]=Find_Page(root,a,p,NULL);
    //cout << data[i] << " " << i << endl;
    if (  data[i] == NULL){puts("not found");return;}
  }
  if (data[0] == data[1] )puts("yes");
  else puts("no");
  //cout << "case0 " <<data[0]->myname << " case1 " << data[1]->myname << endl;
  //cout << "case0 " <<data[0] << " case1 " << data[1] << endl;
}

main(){
  int n,q;
  while(cin>>n>>q &&n){
    Tree root;
    string t;
    vector<string> a;
    int p=0;
    rep(i,n)cin>>t,get_path(t,a),make_tree(&root,a,p=0),a.clear();
    rep(i,q){
      string in[2];
      cin>>in[0]>>in[1];
      solve(in,&root);
    }
  }
  return false;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
#define ll long long
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pl pair<ll,ll>
#define rep(i,b) for(ll i=0;i<b;i++)

using namespace std;

int main() {
    std::cout<<std::fixed<<std::setprecision(10);
    ll N, K, L, R,mx=0,point;
    cin>>N;
    set<ll> a;
    rep(i,N){
        cin>>K;
        a.insert(K);
    }
    a.size()==N?cout<<"YES"<<endl:cout<<"NO"<<endl;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(a) (a).begin(), (a).end()
typedef vector<int> vi;
const int INF = 1LL << 58;
const int MOD = 1000000007;
const int MAX_N = 200100;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
struct mint
{
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}
    mint operator-() const { return mint(-x); }
    mint &operator+=(const mint a)
    {
        if ((x += a.x) >= MOD)
            x -= MOD;
        return *this;
    }
    mint &operator-=(const mint a)
    {
        if ((x += MOD - a.x) >= MOD)
            x -= MOD;
        return *this;
    }
    mint &operator*=(const mint a)
    {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const
    {
        if (!t)
            return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1)
            a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(MOD - 2); }
    mint &operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream &operator>>(istream &is, const mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }

signed main()
{
    //  以降 cin の入力元が 'input.txt' になる
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    string S;
    cin >> S;
    static mint dp[100010][13];
    REP(i, 13)
    {
        REP(j, S.size() + 1)
        {
            dp[j][i] = 0;
        }
    }
    dp[0][0] = 1;
    int ten = 1;
    REP(i, S.size())
    {
        char c = S[S.size() - i - 1];
        if (c == '?')
        {
            REP(j, 13)
            {
                REP(k, 10)
                {
                    int tmp = (k * ten) % 13;
                    tmp += j;
                    dp[i + 1][tmp % 13] += dp[i][j];
                }
            }
        }
        else
        {
            int k = c - '0';
            REP(j, 13)
            {
                int tmp = (k * ten) % 13;
                tmp += j;
                dp[i + 1][tmp % 13] += dp[i][j];
            }
        }
        ten *= 10;
        ten %= 13;
    }

    cout << dp[S.size()][5] << endl;

    return 0;
}

Measured memory_bytes: 10624