akhauriyash/Code-Regression huggingface dataset:
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let m: u64 = sc.read();
    let d: u64 = sc.read();
    let mut ans = 0;
    for m in 1..(m + 1) {
        for d in 1..(d + 1) {
            if d >= 10 {
                let d1 = d % 10;
                let d10 = d / 10;
                if d1 >= 2 && d10 >= 2 && d1 * d10 == m {
                    ans += 1;
                }
            }
        }
    }
    println!("{}", ans);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    char c;
    cin >> c;
    if (c == 'C') {
        std::cout << "G" << std::endl;
    } else 
    if (c == 'G') {
        std::cout << "C" << std::endl;
    } else 
    if (c == 'T') {
        std::cout << "A" << std::endl;
    } else {
        std::cout << "T" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n)for(int i=0;i<n;i++)

const ll INF = 1001001001;


int main(){
  ll n,k;
  cin>>n>>k;
  vector<ll>h(n);
  rep(i,n){
    cin>>h[i];
  }
  ll sum=0;
  sort(h.begin(),h.end());//昇順
  if(n<k){
    cout<<0<<endl;
  }else{
    for(int i=0;i<n-k;i++){
      sum+=h[i];
    }
    cout<<sum<<endl;

  }
  

  
  
}

Measured memory_bytes: 1792
function main(lines) {
  const input = lines.split(' ')
  let count = 0;
  for(let i=0; i<input.length; i++){
      count++
      if(input[i] == 0){
          break;
      }
  }
  console.log(count)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));



Measured memory_bytes: 29584
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string S;
  cin >> S;
  
  if(S[0] == S[1] && S[1] == S[2]) cout << "No" << endl;
  else cout << "Yes" << endl;
  

}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <stdlib.h>
#include <stdio.h>

using namespace std;

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; }

int abs_A(int num) {
    if (num > 0)
        return num;
    else
        return -num;
}

int abs_B(long long num, long long numb) {
    if (num - numb >= 0)
        return num - numb;
    else
        return -1 * (num - numb);
}

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

long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}



const long long MOD = 1000000007;

int main() {
    int N, X;
    cin >> N >> X;
    int ans = 0;

    while (N != 0) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    if (i == j || j == k || i == k) {
                        continue;
                    }
                    if (i + j + k == X) {
                        ans++;
                        //cout << i << j << k << endl;
                    }
                }
            }
        }
        
        cin >> N >> X;
        cout << ans / 6 << endl;
        ans = 0;
        
    }
    

    
}




Measured memory_bytes: 3100
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>
#include <stack>
#include <cstdlib>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define rep(i, a, N) for(int i = a; i < N; i++)
#define rrep(i, a, N) for(int i = a; i >= N; i--)

const int inf = 1000000000;

//#define DEBUG

int main() {
    int n, k;
    cin >> n >> k;
    vector<double> _exp(n);

    rep(i, 0, n) {
        int p;
        cin >> p;
        _exp[i] = (p + 1) / 2.0;

        #ifdef DEBUG
            cout << i << ":" << _exp[i] << endl;
        #endif
    }

    double total = 0.0;
    rep(i, 0, k) total += _exp[i];

    int left = 0;
    int right = k;
    double ans = total;
    while(right < n) {
        total = total + _exp[right] - _exp[left];
        ans = max(ans, total);
        #ifdef DEBUG
            cout << left << " " << right << " " << ans << endl;
        #endif
        left++;
        right++;
    }

    printf("%.10f\n", ans);
}

Measured memory_bytes: 1792
fun main(args: Array<String>) {
    val s = readLine() ?: return
    val match = mapOf('A' to 1, 'C' to 1, 'G' to 1, 'T' to 1)
    var longest = 0
    var counter = 0
    s.forEach {
        if (match.containsKey(it)) {
            counter++
        } else {
            longest = Math.max(counter, longest)
            counter = 0
        }
    }
    longest = Math.max(counter, longest)
    println(longest.toString())
}

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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;

int main() {
	ll n, a, b;
	scanf("%lld%lld%lld", &n, &a, &b);
	if (abs(a-b)%2 == 0) {
		printf("%lld\n", abs(a-b)/2);
	} else {
		ll x = min(min(a-1, b-1), min(n-a, n-b));
		printf("%lld\n", x+(abs(a-b)+1)/2);
	}
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    int a[n];
    //全て奇数の時をカウント   
    int cnt = 1;
    for(int i = 0; i < n; i++ ){
        cin  >> a[i];
        if(a[i] % 2 == 0){
            cnt *= 2;
        }else{
            cnt *= 1;
        }
    }
    cout << pow(3,n) - cnt << endl;
    return 0;
}


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

//#pragma gcc optimize("O3,unroll-loop")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
#define int long long
//#define double long double

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    map<int, int> mp;
    for (int i = -1000; i <= 1000; i++)
        mp[i * i * i * i * i] = i;

    int x;
    cin >> x;

    for (auto p : mp)
        if (mp.count(p.first - x))
            cout << p.second << ' ' << mp[p.first - x] << '\n', exit(0);

    return 0;
}

//      *   *  *****  *   *  *   *
//     *   *  *      **  *  *   *
//    *****  *****  * * *  *   *
//   *   *      *  *  **  *   *
//  *   *  *****  *   *   ***

//      ***** ***** *   * *     ***** *   * ***** *****
//        *  *   * *   * *       *   **  *   *   *   *
//       *  *   * ***** *       *   * * *   *   *****
//   *  *  *   *   *   *       *   *  **   *   *
//  ****  *****   *   ***** ***** *   *   *   *


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

using lli = long long int;

using namespace std;

int main() {
    lli N, K;
    cin >> N >> K;

    std::vector<lli> h(N);
    std::for_each(h.begin(), h.end(), [](auto &x) { cin >> x; });

    std::vector<lli> dp(N, 1000000001);
    dp[0] = 0;
    dp[1] = std::abs(h[0] - h[1]);

    for (lli i = 2; i < N; ++i) {
        for (lli n = i - 1; n >= i - K; --n) {
            if (n < 0) { break; }
            dp[i] = std::min(dp[i], dp[n] + std::abs(h[n] - h[i]));
        }
    }

    cout << dp[N - 1] << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define st first
#define nd second

using ll = long long ;
using namespace std;
using pii = pair<int,int>;
int a[(int)2e5 + 10];
int main(){
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	int mi = 1, ma = 1e9;
	while(mi < ma){
		int mid = mi + ma >> 1;
		int cnt = 0;
		bool io = true;
		for(int i = 1; i <= n; i++){
			cnt += (a[i] - 1) / mid;
			if(cnt > k) {
				io = false;
				break;
			} 
		}
		if(io) ma = mid;
		else mi = mid + 1;
	}
	printf("%d", mi);
	

}

Measured memory_bytes: 4572
N = int(input())
ans = 0
for i in  list(map(int, input().split())):
    if i % 4 == 0:
        ans += 1
    elif i % 2 != 0:
        ans -= 1

if N % 2 != 0:
    ans += 1

print('Yes' if ans >= 0 else 'No')

Measured memory_bytes: 14252
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

int main() {
  string s;
  cin >> s;
  int n = s.length();
  if (n == 1) {
    cout << s << endl;
    return 0;
  }
  for (int i = 1; i < n; ++i) {
    if (s[i] != '9')
      break;
    if (i == n - 1) {
      cout << 9 * (n - 1) + s[0] - '0' << endl;
      return 0;
    }
  }
  auto ans = (n - 1) * 9;
  ans += s[0] - '1';
  cout << ans << endl;
}

Measured memory_bytes: 256
using System;
class Program{
  static void Main(){
    string[] NK = Console.ReadLine().Split(' ');
    int N = int.Parse(NK[0]);
    int K = int.Parse(NK[1]);
    string[] h = Console.ReadLine().Split(' ');
    
    int count = 0;
    for (int i = 0; i < N; i++){
      if (int.Parse(h[i]) >= K)
        count++;
    }
    
    Console.WriteLine(count);
  }
}

Measured memory_bytes: 17504
import math
n,k= map(int, input().split())


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod

mod = 10 ** 9 + 7
N =10 ** 6 # 出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)



if k>=n-1:
    ans = cmb(2 * n - 1, n - 1, mod)
    print(ans)
else:
    ans=1
    for i in range(1,k+1):
        ans+=cmb(n-1,n-1-i,mod)*cmb(n,i,mod)
        ans%=mod
    print(ans)

Measured memory_bytes: 128580
#include <string>
#include <iostream>
#include <set>
 
using namespace std;
 
// 文字列一つ受け取る場合
// string s;
// 整数(max 2^31-1 or 10^9)一つ受け取る場合
// int x;
// int k;
// int n;
// set<int> a;

 
 
int main(){
    int x;
    int y;
    int z;
    cin >> x;
    cin >> y;
    cin >> z;
    cout << z << ' ';
    cout << x << ' ';
    cout << y;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

using ll = long long;
using namespace std;

int N, M;
vector<vector<int>> mat;

bool isend(vector<bool> visited) {
    for (int i = 0; i < N; i++) {
        if (!visited[i])return false;
    }
    return true;
}

//現在の頂点
int dfs(int v, vector<bool> visited) {
    //すべての頂点訪問済み
    if (isend(visited)) {
        return 1;
    }

    int ret = 0;
    for (int i = 0; i < N; i++) {
        if (visited[i])continue;
        //辺が存在する
        if (mat[v][i] == 1) {
            visited[i] = true;
            ret += dfs(i, visited);
            visited[i] = false;
        }
    }
    return ret;
}

int main() {
    cin >> N >> M;
    mat = vector<vector<int>>(N, vector<int>(N));
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        mat[a][b] = 1;
        mat[b][a] = 1;
    }
    vector<bool>visited(N);
    visited[0] = true;
    cout << dfs(0, visited)
        << endl;
    return 0;
}


Measured memory_bytes: 764
### subroutines

def setcost(d, n, e, cost)
  k = (n >= d) ? n : d
  (k * e < cost) ? k * e : cost
end

def min_cost(a, b, c, d, e, na, nb, nc)
  minc = a * na + b * nb + setcost(d, nc, e, c * nc)
  for n in (1..nb)
    c = a * na + b * (nb - n) + setcost(d, nc + n, e, c * nc + b * n)
    minc = c if minc > c
  end
  for n in (1..na)
    c = a * (na - n) + setcost(d, nc + nb + n, e, c * nc + b * nb + a * n)
    minc = c if minc > c
  end
  minc
end

### main

loop do
  a, b, c, d, e = gets.split.map(&:to_i)
  break if a == 0

  na, nb, nc = gets.split.map(&:to_i)

  puts min_cost(a, b, c, d, e, na, nb, nc)
end

Measured memory_bytes: 6116
A, B, M = map(int, input().split())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
c = {}
m = 2000000
for i in range(M):
    x, y, c2 = map(int, input().split())
    c[(x, y)] = c2
    value = a[x-1] + b[y-1] - c2
    if m > value:
        m = value

if (min(a), min(b)) in c:
    print(m)
else:
    if m > min(a) + min(b):
        print(min(a) + min(b))
    else:
        print(m)

Measured memory_bytes: 78780
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int X,A,B;
int N;
vector<string> S;

int main(){
  cin>>X>>A>>B;
  cin>>N;
  S.resize(N);
  rep(i,N) cin>>S[i];

  int now=X;
  for(int i=0;i<N;i++){
    if(S[i][0]=='n') now=max(0,now+A);
    else if(S[i][0]=='t') now=max(0,now+B);
    else now=0;
  }

  cout<<now<<endl;

  return 0;
}



Measured memory_bytes: 3232
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{
    
    class Program
    {

        static List<string> button_combi;

        static void Create_button_combi(string str, int cnt, int state, int N)
        {
            string s = "";

            if (cnt != 0)
            {
                s = str + state.ToString();             
            }

            if (cnt >= N)
            {
                button_combi.Add(s);
                return;
            }
            
            Create_button_combi(s, cnt + 1, 1, N);
            
            Create_button_combi(s, cnt + 1, 0, N);

        }
        
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            button_combi = new List<string>();
            List<int>[] bulb = new List<int>[M];
            int[] bulb_val = new int[M];

            Create_button_combi("", 0, 0, N);

            for(int i = 0; i < M; i++)
            {
                int[] a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

                bulb[i] = new List<int>();

                for (int j = 1; j < a.Count(); j++)
                {
                    bulb[i].Add(a[j] - 1);
                }
            }

            bulb_val = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            int ans = 0;

            foreach(var bt_str in button_combi)
            {
                int cnt_bulb_on = 0;

                // i番目のバルブ
                for(int i = 0; i < M; i++)
                {

                    int cnt_bt_on = 0;

                    for(int j = 0; j < bulb[i].Count(); j++)
                    {
                        int bt_num = bulb[i][j];
                        
                        if(bt_str[bt_num] == '1')
                        {
                            cnt_bt_on++;
                        }                  

                    }
                    
                    if(cnt_bt_on % 2 == bulb_val[i])
                    {
                        cnt_bulb_on++;
                    }

                }

                
                if(cnt_bulb_on == M)
                {
                    ans++;
                }
            }



            Console.WriteLine(ans);
            
        }
    }
}

Measured memory_bytes: 13524
import math
 
N = int(input())
V = []
for _ in range(N):
    V.append([ int(n) for n in input().split() ])
 
R2 = 0
for i in range(100): 
    theta = 2 * math.pi * i / 100  
    a, b = math.cos(theta), math.sin(theta)  ### a=cosθ、b=sinθ　（θ=2π*i/100） 
    X, Y = 0, 0
    for x, y in V: ### xi と yi を取り出す
        if a*x+b*y > 0: ### 正の数ならば
            X += x
            Y += y
    r2 = X**2+Y**2
    if r2 > R2:
        R2 = r2
 
print(math.sqrt(R2))

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

int main() {
    int N, i;
    double a, sum;
    
    while (cin >> N) {
        sum = 0.0;
        for (i=0; i<N; i++) {
            cin >> a;
            sum += 1.0/a;
        }
        cout << 1.0/sum << endl;
    }
    return 0;
}


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

using namespace std;

const int MAX_N = (1 << 22);
const int MAX_M = 25;
const int MOD = 1000000007;

int n;

int comp[MAX_M][MAX_M];
long long dp[MAX_N];

int countBits(int n) {
  int ans = 0;
  while (n > 0) {
    ++ans;
    n -= n & (- n);
  }
  return ans;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      scanf("%d", &comp[i][j]);
    }
  }
  dp[0] = 1;
  for (int mask = 0; mask < (1 << n); ++mask) {
    int bits = countBits(mask);
    for (int i = 0; i < n; ++i) {
      if (((1 << i) & mask) == 0) {
        if (comp[1 + i][bits + 1] > 0) {
          dp[mask | (1 << i)] = (1LL * dp[mask | (1 << i)] + dp[mask] % MOD) % MOD;
        }
      }
    }
  }
  printf("%lld", dp[(1 << n) - 1]);
  return 0;
}


Measured memory_bytes: 18816
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()

    val aa = mutableListOf<Int>()
    val bb = mutableListOf<Int>()
    val cc = mutableListOf<Int>()

    repeat(n) {
        val (a, b, c) = readLine()!!.split(" ").map { it.toInt() }
        aa.add(a)
        bb.add(b)
        cc.add(c)
    }

    val dp = Array(n+1) { IntArray(3) {0} }

    for (i in 1..n) {
        dp[i][Activities.A] = Math.max(dp[i-1][Activities.B], dp[i-1][Activities.C]) + aa[i-1]
        dp[i][Activities.B] = Math.max(dp[i-1][Activities.A], dp[i-1][Activities.C]) + bb[i-1]
        dp[i][Activities.C] = Math.max(dp[i-1][Activities.A], dp[i-1][Activities.B]) + cc[i-1]
    }

    println(listOf(dp[n][Activities.A], dp[n][Activities.B], dp[n][Activities.C]).max())
}

object Activities {
    const val A = 0
    const val B = 1
    const val C = 2
}

Measured memory_bytes: 68388
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define LL long long
const LL inf = 0x3f3f3f3f3f3f3f3f;

LL x[1001],y[1001];

vector<LL>len;

LL dir[4][2]={0,1,0,-1,1,0,-1,0};
char s[4]={'U','D','R','L'};


LL mht(LL x,LL y,LL a,LL b)
{
	return abs(x-a)+abs(y-b);
}

int main()
{
	LL n;
	scanf("%lld",&n);
	for(LL i=1;i<=n;i++){
		scanf("%lld%lld",&x[i],&y[i]);
	}
	for(LL i=2;i<=n;i++){
		if(((x[i]^y[i])&1)!=((x[1]^y[1])&1)){
			printf("-1\n");
			return 0;
		}
	}
	for(LL i=30;i>=0;i--){
		len.push_back(1LL<<i);
	}
	if(((x[1]^y[1])&1)==0){
		len.push_back(1);
	}
	printf("%lld\n",(LL)len.size());
	for(LL i=0;i<len.size();i++){
		if(i) printf(" ");
		printf("%lld",len[i]);
	}
	printf("\n");
	for(LL i=1;i<=n;i++){
		LL xx=0,yy=0;
		for(LL j=0;j<len.size();j++){
			LL Min=inf;
			LL pos=-1;
			for(LL k=0;k<4;k++){
				LL l=mht(xx+dir[k][0]*len[j],yy+dir[k][1]*len[j],x[i],y[i]);
				if(Min>l){
					Min=l;
					pos=k;
				}
			}
			printf("%c",s[pos]);
			xx+=dir[pos][0]*len[j];
			yy+=dir[pos][1]*len[j];
		}
		printf("\n");
	}


}





Measured memory_bytes: 256
fn main() {
    let nmd: Vec<u32> = read_vec();
    let n: f64 = nmd[0] as f64;
    let m: f64 = nmd[1] as f64;
    let d: u32 = nmd[2];

    let k = if d == 0 {n} else {2.0 * (n - d as f64)};
    let mut r = (m - 1.0) * k / n / n;

    println!("{}", r);
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a) ; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sp system("pause")
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
const int N = (int) 1e5 + 10;
void TimeExecution() {
    cout << "\n\n===>> Time Execution: " << clock() / (double)1000 << " sec(s).";
}
int t;
int n, m;
int s[10];
int c[10];
bool check(int i)
{
    bool ok = 1;
    int tmp = i;
    string st;
    if(tmp == 0)
    {
        st = '0' + st;
    }
    else
    {
        while(tmp)
        {
            st = char((tmp % 10) + '0') + st;
            tmp /= 10;
        }
    }
    st = " " + st;
    FOR(j, 1, m)
    {
        if(st[s[j]] - '0' != c[j])
        {
            ok = 0;
            break;
        }
    }
    return ok;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    */
    cin >> n >> m;
    FOR(i, 1, m)
    {
        cin >> s[i] >> c[i];
    }
    if(n == 1)
    {
        FOR(i, 0, 9)
        {
            if(check(i))
            {
                cout << i;
                return 0;
            }
        }
    }
    if(n == 2)
    {
        FOR(i, 10, 99)
        {
            if(check(i))
            {
                cout << i;
                return 0;
            }
        }
    }
    if(n == 3)
    {
        FOR(i, 100, 999)
        {
            if(check(i))
            {
                cout << i;
                return 0;
            }
        }
    }
    //cout << check(702);
    cout << -1;
    return 0;
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	ll N=in(),x=in();
	auto V=vecin<ll>(N);
	ll sum=0;
	REP(i,N-1){
		ll s=V[i]+V[i+1];
		if(s>x){
			ll sub = s-x;
			sum += sub;
			if(V[i+1]-sub<0){
				ll dsub = sub-V[i+1];
				V[i+1] = 0;
				V[i] -= dsub;
			}
			else{
				V[i+1] -= sub;
			}
		}
	}
	out(sum);
	return 0;
}


Measured memory_bytes: 1024
n=int(input())
a,b,c,d=0,0,0,0
for k in range(n):
    s=str(input())
    if(s=='AC'):
        a+=1
    elif(s=="WA"):
        b+=1
    elif(s=="TLE"):
        c+=1
    elif(s=="RE"):
        d+=1
print("AC x",a)
print("WA x",b)
print("TLE x",c)
print("RE x",d)

Measured memory_bytes: 9208
N=int(input())
A=[list(map(int,input().split())) for _ in range(2)]
sum1=[0]
sum2=[0]
for i in range(N):
    sum1.append(sum1[-1]+A[0][i])
    sum2.append(sum2[-1]+A[1][i])

print(max(sum1[i]+sum2[N]-sum2[i-1] for i in range(1,N+1)))


Measured memory_bytes: 9124
#include <iostream>
using namespace std;
static const int MAX = 10000;
int n, T[MAX];

void print()
{
    int p, l, r;
    for (int i = 1; i <= n; ++i)
    {
        p = i / 2;
        l = i * 2;
        r = i * 2 + 1;
        
        cout << "node " << i << ": ";
        cout << "key = " << T[i] << ", ";
        
        if (p >= 1 && p <= n)
        {
            cout << "parent key = " << T[p] << ", ";
        }
        if (l >= 1 && l <= n)
        {
            cout << "left key = " << T[l] << ", ";
        }
        if (r >= 1 && r <= n)
        {
            cout << "right key = " << T[r] << ", ";
        }
        cout << endl;
    }
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> T[i];
    }

    print();
    
    return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vll(v) sort((v).begin(), (v).end(), greater<long long>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}
const int IINF=(1<<30);
const ll LLINF = 1LL<<60;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int w, h, x, y, r;
  cin >> w >> h >> x >> y >> r;

  if(x + r > h || x - r < 0 || y + r > h || y - r < 0){
      cout << "No" << endl;
  }else{
      cout << "Yes" << endl;
  }
}


Measured memory_bytes: 3204
<?php
list($n) = ints();
for ($i = 0; $i < $n; ++$i) {
    list($x[], $y[]) = ints();
    $xi[] = $i;
    $yi[] = $i;
}
array_multisort($x, SORT_ASC, $xi);
array_multisort($y, SORT_ASC, $yi);
$kr = new Kruskal($n);
for ($i = 0; $i < $n - 1; ++$i) {
    $kr->connect($xi[$i], $xi[$i + 1], abs($x[$i + 1] - $x[$i]));
    $kr->connect($yi[$i], $yi[$i + 1], abs($y[$i + 1] - $y[$i]));
}
echo $kr->solve();
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}
class Kruskal
{
    private $X, $Y, $W;
    private $uft;

    function __construct($n)
    {
        $this->uft = new UnionFind($n);
    }

    function connect($x, $y, $w)
    {
        $this->X[] = $x;
        $this->Y[] = $y;
        $this->W[] = $w;
    }

    function solve()
    {
        $costSum = 0;
        array_multisort($this->W, $this->X, $this->Y);
        foreach ($this->W as $k => $w) {
            if (!$this->uft->isSame($this->X[$k], $this->Y[$k])) {
                $this->uft->unite($this->X[$k], $this->Y[$k]);
                $costSum += $w;
            }
        }
        return $costSum;
    }
}

class UnionFind
{
    private $par; // par[$i]:$iの親 自分が根の場合は自身のindexとなる
    private $size;

    function __construct($n)
    {
        for ($i = 0; $i < $n; $i++) {
            $this->par[$i] = $i; // 最初は全てが根
            $this->size[$i] = 1;
        }
    }

    function root($x)
    { // 根を返す
        if ($this->par[$x] === $x) return $x; // 根の場合
        return $this->par[$x] = $this->root($this->par[$x]); // 全ての枝の親を根にしながら再帰処理
    }

    function unite($x, $y)
    { // $xと$yの木を併合
        $ix = $this->root($x);
        $iy = $this->root($y);
        if ($ix === $iy) return;
        if ($this->size[$ix] < $this->size[$iy]) list($ix, $iy) = [$iy, $ix];
        $this->size[$ix] += $this->size[$iy];
        $this->par[$iy] = $ix; // $yの根を$xの根に付ける
    }

    function isSame($x, $y)
    { // $xと$yの根が同じか
        return $this->root($x) === $this->root($y);
    }

    function size($x)
    {
        return $this->size[$this->root($x)];
    }
}


Measured memory_bytes: 89792
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define rrep(i,n) for(int (i)=1;i<=(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};

int D;
vector<int> c(26);
vector<vector<int>> s(365, vector<int>(26));

int evaluate(vector<int> &t) {
	int score = 0;
	vector<int> last(26, -1);
	rep(i, t.size()) {
		score += s[i][t[i]];
		last[t[i]] = i;
		rep(j, 26) score -= c[j] * (i - last[j]);
	}
	return score;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	
	cin >> D;
	rep(i, 26) {
		cin >> c[i];
		c[i]--;
	}
	rep(i, D) {
		rep(j, 26) cin >> s[i][j];
	}

	vector<int> ans;
	rep(i, D) {
		int max_score = LLONG_MIN;
		int type = -1;
		rep(j, 26) {
			ans.push_back(j);
			int score = evaluate(ans);
			if(max_score < score) {
				max_score = score;
				type = j;
			}
			ans.pop_back();
		}
		ans.push_back(type);
	}
	rep(i, ans.size()) cout << ans[i] + 1 << endl;
	return 0;
}

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


int main() {
    int N, K;
    cin >> N >> K;

    vector<double> E(N);
    for (int i = 0; i < N; ++i) {
        int p;
        cin >> p;
        E[i] = (p + 1.0) / 2;
    }


    vector<double> ESum(N+1);
    ESum[0] = 0;
    for (int i = 1; i <= N; ++i) {
        ESum[i] = ESum[i - 1] + E[i - 1];
    }

    double ans = 0;
    for (int i = 0; i <= N - K; ++i) {
        ans = max(ans, ESum[i + K] - ESum[i]);
    }

    cout << fixed << setprecision(12) << ans << endl;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned long;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)

struct Problem {

    void Solve() {
        float a; cin >> a;
        cout << 2 * a * 3.14159 << endl;
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    p->Solve();
    return 0;
}


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

using namespace std;

int main(){
    long int a;
    double b;
  	int b_int;
    cin >> a >> b;
    long int ans;
    b=b*100;
  	b_int=round(b);
    ans=a*b_int;
    ans/=100;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n;
int32_t main(){_

   cin>>n;
   vector<int> a(n+1);
   vector<int> b(n);

   for (int i = 0; i <= n; ++i)
   {
      cin>>a[i];
   }

   for (int i = 0; i < n; ++i)
   {
      cin >> b[i];
   }
   
   int ans = 0;
   for (int i = n-1; i >= 0; --i)
   {
      int minn = min(a[i+1], b[i]);
      a[i+1] -= minn;
      b[i] -= minn;
      ans += minn;
      minn = min(a[i], b[i]);
      a[i] -= minn;
      b[i] -= minn;
      ans += minn;
   }

   cout<<ans;

   return 0;
}

Measured memory_bytes: 1792
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a: u32 = read();
    let b: u32 = read();
    println!("{}", if (a * b) % 2 == 0 { "Even" } else { "Odd" });
}


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

int main(void){
  int n,m;
  while(cin>>n>>m,n+m){
    vector<vector<vector<int> > > dp(2,vector<vector<int> >(100,vector<int>(100,1<<22)));
    rep(i,n){
      int a,b,c,t;
      cin>> a >> b >> c >> t;
      dp[0][--a][--b] = c;
      dp[0][b][a] = c;
      dp[1][a][b] = t;
      dp[1][b][a] = t;
    }
    
    rep(k,m)rep(i,m)rep(j,m)rep(o,2)
      dp[o][i][j] = min(dp[o][i][j],dp[o][i][k]+dp[o][k][j]);
      
    int k;
    cin>>k;
    rep(i,k){
      int p,q,r;
      cin >> p >> q >> r;
      cout<< dp[r][--p][--q] << endl;
    }
  }
}

Measured memory_bytes: 1340
#include<stdio.h>
#include<algorithm>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include <functional>
#include <time.h>
using namespace std;
clock_t fi, endtime;

const int MAX_V = 100;
const int MAX_E = 9000;
long long int INF = INT32_MAX;
int n, m, a, b, c, t;
int k, p, q, r;
long long int wf[MAX_V][MAX_V];

int main()
{
	int cou = 0;
	bool heiro = false;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j){
			wf[i][j] = INF;
		}
	}
	for (int i = 0; i < n; ++i) {
		wf[i][i] = 0;
	}
	
	for (int i = 0; i < m; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		wf[a][b] = c;
	}
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (wf[i][k] != INF && wf[k][j] != INF) {
					wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (wf[i][i] != 0) {
			heiro = true;
			break;
		}
	}
	if (heiro == true) {
		printf("NEGATIVE CYCLE\n");
	}
	else {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (j != 0) { printf(" "); }
				if (wf[i][j] == INF) printf("INF");
				else printf("%lld", wf[i][j]);
			}
			printf("\n");
		}
	}
}

Measured memory_bytes: 3264
#include<bits/stdc++.h>
using namespace std;
#define re register
int pm[20][200100],pg[20][200100],p[200100],lg[200100];
int mp(re int a,re int b)
{
	re int c=lg[b-a+1];
	return min(pm[c][a],pm[c][b-(1<<c)+1]);
}
int gp(re int a,re int b)
{
	re int c=lg[b-a+1];
	return max(pg[c][a],pg[c][b-(1<<c)+1]);
}
int main()
{
	re int n,k,ans=1,jj=1;
	re bool bl=0;
	scanf("%d%d",&n,&k);
	for(re int i=1;i<=n;i++)scanf("%d",&p[i]),pm[0][i]=pg[0][i]=p[i];
	for(re int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(re int i=1;(1<<i)<=n;i++)for(re int j=1;j+(1<<i)-1<=n;j++)
	{
		pm[i][j]=min(pm[i-1][j],pm[i-1][j+(1<<(i-1))]);
		pg[i][j]=max(pg[i-1][j],pg[i-1][j+(1<<(i-1))]);
	}
	for(re int i=2;i<=k;i++)if(p[i]<p[i-1])jj=i;
	if(jj==1)bl=1;
	for(re int i=1;i+k<=n;i++)
	{
		if(p[i+k]<p[i+k-1])jj=i+k;
		if(!(((p[i]<mp(i+1,i+k-1))&&(p[i+k]>gp(i+1,i+k-1)))))
		{
			if(i+k-jj+1>=k)
			{
				if(!bl)bl=1,ans++;
			}
			else ans++;
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 33152
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

int main(){
    Init();
    ll n, m, k; cin >> n >> m >> k;
    bool ans = false;
    // 押す順序は関係無いので、行・列それぞれ0～n, m個押した場合を考える
    for(ll i=0; i<=n; i++){
        for(ll j=0; j<=m; j++){
            // i行目までとj列目までのボタンを押した時の黒いコマの数は
            // i*m + j*n -i*j
            if(i*m + j*n - (2*i*j) == k){
                ans = true;
                goto LAST;
            }
        }
    }
LAST:
    ans ? Yes() : No();
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  vi A(N);
  rep(i,N) {
    cin >> A[i];
  }
  sort(rng(A));
  cout << A[N-1] - A[0] << endl;
  return 0;
}

Measured memory_bytes: 256
char*z,a[2][204];n,m,i,p;main(c){for(;m=scanf("%d %[^\n] %[^\n]",&n,a,a+1)*n;printf(m>n?"NA\n":"%d\n",m))for(i=2;i--;m=c)for(c=p=0;z=p+p+a[c+i&1],c<m&&*z&2|n+~p;)p+=p>=n|*z&2?-1:*z&1&z[2]?1:!++c+2;}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int f[MAX_N]={};
int b[MAX_N]={};

int main() {
    int n;
    cin>>n;
    int r[n]={};
    bool dp[n]={};

    vector<Pii> v[n];

    rep(i,n){
        int a,b,w;
        cin>>a>>b>>w;
        v[a-1].push_back(Pii(b-1,w));
        v[b-1].push_back(Pii(a-1,w));
    }
    queue<int>  que;
    que.push(0);
    while(!que.empty()){
        int p=que.front();
        que.pop();
        if(dp[p])continue;
        dp[p]=true;
        for(int i=0;i<v[p].size();++i){
            int a =v[p][i].first;
            int w=v[p][i].second;
            if(w%2>0){
                r[a]=(r[p]+1)%2;
            }else{
                r[a]=r[p];
            }
            que.push(a);
        }
    }   
    rep(i,n)cout<<r[i]<<endl;
	return 0;
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x,t;
  cin>>n>>x>>t;
  int ans=n/x;
  if(n%x==0)
  {
    cout<<ans*t<<endl;

  }
  else
  cout<<(ans+1)*t<<endl;

  
  
}


Measured memory_bytes: 3628
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int ans = 9999;
    for(int i=0; i<s.length()-2; i++){
      String ss = s.substring(i,i+3);
      int w = Integer.parseInt(ss);
      if(ans > Math.abs(753 - w))
         ans = Math.abs(753 - w);
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int main() {
  int a, b;
  string s;
  cin >> a >> b >> s;
  bool ans = true;

  if (s[a] != '-')
    ans = false;

  for (int i = 0; i < a + b; i++) {
    if (i == a)
      continue;

    if (s[i] < '0' || '9' < s[i])
      ans = false;
  }

  cout << (ans ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
//============================================================================
// Name        : b.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<vector>
using namespace std;

int main() {
	int n,k;cin>>n>>k;
	vector<int> d(k);
	vector<vector<int>> a(k);
	vector<int> c(n,0);
	for(int i=0;i<k;i++){
		cin>>d[i];
		for(int j=0;j<d[i];j++){
			int temp;
			cin>>temp;
			temp--;
			c[temp]=1;
			a[i].push_back(temp);
		}
	}
	int ans=n;
	for(int i=0;i<n;i++){
		ans-=c[i];
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 3612
#define FOR(n) for(int i = 0;i < n;i++)
#define PRN(n) printf("%d\n",n);
#define PRS(s) printf("%s\n",s);
int main(void) {
	int a, b, ans = 0;
	scanf("%d %d", &a, &b);
	if (b > -1) {
		FOR(a - 1) {
			ans += b + i + 1;
		}
	}
	else if (-b < a) {
		FOR(a) {
			ans += b + i;
		}
	}
	else {
		FOR(a - 1) {
			ans += b + i;
		}
	}
	PRN(ans);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m,k,step[1010][1010],temp[1010][3];
char a[1010][1010];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
bool vis[1010][1010];
typedef pair<int,int> P;
int bfs(int x,int y,int ex,int ey)
{
	memset(vis,true,sizeof(vis));
	memset(step,0,sizeof(step));
	queue <P> que;
	que.push(P(x,y));
	vis[x][y]=false;
	while(!que.empty())
	{
		P tmp=que.front();que.pop();
		int b=que.size();
		if(tmp.first==ex&&tmp.second==ey)
		  return step[tmp.first][tmp.second];
		for(int i=0;i<4;i++)
		{
			int tx=tmp.first+dx[i];
			int ty=tmp.second+dy[i];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&vis[tx][ty]==true&&a[tx][ty]!='X')
			{
				que.push(P(tx,ty));
				vis[tx][ty]=false;
				step[tx][ty]=step[tmp.first][tmp.second]+1;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>k;
		int sx,sy;
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=m;j++)
		  {
			cin>>a[i][j];
			if(a[i][j]=='S')
			  sx=i,sy=j;
			//temp[0][0]=i;
			//temp[0][1]=j;
		  }
		a[sx][sy]='0';
		int tot=0,ans=0;
		for(int i=1;i<=k;i++)
		{
			for(int j=1;j<=n;j++)
			  for(int l=1;l<=m;l++)
			    if(a[j][l]=='0'+i)
			    {
			    	tot=bfs(sx,sy,j,l);
			    	sx=j,sy=l;
				}
			ans+=tot;
		}
		cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 9068
#include <iostream>
using namespace std;
int main(void){
    
  while(1){
    string s;
    cin>>s;
    if(s=="-"){
      break;
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
      int h;
      cin>>h;
      s=s.substr(h)+s.substr(0,h);
    }
    cout<<s<<endl;
  }
  return 0;
}



Measured memory_bytes: 3184
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		char[] c = sc.next().toCharArray();
		int[] a = new int[3];
		
		if(c.length>=6){	
			for(int i=0;i<c.length;i++){
				if(Character.isUpperCase(c[i])) a[0]++;
				else if(Character.isLowerCase(c[i])) a[1]++;
				else a[2]++;
			}
		}
		
		if(c.length>=6 && a[0]>0 && a[1]>0 && a[2]>0) System.out.println("VALID");
		else System.out.println("INVALID");
	}	
}

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

using namespace std;

int main()
{
    int n, a, I, Id;
    cin >> n;
    int K[n+1]={0};
    vector <pair<int,int>> Q;
    deque <int> V, A, B;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        Q.push_back({a,i+1});
    }
    sort(Q.begin(),Q.end());
    for (int i = 0; i < Q.size(); i++)
    {
        a = Q[i].first;
        I = Q[i].second;
        for (int y = 0; y < I-1; y++)
        {
            A.push_back(I);
        }
    }
    Id = 1;
    for (int i = 0; i < n; i++)
    {
        a = Q[i].first;
        I = Q[i].second;
        while (Id < a)
        {
            if (A.size() > 0)
            {
                V.push_back(A.front());
                K[A.front()]++;
                A.pop_front();
            }
            else if (B.size() > 0)
            {
                V.push_back(B.front());
                B.pop_front();
            }
            else
            {
                cout << "No";
                return 0;
            }
            Id++;
        }
        if (Id > a)
        {
            cout << "No";
            return 0;
        }
        if (K[I] < I-1)
        {
            cout << "No";
            return 0;
        }
        V.push_back(I);
        for (int y = I; y < n; y++)
        {
            B.push_back(I);
        }
        Id++;
    }
    while (Id <= n*n)
    {
        Id++;
        V.push_back(B.front());
        B.pop_front();
    }
    cout << "Yes" << "\n";
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i] << " ";
    }
    return 0;
}


Measured memory_bytes: 2304
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xy = [None]*n
for i in range(n):
    xy[i] = tuple(map(int, input().split()))
import cmath
ans = [0]*n
ps = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        v = (xy[i][0]-xy[j][0]) + (xy[i][1]-xy[j][1])*1j
        ps[i].append(cmath.polar(v)[1])
pi = cmath.pi
def sub(p):
    """p: 偏角のリスト
    """
    l = [[-pi, pi]]
    for pp in p:
        lb = pp-pi/2
        ub = pp+pi/2
        if lb<-pi:
            ll = [[lb+2*pi, pi], [-pi, ub]]
        elif ub>pi:
            ll = [[lb, pi], [-pi, ub-2*pi]]
        else:
            ll = [[lb,ub]]
        nl = []
        for i,item1 in enumerate(l):
            for j,item2 in enumerate(ll):
                item = [max(item1[0], item2[0]), min(item1[1], item2[1])]
                if item[0]<item[1]:
                    nl.append(item)
        l = nl
    return l
for i,p in enumerate(ps):
    lus = sub(p)
    for lu in lus:
        if lu[0]>lu[1]:
            ans[i] += 0
        else:
            ans[i] += (lu[1]-lu[0]) / (2*pi)
write("\n".join(map(str, ans)))

Measured memory_bytes: 75492