akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int main(){
	int n;
	scanf("%d", &n);
	if (n == (n & -n)) { printf("No\n"); return 0; }
	printf("Yes\n");
	if (n & 1){
		for (int i = 2; i <= n; i += 2)printf("1 %d\n", i);
		for (int i = n + 3; i <= n << 1; i += 2)printf("1 %d\n", i);
		for (int i = 2; i < n; i += 2)printf("%d %d\n", i, i + 1);
		for (int i = n + 2; i < n << 1; i += 2)printf("%d %d\n", i, i + 1);
		printf("3 %d\n", n + 1);
	}else {
		int x = 20;
		while (!(n >> x & 1))--x;
		x = 1 << x;
		int z = n ^ x;
		printf("%d %d\n", x, x + 1);
		printf("%d %d\n", x + n, x + n + 1);
		printf("%d %d\n", 1, x);
		printf("%d %d\n", 1, x + n + 1);
		printf("%d %d\n", n + 1, x + 1);
		printf("%d %d\n", n, x);
		printf("%d %d\n", n + n, z);
		for (int i = 2; i < n; i += 2)if (i != x)printf("%d %d\n", i, x), printf("%d %d\n", i, i + 1);
		for (int i = n + 3; i < n << 1; i += 2)if (i != n + x + 1)printf("%d %d\n", i, i - 1), printf("%d %d\n", i, x + 1);
	}
}

Measured memory_bytes: 2688
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
int A;
  string S;
  string T;
  cin >>S>>T;
  int x=S.size();
 bool answer=false;
  rep(i,x+1) {
    vector<char> M(x);
    repl(i,1,x) {
      M.at(i)=S.at(i-1);
    }
    M.at(0)=S.at(x-1);
    
    rep(i,x) {
      S.at(i)=M.at(i);
    }
    int count=0;
    rep(i,x) {
      if(M.at(i)==T.at(i)) {
        count++;
      }
    }
    if(count==x) {
      answer=true;
      break;
    }
  }
  if(answer) {
cout<< "Yes"<<endl;
  }
else {
cout << "No" << endl;
}
}
    
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 998244353;

using namespace std;

int main()
{
  int a;
  string s;
  cin >> a;
  cin >> s;
  if (a >= 3200)
  {
    cout << s << endl;
  }
  else
  {
    cout << "red" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <string>
#include <sstream>
#include <numeric>
#include <ios> // std::left, std::right

typedef long long int ll;
typedef unsigned long long int ull;

using namespace std;

int gcd(ll x, ll y)
{
  return y == 0 ? x : gcd(y, x % y);
}

int main()
{
  int n, m = 0;
  cin >> n;
  vector<int> a(n, 0), agp(n, 0), agr(n, 0);
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    if (i == 0)
    {
      agp[i] = a[i];
    }
    else
    {
      agp[i] = gcd(agp[i - 1], a[i]);
    }
    // cout << agp[i] << endl;
  }

  for (int i = n - 1; i >= 0; i--)
  {
    if (i == n - 1)
    {
      agr[i] = a[i];
    }
    else
    {
      agr[i] = gcd(agr[i + 1], a[i]);
    }
    // cout << agr[i] << endl;
  }

  for (int i = -1; i < n; i++)
  {
    if (i == -1)
    {
      m = agr[1];
    }
    else if (i == n - 1)
    {
      m = max(m, agp[n - 2]);
    }
    else
    {
      m = max(m, gcd(agp[i], agr[i + 2]));
    }

    // cout << gcd(agp[i], agr[i + 2]) << endl;
  }
  cout << m << endl;

  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  long long a, b, n;
  cin >> a >> b >> n;
  long long ans0 = 0;
  if (n >= b-1) {
    cout << (a*(b-1)) / b - a * ((b-1) / b) << '\n';
  }
  else {
    cout << ((a*n)/b) - a*(n/b) << '\n';
  }
}

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

using namespace std;
using ll = long long;

typedef pair<ll, ll> P;

const int MOD = 1000000007;
const ll INF = 1LL << 60;


// LRUD
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
// const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

vector<vector<int> > vvi;
vector<vector<vector<int> > > vvvi;

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

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }

int main(int argc, char**argv){
    string s;
    cin >> s;

    int n_zero = 0, n_one = 0;
    for (int i = 0; i < s.size(); i++){
        if (s[i] == '0') n_zero++;
        else if (s[i] == '1') n_one++;
    }

    cout << 2 * min(n_zero, n_one) << endl;

    return 0;

}




















Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
const int inf = 1 << 30;
const ll linf = 1e18;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

ll N;
int c[200010];
int cnt[200010];
int son[200010];
ll ans[200010];
vector<int> G[200010];

void dfs(int v, int p){
    son[v] = 1;
    for(auto u : G[v]){
        if(u == p) continue;
        ll memo = cnt[c[v]];
        dfs(u, v);
        ll m = son[u] - (cnt[c[v]] - memo);
        ans[c[v]] -= m * (m - 1) / 2 + m;
        son[v] += son[u];
        cnt[c[v]] = memo + son[u];
    }
    cnt[c[v]]++;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> c[i];
        ans[i] = N * (N - 1) / 2 + N;
    }
    for(int i = 1; i < N; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1, 0);
    for(int i = 1; i <= N; i++){
        ll m = son[1] - cnt[i];
        ans[i] -= m * (m - 1) / 2 + m;
    }
    for(int i = 1; i <= N; i++) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 37088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()


int main()
{
    ll N;  cin>>N;
    vector<long double> x(N);
    vector<string> u(N);
    long double sum=0;
    rep(i,0,N){
        cin>>x[i]>>u[i];
        if(u[i]=="JPY")sum += x[i];
        else if(u[i]=="BTC")sum += x[i]*380000.0;
    }
    cout<<fixed<<setprecision(15)<<sum<<endl;

}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < n; ++i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define stl_repr(itr, x) for (auto itr = x.rbegin(); itr != x.rend(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

using llong = long long int;

const static int MOD = 1000000007;
const static int inf = INT_MAX;
const static llong INF = LLONG_MAX;
const static int dx[4] = {1, 0, -1, 0};
const static int dy[4] = {0, 1, 0, -1};

template<typename T> T my_gcd(T a, T b) {
    return (a ? my_gcd(b % a, a) : b);
}

template<typename T> T my_lcm(T a, T b){
    return a * b / my_gcd(a, b);    
}

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    llong a, b;
    cin >> a >> b;

    cout << my_lcm(a, b) << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
s = input()
if n % 2 == 0:
  half = n//2
  ans = "No"
  for i in range(n-half+1):
    if 2*s[i:i+half] == s:
      ans = "Yes"
      break
else:
  ans = "No"
print(ans)

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

using ll = long long;
using G = vector<vector<int>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;

ll GCD(ll x, ll y){
	return y ? GCD(y, x%y) : x;	
}

int main() {
	ll a, b, c, k; cin >> a >> b >> c >> k;
	if(k<=a){
		cout << k << endl;
		return 0;
	}
	if(k<=a+b){
		cout << a << endl;
		return 0;
	}
	cout << a-(k-(a+b)) << endl;
	return 0;
}

Measured memory_bytes: 3624
//BISMILLAH
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long int i,j,n,cnt = 0,k;
    cin >> n;
    long long int a[n];
    for(i = 0;i<n;i++) cin >> a[i];
    for(i = 0;i<n-2;i++){
        for(j = i+1;j<n-1;j++){
            if(a[i] != a[j]){
            for(k = j + 1;k<n;k++){
                if(a[k] != a[j] && a[k] != a[i]){
                    if(a[i] + a[j] > a[k] && a[j] + a[k] > a[i] && a[i] + a[k] > a[j]) cnt++;
                }
            }
          }
        }
    }
       cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3612
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007;

    public Main() {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        long[] A = new long[N];

        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextLong();
        }

        long R = 0;

        for (int D = 0; D < 60; D++) {
            long zNum = 0L, oNum = 0L;
            long B = 1L << D;
            for (int i = 0; i < N; i++) {
                if ( ( A[i] & B ) == B ){
                    oNum++;
                } else {
                    zNum++;
                }
            }
            B %= MOD;
            R = (R + B * (oNum * zNum % MOD) % MOD) % MOD;

        }

        System.out.println(R);
    }


    long modPow(long n){
        long R = 1L;

        long A = 2;
        while(n > 0){
            if( (n & 1) == 1)
                R = (R * A) % MOD;
            A = (A * A) % MOD;
            n = n >> 1;
        }

        return R;
    }

    public static void main(String[] args) {
        new Main();
    }
}


Measured memory_bytes: 98288
#include<bits/stdc++.h>
using namespace std;
static const int mod=1000000007;
int64_t f(int64_t x,int64_t y){
if(y==0)
  return 1;
  else{
  if(y%2==0){
  return (f(x,y/2)*f(x,y/2))%mod;
  }else{
  return (((x*f(x,y/2))%mod)*f(x,y/2))%mod;
  }
  }

}
int64_t comb(int64_t n,int64_t k){
int64_t N=1; 
  for(int i=n-k+1;i<=n;i++)
    N=(N*i)%mod;
  int64_t K=1;
  for(int i=1;i<=k;i++)
    K=(K*i)%mod;
  return (N*f(K,mod-2))%mod;
}
int main(){
int64_t N,a,b;
  cin>>N>>a>>b;
  int64_t ans=(f(2,N)-1-comb(N,a)-comb(N,b)+2*mod)%mod;
  cout<<ans<<endl;
  
   return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define loop(i, a, n) for(int i = (a); i < (n); i++)
#define rloop(i, n, a) for(int i = (n); i >= (a); i--)
using namespace std;
using ll = int64_t;

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

    ll val() {
        return x;
    }

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

    friend istream& operator>>(istream& is, mint& a) { return is >> a.x;}
    friend ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
};

struct Comb {
    vector<mint> fact, ifact;
    Comb(int n) : fact(n+1), ifact(n+1) {
        fact[0] = 1;
        loop(i, 1, n+1) fact[i] = fact[i-1] * i;
        ifact[n] = fact[n].pow(mod-2);
        rloop(i, n, 1) ifact[i-1] = ifact[i] * i;
    }
    ll operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        mint res = fact[n];
        res *= ifact[k];
        res *= ifact[n-k];
        return res.val();
    }
};

int main(){
    int s; cin >> s;
    int ite = s/3;

    if(s < 3) {
        cout << 0 << endl;
        return 0;
    }

    mint ans = 1;
    for(int slot = 2; slot <= ite; slot++){
        int r = s - 3*slot;
        int n = slot - 1 + r;
        Comb C = Comb(n);
        mint tmp = 0;
        tmp += C(n, slot - 1);
        ans += tmp;
    }
    cout << ans.val() << endl;

    return 0;
}

Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var cnt1 = s.Count(x => x == '1');
            var cnt2 = s.Count() - cnt1;

            Console.WriteLine(Math.Min(cnt1, cnt2) * 2);

        }



    }
}


Measured memory_bytes: 13244
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long

using namespace std;

const ll MOD = 1000000007;

ll BITS[64];
ll one[64];

int main() {
  ll n;
  scanf("%lld", &n);

  memset(one, 0, sizeof(one));
  ll ONE = 1ll;

  for (ll i = 0; i <= 60; i++) {
    BITS[i] = (ONE << i);
  }

  for (ll i = 0; i < n; i++) {
    ll v;
    scanf("%lld", &v);

    for (ll j = 0; j <= 60; j++) {
      if (v & (BITS[j])) {
        one[j]++;
      }
    }
  }

  ll ans = 0;

  for (ll i = 0; i <= 60; i++) {
    ll x = one[i] * (n - one[i]) % MOD;
    ans = (ans + x * (BITS[i] % MOD)) % MOD;
  }

  cout << ans << endl;
}


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

using namespace std;

const int INF = 1000000000;

int main() {
    int H,W;
    cin >> H >> W;

    vector<vector<int>> c(10, vector<int>(10, INF));
    vector<vector<int>> A(H, vector<int>(W, 0));

    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            cin >> c[i][j];
        }
    }

    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> A[i][j];
        }
    }

    // ワーシャルフロイド法におけるiからjまで数字を変えるときの最小コストdp[k][i][j]
    vector<vector<int>> dp(10, vector<int>(10, INF));

    // 初期条件
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            dp[i][j] = c[i][j];
        }
    }

    // dp開始
    for(int k = 0; k < 10; k++) {
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < 10; j++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }

    int count = 0;

    // 全ての数字に対して1に変えるのに必要なコストを求めて合計する
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(A[i][j] != -1) {
                count += dp[A[i][j]][1];   
            }
        }
    }

    cout << count << endl;
	return 0;
}

Measured memory_bytes: 3804
#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 140576
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int n,l;
  cin>>n>>l;
  string s[n+1];
  for(int i=0;i<n;i++){
    cin>>s[i];
  }
  sort(s,s +n);
  for(int i=0;i<n;i++){
    cout<<s[i];
  }
  cout<<'\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

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

    int h, w;
    cin >> h >> w;

    vector<string> s(h);
    rep(i, h) cin >> s[i];

    bool flg = true;
    rep(i, h){
        rep(j, w){
            if(s[i][j] == '#'){
                bool all_white = true;
                rep(dir, 4){
                    int ni = i + dy[dir];
                    int nj = j + dx[dir];

                    if(ni<0 || ni>=h || nj<0|| nj>=w) continue;

                    if(s[ni][nj] == '#'){
                        all_white = false;
                        break;
                    }
                }

                if(all_white){
                    puts("No");
                    return 0;
                }
            }
        }
    }

    puts("Yes");

    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int N,C,K;
			N = scanner.nextInt();
			C = scanner.nextInt();
			K = scanner.nextInt();

			int[] T = new int[N];
			for (int i = 0; i < N; i++) {
				T[i] = scanner.nextInt();
			}


			Arrays.sort(T);

			int cnt = 1;
			int bus = 1;
			int busTime = T[0];

			for (int i = 1; i < N; i++) {
				if (cnt == C || T[i] > busTime + K) {
					cnt = 0;
					busTime = T[i];
					bus++;
				}
				cnt++;
			}

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

Measured memory_bytes: 50004
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 4001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

// MOD確認

int main(){
    ll N,K,ans = 0;
    cin >> N >> K;
    FOR(i,K,N+2){
      ll m = i*(i-1)/2,M = N*(N+1)/2 - (N-i)*(N-i+1)/2;
      ans += M - m + 1;
      ans %= MOD;
    }
    cout << ans % MOD << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,l,r) for(i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define P pair<ll,ll>
#define F first
#define S second
signed main(){
  ll A,B,C,D;cin>>A>>B>>C>>D;
  cout<<max(max(A*C,A*D),max(B*C,B*D))<<endl;
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;

/*
123
132
213
231
312
321

12:4
13:4
23:4

全部のパターン：n!*(n-1)
これをnC2=n*(n-1)/2で割って、(n-1)!*2
n!で割って、2/n

*/

int fact(int n){
    if(n==1) return 1;
    else{
        return n*fact(n-1);
    }
}

void solve(){
    int n;
    cin >> n;
    vector<pair<int,int>> town;
    rep(i,n){
        int x,y;
        cin >> x >> y;
        town.push_back(make_pair(x,y));
    }



    long double sum = 0;

    rep(i,n){
        rep(j,n){
            if(i<j){
                long double p=town[i].first;
                long double q=town[i].second;
                long double r=town[j].first;
                long double s=town[j].second;
                sum += sqrt((p-r)*(p-r) + (q-s)*(q-s)) * 2 / n;
            }
        }
    }


    cout << setprecision(10) << sum << endl;

}

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


Measured memory_bytes: 256
#include <iostream>
bool isRight(int a, int b, int c)
{
    //?????§???c??????????????????????????´???
    if (a > c) {
        std::swap(a, c);
    }
    if (b > c){
        std::swap(b, c);
    }
    
    return a * a + b * b == c * c;
}

int main()
{
    int N;
    int a, b, c;
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::cin >> a >> b >> c;
        if (isRight(a, b, c)) {
            std::cout << "YES" << std::endl;
        } else {
            std::cout << "NO" << std::endl;
        }
    }
}

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

int main() {
  int n,ame;
  cin >>n>>ame;
  vector<int>a(n);
  long long sum=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  if(ame<a[0]){
    cout<<0<<endl;
    return 0;
  }
  int count =0;
  for(int i=0;i<n;i++){
    sum+=a[i];
    if(sum>ame)break;
    if(i==n-1){
      //cout<<sum<<" "<<ame<<endl;
      if(sum==ame){
        count++;
        break;
      }else break;
    }
    count++;
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 256
/* Alohomora */
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define F          first 
#define S          second
#define mod        1000000007
#define all(x) 	   x.begin(),x.end()	
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
void comp() {
	ll i,j,k,n,m,p,ind;
	cin>>n>>m;
	n+=1;
	ll ans=0;
	fli(i,m,n+1) {
		ll temp=((i-1)*(i))/2;
		ll temp1=((n-1)*(n))/2-((n-i-1)*(n-i))/2;
		//cout<<temp<<" "<<temp1<<endl;
		ans+=temp1-temp+1;
		ans%=mod;
	}
	cout<<ans<<endl;
}

int main() {
    speedup;
    ll i=0,t;
    //cin>>t;
    t=1;
    while(t--) {
        comp();
    }
    return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int N, M, Q;
vector<int> as;
vector<int> vs[114514];
vector<int> needs[114514];

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  cin >> N >> M >> Q;
  rep(i, Q) {
    int q;
    cin >> q;
    as.eb(q);
  }

  reps(i, 1, N) needs[0].eb(i);

  set<int> has;
  rrep(i, Q) {
    int t = as[i];
    if (needs[t].empty()) {
      if (has.count(t)) continue;
      has.insert(t);
      vs[0].eb(t);
      needs[t].swap(needs[0]);
    } else {
      int idx = needs[t].back(); needs[t].pop_back();
      vs[idx].eb(t);
      assert(vs[0].size() >= vs[idx].size());
      if (vs[0].size() == vs[idx].size()) needs[0].eb(idx);
      else needs[vs[0][vs[idx].size()]].eb(idx);
    }
  }

  int m = vs[0].size();
  int incr = 0;
  set<int> st;
  rep(i, M) st.insert(i+1);
  rep(i, m) {
    int v = vs[0][i];
    if (st.count(v)) {
      if (v != *st.begin()) incr = i+1;
      st.erase(v);
    }
  }

  reps(i, 1, N) {
    if (incr > vs[i].size()) {
      cout << "No\n";
      return 0;
    }
  }
  cout << "Yes\n";
}


Measured memory_bytes: 16120
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<int,int> P;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
const ll INF = 1e+9+7;
ll n,m,l;
string s,t;
ll d[100000],dp[100][100];

int main(){
  vs vec;
  cin >> n >> m;
  rep(i,0,n){
    cin >> s;
    vec.pb(s);
  }
  rep(i,0,vec.sz){
    print(vec[i]);
    print(vec[i]);
  }
  return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
KA = list(map(int,input().split()))
result = KA[1:]
for _ in range(N-1):
    KA = list(map(int, input().split()))
    A = KA[1:]
    new_result = []
    for i in result:
        if i in A:
            new_result.append(i)

    result = new_result

print(len(result))


Measured memory_bytes: 3060
X,Y,A,B,C = map(int, input().split())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
R = list(map(int,input().split()))

P.sort(reverse=True)#X
Q.sort(reverse=True)#Y
R.sort(reverse=True)

P = P[:X]
Q = Q[:Y]
P.extend(Q)
P.sort()
Z = list()
for i in P:
  if len(R) == 0:
    best = i
  else:
    best = R[0]
  if best > i:
    Z.append(R[0])
    R.pop(0)
  else:
    Z.append(i)
print(sum(Z))

Measured memory_bytes: 22720
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MOD2 1494318097
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ull randlong(ull a,ull b){return uniform_int_distribution<unsigned long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
//ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
//ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

//ll fmul(ll a, ll b, ll mod){ll res=0;while(a){if(a&1)res=(res+b)%mod;a>>=1;b=(b<<1)%mod;}return res;}
//ll fpowfast(ll b, ll exp, ll mod){ll res=1;while(exp){if(exp&1)res=fmul(res,b,mod);b=fmul(b,b,mod);exp>>=1;}return res;}
//inline bool rabbin_miller(ll x){if(x%2==0) return false;for(int i=0;i<5;i++){ll rd=randlong(2,x-2);if(fpowfast(rd,x-1,x)!=1)return false;}return true;}

ll A,B,res=1;

ull fmul(ull a, ull b, ull mod){
	ull res = 0;
	while(a){
		if(a&1) res = (res+b)%mod;
		a>>=1;
		b = (b<<1)%mod;
	}
	return res;
}

ull fpow(ull b, ull exp, ull mod){
	ull res = 1;
	while(exp){
		if(exp&1) res = fmul(res,b,mod);
		b = fmul(b,b,mod);
		exp>>=1;
	}
	return res;
}

inline bool prim(ull x){
	if(x == 2 || x == 3) return true;
//	if(x%2 == 0) return false;
	for(int i=0; i<30; i++){
		ull rd = randlong(2,x-2);
		if(fpow(rd,x-1,x) != 1)
			return false;
	}
	return true;
}

//inline bool prim(ull x){
//	if(x == 2) return true;
//	ull lim = sqrt(x);
//	while(lim*lim < x) lim++;
//	while(lim*lim > x) lim--;
//	for(ull k=2; k<=lim; k++){
//		if(x%k == 0) return false;
//	}
//	return true;
//}

int main(){
	scanf("%lld %lld",&A,&B);
	ull gg = __gcd(A,B);
	ull lim = sqrt(gg);
	while(lim*lim < gg) lim++;
	while(lim*lim > gg) lim--;
	for(ull i=2; i<=lim; i++){
		if(gg%i == 0){
			if(prim(i))
				res++;
			if(i*i != gg && prim(gg/i))
				res++;
		}
	}
	if(prim(gg) && gg != 1) res++;
	printf("%lld\n",res);
}

Measured memory_bytes: 256
#include <iostream>
using namespace  std;
int main(){
	int a, b, c, d;
	int m, s;
	cin >> a >> b >> c >> d;
	m = (a + b + c + d) / 60;
	s = a + b + c + d - m * 60;
	cout << m << endl;
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 3056
#include <cstdio>
#include <cstring>
using namespace std;

int n,m,a[50][50],b[50][50],ans;
bool inRange(int z,int l,int r){
	return z>=l&&z<r;
}
void fill(int x,int y){
	if(!a[x][y]||b[x][y])return;
	b[x][y]=true;
	for(int xx=-1;xx<=1;xx++)if(inRange(x+xx,0,n)){
		for(int yy=-1;yy<=1;yy++)if(inRange(y+yy,0,m)){
			fill(x+xx,y+yy);
		}
	}
}
int main(){
	while(scanf("%d%d",&m,&n),n*m){
		ans=0;
		memset(b,0,sizeof(int)*2500);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				scanf("%d",&a[i][j]);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(!b[i][j]&&a[i][j])
					ans++,fill(i,j);
		printf("%d\n",ans);
	}

	return 0;
}

Measured memory_bytes: 1164
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
typedef long long s64;

const int ONE = 100005;

int get()
{
		int res = 1, Q = 1; char c;
		while( (c = getchar()) < 48 || c > 57)
			if(c == '-') Q = -1;
		if(Q) res = c - 48;
		while( (c = getchar()) >= 48 && c <= 57)
			res = res * 10 + c - 48;
		return res * Q;
}

int n, a[ONE];
int maxx, pos, x;

int main()
{
		n = get();
		for(int i = 1; i <= n; i++)
		{
			a[i] = get();
			if(abs(a[i]) >= maxx) maxx = abs(a[i]), pos = i;
		}

		cout << n - 1 + n - 1 << endl;

		for(int i = 1; i <= n; i++)
			if(i != pos) printf("%d %d\n", pos, i);

		if(a[pos] < 0)
			for(int i = n - 1; i >= 1; i--)
				printf("%d %d\n", i + 1, i);
		else
			for(int i = 2; i <= n; i++)
				printf("%d %d\n", i - 1, i);
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N := nextInt()
	M := nextInt()
	K := nextInt64()
	sa := make([]int64, N+1)
	sb := make([]int64, M+1)

	for i := 0; i < N; i++ {
		a := nextInt64()
		sa[i+1] = sa[i] + a
	}
	for i := 0; i < M; i++ {
		b := nextInt64()
		sb[i+1] = sb[i] + b
	}

	maxk := 0

	for i := 0; i < len(sa); i++ {
		ok := -1
		ng := len(sb)

		for abs(ok-ng) > 1 {
			mid := (ok + ng) / 2

			if sa[i]+sb[mid] <= K {
				ok = mid
			} else {
				ng = mid
			}
		}

		if ok >= 0 && sa[i]+sb[ok] <= K {
			maxk = max(maxk, i+ok)
		}
	}

	fmt.Println(maxk)
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}

func debug(args ...interface{}) {
	fmt.Fprintln(os.Stderr, args)
}


Measured memory_bytes: 10396
#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(defmacro dp (name args memo-size &body body)
  (let ((memo (gensym)))
    `(let ((,memo (make-array ,memo-size :initial-element nil)))
       (defun ,name ,args
         (or (aref ,memo ,@args)
             (setf (aref ,memo ,@args)
                   ,@body))))))

(defun split (x str)
  (let ((pos (search x str))
        (size (length x)))
    (if pos
        (cons (subseq str 0 pos)
              (split x (subseq str (+ pos size))))
        (list str))))

(defmacro collect-times (time body)
  `(loop repeat ,time collect ,body))

(defun read-times (time)
  (collect-times time (read)))

(defmacro aif (expr then else)
  `(let ((it ,expr))
     (if it ,then ,else)))

(defmacro awhen (expr &rest then)
  `(aif ,expr (progn ,@then) nil))

(defun comulative (function list &key base)
  (if base
      (comulative function (cons base list))
      (do ((lst (cdr list) (cdr lst))
           (acc (list (car list))))
          ((null lst) (reverse acc))
        (push (funcall function (car acc) (car lst)) acc))))

(defun binary-search (function left right
                      &optional
                        (eps 1)
                        (average-function (lambda (x y) (ash (+ x y) -1))))
  (if (<= (abs (- left right)) eps)
      right
      (let ((mid (funcall average-function left right)))
        (if (funcall function mid)
            (binary-search function left mid eps average-function)
            (binary-search function mid right eps average-function)))))

(defun arithmetic-mean (&rest body)
  (/ (apply #'+ body) (length body)))

(defvar +MOD+ (+ (expt 10 9) 7))

(defun mapa-b (fn a b &optional (step 1))
  (do ((i a (+ i step))
       (result nil))
      ((> i b) (nreverse result))
    (push (funcall fn i) result)))

(defun map0-n (fn n)
  (mapa-b fn 0 n))

(defun map1-n (fn n)
  (mapa-b fn 1 n))

(defun read-string (&optional (stream *standard-input*))
  (labels ((is-empty (x)
             (or (char= x #\space) (char= x #\newline))))
    (loop for char = (read-char stream)
          with result
          when (is-empty char)
            do (return (concatenate 'string (nreverse result)))
          do (push char result))))

(defun main (lst)
  (let* ((max (reduce #'max lst))
         (dis (- (* 3 max) (reduce #'+ lst))))
    (if (evenp dis)
        (/ dis 2)
        (/ (+ dis 3) 2))))

(princ (main (read-times 3)))


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

/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______      
 * |\  \|\  \  |\  ___ \  |\  ___ \     
 * \ \  \/  /|_\ \   __/| \ \   __/|    
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__  
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \ 
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

int g[25][25];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	//	freopen("turtle.in","r",stdin);
	//	freopen("turtle.out","w",stdout);

	int N,M,K;
	cin>>N>>M>>K;
//	vector<int> out;
//	{
//		for(int i = 0;i < (1<<N);i++) {
//			for(int j = 0;j < (1<<M);j++) {
//				for(int a = 0;a < N;a++) {
//					for(int b = 0;b < M;b++) {
//						g[a][b] = 0;
//					}
//				}
//				for(int a = 0;a < N;a++) {
//					for(int b = 0;b < M;b++) {
//						if(i & (1<<a))
//							g[a][b] ^= 1;
//						if(j & (1<<b))
//							g[a][b] ^= 1;
//					}
//				}
//				int K = 0;
//				for(int a = 0;a < N;a++) {
//					for(int b = 0;b < M;b++) {
//						K += g[a][b];
//					}
//				}
//				out.push_back(K);
//			}
//		}
//		sort(out.begin(),out.end());
//		auto it = unique(out.begin(),out.end());
//		out.erase(it,out.end());
//		for(auto k : out) cout<<k<<'\n';
//	}
	bool can = false;
	for(int i = 0;i <= N;i++) {
		for(int j = 0;j <= M;j++) {
			can |= K == (j * (N - i)) + (i * (M-j));
		}
	}
	cout<<(can?"Yes":"No")<<'\n';
//	assert(can == binary_search(out.begin(),out.end(),K));
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
// int mod = 998244353;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b % mod; if (a >= mod) a -= mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12); // debuged
    int T;
    T = 1;
    while (T--) solve();
}

// https://atcoder.jp/contests/abc146/submissions/15283088
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    cin >> a;
    
    rep(i, n) {
        --a[i];
        (a[i] += k) %= k; // debuged, 必ず正になるように
    }
    vector<ll> acc(n + 1);
    rep(i, n) (acc[i + 1] = acc[i] + a[i]) %= k;
    // cerr << acc << endl;
    
    map<ll, vector<int> > mp;
    ll ans = 0;
    rep(i, n + 1) {
        int it = lb(mp[acc[i]], i - k + 1);
        if (it != sz(mp[acc[i]]) && mp[acc[i]][it] < i - k + 1) --ans; // debuged
        // cerr << i << " " << it << "  " << mp[acc[i]] << endl;
        ans += sz(mp[acc[i]]) - it;
        mp[acc[i]].eb(i);
    }
    cout << ans << endl;
}


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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int dp[100][100][100] = {};    // a,b,c から見て何ステップで到達できるか
    for(int i =0; i<100; i++){
        for(int j =0; j<100; j++){
            for(int k =0; k<100; k++){
                dp[i][j][k] = 10000;
            }
        }
    }
    dp[a][b][c] = 0;
    for(int i=a; i <98; i++){
        for(int j=b; j <98; j++){
            for(int k=c; k<98; k++){
                dp[i+2][j][k] = min(dp[i][j][k]+1, dp[i+2][j][k]);
                dp[i][j+2][k] = min(dp[i][j][k]+1, dp[i][j+2][k]);
                dp[i][j][k+2] = min(dp[i][j][k]+1, dp[i][j][k+2]);
                dp[i+1][j+1][k] = min(dp[i][j][k]+1, dp[i+1][j+1][k]);
                dp[i][j+1][k+1] = min(dp[i][j][k]+1, dp[i][j+1][k+1]);
                dp[i+1][j][k+1] = min(dp[i][j][k]+1, dp[i+1][j][k+1]);
                //cout << dp[i][j][k];
            }
        }
    }
    int ans = 10000;
    for(int i =max(a,max(a,b)); i<100; i++){
        ans = min(ans, dp[i][i][i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4096
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        a -= b;
        c -= a;
        int ans = c < 0 ? 0 : c;
        System.out.println(ans);
    }
}


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

int main(){
	int N;
	cin >> N;
	vector<long long> A(N);
	for(auto &i:A)cin >> i;
	
	long long dp[N-1][2];
	for(int i=0;i<N-1;i++)for(int j=0;j<2;j++)dp[i][j]=-9999999999999999ll;
	dp[0][0]=A[0]+A[1];
	dp[0][1]=0-(A[0]+A[1]);
	
	for(int i=1;i<N-1;i++){
		dp[i][0]=max(dp[i-1][0],dp[i-1][1])+A[i+1];
		dp[i][1]=max(dp[i-1][0]-2*A[i],dp[i-1][1]+2*A[i])-A[i+1];
	}
	cout << max(dp[N-2][0],dp[N-2][1]) << endl;
	return 0;
}

Measured memory_bytes: 2560
X = int(input())
N = pow(10,5)

dp = [0]*(N+1)
for i in range(6):
    dp[100+i]=1

for i in range(106,N+1):
    for j in range(6):
        if dp[i-100-j]:
            dp[i]=1
            break

print(dp[X])

Measured memory_bytes: 40252
n, k = map(int, input().split())
A = list(map(int, input().split()))

for i in range(1, 100):
  imos = [0] * (n + 1)
  for j in range(n):
    imos[max(0, j - A[j])] += 1
    imos[min(n, j + A[j] + 1)] -= 1
  
  nA = [0] * n
  nA[0] = imos[0]
  for j in range(1, n):
    nA[j] = nA[j - 1] + imos[j]

  A = nA[:]
  if i >= k:
    break

print(*A)

Measured memory_bytes: 170824
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iomanip>

#define REP(i,n) for(int i=0;i<n;++i)
#define RREP(i,n) for(int i=n-1;i>=0;--i)
#define FOR(i,m,n) for(int i=m;i<n;++i)
#define RFOR(i,m,n) for(int i=m-1;i>=n;--i)
#define ALL(v) v.begin(),v.end()
#define PB(a) push_back(a)
#define INF 1000000001
#define MOD 1000000007

using namespace std;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (1) {
		int n, p;
		cin >> n >> p;
		if (n == 0) break;
		int* m = new int[n];
		REP(i, n) m[i] = 0;
		for (int i = 0;;++i) {
			int j = i%n;
			if (p == 0) {
				p += m[j];
				m[j] = 0;
			}
			else {
				p--;
				m[j]++;
				if (p == 0) {
					int flag = 1;
					for (int k = 0;k < n;++k) {
						if (m[k] !=0&&k!=j)flag = 0;
					}
					if (flag) {
						cout << j << endl;
						break;
					}
				}
			}
			
		}
		delete[] m;
		
	}
	return 0;
}

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

#define int int64_t
#define rep(i,a,n) for(int i=(a); i<(n); ++i)
#define gsort(x,n) sort((x),(x)+(n),greater<int>())
#define all(x) (x).begin(), (x).end()
#define re(s) reverse((s).begin(),(s).end())
#define ll long long
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3fLL;
const int mod = 1000000007;
using namespace std;

int x[510][510];
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,m,q;
    cin>>n>>m>>q;
    int l,r;

    rep(i,0,m){
        cin>>l>>r;
        rep(j,r,n+1) ++x[l][j];
    }

    rep(i,0,q){
        int ans = 0;
        cin>>l>>r;
        
        rep(j,l,r+1){
            ans += x[j][r] - x[j][l-1];
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
int n,m,k;

int main(){
    cin>>n;
    for(int i=2;i>0;i--){
        k=1;
       if(n%10==9){
           cout<<"Yes"<<endl;
    k=0;   break;
       }
       n=n/10;
       }
     if(k==1){
         cout<<"No"<<endl;
}

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(v) v.begin(), v.end()
#define revall(v) v.rbegin(), v.rend()
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){ if(y<h && y>=0 && x<w && x>=0) return true; return false; }
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 main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	while(1){
		bool ok = true;
		for(int j = 2; j * j <= n; j++){
			if(n % j == 0){
				ok = false;
				break;
			}
		}
		if(ok){
			cout << n << endl;
			break;
		}
		n++;
	}
}


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

using namespace std;

using ll = long long;
struct Edge {
    ll dst, w;
    Edge() {}
    Edge(ll d, ll w) : dst(d), w(w) {}
};
using Graph = vector<vector<Edge>>;
struct Cube { ll p[3]; };

// グラフを構成する
Graph MakeGraph(const int n, const int s, vector<Cube> &c) {
    Graph g(n);
    ll d[3];

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = 0; k < 3; ++k)
                d[k] = s - abs(c[i].p[k] - c[j].p[k]);

            // c[i]とc[j]は交差しない
            if (min({d[0], d[1], d[2]}) <= 0) continue;

            ll w = 2 * d[0] * d[1] + 2 * d[0] * d[2] + 2 * d[1] * d[2];
            g[i].emplace_back(Edge(j, w));
            g[j].emplace_back(Edge(i, w));
        }
    }

    return g;
}

ll Dfs(const int start, const int prev, const int cur, int size, const Graph &g) {
    if (size == 0) {
        if ((g[cur].size() == 2) && ((g[cur][0].dst == start && g[cur][0].dst != prev)
             || (g[cur][1].dst == start && g[cur][1].dst != prev)))
            return (g[cur][0].dst == start) ? g[cur][0].w : g[cur][1].w;
        else
            return 0;
    }

    ll max_w = -1;
    for (const auto &e : g[cur])
        if (e.dst != prev) {
            const ll res = Dfs(start, cur, e.dst, size - 1, g);
            if (res != -1) max_w = max(max_w, res + e.w);
        }

    return max_w;
}

int MinimumArea(const int n, const int k, const int s, const Graph &g) {
    ll res = -1;

    for (int v = 0; v < n; ++v)
        res = max(res, Dfs(v, -1, v, k - 1, g));

    return (res == -1) ? -1 : 6 * k * s * s - res;
}

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

    int n, k, s;

    while (cin >> n >> k >> s, n) {
        vector<Cube> cube(n);
        for (auto &c : cube)
            for (int i = 0; i < 3; ++i) cin >> c.p[i];

        cout << MinimumArea(n, k, s, MakeGraph(n, s, cube)) << '\n';
    }

    return 0;
}



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

int main(void)
{
    string x,y;
    string ans;
    cin>>x>>y;
    int j=0;
    int k=0;
    for(int i=0;i<x.length()+y.length();i++)
    {
        if(i%2==0)
        {
            ans+=x[j];
            j++;
        }
        else
        {
            ans+=y[k];
            k++;
        }
    }
    cout << ans <<endl;
    return 0;
}


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

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

	array<bool, 4> a = {}; // [PWGY]

	for( int i = 0; i < N; i++ ) {
		string c;
		cin >> c;

		if( c == "P" ) {
			a[0] = true;
		}
		else if( c == "W" ) {
			a[1] = true;
		}
		else if( c == "G" ) {
			a[2] = true;
		}
		else if( c == "Y" ) {
			a[3] = true;
		}
	}

	int r = 0;
	r += a[0];
	r += a[1];
	r += a[2];
	r += a[3];

	if( r == 4 ) {
		cout << "Four" << endl;
	}
	else if( r == 3 ) {
		cout << "Three" << endl;
	}
}


Measured memory_bytes: 256