akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int main(){
  int h,w;
  scanf("%d%d",&h,&w);
  int a[h][w];
  int b[h][w];
  int i,j;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      scanf("%d",&a[i][j]);
      b[i][j]=a[i][j];
    }
  }
  int n = 0;
  for(i=0;i<h-1;i++){
    for(j=0;j<w;j++){
      if(b[i][j]%2==1){
        n++;
        b[i+1][j]++;
      }
    }
  }
  for(j=0;j<w-1;j++){
    if(b[h-1][j]%2==1){
      n++;
      b[h-1][j+1]++;
    }
  }
  printf("%d\n",n);
  for(i=0;i<h-1;i++){
    for(j=0;j<w;j++){
      if(a[i][j]%2==1){
        printf("%d %d %d %d\n",i+1,j+1,i+2,j+1);
        a[i+1][j]++;
      }
    }
  }
  for(j=0;j<w-1;j++){
    if(a[h-1][j]%2==1){
      printf("%d %d %d %d\n",h,j+1,h,j+2);
      a[h-1][j+1]++;
    }
  }
  return 0;
}


Measured memory_bytes: 3968
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main{
    static List<Node> list = new LinkedList<>();

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        while (true) {
            int w = scan.nextInt();
            int h = scan.nextInt();
            if (w == 0 && h == 0) {
                break;
            }
            int[][] c = new int[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    c[i][j] = scan.nextInt();
                }
            }
            int count = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (c[i][j] == 1) {
                        c=addList(c, list, i, j, h, w);
                        while (true) {
                            if (list.size() == 0) {
                                break;
                            }
                            Node node = list.get(0);
                            list.remove(0);
                            c=addList(c, list, node.y, node.x, h, w);
                        }
                        count++;
                    }

                }
            }
            System.out.println(count);
        }
    }

    private static int[][] addList(int[][] c, List<Node> list, int i, int j, int h, int w) {
        for (int y = -1; y < 2; y++) {
            for (int x = -1; x < 2; x++) {
                if (i + y < 0 || j + x < 0 || i + y >= h || j + x >= w) {
                    continue;
                }
                if (x == 0 && y == 0) {
                    continue;
                }
                if (c[i + y][j + x] == 1) {
                    c[i + y][j + x] = 0;
                    Node node = new Node();
                    node.setX(j + x);
                    node.setY(i + y);
                    list.add(node);
                }
            }
        }
        return c;
    }
}

class Node {
    int x, y;

    public void setX(int a) {
        x = a;
    }

    public void setY(int a) {
        y = a;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}


Measured memory_bytes: 45028
def chck(n1, n2) :
	c = 0
	while(n2 <= n1) :
		n2 = n2 * 2
		c = c + 1
	return c, n2

def main() :
	a, b, c = list(int(j) for j in input().strip().split())
	k = int(input())
	m1, b = chck(a, b)
	m2, c = chck(b, c)
	mi = m1 + m2
	if mi <= k :
		print("Yes")
	else :
		print("No")

if __name__ == '__main__' :
	main()

Measured memory_bytes: 9192
#include <cstdio>
#include <map>
using namespace std;
int N; long long ans;
char c[10]; map<char, long long> m;
char I[5] = {'M', 'A', 'R', 'C', 'H'};
int main() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%s", c); m[c[0]]++;
  }
  for(int i = 0; i < 3; i++) {
    for(int j = i+1; j < 4; j++) {
      for(int k = j+1; k < 5; k++) {
        ans += m[I[i]]*m[I[j]]*m[I[k]];
      }
    }
  }
  printf("%ld", ans);
}

Measured memory_bytes: 256
base = 127
mask = (1 << 32) - 1
def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()
    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp
t = tuple(ord(c) for c in input())
tl = len(t)
q = int(input())
h = dict()
c = dict()
a = []
for _ in range(q):
    p = input()
    if p in c:
        a.append(c[p])
        continue
    p = tuple(ord(c) for c in p)
    pl = len(p)
    if pl > tl:
        a.append("0")
        continue
    bs = min(19, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append("1" if keys.issubset(h[bs]) else "0")
print('\n'.join(a))



Measured memory_bytes: 1072676
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;




namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] s = Console.ReadLine().Split(' ');

            int div4 = 0;
            int div2 = 0;

            for (int i = 0; i < N; i++)
            {
                int val = int.Parse(s[i]);
                if (0 == (val % 4))
                {
                    div4++;
                }
                else if(0== (val % 2))
                {
                    div2++;
                }
            }

            div2 /= 2;
            div4 += div2;

            if(N / 2 <= div4)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 15968
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int f=0,s=0,a;
    for(int i=0;i<3;i++){
        cin >> a;
        if(a==7) s++;
        if(a==5) f++;
    }
    if(f==2 && s==1){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 3628
H, W = map(int, input().split())
N = H * W
board = [[int(x == "#") for x in input()] for _ in range(H)]
INF = N ** 2
A = [[INF] * N for _ in range(N)]
for i in range(N):
    A[i][i] = 0
drc = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for r in range(H):
    for c in range(W):
        for dr, dc in drc:
            nr, nc = r + dr, c + dc
            if nr < 0 or H <= nr or nc < 0 or W <= nc:
                continue
            if board[nr][nc] == 1:
                continue
            A[r * W + c][nr * W + nc] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])
ans = 0
for sr in range(H):
    for sc in range(W):
        if board[sr][sc]:
            continue
        for gr in range(H):
            for gc in range(W):
                if board[gr][gc]:
                    continue
                ans = max(ans, A[sr*W+sc][gr*W+gc])
print(ans)


Measured memory_bytes: 46108
A = int(input())
B = int(input())
C = int(input())
X = int(input())//50

ans = 0
for a, b, c in [(a, b, c) for a in range(A+1) for b in range(B+1) for c in range(C+1)]:
  if 10*a + 2*b + c == X:
    ans += 1

print(ans)

Measured memory_bytes: 18316
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll INF = 1'000'000'000'000'000'000;
namespace utils{
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
    template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;
    template<class T> using min_queue = p_queue<T, greater<T>>;
    template<class T> using max_queue = p_queue<T, less<T>>;

    template<class T> bool up_min(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }
    template<class T> bool up_max(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }

    ll operator"" _64(unsigned long long x){ return ll(x); }
    ull operator"" _64u(unsigned long long x){ return ull(x); }

    template<class T>
    vector<T> make_mdvector(int n, T t){
        return vector<T>(n, t);
    }
    template<class ...Ts>
    auto make_mdvector(int n, Ts ... ts){
        return vector<decltype(make_mdvector(ts...))>(n, make_mdvector(ts...));
    }

    inline ll bit(int x){
        return 1ll << x;
    }

    template<class T>
    istream& operator>>(istream& is, vector<T>& v){
        for (auto &&x : v) { is >> x; } return is;
    }

    template<class T>
    ostream& operator<<(ostream& os, const vector<T>& v){
        for (auto &&x : v) { os << x << ' '; } cout << endl; return os ;
    }
}
using namespace utils;

class solver{
    istream& is;
    ostream& os;

public:
    solver(istream& I, ostream& O) :is(I), os(O) {}
    ll N;
    void run();
};

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef XELMH
    string test_cases = "test_B.txt";
    cerr << test_cases << " -->" << endl;
    auto fs = fstream(test_cases, fstream::in);
    int loop = 0;
    while(fs) {
        loop++;
        cout << '#' << loop << "#------\n";
        solver(fs, cout).run();
    }
    if(loop <= 1) {
        cout << "===" << endl;
        while(cin) solver(cin, cout).run();
    }
#else
    solver(cin, cout).run();
#endif
    return 0;
}


void solver::run(){
    is >> N;
    if(!is) return;
    vector<ll> A(N); is >> A;
    ll len = accumulate(ALL(A), 0ll);
    ll ans = INF;
    ll lsum = 0;
    for (int i = 0; i < N; ++i) {
        lsum += A[i];
        ll rsum = len - lsum;
        ans = min(ans, abs(rsum - lsum));
    } // end i

    os << ans << endl;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  string S;
  cin >> S;
  string ans;
  if (S == "Sunny") {
    ans = "Cloudy";

  } else if (S == "Cloudy") {
    ans = "Rainy";
  } else {
    ans = "Sunny";
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define LL long long
#define MOD 1000000007
#define INF 2000000000
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
ll N, M, K,H,W, mi1,mi2,sum;
LL ans,a;
LL no;
bool b,bb[1000000000];
string s,t;

int main() {
	cin >> N>>M;
	vector<pair<LL, LL>> v(M);
	for (int i = 0; i < M; i++) {
		cin >> K >> H;
		v[i] = make_pair(H - 1, K - 1);
	}
	sort(v.begin(), v.end());
	LL now = 0;
	now = v[0].first - 1;
	for (int i = 1; i < M; i++) {
		if (v[i].second <= now)continue;
		ans++;
		now = v[i].first - 1;
	}
	cout << ans+1 << endl;


	return 0;
}



Measured memory_bytes: 1792
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <list>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;

void maxHeap(int* keys, int size, int cur){
	if(cur*2 > size){
		// noop
	}else if(cur*2+1 > size && keys[cur*2] > keys[cur]){
		swap(keys[cur*2], keys[cur]);
	}else{
		int l = keys[cur*2];
		int r = keys[1+cur*2];
		if(l > r && l > keys[cur]){
			swap(keys[cur*2], keys[cur]);
			maxHeap(keys, size, cur*2);
		}else if(r > keys[cur]){
			swap(keys[1+cur*2], keys[cur]);
			maxHeap(keys, size, 1+cur*2);
		}
	}
}
void fixHeap(int* keys, int cur){
	if(cur/2 >= 1 && keys[cur] > keys[cur/2]){
		swap(keys[cur], keys[cur/2]);
		fixHeap(keys, cur/2);
	}
}

int main() {
	int node = 0;
	int keys[2000000];
	for(;1;){
		char *com = new char[16];
		scanf("%s", com);
		
		if(com[0] == 'i'){
			scanf("%d", &keys[++node]);
			fixHeap(keys, node);
		}else if(com[1] == 'x'){
			printf("%d\n", keys[1]);
			keys[1] = keys[node--];
			maxHeap(keys, node, 1);
		}else break;
	}
	
	return 0;
}

Measured memory_bytes: 67636
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int man=1e5+5;
int a[man];
struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
    friend ostream & operator<<(ostream & O,const node &a)
    {
        O<<a.x<<" "<<a.y;
        return O;
    }
}dian[man];
int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    int sum=0,cnt=0;
    if(a[n-1]<=0)
    {
        dian[cnt++]=node(a[n-1],a[0]);
        sum=a[n-1]-a[0];
        for(int i=1;i<n-1;i++)
        {
            dian[cnt++]=node(sum,a[i]);
            sum-=a[i];
        }
        cout<<sum<<endl;
        for(int i=0;i<cnt;i++)
        {
            cout<<dian[i]<<endl;
        }
    }
    else if(a[0]>=0)
    {
        dian[cnt++]=node(a[0],a[n-1]);
        sum=a[n-1]-a[0];
        for(int i=1;i<n-2;i++)
        {
            dian[cnt++]=node(-sum,a[i]);
            sum+=a[i];
        }
        dian[cnt++]=node(a[n-2],-sum);
        sum+=a[n-2];
        cout<<sum<<endl;
        for(int i=0;i<cnt;i++)
        {
            cout<<dian[i]<<endl;
        }
    }
    else if(a[0]<0&&a[n-1]>0)
    {
        int num=0,ans=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]<0)
                num=i;
            sum+=abs(a[i]);
        }
        cout<<sum<<endl;
        ans=a[num];
        for(int i=num+1;i<n-1;i++)
        {
            cout<<ans<<" "<<a[i]<<endl;
            ans-=a[i];
        }
        a[num]=ans;
        ans=a[n-1];
        for(int i=0;i<=num;i++)
        {
            cout<<ans<<" "<<a[i]<<endl;
            ans-=a[i];
        }
    }
    return 0;
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	double ans;
	double m;
	while (1) {
		ans = 0;
		m = 0;
		cin >> n;
		if (n == 0)break;
		vector<int>s(n);
		for (int i = 0;i < n;i++) {
			cin >> s[i];
			m = m + s[i];
			ans = ans + s[i] * s[i];
		}
		ans = ans / n;
		m = m / n;
		ans = ans - m * m;
		ans = sqrt(ans);
		cout<<fixed<<setprecision(15) << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3296
#include <stdio.h>
#include <string.h>

int main(){
    int n;
    char str[102];

    scanf("%d", &n);
    scanf("%s", str);
    
    if (strlen(str) <= n){
        printf("%s", str);
    }
    else{
        for (int i=0; i<n; i++){
            printf("%c", str[i]);
        }
        printf("...");
    }

    return 0;
}


Measured memory_bytes: 1720
# -*- coding:utf-8 -*-
N, T = map(int , input().split())
t = list(map(int, input().split()))
ans = 0
for tmp in range(N):
    if tmp == 0:
        ans += T
    else:
        a = t[tmp] - t[tmp-1]
        if a < T:
            ans -= T-a
        ans += T
print(ans)

Measured memory_bytes: 26836
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i<x;i++)
int dp[1005][1005];
int f[1005][1005];
int main()
{
	srand((unsigned int)time(NULL));
	while(1)
	{
		int h,w,n;
		memset(dp,0,sizeof(dp));
		scanf("%d %d %d",&h,&w,&n);
		if(!h) return 0;
		for(int i=1;i<=h;i++)
		{
			for(int j=1;j<=w;j++)
			{
				scanf("%d",&f[i][j]);
			}
		}
		dp[1][1]=n-1;
		for(int i=1;i<=h;i++)
		{
			for(int j=1;j<=w;j++)
			{
				dp[i][j]+=(dp[i-1][j]+(!f[i-1][j]?1:0))/2+(dp[i][j-1]+(f[i][j-1]?1:0))/2;
			}
		}
		int x=1,y=1;
		while(x!=h+1 && y!=w+1)
		{
			int dir=(f[x][y]+dp[x][y])%2;
			if(!dir) x++; else y++;
		}
		printf("%d %d\n",x,y);
	}
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int a,b;
    cin>>a>>b;
    if(a+b==15)cout<<"+"<<endl;
    else if(a*b==15)cout<<"*"<<endl;
    else cout<<"x"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;

int main(int argc, char const *argv[]) {
  double a, b, c, d;
  cin >> a >> b >> c >> d;
  bool flag = true;
  while (a > 0 && b > 0) {
    c -= b;
    if (c <= 0)
      break;
    a -= d;
    if (a <= 0) {
      flag = false;
      break;
    }
  }
  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


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

using namespace std;

inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int n,m,si[200010],fs;
int main()
{
	n=read(); m=read(); fs=1;
	for(int i=1;i<=m;i++)
		fs=read(),si[fs]++,
		fs=read(),si[fs]++;
	for(int i=1;i<=n;i++) if(si[i]&1)
	{
		printf("NO\n");
		return 0;
	}
	printf("YES\n");
	return 0 ;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;

int main(){
    int n; cin>>n;
    bool c[9]={false};
    int cnt=0,ans=0;
    for(int i=0;i<n;i++){
        int a; cin>>a;
        c[a/400]=true;
        if(a>=3200) cnt++;
    }
    for(int i=0;i<8;i++){
        if(c[i]) ans++;
    }
    if(ans) cout<<ans<<" "<<ans+cnt<<endl;
    else    cout<<1<<" "<<cnt<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define loop(i,n) for(int i = 0;i < (n);i++)
#define range(i,a,b) for(int i = (a);i <= (b);i++)
#define all(A) A.begin(),A.end()
#define pb push_back
#define mp make_pair
#define sz(A) ((int)A.size())
#define vi vector<int>
#define vl vector<long long>
#define vd vector<double>
#define vp vector<pair<int,int> >
#define ll long long
#define pi pair<int,int>
#define popcnt(x) __builtin_popcountll(x)
#define LSOne(x) ((x) & (-(x)))
#define xx first
#define yy second
#define PQ priority_queue
#define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
#define prp(p) cerr << "(" << (p).first << " ," << (p).second << ")";
#define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
#define PRESTDIO() cin.tie(0),cerr.tie(0),ios_base::sync_with_stdio(0)
#define what_is(x) cerr << #x << " is " << x << endl
#define bit_lg(x) (assert(x > 0),__builtin_ffsll(x) - 1)
const double PI = acos(-1);
using namespace std;

const int MAX = 200*1000 + 10,MAXA = 2*2000 + 10,MAXB = 2*MAXA,mod = 1e9 + 7;
int A[MAX],B[MAX],n;
int cnt[MAXA][MAXA],f[MAXA][MAXA];
int fact[MAXB],inv[MAXB];

int add(int a,int b){
	a += b;
	if(a >= mod) a -= mod;
	if(a < 0) a += mod;
	return a;
}

int mul(int a,int b){
	return (a*1LL*b)%mod;
}

int pow_mod(int a,int b){
	if(!b) return 1;
	int x = 1;
	for(;b > 1;b >>= 1){
		if(b & 1) x = mul(a,x);
		a = mul(a,a);
	}
	return mul(a,x);
}


void init(){
	fact[0] = 1;
	loop(i,MAXB-1) fact[i + 1] = mul(fact[i],i + 1);
	loop(i,MAXB) inv[i] = pow_mod(fact[i],mod-2);
}

int C(int n,int k){
	if(n < k) return 0;
	return mul(fact[n],mul(inv[k],inv[n - k]));
}

int main(){
	#ifdef HOME
		freopen("in.in", "r", stdin);
	#endif
	init();
	scanf("%d",&n);
	loop(i,n) {
		scanf("%d %d",A + i,B + i);
		cnt[2000-A[i]][2000-B[i]]++;
	}
	for(int x = 0;x <= 4000;x++)
		for(int y = 0;y <= 4000;y++) {
			f[x][y] = cnt[x][y];
			if(x) f[x][y] = add(f[x][y],f[x - 1][y]);
			if(y) f[x][y] = add(f[x][y],f[x][y - 1]);
		}
	int ans = 0;
	loop(i,n){
		int x = A[i],y = B[i];
		ans = add(ans,f[x + 2000][y + 2000]);
		ans = add(ans,-C(2*x + 2*y,2*y));
	}
	ans = (ans * 500000004LL)%mod;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 96768
n,k = list(map(int,input().split()))
x = list(map(int,input().split()))
ans = float('inf')
i = 0
while i+k-1<n:
    ans = min(ans,-x[i]+x[i+k-1]+abs(x[i]),-x[i]+x[i+k-1]+abs(x[i+k-1]))
    i += 1
print(ans)


Measured memory_bytes: 14252
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
using ll = long long int;
const int MOD = 1e9 + 7;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	int N = (1 << n);
	vector<int> a(N);
	vector<int> ans(N, 0);
	vector<array<int, 2>> best(N, {-1, -1});
	for (int i = 0; i < N; ++i)
	{
		cin >> a[i];
		best[i][0] = i;
	}
	for (int mask = 0; mask < N; ++mask)
	{
		set<int> ids;
		for (int bit = 0; bit < n; ++bit)
		{
			if ((mask & (1 << bit)) == 0) continue;
			ids.insert(best[mask ^ (1<<bit)][0]);
			if (best[mask ^ (1<<bit)][1] != -1) ids.insert(best[mask ^ (1<<bit)][1]);
		}
		ids.erase(-1);
		for (auto i : ids)
		{
			if (a[i] >= a[best[mask][0]])
			{
				best[mask][1] = best[mask][0];
				best[mask][0] = i;
			}
			else if (best[mask][1] == -1 or a[i] >= a[best[mask][1]]) best[mask][1] = i;
		}
		if (best[mask][1] != -1) ans[mask] = a[best[mask][0]] + a[best[mask][1]];
		if (mask) ans[mask] = max(ans[mask], ans[mask-1]);
		if (mask) cout << ans[mask] << ' ';
	}
}

Measured memory_bytes: 7168
S = input()
if len(S) % 2 == 1:
    print("No")
else:
    for i in range(len(S) // 2):
        if S[2 * i : 2 * i + 2] == "hi":
            pass
        else:
            print("No")
            break
    else:
        print("Yes")


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

using namespace std;

int main(void) {
    long n, m;
    cin >> n >> m;

    vector<pair<long,long>> v(m);
    for(auto &e: v) {
        long a, b;
        cin >> a >> b;
        a--, b--;
        e = make_pair(b, a);
    }
    sort(v.begin(), v.end());

    long r = 0, t = -1e9;
    for(auto &e: v) {
        if(e.second >= t)
            r++, t = e.first;
    }
    cout << r << endl;
}


Measured memory_bytes: 1792
n = int(input())
numl = list(map(int, input().split()))
#numl = list(set(lis))
res = 0
for i in range(len(numl)):
    for j in range(len(numl)):
        if(i <= j):
            break
        else:
            for k in range(len(numl)):
                if((numl[i] + numl[j]> numl[k]) and (i < k) and (numl[k] + numl[j]> numl[i]) and (numl[i] + numl[k]> numl[j])and numl[i] != numl[j]and numl[j] != numl[k] and numl[k] != numl[i]):
                    #print(numl[j], numl[i], numl[k])
                    #print(i, j, k)
                    res+=1
print(res)
             

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

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

int N, M;
struct UnionFind{
    vector<int> parents;
    vector<int> rank;
    UnionFind(int n){
        parents.resize(n);
        rank.assign(n, 1);
        REP(i, n){
            parents[i] = i;
        }
    }
    int find(int x){
        if(parents[x] == x) return x;
        return parents[x] = find(parents[x]);
    }
    
    int unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return -1;
        if(rank[x] > rank[y]) parents[y] = x;
        else{
            parents[x] = y;
            if(rank[x]==rank[y]) rank[y]++;
        }
        return 0;
    }
    
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

struct edge{ll to, cost;};
vector<vector<edge> > edges;
vector<ll> val;
bool isValid = true;
void solve(ll st) {
    for(auto x: edges[st]) {
        if (val[x.to] == -INF*INF) {
            val[x.to] = val[st] + x.cost;
            solve(x.to);
        } else if (val[x.to] != val[st] + x.cost) {
            isValid = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin >> N >> M;
    UnionFind uf(N);
    edges.resize(N, vector<edge>());
    val.resize(N, -INF*INF);
    REP(i, M) {
        int L, R, D;
        cin >> L >> R >> D;
        L--;
        R--;
        uf.unite(L, R);
        edges[L].pb(edge{R, D});
        edges[R].pb(edge{L, -D});
    }
    unordered_set<ll> roots;
    REP(i, N) {
        roots.insert(uf.find((int)i));
    }
    for(auto x: roots) {
        val[x] = 0;
        solve(x);
    }
    if (isValid) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 17280
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
  int n, x;
  cin >> n >> x;

  vector<int> m(n);
  for(int i = 0; i < n; i++) cin >> m[i];

  sort(m.begin(), m.end());

  int cnt = 0;

  for(int i = 0; i < n; i++){
    x -= m[i];
    cnt++;
  }

  for(int i = 0; i < n; i++){
    cnt += x / m[i];
    x %= m[i];
  }

  cout << cnt << endl;

  return 0;

}


Measured memory_bytes: 256
MAX = 10**5 + 1
##下準備(素数判定)(https://python.ms/eratosthenes/#_1-%E7%B0%A1%E5%8D%98%E3%81%AA%E3%82%82%E3%81%AE)
def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return is_prime
a = primes(MAX)
prime = [0]*MAX
for i in range(1,MAX,2):
    if a[i] == 1 and a[int((i+1)/2)] == 1:
        prime[i] = 1
##下準備(累積和)
tmp = 0
csum = [0]*MAX
for i in range(MAX):
    if prime[i] == 1:
        tmp += 1
    csum[i] = tmp
csum.pop()

##入出力
Q = int(input())
lr = []
for i in range(Q):
    lr.append(list(map(int,input().split())))
for i in range(Q):
    print(csum[lr[i][1]]-csum[lr[i][0]-1])

Measured memory_bytes: 30608
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <algorithm>  // std::unique
#include <cmath>
#include <limits.h>
#include <unordered_map>

#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;

using ll = long long;
constexpr auto PrimeBigNum10_9_7 = 1000000007;


// 素数判定
template <typename T>
bool IsPrimeNumber(T value) {

	for (int i = 2; i * i <= value; ++i) {
		if ((value % i) == 0) {
			return true;
		}
	}
	return false;
}

// 桁数判定
template <typename T>
T GetFigureLength(T value) {
	T figure = 1;
	while (value >= 10) {
		value /= 10;
		++figure;
	}
	return figure;
}

// 素因数分解結果
template <typename T>
map<T, T> GetPrimeFactorize(T value) {

	map<T, T> res;

	for (T i = 2; i * i <= value; ++i) {
		if ((value%i) != 0)	continue;

		T count = 0;
		while ((value % i) == 0) {
			value /= i;
			++count;
		}

		res[i] = count;
	}

	if (value != 1) {
		res[value] = 1;
	}
	return res;
}

void DebugPrint(const vector<ll>& vec) {
	cout << "{";
	for (auto itr = vec.begin(); itr != vec.end(); ++itr) {
		cout << *itr << ",";
	}
	cout << "}" << endl;
}

// valueが2のx乗以下である計算
ll calc2x(ll value) {
	ll n = 0;
	while (value > 0) {
		value /= 2;
		++n;
	}
	return n;
}

struct Vec2 {
	double x;
	double y;

	void rotate(double rad) {
		double s = sin(rad);
		double c = cos(rad);
		double tmpX = this->x*c - this->y*s;
		double tmpY = this->x*s + this->y*c;
		this->x = tmpX;
		this->y = tmpY;
	}
};

int main(void) {

	ll a,b;
	cin >> a >> b;
	int h, m;
	cin >> h >> m;

	string ans = "";

	double m2 = m / 60.0;
	double radH = (h / 12.0+m2/12.0) * 2* M_PI;
	double radM = m / 60.0 * 2 * M_PI;

	Vec2 posH = { 0,(double)a };
	posH.rotate(radH);
	
	Vec2 posM = { 0,(double)b };
	posM.rotate(radM);


	double d = pow(posH.x - posM.x, 2) + pow(posH.y - posM.y, 2);
	d = sqrt(d);
	cout << fixed << setprecision(20) << d;
	//auto output = d;
	//cout << output;

	return 0;
}


Measured memory_bytes: 4132
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
#define rep(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int inf = 2e9;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	vector<vector<int>> s(m);
	rep(i, 0, m) {
		int k; cin >> k;
		rep(j, 0, k) {
			int q; cin >> q;
			s[i].push_back(q);
		}
	}
	vector<int> p(m);
	rep(i, 0, m) cin >> p[i];
	int ans = 0;
	rep(mask, 0, (1 << n)) {
		int flag = true;
		rep(i, 0, m) {
			int cnt = 0;
			rep(k, 0, s[i].size()) {
				if ((mask >> (s[i][k]-1)) & 1) cnt++;
			}
			if (cnt % 2 != p[i]) flag = false;
		}
		if (flag) ans++;
	}
	printf("%d",ans);
	return 0;
}


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

using namespace std;
#define intMax 2147483647
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repp(i, a, b) for (int i = a; i >= b; i--)
#define be(a) (a.begin(), a.end())
#define rbe(p) (p.rbegin(), p.rend())
#define pb push_back

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    if (n * 500 >= m)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}

Measured memory_bytes: 256
N = int(input())
dic = {"AC":0, "WA":0, "TLE":0, "RE":0}
for _ in range(N):
    s = input()
    dic[s] += 1

print("AC x " + str(dic["AC"]))
print("WA x " + str(dic["WA"]))
print("TLE x " + str(dic["TLE"]))
print("RE x " + str(dic["RE"]))

Measured memory_bytes: 9204
N = int(input())
S = list(map(str, input()))
# print(S)
count = 0
for i in range(N - 2):
    cha = "".join(S[i:i + 3])
    # print(cha)
    if cha == "ABC":
        count += 1
    else:
        continue

print(count)

Measured memory_bytes: 3060
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
const int maxn = 1100;

int main()
{
	char s[maxn], t[maxn];
	cin >> s >> t;
	int len;
	len = strlen(s);
	int flag = 0;
	int count = 0;
	while(count < len)
	{
		reverse(s , s + len - 1);
		reverse(s, s + len);
		if(strcmp(s, t) == 0)
		{
			flag = 1;
			break;
		}
		count++;
	}
	if(flag == 1){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

	
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

B = []
b = 0
for a in A:
    b += a
    B.append(b)

ans = 10**14
for i in range(N):
    ans = min(abs(B[-1]-2*B[i]), ans)
print(ans)

Measured memory_bytes: 92240
#include <iostream>
#include <set>
#include <map>
#include <vector>
#define llint long long

using namespace std;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint n, m, k;
vector<llint> G[100005], G2[100005];
UnionFind uf(100005);
map<llint, llint> mp;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k;
	llint u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		uf.unite(u, v);
	}
	for(int i = 1; i <= k; i++){
		cin >> u >> v;
		G2[u].push_back(v);
		G2[v].push_back(u);
	}
	
	for(int i = 1; i <= n; i++) mp[uf.root(i)]++;
	for(int i = 1; i <= n; i++){
		llint ans = mp[uf.root(i)] - 1;
		ans -= (int)G[i].size();
		for(int j = 0; j < G2[i].size(); j++){
			if(uf.same(i, G2[i][j])) ans--;
		}
		cout << ans << " ";
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 17024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
    int t0, t1, id;
    bool operator<(const node a) const
    {
        return 1LL * t1 * a.t0 > 1LL * t0 * a.t1;
    }
};
int n, f[200001], fa[200001], cnt[200001][2];
priority_queue<node> q;
int find(int x)
{
    if (x == fa[x])
    {
        return x;
    }
    return fa[x] = find(fa[x]);
}
int main(int argc, char const *argv[])
{
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
    {
        scanf("%d", &f[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        cnt[i][x]++;
        fa[i] = i;
    }
    long long ans = 0;
    for (int i = 2; i <= n; i++)
    {
        q.push((node){cnt[i][0], cnt[i][1], i});
    }
    while (!q.empty())
    {
        node tmp = q.top();
        q.pop();
        int fx = find(tmp.id), fy = find(f[fx]);
        if (cnt[fx][0] != tmp.t0 || cnt[fx][1] != tmp.t1)
        {
            continue;
        }
        ans += 1LL * cnt[fx][0] * cnt[fy][1];
        cnt[fy][0] += cnt[fx][0];
        cnt[fy][1] += cnt[fx][1];
        fa[fx] = fy;
        if (fy > 1)
        {
            q.push((node){cnt[fy][0], cnt[fy][1], fy});
        }
    }
    printf("%lld", ans);
    return 0;
}

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

#define TASK ""
#define openfile ({freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);})

const int N = 100005;

int n;
int a[N];
map <int, int> f;

int main() {
	//openfile;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], f[a[i]]++;
	sort(a + 1, a + 1 + n);
	if (f.size() == 1) {
		return cout << n, 0;
	} else if (f.size() == 2) {
		if (a[n] - a[1] == 1 || a[n] - a[1] == 2) return cout << n, 0;
		int cnt1 = 0, cnt2 = 0;
		for (int i = 1; i <= n; i++)
			if (a[i] == a[1]) cnt1++;
			else if (a[i] == a[n]) cnt2++;
		return cout << max(cnt1, cnt2), 0;
	} else {
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			ans = max(ans, f[a[i]] + f[a[i] - 1] + f[a[i] + 1]);
		}
		cout << ans << "\n";
	}
	return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
int main()
{
    int H, W;
    cin>>H>>W;

    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            string s;
            cin >> s;
            if (s=="snuke") cout << char(j+'A') << i+1<< endl;
        }
    }


   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<bool>> vvb;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define vrep(v,n) for(int i=0;i<n;i++){cin >> v.at(i);} 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int mod = 1000000007;
const int inf = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};

ll n;

ll dfs(ll k){
    if(k > n) return 0;
    ll nk = k;

    set<ll> a;
    while(nk>0){
        a.insert(nk%10);
        nk /= 10;
    }

    ll ret = 0;
    if(a.size()==3) ret++;
    ret += dfs(k*10+3);
    ret += dfs(k*10+5);
    ret += dfs(k*10+7);
    return ret;
}

int main(){
    cin >> n;
    cout << dfs(0LL);   
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
  int a, b, c, x;
  scanf("%d", &a);
  scanf("%d", &b);
  scanf("%d", &c);
  scanf("%d", &x);
  int cnt = 0;
  for (int i = 0; i <= a; i++)
  {
    for (int j = 0; j <= b; j++)
    {
      for (int k = 0; k <= c; k++)
      {
        if (i * 500 + j * 100 + k * 50 == x)
        {
          cnt++;
        }
      }
    }
  }
  printf("%d\n", cnt);
}

Measured memory_bytes: 888
#include<stdio.h>
#include<math.h>
int main(void){
    int n,i;
    double x1,y1,x2,y2,x3,y3,px,py,r,A1,B1,C1,A2,B2,C2,X,Y,a,b,c,R;
    scanf("%d",&n);
    for(i=0;i<n;i++){
    scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
    A1=2*(x2-x1),B1=2*(y2-y1),C1=x1*x1-x2*x2+y1*y1-y2*y2;
    A2=2*(x3-x1),B2=2*(y3-y1),C2=x1*x1-x3*x3+y1*y1-y3*y3;
    X=(B1*C2-B2*C1)/(A1*B2-A2*B1);
    Y=(C1*A2-C2*A1)/(A1*B2-A2*B1);
    a=sqrt((fabs(x1-x2))*(fabs(x1-x2))+(fabs(y1-y2))*(fabs(y1-y2)));
    b=sqrt((fabs(x2-x3))*(fabs(x2-x3))+(fabs(y2-y3))*(fabs(y2-y3)));
    c=sqrt((fabs(x3-x1))*(fabs(x3-x1))+(fabs(y3-y1))*(fabs(y3-y1)));
    R=(a*b*c)/(sqrt((a+b+c)*(0-a+b+c)*(a-b+c)*(a+b-c)));
    if(fabs(X)<0.0000001)
        X=0;
    if(fabs(Y)<0.0000001)
        Y=0;
    if(fabs(R)<0.0000001)
        R=0;
    printf("%.3lf %.3lf %.3lf\n",X,Y,R);
    }
    return 0;
}

Measured memory_bytes: 664
//
//  main.cpp
//  D
//
//  Created by 黄宇凡 on 2017/4/9.
//  Copyright © 2017年 黄宇凡. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 150000 + 5;

double dp[maxn][2];
vector<int> G[maxn];

int n;

void dfs(int u,int fa){
    dp[u][0] = 1.0;
    int deg = G[u].size() - (u != fa);
    //cout << deg << endl;
    for(int i = 0;i < G[u].size();i++){
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v,u);
        dp[u][0] += 1.0 / deg * dp[v][0];
    }
    //cout << u << "!!!" << dp[u][0] << endl;
}

void Dfs(int u,int fa){
    if(u == fa){
        dp[u][1] = dp[u][0];
    }else{
        int d1 = G[u].size();
        int d2 = G[fa].size();
        dp[u][1] = 1.0 * (d1 - 1) / d1 * (dp[u][0] - 1) + 1 + 1.0 / d1 * ((d2 == 1 ? 0 : ((dp[fa][1] - 1) - 1.0 / d2 * dp[u][0]) * 1.0 * d2 / (d2 - 1)) + 1);
    }
    for(int i = 0;i < G[u].size();i++){
        int v = G[u][i];
        if(v == fa) continue;
        Dfs(v,u);
    }
}


int main(int argc, const char * argv[]) {
    cin >> n;
    for(int i = 1;i <= n;i++) G[i].clear();
    for(int i = 1;i < n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,1);
    Dfs(1,1);
    for(int i = 1;i <= n;i++){
        //cout << dp[i][0] << endl;
        //cout << dp[i][1] - 1 << endl;
        printf("%.10lf\n",dp[i][1] - 1);
    }
    return 0;
}


Measured memory_bytes: 18560
# include <stdio.h>

int main(){
	int dish[25];
	int points[55];
	int extra[55];
	int n;
	int max = 0;
	int ex = 0;

	scanf("%d", &n);
	for (int j = 0; j < n; ++j){
		scanf("%d", &dish[j]);
	}
	for (int v = 0; v < n; ++v){
		scanf("%d", &points[v]);
	}

	for (int h = 0; h < n-1; ++h){
		scanf("%d", &extra[h]);
	}

	for (int i = 0; i < n; ++i){
		max = max + points[i];

		if (i != 0 && dish[i] - dish[i-1] == 1){
			max = max + extra[dish[i-1]-1];
			ex = ex+1;
				}
			}

	printf("%d\n", max);


	return 0;
}


Measured memory_bytes: 128
function main(){
	x = [];
	rep(10, function(i){
		x[i] = scan();
	});
	x.sort(function(a, b){
		return b - a;
	});
	rep(3, function(i){
		print(x[i]);
	});
}
 
function rep(a, b, c){
	if(c == null){
		c = b;
		b = a;
		a = 0;
	}
	for(var i = a; i < b; ++i){
		c(i);
	}
}
 
process.stdin.resume();
process.stdin.setEncoding('utf8');
 
var input = '';
var input_index = 0;
 
function scan(type){
	if(type === 'string'){
		return input[input_index++];
	}
	else{
		return +input[input_index++];
	}
}
 
function print(val){
	console.log(val);
}
 
process.stdin.on('data', function(chunk){
	input += chunk;
});
process.stdin.on('end', function(){
	input = input.split(/\s+/);
	main();
});

Measured memory_bytes: 15576
# -*- coding: utf-8 -*-
r,g,b,n = map(int, input().split())

cnt = 0
for ri in range(n+1):
    if r*ri>n:
        break
    for gi in range(n+1):
        x = n - r*ri - g*gi
        if x<0:
            break
        if x%b==0:
            cnt += 1

print(cnt)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define ff first
#define ss second
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end();
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int main(){
	ios::sync_with_stdio(0);
		int x, a;
		cin >> x >> a;
	if(x<a)
		cout << 0 << endl;
	else 
		cout << 10 << endl;
}

Measured memory_bytes: 256
object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList
  val n    = inputs(0).toInt
  val nums = inputs(1).split(" ").map(_.toInt)

  println(solve(n, nums))

  def solve(n: Int, nums: Array[Int]): Int = {
    val countMap = scala.collection.mutable.HashMap.empty[Int, Int]

    nums.foreach { num =>
      countMap.update(num, countMap.applyOrElse(num, (v: Int) => 0) + 1)
    }

    var ans = 0
    countMap.foreach { case (k, v) =>
      if (k != v) {
        if (k < v) {
          // println(s"k = $k, v = $v: ${k - v}")
          ans = ans + Math.abs(k - v)
        } else {
          // println(s"k = $k, v = $v: $v")
          ans = ans + v
        }
      }
    }

    ans
  }
}

Measured memory_bytes: 65972
n,k=map(int,input().split())
s=[]
s2=[]
mod=998244353

for i in range(k):
    l,r=map(int,input().split())
    s+=[i for i in range(l,r+1)]
    s2.append([l,r])
s.sort()
dp=[0]*(n+1)
dpsum=[0]*(n+1)
dp[1]=1
dpsum[1]=1
for i in range(2,n+1):
    for j in range(k):
        if i-s2[j][0]>=0:
            dp[i]+=(dpsum[i-s2[j][0]]-dpsum[max(i-s2[j][1],1)-1])%mod
            dp[i]%=mod
    dpsum[i]=(dpsum[i-1]+dp[i])%mod
print(dp[n])


Measured memory_bytes: 91192
#include <iostream>
#include <vector>

using namespace std;

int N;
int Max;
vector< vector<char> > Field;

void DFS_right(int y, int x, int count)
{
	if(Max < count)
	{
		Max = count;
	}
	if(0 <= x && x < N && 0 <= y && y < N && Field[y][x] == '1')
	{
		DFS_right(y, x + 1, count + 1);
	}	
}

void DFS_down(int y, int x, int count)
{
	if(Max < count)
	{
		Max = count;
	}
	if(0 <= x && x < N && 0 <= y && y < N && Field[y][x] == '1')
	{
		DFS_down(y + 1, x, count + 1);
	}	
}

void DFS_rightdown(int y, int x, int count)
{
	if(Max < count)
	{
		Max = count;
	}
	if(0 <= x && x < N && 0 <= y && y < N && Field[y][x] == '1')
	{
		DFS_rightdown(y + 1, x + 1, count + 1);
	}	
}

void DFS_leftdown(int y, int x, int count)
{
	if(Max < count)
	{
		Max = count;
	}
	if(0 <= x && x < N && 0 <= y && y < N && Field[y][x] == '1')
	{
		DFS_leftdown(y + 1, x - 1, count + 1);
	}	
}

void solve()
{
	while(cin >> N, N)
	{
		Field.resize(N);
		for(int i = 0; i < N; ++i)
		{
			Field[i].resize(N);
			for(int j = 0; j < N; ++j)
			{
				cin >> Field[i][j];
			}
		}

		Max = 0;
		for(int i = 0; i < N; ++i)
		{
			for(int j = 0; j < N; ++j)
			{
				if(Field[i][j] == '1')
				{
					DFS_right(i, j + 1, 1);
					DFS_down(i + 1, j, 1);
					DFS_rightdown(i + 1, j + 1, 1);
					DFS_leftdown(i + 1, j - 1, 1);
				}
			}
		}
		cout << Max << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 980
import java.io.*;
public class Main {
	public static void main(String[] args){
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		try{
        	while(true) {
        		String line = reader.readLine();
        		String[] num = line.split(" ", -1);
        		int H = Integer.parseInt(num[0]);
        		int W = Integer.parseInt(num[1]);
        		if (H == 0 && W == 0) {
        			break;
        		} else {
        			for (int i = 0; i < H; i++) {
        				for (int j = 0; j < W; j++) {
        					System.out.print("#");
        				}
        				System.out.println();
        			}
        			System.out.println();
        		}
        	}
        } catch (IOException e) {
          System.out.println(e);
        } catch (NumberFormatException e) {
          System.out.println("error");
        }
    }
}

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

using namespace std;

int main() {
    // input
    int A, B, C, X;
    cin >> A >> B >> C >> X;

    // O(ABC) = 0(N^3)
    int count = 0;
    for (int i = 0; i <= A; i++) {
        for (int j = 0; j <= B; j++) {
            for (int k = 0; k <= C; k++) {
                if (X == (500 * i + 100 * j + 50 * k)) {
                    count++;
                    break;
                }
            }
        }
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 256