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

int main(){
  int h,w;
  cin >> h >> w;
  vector<vector<int>> c(10,vector<int>(10));
  vector<vector<int>> a(h,vector<int>(w));
  rep(i,10){
    rep(j,10){
      cin >> c[i][j];
    }
  }
  rep(i,h){
    rep(j,w){
      cin >> a[i][j];
    }
  }
  rep(k,10){
    rep(i,10){
      rep(j,10){
        c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
      }
    }
  }
  int ans=0;
  rep(i,h){
    rep(j,w){
      if(a[i][j]!=-1) ans+=c[a[i][j]][1];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main() {

  // 重要な考察： 操作が行えなくなる、最終状態に注目する
  // 最終的な状態はabababa・・・のようになっているはず
  // 最終的な状態の長さの偶奇は「先頭の文字」と「最後尾の文字」が同じかどうかだけできまる
  // もとの長さと合わせて、偶数回ゲームをする必要があるか奇数ゲームをする必要があるかが決まる。

  string s;
  cin >> s;
  if ((s[0] == s.back()) ^ (s.size() % 2 == 0)) {
    cout << "Second" << endl;
  } else {
    cout << "First" << endl;
  }
  return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <assert.h>
#include <string>
#include <algorithm>
#include <sstream>
#include <iostream>
using namespace std;

typedef long long ll;
const ll maxl = 100010;
const ll mod = 1000000007;

ll n, w, k;
ll f[105][10], p[maxl], g[200];

ll P(ll n) {
    if (n < 0)
        return 0;
    return p[n];
}

void add(ll &a, ll b) {
    a = (a + b) % mod;
}

int main() {
    p[0] = 1;
    for (ll i = 1; i < maxl; i++)
        p[i] = (ll)p[i - 1] * 2 % mod;

    memset(g, 0, sizeof g);
    g[0] = 1;
    g[1] = 2;
    for (int i = 2; i < 10; i++) {
        g[i] = (g[i - 1] + g[i - 2]) % mod;
    }

    while (cin >> n >> w >> k) {
        memset(f, 0, sizeof f);
        f[n + 1][0] = 1;
        for (ll i = n + 1; i > 1; i--) {
            for (ll j = 0; j < w; j++) {
                if (f[i][j] == 0)
                    continue;

                ll c = 0;
                int l = j, r = w - 1 - j;
                if (l > 0) l--;
                if (r > 0) r--;;
                add(f[i - 1][j], f[i][j] * g[l] % mod * g[r] % mod);

                if (j + 1 < w) {
                    int l = j, r = w - 1 - (j + 1);
                    if (l > 0) l--;
                    if (r > 0) r--;
                    add(f[i - 1][j + 1], f[i][j] * g[l] % mod * g[r] % mod);
                }
                if (j - 1 >= 0) {
                    int l = j - 1, r = w - 1 - j;
                    if (l > 0) l--;
                    if (r > 0) r--;
                    add(f[i - 1][j - 1], f[i][j] * g[l] % mod * g[r] % mod);
                }
            }
        }
        cout << f[1][k - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 1532
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int x[] = new int[n];
        int i;

        for(i = 0;i < n;i++){
            x[i] = sc.nextInt();
        }

        for(i = n - 1;i >= 0;i--){
            if(i == 0){
                System.out.printf("%d\n",x[i]);
            }else{
                System.out.printf("%d ",x[i]);
            }
        }
    }
}


Measured memory_bytes: 26576
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9+7;
 
int main(){
    string s1, s2;
    cin >> s1 >> s2;

    char tmp;
    tmp=s1[0];
    s1[0]=s1[2];
    s1[2]=tmp;

    if(s1==s2) cout << "YES" << endl;
    else cout << "NO" << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();

        int ans = 0;
        if(b >= a * c) {
        	ans = c;
        }else {
        	ans = b /a;
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner scan = new Scanner(System.in);

	int A = scan.nextInt();
	int B = scan.nextInt();
	int K = scan.nextInt();

	for(int i = 0; i < K; i++){
	    if(A+i < (A+B)/2.0){
		System.out.println(A+i);
	    }
	}

	for(int i = 1; i <= K; i++){
	    if(B-K+i >= (A+B)/2.0){
		System.out.println(B-K+i);
	    }
	}
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;
const int mod = 1e9 + 7;
const int MX = 110000;
ll inv[MX], f[MX], invf[MX];
void calc(){
	inv[0] = inv[1] = f[0] = f[1] = invf[0] = invf[1] = 1;
	for (int i = 2; i < MX; i++){
		inv[i] = mod - mod / i * inv[mod % i] % mod;
		f[i] = f[i - 1] * i % mod;
		invf[i] = invf[i - 1] * inv[i] % mod;
	}
}
inline ll C(ll n, ll k){
	return f[n] * invf[k] % mod * invf[n - k] % mod;
}
int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	calc();
	
	int n; cin >> n;
	vi a(n + 1); rep(i, n + 1) cin >> a[i];
	vi ans(n + 1);
	
	vi v;
	int dup;
	map<int,int> cnt;
	for(int i : a) cnt[i]++;
	for(auto p : cnt) if(p.second == 2) dup = p.first;
	rep(i, n + 1) if(a[i] == dup) v.pb(i);
	int l = v[0], r = n - v[1];
	
	//dbg(l, r, dup);
	
	rep(i, n + 1){
		ans[i] = C(n + 1, i + 1);
		if(i == 0) (ans[i] += mod - 1) %= mod;
		else if(l + r >= i) (ans[i] += mod - C(l + r, i)) %= mod;
		
		cout << ans[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 9344
#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define mp make_pair
#define F(i, a, n, b) for(int i=a;i<n;i+=b)
#define REVF(i, a, b, c) for(int i=a;i>=b;i-=c)
#define REP(i, n) F(i, 0, n, 1)
#define REP1(i, n) F(i, 1, n+1, 1)
#define REV(i, n) REVF(i, n, 0, 1)
#define PTR(it, x) for(auto it=x.begin();it!=x.end();++it)
#define MOD 1000000007

typedef unsigned long long ll;

const ll MAX = 1e10;

int n;
string s,t;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>s>>t;
	REP(i,n){
		cout<<s[i]<<t[i];
	}
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var n, k float64
	fmt.Scan(&n, &k)
	sum := 0
	for i := 0; i < int(n); i++ {
		var tmp float64
		fmt.Scan(&tmp)
		sum += 2 * int(math.Min(math.Abs(tmp-k), tmp))
	}
	fmt.Println(sum)
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define r(i,n) for(long long i=1;i<=n;i++)
using namespace std;
#define int long long
main(){
  int a,b,c,ans=1e13;
  cin>>a>>b>>c;
  r(i,c)r(j,c)if(!(b*i%j))ans=min(ans,abs(b*i/j-a));
  cout<<ans<<endl;
}

Measured memory_bytes: 3100
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a, b, c, d, p;
int x, y;
int main()
{
	cin >> a >> b >> c >> d >> p;
	x=a*p;
	if(p<=c)
	{
		y=b;
	}
	else
	{
		y=b+(p-c)*d;
	}
	cout << min(x, y) << endl;
	return 0;
}

Measured memory_bytes: 1160
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
s = 0
t = 0
ai = -1
bi = -1
for i in range(n):
    if s + a[i] <= k:
        s += a[i]
        t += 1
        ai = i
    else:
        break
ans = t
while True:
    for i in range(bi+1, m):
        if s + b[i] <= k:
            s += b[i]
            t += 1
            bi = i
        else:
            break
    ans = max(t, ans)
    if ai == -1 or bi == m-1:
        break
    s -= a[ai]
    t -= 1
    ai -= 1
print(ans)

Measured memory_bytes: 42368
h, w = map(int, input().split())

WF = []
wall = []
ans = 0

for _ in range(10):
    array = list(map(int, input().split()))
    WF.append(array)

for _ in range(h):
    array = list(map(int,input().split()))
    wall.append(array)

for k in range(10):
    for i in range(10):
        for j in range(10):
            WF[i][j]=min(WF[i][j],WF[i][k]+WF[k][j])

for i in range(h):
    for j in range(w):
        num = wall[i][j]
        if num != -1:
            ans += WF[num][1]

print(ans)

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

int main()
{

int a,b,c;
cin >> a >> b >> c;
int i = 0;
if (a == 5 && b == 7 && c == 5){
    i++;
}else if (a == 5 && b == 5 && c == 7){
    i++;
}else if (a == 7 && b == 5 && c == 5){
    i++;
}

if (i == 1){
    cout << "YES";
}else {
    cout << "NO";
}

return 0;
}


Measured memory_bytes: 256
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

K = int(input())
S = input()

L = len(S)

if L <= K:
    print(S)
else:
    print(S[:K] + "...")

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

typedef long long int ll;

double prob[3005];
double ans[3005][3005];

bool isPrime(ll n) 
{ 
    // Corner cases 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
  
    // This is checked so that we can skip 
    // middle five numbers in below loop 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
}

int main()
{
    ios::sync_with_stdio(false);

    ll i,j,k,l,m,n;

    cin >> n;

    for(i=1;i<=n;i++)
        cin >> prob[i];

    ans[0][0] = 1;

    for(i=1;i<=n;i++)
    {
        ans[i][0] = (1- prob[i])*(ans[i-1][0]);
        for(j=1;j<=i;j++)
        {
            ans[i][j] = prob[i]*ans[i-1][j-1] + (1- prob[i])*(ans[i-1][j]);

            // cout << ans[i][j] << " "; 
        }

        // cout << '\n';
    }

    double sum=0;


    for(i=0;i<=n;i++)
    {
        for(j=0;j<=i;j++)
        {
            // cout << ans[i][j] << " ";

            if(i==n)
            {
                if(j>(n/2))
                {
                    sum += ans[i][j];
                }
            }
        }

        // cout << '\n';
    }

    std::cout << std::fixed;
    cout << std::setprecision(9) << sum << '\n';
}

Measured memory_bytes: 69120
import heapq

N = int(input())
A = [int(x) for x in input().split()]

max_value = max(A)
positive = []
negative = []
flag = True
for a in A:
    if a == max_value and flag:
        flag = False
        continue
    elif a > 0:
        heapq.heappush(positive, a)
    else:
        negative.append(a)

if len(negative) > 0:
    nega = negative.pop()
else:
    nega = heapq.heappop(positive)

actions = []
while len(positive) > 0:
    y = heapq.heappop(positive)
    actions.append((nega, y))
    nega = nega - y

negative.append(nega)

while len(negative) > 0:
    y = heapq.heappop(negative)
    actions.append((max_value, y))
    max_value = max_value - y

print(max_value)
for action in actions:
    x, y = action
    print("{} {}".format(x, y))


Measured memory_bytes: 20232
from math import atan, pi
a, b, x = list(map(int,input().split()))
V = a*a*b/2
if x<=V:
    c = 2*x/a/b
    angle = atan(b/c)*180/pi
else:
    d = 2*x/a/a - b
    angle = atan((b-d)/a)*180/pi
print(angle)

Measured memory_bytes: 3060
#include<stdio.h>

int main(void){
  
  int a,b,c;
  
  scanf("%d %d %d",&a,&b,&c);
  
  if(a+b>=c){
    
    printf("Yes");
    
  }else{
    
    printf("No");
    
  }
  
  return 0;
  
}

Measured memory_bytes: 128
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
kaidan = [-1] * (n + 1)
for i in range(len(l)):
    kaidan[l[i][0]] = 0
for i in range(1, len(kaidan) + 1):
    if not (kaidan[-i] == 0):
        if i == 1:
            kaidan[-1] = 1
        elif i == 2:
            kaidan[-2] = kaidan[-1]
        else:
            kaidan[-i] = kaidan[-i + 1] + kaidan[-i + 2]
print(kaidan[0] % 1000000007)

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

int main() {
    int a, b;
    cin >> a >> b;
    const double tax8 = 0.08;
    const double tax10 = 0.1;
    for (int i = 1; i < 1010; i++) {
        if ((int)(i * tax8) == a && (int)(i * tax10) == b) {
            cout << i << endl;
            return 0;
        }
    }

    cout << "-1" << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a1 = sc.nextInt()
    val a2 = sc.nextInt()
    val a3 = sc.nextInt()
    println(problem103a(a1, a2, a3))
}

fun problem103a(a1: Int, a2: Int, a3: Int): Int {
    val a = listOf(a1, a2, a3).sorted()
    return (a[2] - a[1]) + (a[1] - a[0])
}

Measured memory_bytes: 35820
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

int n;
vector<int> l;
int main() {
  cin >> n;
  read_n(l, n);

  int s = 0;
  for (int x : l) s += x;

  bool f = true;
  for (int x : l) {
    if (x >= s - x) f = false;
  }

  cout << (f ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int cave_nums = sc.nextInt();
	
	for(int i=0;i<cave_nums;i++){
	    int x,y,now_x=0,now_y=0;
	    double tmp_dist = 0;
	    String tmp_treasure="";
	    int tmp_x=0;
	    while(true){
		x = sc.nextInt();
		y = sc.nextInt();
		if(x == 0 && y == 0)break;
		now_x = now_x + x;
		now_y = now_y + y;
		if(tmp_dist < Math.pow(now_x,2) + Math.pow(now_y,2)){
		    tmp_treasure = Integer.toString(now_x) +  " " + Integer.toString(now_y);
		    tmp_dist = Math.pow(now_x,2) + Math.pow(now_y,2);
		    tmp_x = now_x;
		}else if(tmp_dist == Math.pow(now_x,2) + Math.pow(now_y,2)){
		    if(now_x>tmp_x){
			tmp_treasure = Integer.toString(now_x) +  " " + Integer.toString(now_y);
			tmp_dist = Math.pow(now_x,2) + Math.pow(now_y,2);
			tmp_x = now_x;
		    }
		}
      	    }
	    System.out.println(tmp_treasure);
	}
    }
}

Measured memory_bytes: 26192
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a+b>c+d){
    cout<<"Left"<<endl;
  }
  else if(a+b==c+d){
    cout<<"Balanced"<<endl;
  }
  else{
    cout<<"Right"<<endl;
  }
}
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define M 1000000007
#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define REPI(i,a,b) for(ll i=b-1;i>=a;i--)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define G(a,b) get<a>(b)
#define VI vector<int>
#define VLL vector<long long>

#define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define o_setll tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set

ll modI(ll a, ll m);
ll gcd(ll a, ll b);
ll powM(ll x, unsigned ll y, unsigned ll m);
void pairsort(int a[], int b[], int n);
void pairsortll(ll a[],ll b[],ll n);
ll logint(ll x,ll y);


ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powM(ll x,ll y,ll m)
{
    if(y==0) return 1;
    ll p=powM(x,y/2,m)%m;
    p=(p*p)%m;
    return (y%2==0)?p:(x*p)%m;
}

ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}

void pairsort(int a[],int b[],int n)
{
    pair<int,int> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}

void pairsortll(ll a[],ll b[],ll n)
{
    pair<ll,ll> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}

ll logint(ll x,ll y)
{
    ll ans=0;
    ll a=1;
    for(ll i=0;i<=x;i++)
    {
        if(x<a)
        {
            return ans;
        }
        ans++;
        a*=y;
    }
    return -1;
}

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

    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */

    ll q=1;
    //cin>>q;
    while(q--)
    {
        ll n;
        cin>>n;
        ll a[n+1];
        REP(i,0,n+1)
        {
            ll t;
            cin>>t;
            a[i]=t;
        }
        ll ans=0;
        REP(i,0,n)
        {
            ll t;
            cin>>t;
            ll x=min(t,a[i]);
            a[i]-=x;
            t-=x;
            ans+=x;
            ll y=min(t,a[i+1]);
            a[i+1]-=y;
            t-=y;
            ans+=y;
        }
        cout<<ans;
    }

    return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    string S;
    cin >> S;

    int N = S.size();
    reverse(S.begin(), S.end());

    vector<int> f(N+1);
    int k = 1;
    rep(i, N) {
        f[i+1] = (f[i] + (S[i] - '0') * k) % 2019;
        k *= 10;
        k %= 2019;
    }

    vector<ll> count(2019);
    rep(i, N+1) count[ f[i] ]++;

    ll ans = 0;
    rep(i, 2019) ans += count[i] * (count[i] - 1) / 2;

    cout << ans << endl;
}

Measured memory_bytes: 4328
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!

/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define l long
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<int,int>
#define maxn 100005
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
using namespace __gnu_pbds;

signed main()
{
    fast;
   
    ll n,m,i,j;
    cin>>n>>m;
    ll a[5];
    for(i=0;i<=4;i++) a[i] = -1;
    bool ok = true;
    for(i=0;i<m;i++)
    {
    	ll s,d;
    	cin>>s>>d;
    	if(a[s]==-1) a[s] = d;
    	else if(a[s]!=d) ok = false;
    }
    if(a[1]==0 and n!=1) ok = false;
    if(!ok) cout<<"-1";
    else
    {
    	for(i=1;i<=n;i++)
    	{
    		if(a[i]==-1)
    		{
    			if(i==1) 
    			{
    				if(n==1) a[i] = 0;
    				else a[i] = 1;
    			}
    			else a[i] = 0;
    		}
    	}
    	for(i=1;i<=n;i++) cout<<a[i];
    }
}

Measured memory_bytes: 256
import java.util.*;

class Main{
 public static void main(String args[]){
   Scanner scn = new Scanner(System.in);
   String a = scn.nextLine();
   String b = scn.nextLine();
   List<String> li = new ArrayList<String>();
   li.add("1");
   li.add("2");
   li.add("3");
   li.remove(a);
   li.remove(b);
   System.out.println(Integer.parseInt(li.get(0)));
 }
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
int main(){
    int m,f,r;
    while(1){
        cin >> m >> f >> r;
        if(m == -1&&f == -1&&r == -1)break;
        if(m == -1||f == -1)cout << "F" << endl;
        else if(m+f >= 80)cout << "A" << endl;
        else if(m+f >= 65&&m+f < 80)cout << "B" <<endl;
        else if(m+f >= 50&&m+f < 65)cout << "C" <<endl;
        else if(m+f < 30)cout << "F" << endl;
        else if(m+f >= 30&&m+f < 50){
            if(r>=50)cout << "C" <<endl;
            else cout << "D" << endl;
        
        }
    }
    
    return 0;
}


Measured memory_bytes: 3092
#include<stdio.h>
int main()
{
    int n,x,i,j,count=1,t=0;
    scanf("%d%d",&n,&x);
    int a[n];

    for(i=0;i<n;i++)
        scanf("%d",&a[i]);




            for(i=0;i<n;i++)
            {
              t+=a[i];
                if(t>x) break;
                count++;
               
            }
            printf("%d",count);
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
//ranker
using namespace std;
using std::printf;
using std::scanf;

#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using psi = pair<string, int>;
using D = double;


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

  string s;

  cin >> s;

  if((s.front() == s.back())^(s.size()%2 == 0)) cout << "Second" << endl;
  else cout << "First" << endl;


}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Set         std::set
#define PQueue      std::priority_queue
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define UMap        std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    llong power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    llong power ( llong x, llong n ) { return power( x, n, 1000000007 ); }
    llong gcd   ( llong x, llong y ) { return x % y ? gcd( y, x % y ) : y; }
    llong lcm   ( llong x, llong y ) { return ( x / gcd(x, y) * y ); }
    llong abs   ( llong n )          { return ( n < 0 ) ? -n : n; }
    template<class A, class B>inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B>inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    signed call_of_Cthulhu( signed datum ) {

        int h, w;
        read h >> w;
        w += 'A' - 1;
        for ( int i = 1; i <= h; i++ ) {
            for ( char j = 'A'; j <= w; j++ ) {
                String str;
                read str;
                if ( str == "snuke" ) {
                    echo j << i fin;
                }
            }
        }

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); echo std::fixed << std::setprecision(8); int main_result = Rlyeh::call_of_Cthulhu(114514); return main_result;}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int x,a,b; cin>>x>>a>>b;
    if(abs(a-x)>abs(b-x)) cout<<'B'<<endl;
    else cout<<'A'<<endl;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class CSkillUp {
public:
    int N, M, X;
    const int INF = ten(9);
    vc<int> C;
    vvc<int> A;

    int rec(int i, int sum, vc<int> val){
        if(i==N){
            REP(j, M){
                if(val[j]<X) return INF;
            }
            return sum;
        }
        int res = rec(i+1, sum, val);
        sum += C[i];
        REP(j, M) val[j] += A[i][j];
        chmin(res, rec(i+1, sum, val));
        return res;
    }

    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        in>>N>>M>>X;
        C.resize(N);
        A.resize(N, vc<int>(M));
        REP(i, N){
            in>>C[i];
            REP(j, M) in>>A[i][j];
        }
        vc<int> val(M, 0);
        int ans = rec(0, 0, val);
        if(ans==INF) ans = -1;
        out<<ans<<'\n';
    }
};


int main() {
	CSkillUp solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3676
// Problem : G - Longest Path
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_g
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
 
#define endl "\n"
#define int long long
#define FAST {ios_base::sync_with_stdio(false);cin.tie(NULL);}
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
#define rep(n) for(int i=0;i<(n);i++)
#define rrep(n) for(int i=(n)-1;i>=0;i--)
#define mem(a,b) memset((a),(b),sizeof (a))
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define INF (long long) 1e18
#define MOD 1000000007
const int MAX = 2e5+5;

int maxm = 0,n,m;
int dp[MAX],visited[MAX],deg[MAX];
vector<int> adj[MAX];
vector<int> adjT[MAX];

int32_t main(){
      cin>>n>>m;
      memset(dp,0,sizeof dp);
      memset(deg,0,sizeof deg);
      for(int i=0;i<m;i++){
            int x,y;
            cin>>x>>y;
            adj[x].pb(y);
            adjT[y].pb(x);
            deg[y]++;
      }
      queue<int> que;
      for(int i=1;i<=n;i++){
            if(deg[i]==0) que.push(i);
      }
      while(!que.empty()){
            int node = que.front();
            que.pop();
            dp[node] = 0;
            for(int x : adjT[node]){
                  dp[node] = max(dp[node],1+dp[x]);
            }
            for(int parent : adj[node]){
                  deg[parent]--;
                  if(deg[parent]==0) que.push(parent);
            }
      }
      int maxm = 0;
      for(int i=1;i<=n;i++){
            maxm = max(maxm,dp[i]);
      }
      cout<<maxm<<endl;
      return 0;
}




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

#define int long long

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

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

int N;
int D[55];

int cost[24][24];

signed main(){
    rep(i,24)rep(j,24){
        int x=(i-j+24)%24;
        cost[i][j]=min(x,24-x);
    }


    cin>>N;
    D[0]=0;
    rep(i,N)cin>>D[i+1];
    N++;

    if(N>24){
        cout<<0<<endl;
        return 0;
    }
    if(N>12){
        int cnt[13]={};
        rep(i,N)cnt[D[i]]++;
        bool ok=true;
        if(cnt[0]>1||cnt[12]>1)ok=false;
        for(int i=1;i<12;i++)if(cnt[i]>2)ok=false;
        if(ok)cout<<1<<endl;
        else cout<<0<<endl;
        return 0;
    }

    int ans=0;
    rep(i,1<<N){
        vint d(N);
        rep(j,N){
            d[j]=D[j];
            if(i>>j&1)d[j]=(24-d[j])%24;
        }

        int latte=INT_MAX;
        rep(j,N)rep(k,N)if(j!=k)chmin(latte,cost[d[j]][d[k]]);
        chmax(ans,latte);
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  long n;
  int k,a,cc;
  cin >> n >> k;
  vector<long> data(1000000);
  for (long i=0; i<n; i++) {
    cin >> a;
    data.at(i) = a;
  }

  cc = 0;
  for (long i=0; i<n; i++) {
    if (data.at(i) >= k) {
      cc++;
    }
  }
  cout << cc << endl;
}


Measured memory_bytes: 8064
#include<iostream>
#include<cstdio>
#include<string>
#include<cfloat>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
#include<map>
#include<functional>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
const int mod = 1e9+7;
const int INFINT = INT_MAX/2;
typedef long long ll;
typedef unsigned long long ull;

int calculate(vector<int> &a, int x){
    int N=a.size();
    int S = 0;
    REP(i, N){
        S += (a[i] - x)*(a[i] - x);
    }
    return S;
}

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N){
        cin >> a[i];
    }
    int S = 0;
    REP(i, N){
        S += a[i];
    }
    int c = S/N;
    if(calculate(a, c) < calculate(a, c+1)){
        cout << calculate(a,c) << endl;
    }else{
        cout << calculate(a,c+1) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

typedef long long LL;
const LL INF = 123456789012345;

const int ST_MAX = (1 << 20);

template <class T> class ST{
	T x[ST_MAX * 2];
	
	T eval(T a , T b){
		return min(a , b);
	}
	
	void ren(int a){
		x[a] = eval(x[2 * a] , x[2 * a + 1]);
		if(a > 0) ren(a / 2);
	}
	
	T read_ST(int a , int b , int e , int s , int f){
		if(e <= s || f <= b) return INF;
		if(s <= b && e <= f) return x[a];
		return eval(read_ST(2 * a , b , (b + e) / 2 , s , f) , read_ST(2 * a + 1 , (b + e) / 2 , e , s , f));
	}
	
public:
	
	ST(){
		fill(x , x + 2 * ST_MAX , INF);
	}
	
	void put(int a , T b){
		x[a + ST_MAX] = b;
		ren((a + ST_MAX) / 2);
	}
	
	T get(int s , int f){
		return read_ST(1 , 0 , ST_MAX , s , f);
	}
};

ST<LL> b;
int N , E , T;
LL x[100010];
LL dp[100010];

int main(){
	scanf("%d%d%d" , &N , &E , &T);
	repp(i,1,N+1){
		scanf("%lld" , x + i);
	}
	LL a = INF;
	b.put(0,0);
	int z = 1;
	repp(i,1,N+1){
		while(z < i && T <= 2 * (x[i] - x[z])){
			a = min(a , dp[z-1] - 2 * x[z] - x[z-1]);
			++z;
		}
		dp[i] = min(a + 3 * x[i] , b.get(z-1,i) + (LL)T + x[i]);
		b.put(i , dp[i] - x[i]);
	}
	printf("%lld\n" , dp[N] + (LL)E - x[N]);
	return 0;
}


Measured memory_bytes: 18176
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String strs[] = br.readLine().split(" ");
    String s = br.readLine();
    int N = Integer.parseInt(strs[0]), Q = Integer.parseInt(strs[1]);
    int index = 1;
    int[] ac = new int[s.length() + 1];
    for (int i = 0; i < s.length(); i++) {
      if (i - 1 >= 0 && 'A' == s.charAt(i - 1) && 'C' == s.charAt(i)) {
        ac[index] = ac[index - 1] + 1;
      } else {
        ac[index] = ac[index - 1];
      }
      index++;
    }
    for (int i = 0; i < Q; i++) {
      String[] str = br.readLine().split(" ");
      int start = Integer.parseInt(str[0]), end = Integer.parseInt(str[1]);
      System.out.println(ac[end] - ac[start]);
    }
  }
}


Measured memory_bytes: 48328
def common(n)
  cnt = 0
  for i in (1..Math.sqrt(n)) do
    if n % i == 0
      if i == Math.sqrt(n)
        cnt += 1
      else
        cnt += 2
      end
    end
  end
  cnt
end

num = gets.to_i
cnt=0
1.step(num,2) do |i|
  if common(i) == 8
    cnt += 1
  end
end

puts cnt

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

// typedef
// -----------------------------------------------------------------------------
typedef long long ll;
typedef long double ld;

// container util
// -----------------------------------------------------------------------------
#define ALL(c)  (c).begin(),(c).end()
#define SZ(c) ((ll)(c).size())
#define MAX(c) *max_element(ALL(c))
#define MIN(c) *min_element(ALL(c))
#define SORT(c) sort((c).begin(),(c).end())

// repetition
// -----------------------------------------------------------------------------
#define FOR(i, a, b) for(ll i= (a); i < (ll)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
// -----------------------------------------------------------------------------
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);

// debug
// -----------------------------------------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    ld N; cin >> N;
    ll min_v = ceill(N / 1.08);
    ll max_v = floorl((N + 1) / 1.08);
    if (min_v <= max_v) {
        cout << min_v << "\n";
    } else {
        cout << ":(" << "\n";
    }
}


Measured memory_bytes: 3756
#include<bits/stdc++.h>
using namespace std;
int cnt;
void insertionSort(int *A,int n,int g){
  for(int i=g;i<n;i++){
    int v=A[i];
    int j=i-g;
    while(j>=0&&A[j]>v){
      A[j+g]=A[j];
      j-=g;
      cnt++;
    }
    A[j+g]=v;
  }
}
void shellSort(int *A,int n){
  cnt=0;
  int r=1;
  vector<int> G;
  while(r<=n){
    G.push_back(r);
    r*=2;
  }
  int m=G.size();
  reverse(G.begin(),G.end());
  cout<<m<<endl;
  for(int i=0;i<m;i++) cout<<G[i]<<" \n"[i==m-1];
  for(int i=0;i<m;i++) insertionSort(A,n,G[i]);
  cout<<cnt<<endl;
}
signed main(){
  int n;
  cin>>n;
  int A[n];
  for(int i=0;i<n;i++) cin>>A[i];
  shellSort(A,n);
  for(int k=0;k<n;k++) cout<<A[k]<<endl;
  return 0;
}



Measured memory_bytes: 7060
#include <bits/stdc++.h>
#define REP(i, n) for(long long i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;


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

Measured memory_bytes: 256
#ifdef LOCAL_BUILD
#include "pch.h"
#define DLOG(msg) cout << "#" << __LINE__ << ":" << msg << endl;
#else
#include <bits/stdc++.h>
#define DLOG(msg)
#endif
using namespace std;

int main() {
  int n;
  cin >> n;
  int min_ = numeric_limits<int>::max();
  int max_diff = numeric_limits<int>::lowest();
  for (int t, i = 0; i < n; ++i) {
    cin >> t;
    max_diff = max(max_diff, t - min_);
    min_ = min(min_, t);
  }
  cout << max_diff << endl;
}

Measured memory_bytes: 3088
N=int(input())

S=list(map(int, input().split()))

T=[0]*9
for i in range(N):
    if S[i] < 400:
        T[0]+=1
    elif S[i] < 800:
        T[1]+=1
    elif S[i] < 1200:
        T[2]+=1
    elif S[i] < 1600:
        T[3]+=1
    elif S[i] < 2000:
        T[4]+=1
    elif S[i] < 2400:
        T[5]+=1
    elif S[i] < 2800:
        T[6]+=1
    elif S[i] < 3200:
        T[7]+=1
    elif S[i] >= 3200:
        T[8]+=1

K=0
for i in range(8):
    if T[i] >= 1:
        K+=1

if K>0:
    print(K,K+T[8])
else:
    print(1,T[8])


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

int main() {
    long long int a, b, c, d;
    cin >> a >> b >> c >>d;
    long long int mal[4];
    mal[0] = a*c;
    mal[1] = a*d;
    mal[2] = b*c;
    mal[3] = b*d;
    long long int max = mal[0];
    for(int i=1; i<4; ++i){
        if(max<mal[i]) max = mal[i];
    }
    cout << max <<endl;
}

Measured memory_bytes: 3632
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define printd(val) std::cout<< #val" = " <<val<<"\n";
#include<bits/stdc++.h>
using ll = long long;
using pii = std::pair<int,int>;
using namespace std;
template<class T>T chmin(T a,T b){if(a>b){a^=b;b^=a;a^=b;return 1;}return 0;}
template<class T>T chmax(T b,T a){if(a<b){a^=b;b^=a;a^=b;return 1;}return 0;}

map<string,ll> memory_count;
int n;
string s;

void input(){
    cin>>n;
}
void src(){
    rep(i,n){
        cin>>s;
        sort(s.begin(),s.end());
        memory_count[s]++;
    }
    ll sum=0;
    for(auto i:memory_count) if(i.second>1)sum+=i.second*(i.second-1)/2ll;
    cout<<sum;
    return;
}

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
    //ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N;
  	cin>>N;
  	vector<int>arr(N);
  	for(int i = 0; i < N; i++){
    	cin>>arr[i];
    }
  	int ans = 0;
  	for(int i = 0; i < N; i++){
    	int temp;
      	cin>>temp;
      	ans+=temp;
    }
  	vector<int>Barr(N);
  	for(int i = 0; i < N-1; i++){
    	cin>>Barr[i];
    }
  	for(int i = 0; i < N-1; i++){
    	if(arr[i] == arr[i+1]-1){
        	ans+=Barr[arr[i]-1];
        }
    }
  	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int count=0;
int s,n;

void ans(int i,int n,int sum);

void main()
{

	while(scanf("%d %d",&n,&s),n){
		count=0;
		ans(0,0,0);
		printf("%d\n",count);
	}
}

void ans(int i,int sum,int ele)
{
	if(i==n){
		if(sum==s)
			count++;
	}
	else{
		if(ele<=9){
			ans(i+1,sum+ele,ele+1);
			ans(i,sum,ele+1);
		}
	}
}

Measured memory_bytes: 600
#include <algorithm>
// #include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double db;
const int oo=2139063143;
const int N=2010;
const int P=1000000007;
const db eps=1e-7;
#define pritnf printf
//char buf[1<<22],*p1=buf,*p2=buf,obuf[1<<22],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
    if (x< 0) putchar('-'),x=-x;
    if (x>=10) print(x/10);
    putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
template <typename T1,typename T2>
void chkmax (T1 &A,T2 B) { A=A>=B?A:B; }
template <typename T1,typename T2>
void chkmin (T1 &A,T2 B) { A=A<=B?A:B; }
int n,a[N];
#define pb push_back
vector <int> G[N];
int siz[N],f[N],dep[N];
void dfs0 (int u,int fa)
{
	siz[u]=a[u],dep[u]=dep[fa]+1,f[u]=a[u]*dep[u];
	for (int v:G[u]) if (v!=fa)
		dfs0 (v,u),siz[u]+=siz[v],f[u]+=f[v];
}
bool dfs (int u,int fa,int x)
{
	int sum=0,ma=0,son=0;
	for (int v:G[u]) if (v!=fa)
	{
		int g=f[v]-siz[v]*dep[u];
		if (g> ma) sum+=ma,ma=g,son=v;
		else sum+=g;
	}
	if (sum>=ma) return sum+ma>=x;
	return dfs (son,u,x-(sum<<1));
}
char s[N];
int main ()
{
    // freopen (".in","r",stdin);
    // freopen (".out","w",stdout);
	sc(n);
	scanf ("%s",s+1);
	for (int i=1; i<=n; i++)
		a[i]=s[i]-'0';
	for (int i=1; i< n; i++)
	{
		int x,y; sc(x),sc(y);
		G[x].pb (y),G[y].pb (x);
	}
	int ans=oo; dep[0]=-1;
	for (int x=1; x<=n; x++)
	{
		dfs0 (x,0);
		if ((f[x]&1)||(f[x]>>1)> ans) continue;
		if (dfs (x,0,f[x])) ans=f[x]>>1;
	}
	pr(ans==oo?-1:ans);

    return 0;
}


Measured memory_bytes: 512
import math
N = int(input())
X = list(map(float, input().split()))
Y = list(map(float, input().split()))
S = [abs(x-y) for x,y in zip(X, Y)]
SS = [s**2 for s in S]
SSS = [s**3 for s in S]
print(sum(S))
print(pow(sum(SS), 1/2))
print(pow(sum(SSS), 1/3))
print(max(S))


Measured memory_bytes: 5720
#include <bits/stdc++.h>
 
using namespace std;
  
int main(){
int N;
  cin >>N;
vector<int>data(N);
  for(int i=0;i<N;i++){
  cin >>data.at(i);
  }
  sort(data.begin(),data.end());
  double s=(data.at(0)+data.at(1)) /pow(2.0,N-1);
  for (int i=0;i<N-2;i++){
  s+=data.at(i+2) /pow(2.0,N-i-2) ;
  }
  cout <<s<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=1; i<=(n); ++i)
typedef long long ll;
ll comb(ll n){
  return n*(n-1)/2;
}
int main(){
  ll n; cin >> n;
  vector<ll> a;
  map<ll, ll> m;
  rep(i,n){
    ll t; cin >> t;
    a.push_back(t);
    m[t] +=1;
  }
  a.resize(n);
  ll sum=0;
  
  rep(i,n){
    sum += comb(m[i]);
  }
  
  rep(i,n){
    ll b = a[i-1];
    cout << max((sum-(m[b]-1)),(ll)0) << endl;
  }
}

Measured memory_bytes: 16752
# coding: utf-8
# Your code here!
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
slist = {}
ans = 0
for i in range(N):
    S = []
    moji = input()
    for j in range(10):
        S.append(moji[j])
    ins = "".join(sorted(S))
    if ins in slist:
        ans += slist[ins]
        slist[ins] += 1
    else:
        slist[ins] = 1

mul = slist.values()
ansl = [n for n in mul if n!=1]

ret = 0
for x in ansl:
    ret += combinations_count(x, 2)
print(ret)





Measured memory_bytes: 17888
#include "bits/stdc++.h"
using namespace std;

int main() {
	
	
	int n, k;
	cin >> n >> k;
	
	int ac = 0;
	
	bool did[n+1];
	memset(did, 0, sizeof did);
	
	int pen[n+1];
	memset(pen, 0, sizeof pen);
	
	for (int i=0; i<k; i++) {
		int y;
		cin >> y;
		string v;
		cin >> v;
		if (v == "AC") {
			did[y] = true;
		}
		else {
			if (!did[y]) pen[y]++;
		}
	}
	
	int x = 0;
	int y = 0;
	
	for (int i=1; i<=n; i++) {
		if (did[i]) {
			x++;
			y += pen[i];
		}
	}
	
	cout << x << ' ' << y << endl;
	
}


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

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

long long extGcd(long long a, long long b, long long &p, long long &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    long long d = extGcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}

// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) {
  long long r = 0, M = 1;
  for (int i = 0; i < (int)b.size(); ++i) {
    long long p, q;
    long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
    if ((b[i] - r) % d != 0) return make_pair(0, -1);
    long long tmp = (b[i] - r) / d * p % (m[i]/d);
    r += M * tmp;
    M *= m[i]/d;
  }
  return make_pair(mod(r, M), M);
}

int main(){
  
  long long N,M;
  cin >> N;
  cin >> M;
  
  vector<long long> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
    if (a.at(i) % 2 == 1){
      cout << 0 << endl;
      exit(0);
    }
  }
  
  vector<long long> b(N);  
  for (int i = 0;i < N;i++){
    b[i] = a[i] / 2;
  }
  
  pair<long long , long long> foo = ChineseRem(b,a);
  //cout << foo.first << " " << foo.second << endl;
  if (foo.second != -1 && M >= foo.first){
    
  	cout << (M - foo.first) / foo.second  + 1<< endl;
  }else{
    cout << 0 << endl;
  }
  return 0;
}
  

Measured memory_bytes: 1792