akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k,s;
int dfs(int pos,int sum,int cnt){
    if(pos>n){
        if(cnt==k&&sum==s)return 1;
        else return 0;
    }
    return dfs(pos+1,sum,cnt)+dfs(pos+1,sum+pos,cnt+1);
}
int main(){
    while(cin>>n>>k>>s,n||k||s){
        cout<<dfs(1,0,0)<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <string>
#include <cstdio>

using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()


/*
int main(){
    string s;
    cin>>s;
    string al="",num="";
    rep(i,s.size()){
        if(isalpha(s[i])){
            al+=s[i];
        }
        else num+=s[i];
    }
    
    sort(all(al));
    sort(all(num));
    
    int ans=0;
    for(int i=0;i<al.size();){
        int c=0;
        for(int j=1;i+j<al.size();j++){
            if(al[i+j]==al[i+j-1]+1)c++;
            else break;
        }
        if(c>=3){
            ans+=3;
            i+=c;
        }
        else{
            ans++;
            i++;
        }
    }
    for(int i=0;i<num.size();){
        int c=0;
        for(int j=1;i+j<num.size();j++){
            if(num[i+j]==al[i+j-1]+1)c++;
            else break;
        }
        if(c>=3){
            ans+=3;
            i+=c;
        }
        else{
            ans++;
            i++;
 
 #include <iostream>
 #include <vector>
 #include <algorithm>
 #include <cmath>
 #include <string>
 #include <cstdio>
 
 using namespace std;
 #define rep(i,n) for(int i=0;i<(int)(n);i++)
 #define all(a) (a).begin(),(a).end()
 
 
 
 int main(){
 string s;
 cin>>s;
 string al="",num="";
 rep(i,s.size()){
 if(isalpha(s[i])){
 al+=s[i];
 }
 else num+=s[i];
 }
 
 sort(all(al));
 sort(all(num));
 
 int ans=0;
 for(int i=0;i<al.size();){
 int c=0;
 for(int j=1;i+j<al.size();j++){
 if(al[i+j]==al[i+j-1]+1)c++;
 else break;
 }
 if(c>=3){
 ans+=3;
 i+=c;
 }
 else{
 ans++;
 i++;
 }
 }
 for(int i=0;i<num.size();){
 int c=0;
 for(int j=1;i+j<num.size();j++){
 if(num[i+j]==al[i+j-1]+1)c++;
 else break;
 }
 if(c>=3){
 ans+=3;
 i+=c;
 }
 else{
 ans++;
 i++;
 }
 }
 
 cout<<ans<<endl;
 }
 
 
 
 
 
 /*
 int main(int argc, const char * argv[]) {
 int n, a, d, m;
 cin >> n >> a >> d >> m;
 vector<int> array(n);
 array[0] = a;
 for(int i = 1; i < n; i++){
 array[i] += array[i - 1] + d;
 }
 
 for (int i = 0; i < m ; i++) {
 int x, y, z;
 cin >> x >> y >> z;
 if(x == 1){
 array[y - 1] = array[z - 1];
 }else{
 swap(array[y - 1], array[z - 1]);
 }
 }
 int k;
 cin >> k;
 cout << array[k - 1] <<endl;
 
 return 0;
 }
 */




int main(int argc, const char * argv[]) {
    int n, a, d, m;
    cin >> n >> a >> d >> m;
    map<int, int> sw;

    for (int i = 0; i < m ; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if(sw[y] == 0 )sw[y] = y;
        if(sw[z] == 0 )sw[z] = z;
        if(x == 1){
            sw[y] = sw[z];
         }else{
             swap(sw[y], sw[z]);
        }
    }
    int k;
    cin >> k;
    if(sw[k] == 0)sw[k]=k;
    cout << (sw[k] - 1)*d + a << endl;

    return 0;
}

Measured memory_bytes: 1200
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    input_raw = read_func().strip().split()
    W  = [int(input_raw[i]) for i in range(N)]

    ans = sys.maxint
    for i in range(N):
        S1 = 0
        S2 = 0
        for j in range(N):
            if j <= i:
                S1 += W[j]
            else:
                S2 += W[j]
        ans = min(abs(S1 - S2), ans)
    print ans


if __name__ == '__main__':
    main()


Measured memory_bytes: 2932
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int x, y;

bool solve() {
    for (int i = 0; i <= x; i++) {
        if (2*i + 4*(x-i) == y)
            return true;
    }
    return false;
}

void input() {
    cin >> x >> y;
}

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

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


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int dp[100100],dp2[100100];
signed main(){
  string L;
  cin>>L;
  dp2[0]=1;
  for(int i=1;i<=L.size();i++){
    dp[i]=dp[i-1]*3,dp2[i]=dp2[i-1];
    if(L[i-1]=='1')dp[i]+=dp2[i],dp2[i]*=2;
    dp[i]%=mod,dp2[i]%=mod;
  }
  cout<<(dp[L.size()]+dp2[L.size()])%mod<<endl;
}

Measured memory_bytes: 5296
n,m=map(int,input().split())
coins=list(map(int,input().split()))

data=[0,1]
for i in range(2,n+1):
    mini=i
    for coin in coins:
        if i-coin>=0:
            if data[i-coin]<mini:
                mini=data[i-coin]
    data.append(mini+1)
print(data[n])


Measured memory_bytes: 7516
#include <stdio.h>

#define MAX 100000
#define NIL -1

typedef struct{
  int parent, left, right;
}node;

node Tree[MAX];
int Depth[MAX];

//出力関数
void print(int u){
  int i, j;
  printf("node %d: parent = %d, depth = %d, ",u ,Tree[u].parent, Depth[u]);

  if(Tree[u].parent == NIL) printf("root, ");
  else if(Tree[u].left == NIL) printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for(i = 0, j = Tree[u].left; j != NIL; i++, j = Tree[j].right){
    if(i) printf(", ");
    printf("%d",j);
  }
  printf("]\n");
}

//ノードの深さを求める関数
void calcDepth(int u, int p){
  Depth[u] = p;
  if(Tree[u].right != NIL) calcDepth(Tree[u].right, p);
  if(Tree[u].left != NIL) calcDepth(Tree[u].left, p+1);
}

int main(){
  int i, j, k, n;
  int id, sib, child;
  int root = NIL;

  scanf("%d",&n);

  for(i = 0; i < n; i++){
    Tree[i].parent = Tree[i].left = Tree[i].right = NIL;
  }

  for(i = 0; i < n; i++){
    scanf("%d %d",&id, &k);
    for(j = 0, sib = NIL; j < k; j++){
      scanf("%d", &child);
      Tree[child].parent = id;

      if(j == 0) Tree[id].left = child;
      else Tree[sib].right = child;
      sib = child;
    }
  }

  for(i = 0; i < n; i++){
    if(Tree[i].parent == -1) root = i;
  }

  calcDepth(root, 0);

  for(i = 0; i < n; i++) print(i);
  
  return 0;
}



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

class Dice{
public:
    int f[6];
    Dice(){}
    void z(){move(1,2,4,3);}
    void y(){move(0,2,5,3);}
    void x(){move(0,1,5,4);}
    void move(int i,int j,int k,int l){
        int t=f[i];f[i]=f[j];f[j]=f[k];f[k]=f[l];f[l]=t;
    }
};

bool eq(Dice a,Dice b){
    for(int i=0;i<6;i++)
        if(a.f[i]!=b.f[i])return false;
    return true;
}

bool same(Dice a,Dice b){
    for(int i=0;i<6;i++){
        for(int j=0;j<4;j++){
            if(eq(a,b))return true;
            a.z();
        }
        if(i%2==0)a.y();
        else a.x();
    }
    return false;
}

Dice D[100];int n;

bool check(){
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)if(same(D[i],D[j]))return false;
    return true;
}

int main(){
    cin>>n;
    for(int j=0;j<n;j++)
        for(int i=0;i<6;i++)cin>>D[j].f[i];
    
    if(check())cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    return 0;
}



Measured memory_bytes: 3100
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int MOD = 998244353;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> d(n);
  rep(i, n) cin >> d[i];
  vector<int> b(n);
  rep(i, n) b[d[i]]++;
  if (d[0] || b[0] != 1) {
    cout << 0 << endl;
    return 0;
  }
  int sum = 0;
  rep(i, n) {
    if (sum == n)
      break;
    if (!b[i]) {
      cout << 0 << endl;
      return 0;
    }
    sum += b[i];
  }
  ll ans = 1;
  sum = 1;
  for (int i = 1; i < n && sum < n; i++) {
    ll p = 1;
    rep(j, b[i])
      (p *= b[i-1]) %= MOD;
    (ans *= p) %= MOD;
    sum += b[i];
  }
  cout << ans << endl;
  return 0;
}

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

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mx2 102
#define mx3 1003
#define mx4 10004
#define mx5 100005
#define mx6 1000006
#define mod 1000000007
#define PI 3.14159265
#define fo(i,n) for(int i=0 ; i<n ; i++)
#define Fo(i,k,n) for(int i=k ; i<n ; i++)
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pair<int,int>,int> piii;

int n ,k, ans , sum , a , b ;
pii arr[mx5];
string str;
 
int main() {
	ios::sync_with_stdio(false);
	//int t;cin>>t;while(t--)
	{
		cin>>n;
		fo(i,n)
		{
			cin>>a;
			arr[i]={a,i};
		}
		sort(arr,arr+n);
		fo(i,n)
		{
			cout<<arr[i].se+1<<" ";
		}
	}
	return 0;
}


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

typedef long long ll;
const int N = 41, MAXM = (1 << 17) + 50, mod = (int)1e9 + 7;
int n,x,y,z;
int len;
int dp[N][MAXM];

bool is_haiku(int mask) {
    return (((mask >> (x + y + z - 1)) & (mask >> (y + z - 1)) & (mask >> (z - 1))) & 1) == 1;
}

int get_next(int mask, int x) {
    return ((mask << x)|(1 << (x - 1))) & ((1 << len) - 1);
}

void add(int &to, int x) {
    to += x;
    if(to >= mod) to -= mod;
}

int main() {
    cin >> n >> x >> y >> z;
    len = x + y + z;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 1 << len; j++) {
            if(is_haiku(j)) continue;
            for(int k = 1; k <= 10; k++) {
                add(dp[i][get_next(j, k)], dp[i-1][j]);
            }
        }
    }
    ll res = 1;
    for(int i = 0; i < n; i++) res *= 10, res %= mod;
    int f_res = 0;
    for(int i = 0; i < 1 << len; i++) if(!is_haiku(i)) add(f_res, dp[n][i]);
    cout << (res - f_res + mod) % mod << endl;
}

Measured memory_bytes: 20736
n = int(input())
d = {"AC":0, "WA":0, "TLE":0, "RE":0}
for i in range(n):
    s = input()
    d[s] += 1
print("AC x " + str(d["AC"]))
print("WA x " + str(d["WA"]))
print("TLE x " +str(d["TLE"]))
print("RE x " +str(d["RE"]))

Measured memory_bytes: 9156
#include <stdio.h>

int max(int a, int b)
{
   if(a>b) return a;
   else return b;
}

int main(void)
{
   int q1, b, c1, c2, q2;
   int qa;
   int hi, lo, ce;

   while(scanf("%d", &q1)){
      if(q1==0) break;
      scanf("%d %d %d %d", &b, &c1, &c2, &q2);

      qa=0;
      hi=q2;
      lo=1;
      //while(hi>=lo){
         ce=(hi+lo)/2;
	 if(c1*ce+c2*max(q1-ce, 0)<=b){
	    //lo=ce+1;
	    //qa=ce;
            for(qa=q2; qa>=ce; qa--){
               if(c1*qa+c2*max(q1-qa, 0)<=b) break;
            }
	 }
	 else {
	    //if(c1>=c2) hi=ce-1;
	    //else lo=ce+1;
            for(qa=q2; qa>0; qa--){
               if(c1*qa+c2*max(q1-qa, 0)<=b) break;
            }
	 }
      //}
      if(qa==0) printf("NA\n");
      else printf("%d %d\n", qa, (b-c1*qa)/c2);
   }
   return 0;
}

Measured memory_bytes: 612
import sys
input = sys.stdin.readline
from collections import deque
def r(a):
    for i in range(1, 10001):
        if i and a * i % mod <= 10000:
            return str(a*i%mod) + "/" + str(i)
        if i and -a * i % mod <= 10000:
            return str(-(-a*i%mod)) + "/" + str(i)
    return a
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
i0 = min([i for i in range(N) if len(X[i]) == 1])

P = [-1] * N
Q = deque([i0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

mod = 10 ** 9 + 7
inv2 = (mod + 1) // 2
A = [1] * N # これ以下の部分木に黒を含まない確率
B = [1] * N # これより上の部分木に黒を含まない確率
for i in R[::-1]:
    s = inv2
    for j in X[i]:
        s = (s * A[j]) % mod
    A[i] = s

for i in R[1:]:
    if P[i] == i0:
        B[i] = A[i0] * pow(A[i], mod-2, mod) % mod
    else:
        B[i] = B[P[i]] * A[P[i]] * pow(A[i], mod-2, mod) % mod
ans = 0
for i in range(N):
    s = B[i]
    t = 1 + (1-B[i]) * pow(B[i], mod-2, mod)
    for j in X[i]:
        s = (s * A[j]) % mod
        t = (t + (1-A[j]) * pow(A[j], mod-2, mod)) % mod
    ans = (ans + 1 - s * t) % mod
    
print(ans * inv2 % mod)

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

using namespace std;

int b,a[1000],n,k,cnt=1;
double ans;

int main () {
	cin >> n >> k;
	for(int i = k - n + 1; i < k; i++) {
		cout << i << " ";
	}
	for(int i = k; i < k + n; i++) {
		cout << i << " ";
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    static long[] fac = new long[1000003];
    static long[] finv = new long[1000003];
    static long[] inv = new long[1000003];
    static final int MOD = 998244353;
    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < 1000003; i++) {
            fac[i] = fac[i - 1] * i % MOD;
            inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
            finv[i] = finv[i - 1] * inv[i] % MOD;
        }
        long ans = 0;
        for (int i = 0 ; i <= k ; i++) {
            long c = comb(n - 1, i) % MOD;
            c %= MOD;
            c *= m;
            c %= MOD;
            c *= pow(m - 1, n - i - 1) % MOD;
            c %= MOD;
            ans += c % MOD;
        }
        System.out.println(ans % MOD);


    }

    static long comb(int n, int k) {
        if (n < k)
            return 0;
        if (n < 0 || k < 0)
            return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }

    static int pow (long b, int e) {
        long ans = 1;
        while (e > 0) {
            if (e % 2 == 1) {
                ans = ans * b % MOD;
            }
            e >>= 1;
            b = b * b % MOD;
        }
        return (int) ans;
    }

}

Measured memory_bytes: 75440
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
const int inf = 1001001001;
const int mod = 1000000007;

vector<int> to[100001];
int n;

vector<int> dist;

void dfs(int a, int d = 0, int p = -1) {
	dist[a] = d;
	for (auto& c : to[a]) {
		if (c == p) continue;
		dfs(c, d + 1, a);
	}
	return;
}

vector<int> calcdist(int a) {
	dist = vector<int>(n);
	dfs(a);
	return dist;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	int u, v;
	cin >> u >> v;
	u--; v--;
	rep(i, n - 1) {
		int a, b; cin >> a >> b;
		a--; b--;
		to[a].emplace_back(b);
		to[b].emplace_back(a);
	}

	vector<int> distT = calcdist(u);
	vector<int> distA = calcdist(v);

	int ans = 0;
	rep(i, n) {
		if (distT[i] < distA[i]) {
			ans = max(ans, distA[i]);
		}
	}

	dunk(ans - 1);

	return 0;
}

Measured memory_bytes: 10744
#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 << "Right" << endl;
  else
    cout << "Balanced" << endl;
}

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

intervals = list(tuple(map(int,input().split())) for _ in range(N))

L = sorted(((l,i) for i,(l,r) in enumerate(intervals)))
R = sorted(((r,i) for i,(l,r) in enumerate(intervals)), reverse=True)

def helper(L,R,turn):
  used = [False]*(N+1)
  used[N] = True

  x = 0
  cost = 0
  while True:
    A = [L,None,R][turn+1]

    i = N
    while used[i]:
      y,i = A.pop()

    if turn*(y-x) < 0:
      cost += abs(x-y)
      x = y
    else:
      break
    turn *= -1
  cost += abs(x)
  return cost

print(max(helper(L.copy(), R.copy(), t) for t in [-1,1]))

Measured memory_bytes: 40244
#include <stdio.h>

int main(){
	int hei[10],i,j,temp;

	for(i=0;i<10;i++){
		scanf("%d",&hei[i]);
	}
	for(i=0;i<10;i++){
		for(j=i+1;j<10;j++){
			if(hei[i]<hei[j]){
				temp=hei[i];
				hei[i]=hei[j];
				hei[j]=temp;
			}
		}
	}
	for(i=0;i<3;i++){
	printf("%d\n",hei[i]);
	}
return(0);

}

Measured memory_bytes: 600
// 提出時に消す


import java.util.Scanner;

// 提出時にMainに変更する
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();

        int ans = 0;
        int cnt = 0;
        while (cnt < k) {
            if (0 < a) {
                ans++;
                cnt++;
                a--;
                continue;
            }
            if (0 < b) {
                cnt++;
                b--;
                continue;
            }
            if (0 < c) {
                cnt++;
                ans--;
                continue;
            }
        }

        System.out.println(ans);
        sc.close();
    }
}

Measured memory_bytes: 36032
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#define INF 1e9
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int n;cin>>n;
  ll ans=1;
  for(int i=1;i<=n;i++)ans*=i;
  cout<<ans<<endl;
  return 0;
}


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

typedef long long ll;

const int Maxn = 200005;

int n, mod;
char str[Maxn];
ll res;
int pw[Maxn], inv[Maxn];
int has[Maxn];

int toPower(int a, int p)
{
    int res = 1;
    while (p) {
        if (p & 1) res = ll(res) * a % mod;
        p >>= 1; a = ll(a) * a % mod;
    }
    return res;
}

int Inv(int a) { return toPower(a, mod - 2); }

int main()
{
    scanf("%d %d", &n, &mod);
    scanf("%s", str + 1);
    if (mod == 2 || mod == 5) {
        for (int i = 1; i <= n; i++)
            if ((str[i] - '0') % mod == 0) res += i;
        cout << res << endl;
        return 0;
    }
    pw[0] = inv[0] = 1;
    int inv10 = Inv(10);
    for (int i = 1; i <= n; i++) {
        pw[i] = ll(pw[i - 1]) * 10 % mod;
        inv[i] = ll(inv[i - 1]) * inv10 % mod;
    }
    int cur = 0;
    has[cur]++;
    for (int i = 1; i <= n; i++) {
        cur = (10 * cur + int(str[i] - '0')) % mod;
        int x = ll(cur) * inv[i] % mod;
        res += has[x];
        has[x]++;
    }
    cout << res << endl;
    return 0;
}


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

int main() {
  ll Ans = 0;  // 回答：
  int N; cin >> N; // 品物数：１～１００
  int MW; cin >> MW;  // 積載可能重量：1～１０００００
  vector<int> W(N+1,0); // 重量配列：１番目の荷物持ち判断の際に、０番目を参照する。
  vector<int> V(N+1,0); // 価値配列：１番目の荷物持ち判断の際に、０番目を参照する。
  rep(i,N){
    cin >> W.at(i+1) >> V.at(i+1);
  }

  vector<vector<ll>> DP(N+1,vector<ll>(MW+1,0));  // N 番目での重量別最大価値
  rep1(i,N){ // i 番目の荷物を持つ／持たない
    rep1(j,MW){   // 各重量毎に持つ／持たないを判定する。
      if(j>=W.at(i)){
        DP.at(i).at(j) = max( DP.at(i-1).at(j) , DP.at(i-1).at(j-W.at(i)) + V.at(i) );
      } else {
        DP.at(i).at(j) = DP.at(i-1).at(j);
      }
    }
  }

  // rep1(i,N){ // i 番目の荷物を持つ／持たない
  //   rep1(j,MW){   // 各重量毎に持つ／持たないを判定する。
  //     cout << "i:" << i << " j:" << j << " DP:" << DP.at(i).at(j) << endl;
  //   }
  // }
  Ans = DP.at(N).at(MW);
  cout << Ans << endl;
}


Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef vector<int> vi;
typedef vector<pair<int,int> > vii;
#define pb push_back
#define INF 1e5
#define REP(i,a,b) for(int i=a;i<b;++i)
#define REPN(i,a,b) for(int i=a;i<=b;++i)

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);   
    
    string s;
    cin>>s;
    REP(i,0,s.size())
    {
    	cout<<"x";
	}
    cout<<"\n";
	return 0;
    
}

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

dist_list = []

for dj in make_divisors(N):
    if N % dj != 0:
        continue
    di = N / dj
    dist_list.append(
        [int(dj + di - 2), [di, dj]]
    )

dist_list.sort(key=lambda x: x[0])
print(dist_list[0][0])


Measured memory_bytes: 4960
#include <bits/stdc++.h>
#define PI M_PI
#define EPS 1e-14
using namespace std;
typedef complex<double> point;
namespace std {
  bool operator < (const point& a, const point& b){
    return fabs(real(a)-real(b)) <EPS  ? imag(a) < imag(b) : real(a) < real(b);
  }
  bool operator == (const point& a,const point& b){
    return abs(real(a)-real(b))<EPS&&abs(imag(a)-imag(b))<EPS;
  }
  bool operator != (const point& a,const point& b){
    return !(abs(real(a)-real(b))<EPS&&abs(imag(a)-imag(b))<EPS);
  }
  
}
int n;
double cross(point a,point b){return a.real()*b.imag()-a.imag()*b.real();}

point rot(point a,double rad){
  return a*conj(point(cos(rad),sin(rad)));
}

point crosspoint(point a,point b,point c,point d){
  a-=d;b-=d;c-=d;
  return d+a+(b-a)*imag(a/c)/imag(a/c-b/c);
}
double getArea3(point a,point b,point c){return abs(cross(b-a,c-a)/2);}

double solve(){
  vector <point> a;
  double base=2*PI/3;
  point A=point(0,1/sqrt(3));
  a.push_back(A);
  a.push_back(rot(A,base));  
  a.push_back(rot(A,base*2));

  double rad=2*PI/n;
  for(int i=1;i<=n;i++)
    for(int j=0;j<3;j++)a.push_back(rot(a[j],rad*i));
  sort(a.begin(),a.end());
  a.erase(unique(a.begin(),a.end()),a.end());
  
  double dis=1e9;
  point B;
  for(int i=0;i<a.size();i++)
    if(A!=a[i]&&real(a[i])>0&&abs(A-a[i])<dis)dis=abs(A-a[i]),B=a[i];
  point C=crosspoint(A,rot(A,base),B,rot(B,base*2));
  double s=getArea3(A,B,C);
  double S=(dis/2)*(dis/2)/tan(PI/a.size());
  return (S-s)*a.size();
}


int main(){
  while(cin>>n,n)printf("%.15f\n",solve());
  return 0;
}

Measured memory_bytes: 3672
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cmath>
#include <queue>

using namespace std;

long long int dist_origin[20], dist[20], laps[20];

long long int GCD(long long int a, long long int b){
	long long int dummy1, dummy2, dummy;
	dummy1 = max(a, b);
	dummy2 = min(a, b);
	while(true){
		dummy = dummy1 % dummy2;
		dummy1 = dummy2;
		dummy2 = dummy;
		if(dummy == 0){
			break;
		}
	}
	return dummy1;
}

int main(){
	
	int n;
	
	while(true){
		cin >> n;
		if(n == 0){
			break;
		}
		for(int i = 0; i < n; i++){
			cin >> dist_origin[i] >> laps[i];
			dist[i] = dist_origin[i];
		}
		for(int i = 0; i < n - 1; i++){
			long long int gcd = GCD(dist[i] * laps[i + 1], dist[i + 1] * laps[i]);
			long long int hoge = dist[i + 1];
			dist[i + 1] *= dist[i] * laps[i + 1] / gcd;
			for(int j = 0; j <= i; j++){
				dist[j] *= hoge * laps[i] / gcd;
			}
		}
		
		for(int i = 0; i < n; i++){
			long long int ans = dist[i] / dist_origin[i];
			cout << ans << endl;
		}
		
	}
	
	return 0;
}

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

#define MAXN 200010

int n,k,a[MAXN],b[MAXN];

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",a+i);
	for(int cnt=1;cnt<=k;++cnt)
	{
		for(int i=1;i<=n;++i)b[i]=0;
		for(int i=1;i<=n;++i)
		{
			int l=max(i-a[i],1),r=min(i+a[i],n);
			++b[l];
			--b[r+1];
		}
		long long sum=0;
		for(int i=1;i<=n;++i)sum+=(a[i]=a[i-1]+b[i]);
		if(sum==(long long)n*n)break;
	}
	for(int i=1;i<=n;++i)printf("%d ",a[i]);
}

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

char m[51][51];
int num[51][51] = {0};

int main() {
    int H, W;
    cin >> H >> W;
    for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
            cin >> m[y][x] ;
        }
    }
    for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
            for (int dy = -1; dy <= 1; dy++ ) {
                for (int dx = -1; dx <= 1; dx++) {
                    if (dx == 0 && dy == 0) continue;
                    int nx = x + dx, ny = y + dy;
                    if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                    if (m[ny][nx] == '#') num[y][x]++;
                }
            }
        }
    }
    for (int i = 0; i < H; i ++) {
        for (int j = 0; j < W; j++) {
            if (m[i][j] == '#') cout << '#';
            else cout << num[i][j] ;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
signed main(){
	int n,a,b;cin >> n >> a >> b;
	int h[n];
	rep(i,n)cin>> h[i];
	sort(h,h+n);
	reverse(h,h+n);
	auto ok = [&](int c){
		//c回でできるか
		int ret = 0;
		rep(i,n){
			int rest = max(0ll,h[i] - c*b);
			//-(a-b)する
			int shine = (rest + a-b - 1)/(a-b);
			ret += shine;

		}
		return ret <= c;
	};
	
	int bot = -1,top = 1e10;
	while(top - bot > 1){
		int mid = (top + bot)/2;
		if(ok(mid))top = mid;
		else bot = mid;
	}
	cout << top  << endl;
	return 0;
}


Measured memory_bytes: 4396
#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; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;



int main() {
    int MAX = 10e6;

    vector<int> dp(MAX+1, INF);
    vector<int> odd_dp(MAX+1, INF);

    dp[0] = 0;
    odd_dp[0] = 0;


    // FOR(i,0,10e6+1){
    //     cout << i << endl;
    //     FOR(j,1,1000){
    //         int num = j*(j+1)*(j+2)/6;
    //         if (i+num >= 10e6) break;
    //         dp[i+num] = min(dp[i+num], dp[i]+1);
    //         if(j%2 == 0){
    //             odd_dp[i+num] = min(odd_dp[i+num], odd_dp[i]+1);
    //         }
    //     }
    // }

    FOR(j,1,1000){
        int num = j*(j+1)*(j+2)/6;
        if (num > MAX) break;
        FOR(i,0,MAX+1){
            if (i+num > MAX) break;
            dp[i+num] = min(dp[i+num], dp[i]+1);
            if(num%2 == 1){
                odd_dp[i+num] = min(odd_dp[i+num], odd_dp[i]+1);
            }
        }
    }

    while(1){
        int N;
        cin >> N;
        if (N == 0) break;

        cout << dp[N] << " " << odd_dp[N] << endl;

    }
    return 0;
}

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

// const int MAX = 1000100;
// const int INF = 1<<29;

// int main() {
//     vector<int> dp(MAX, INF), odddp(MAX, INF);
//     dp[0] = odddp[0] = 0;
//     for (int i = 1;; ++i) {
//         int num = i * (i+1) * (i+2) / 6;
//         if (num >= MAX) break;
//         for (int j = num; j < MAX; ++j) {
//             dp[j] = min(dp[j], dp[j-num]+1);
//             if (num & 1) odddp[j] = min(odddp[j], odddp[j-num]+1);
//         }
//     }
//     int n;
//     while (cin >> n) {
//         if (n == 0) break;
//         cout << dp[n] << " " << odddp[n] << endl;
//     }
// }


Measured memory_bytes: 80788
N = int(input())
h = list(map(int,input().split()))
sum = []
sum.append(0)
for i in range(1,N):
    if i>1:
        sum.append(min(sum[i-1]+abs(h[i-1]-h[i]),sum[i-2]+abs(h[i-2]-h[i])))
    else:
        sum.append(sum[i-1]+abs(h[i-1]-h[i]))
print(sum[N-1])

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

int main(){
//DICE input
int d1,d2,d3,d4,d5,d6;
cin>>d1>>d2>>d3>>d4>>d5>>d6;
int m1=d1,m2=d2,m3=d3,m4=d4,m5=d5,m6=d6;
//END DICE input
char x;
while(1)
{

//memory replace
m1=d1;m2=d2;m3=d3;m4=d4;m5=d5;m6=d6;
//
if(cin>>x) 1; else break;
if(x=='N')
	{m1=d2;m2=d6;m6=d5;m5=d1;
	}
if(x=='S')
	{m1=d5;m5=d6;m6=d2;m2=d1;
	}
if(x=='W')
	{m3=d6;m6=d4;m4=d1;m1=d3;
	}
if(x=='E')
	{m6=d3;m3=d1;m1=d4;m4=d6;
	}
//DICE set now
d1=m1;d2=m2;d3=m3;d4=m4;d5=m5;d6=m6;
//END DICE set now
}
cout<<d1<<endl;
return 0;
}


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

int main(void){
    long long int n,y,b,i,j,k,v=0,d[100010],saisyou=10000,ans=0,t;
    cin >> n >> y;
    /*for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            for(k=0;k<=n;k++)
            {
                b=i+j+k;
                if(b==n && i*10000+j*5000+k*1000==y)
                {
                    cout << i << " " << j << " " << k << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1 -1 -1" << endl;*/
    v=1000*n;
    b=n;
    if(v==y)
    {
        cout << "0" << " " << "0" << " " << n << endl;
        return 0;
    }

        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                b=n-(i+j);
                t=i+j+b;
                if(v+9000*i+j*4000==y && n==t && b>=0)
                {
                    cout <<  i << " " <<  j << " "  << b << endl;
                    return 0;
                }
            }
        }
     
    cout << "-1" << " " << "-1" << " " << "-1" << endl; 

    return 0;

}


Measured memory_bytes: 3588
from scipy.sparse import *;N,M,*A=map(int,open(0).read().split());g=csr_matrix(([1]*M,(A[::2],A[1::2])),shape=(N+1,N+1)).tolil();c=0
for a,b in zip(*g.nonzero()):
 g[a,b]=0;n,_=csgraph.connected_components(g);c+=n!=2;g[a,b]=1
print(c)

Measured memory_bytes: 13768
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
ll fr[200005];
ll inv( ll d )
{
  // d^(MOD-1) == 1
  ll m = MOD - 2;
  ll ret = 1;
  while( m > 0 ){
    if( m & 1 ){
      ret = (ret * d) % MOD;
    }
    d = (d * d) % MOD;
    m >>= 1;
  }
  return ret;
}
ll comb( ll a, ll b )
{
  // nCb = (a+b)! / a!b!
  ll ret = fr[a+b];
  ret = (ret * inv(fr[a])) % MOD;
  ret = (ret * inv(fr[b])) % MOD;
  return ret;
}
int main()
{
  ll H, W, A, B;
  cin >> H >> W >> A >> B;
  ll ret = 0;
  fr[0] = 1;
  for( ll i=1; i<=200004; i++ ){
    fr[i] = (fr[i-1] * i) % MOD;
  }
  for( ll i=1; i<=H-A; i++ ){
    ret += comb(i-1, B-1) * comb(H-i, W-B-1);
    ret %= MOD;
  }
  cout << ret << endl;
}

Measured memory_bytes: 1792
h,w=map(int, input().split())
a=[input() for i in range(h)]

from collections import deque
b=[[0]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            b[i][j]=1
ans=-1
while len(q)>0:
    ans+=1
    q2=deque()
    for i,j in q:
        if j>0 and b[i][j-1]==0:
            q2.append((i,j-1))
            b[i][j-1]=1
        if j<w-1 and b[i][j+1]==0:
            q2.append((i,j+1))
            b[i][j+1]=1
        if i>0 and b[i-1][j]==0:
            q2.append((i-1,j))
            b[i-1][j]=1
        if i<h-1 and b[i+1][j]==0:
            q2.append((i+1,j))
            b[i+1][j]=1
    q=q2
print(ans)

Measured memory_bytes: 102364
#include <bits/stdc++.h>
#define off  exit( 0 )
#define cn   continue
#define rt   return
#define sc   scanf
#define pr   printf
#define pb   push_back
#define pf   push_front
#define p_f  pop_front
#define p_b  pop_back
#define ff   first
#define ss   second
#define ll   long long
#define ld   long double
#define N    100256
#define M    1000000007
#define I    1000000000000000000
#define pdd  pair < ld, ld >
#define pll  pair < ll, ll >
#define pii  pair < int, int >
#define sqr( a )           a * a
#define all( c )           c.begin(), c.end()
#define srt( c )           sort( all( c ) )
#define rev( c )           reverse( all( c ) )
#define srtr( c )          sort( c.rbegin(), c.rend() );
using namespace std;

ll n, m, k;
ll a, b, c;
ll ans, sum, cnt, cur;
string s, t;


void solve()
{
    cin >> s;
    if( s == "SUN" )
    {
        cout << 7;
        rt;
    }
    if( s == "MON" )
    {
        cout << 6;
        rt;
    }
    if( s == "TUE" )
    {
        cout << 5;
        rt;
    }
    if( s == "WED")
    {
        cout << 4;
        rt;
    }
    if( s == "THU" )
    {
        cout << 3;
        rt;
    }
    if( s == "FRI" )
    {
        cout << 2;
        rt;
    }
    if( s == "SAT" )
    {
        cout << 1;

    }
}
int main()
{
    ll tt = 1;
   // sc( "%d", &tt );
    for( ll i = 1; i <= tt; i ++ )
    {
        solve();
    }
}












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

struct UnionFindTree {
    vector<int> par, sz;
    int operator [](int x) { return find(x); }
    void build(int n) { par.assign(n, -1); sz.assign(n, 0); }
    int find(int x) { return par[x] < 0 ? x : (par[x] = find(par[x])); }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
    bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return 0;
        par[x] = min(par[x], par[y] - 1); sz[x] += sz[y]; par[y] = x; return 1;
    }
    bool uniteByRank(int x, int y) {
        if (par[find(x)] > par[find(y)]) swap(x, y);
        return unite(x, y);
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> com(q), x(q), y(q);
    for (int i = 0; i < q; ++i) cin >> com[i] >> x[i] >> y[i];

    UnionFindTree uf;
    uf.build(n);

    for (int i = 0; i < q; ++i) {
        if (com[i] == 0) uf.uniteByRank(x[i], y[i]);
        else cout << (int)uf.same(x[i], y[i]) << endl;
    }
}


Measured memory_bytes: 4164
#include <bits/stdc++.h>
using namespace std;
#define lld long long int
#define M 1000000007
#define fors(i,n) for(int i=0;i<n;++i)
#define fore(i,a,b) for(int i=a;i<=b;++i)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vv vector<int>
#define endl "\n"
#define test(i) cout<<i<<endl
#define itrt int t; cin>>t; fors(i,t)
#define itr1 int t; cin>>t;
#define ff first
#define ss second
#define pb push_back
#define vmp make_pair
#define ppb pop_back
#define sorta(a,n) sort(arr,arr+n)
#define sortv(x) sort(x.begin(),x.end())
void file(){
    #ifdef LOCAL
    freopen("demo.in","r",stdin);
    freopen("demo.out","w",stdout);
    #endif
}
int main(){
    fastio;
    file();
    int a,b;
    cin>>a>>b;
    if(a+b==4){
        cout<<"2"<<endl;
    }
    else if(a+b==5){
        cout<<"1"<<endl;
    }
    else{
        cout<<"3"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int) n; i++)
using ll = long long;
template <class T>
using vt = std::vector<T>;
using vvi = std::vector<vt<int>>;

int main(){
  std::string s;
  std::cin >> s;

  std::string key = "keyence";
  int cnt = 7;
  rep(i,s.size()) {
    if(s[i] == key[7-cnt])  cnt--;
    else{
      for(int j = s.size()-cnt; j < s.size(); j++){
        if(s[j] != key[7-cnt]){
          std::cout << "NO" << '\n';
          return 0;
        }
        else{
          cnt--;
          if(cnt == 0)
            break;
        }
      }
    }
    if(cnt == 0)
      break;
  }

  std::cout << "YES" << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;

typedef pair<int,string> pis;
#define fi first
#define se second

vector<pis> solve(vector<int> nums) {
	vector<pis> res;
	if(nums.size() == 1) {
		string s;
		stringstream sstr;
		sstr << nums[0];
		sstr >> s;
		res.push_back(pis(nums[0],s));
		return res;
	}
	for(int i = 1; i < nums.size(); i++) {
		vector<int> a(nums.begin(), nums.begin()+i);
		vector<int> b(nums.begin()+i, nums.end());
		vector<pis> aa, bb;
		aa = solve(a);
		bb = solve(b);
		for(int i = 0; i < aa.size(); i++) {
			for(int j = 0; j < bb.size(); j++) {
				res.push_back(pis(aa[i].fi + bb[j].fi, "(" + aa[i].se + "+" + bb[j].se + ")"));
				res.push_back(pis(aa[i].fi - bb[j].fi, "(" + aa[i].se + "-" + bb[j].se + ")"));
				res.push_back(pis(aa[i].fi * bb[j].fi, "(" + aa[i].se + "*" + bb[j].se + ")"));
			}
		}
	}
	return res;
}

int main() {
	while(1) {
		vector<int> a;
		a.resize(4);
		bool brk = true;
		for(int i = 0; i < 4; i++) {
			cin >> a[i];
			if(a[i] != 0) brk = false;
		}
		if(brk) break;

		sort(a.begin(), a.end());
		string res = "0";
		do {
			vector<pis> tmp;
			tmp = solve(a);
			for(int i = 0; i < tmp.size(); i++) {
				if(tmp[i].fi == 10)
					res = tmp[i].se;
			}
		} while(next_permutation(a.begin(), a.end()));
		cout << res << endl;
	}
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll n;
int main() {
    cin >> n;
    vector<ll> s(n);
    ll ans = 0, cnt = 0;
    REP(i,n){
        cin >> s[i];
    }
    sort(ALL(s));
    reverse(ALL(s));
    REP(i, n){
        if(i == 0){
            ans += s[i];
            cnt++;
        }
        else if(cnt <= n - 3){
            ans += s[i] * 2;
            cnt += 2;
        }
        else if(cnt <= n - 2){
            ans += s[i];
            cnt += 1;
        }
    }
     cout << ans << endl;
}


Measured memory_bytes: 4836
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

S = s()
n = len(S)
a = S[:n//2]
b = S[n//2+1:]
print("Yes" if a == a[::-1] == b == b[::-1] else "No")


Measured memory_bytes: 9964
import Data.Maybe
import Control.Monad
import qualified Data.ByteString.Char8 as C

readInteger = fst.fromJust.C.readInteger
readLnInteger = map readInteger.C.words<$>C.getLine
readCsInteger n = concat<$>replicateM n readLnInteger

x ? (a,b) = if x then a else b
a~>(f,x) = [a] ++ (null x)?([],f x)
half = flip div 2
aliq = ((0==).).mod

main = do
  [n] <- readLnInteger
  print $ solve n

solve n = calc n [n,n,n] 0

calc n [0,0,0] t = t
calc n [a,b,c] t = calc n list t' where
  list = [mec [a,b,c] [a,a,a-1],mec [a,b,c] [b,b-1,n],mec [a,b,c] [c-1,n,n]]
  t' = t + (foldr1 gcd [a,b,c])

mec [a,b,c][d,e,f]
 | c/=1 = d
 | b/=1 = e
 | a/=1 = f
 | otherwise = 0


Measured memory_bytes: 4888
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define MAX_C 1000000001

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  vector<int> q(n);
  for (int i = 0; i < n; i++) cin >> p[i];
  for (int i = 0; i < n; i++) cin >> q[i];

  vector<int> nums(n);
  for (int i = 0; i < n; i++) nums[i] = i+1;

  bool flag_p = false, flag_q = false;
  int pi = 0, qi = 0, index = 0;
  do {
    int i, j;
    if (!flag_p) {
      for (i = 0; i < n; i++) {
        if (p[i] != nums[i]) break;
      }
      if (i == n) {
        pi = index;
        flag_p = true;
      }
    }

    if (!flag_q) {
      for (j = 0; j < n; j++) {
        if (q[j] != nums[j]) break;
      }
      if (j == n) {
        qi = index;
        flag_q = true;
      }
    }
    
    index++;
  } while (next_permutation(nums.begin(), nums.end()));

  cout << abs(pi - qi) << endl;
}


Measured memory_bytes: 256
import java.io.PrintWriter
import java.util.*

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val (N, Q) = nextIntList()
    val G = Graph(N)
    repeat(N - 1) {
        val (a, b) = nextIntList()
        G.addEdge(a, b)
        G.addEdge(b, a)
    }
    repeat(Q) {
        val (p, x) = nextIntList()
        G.addScore(p, x.toLong())
    }
    G.spreadScore(1)
    println(G.scores.drop(1).joinToString(" "))
}

class Graph(v: Int) {
    private val vec = Array(v + 1) { mutableListOf<Int>() }
    val scores = Array(v + 1) { 0L }

    fun addEdge(a: Int, b: Int) {
        vec[a].add(b)
    }

    fun addScore(p: Int, x: Long) {
        scores[p] += x
    }

    fun spreadScore(start: Int) {
        val que = ArrayDeque<Int>()
        que.addLast(start)
        val visited = BooleanArray(vec.size) { false }
        while (que.size > 0) {
            val current = que.removeFirst()
            if (visited[current]) continue
            for (next in vec[current]) {
                if (!visited[next]) addScore(next, scores[current])
                que.addLast(next)
            }
            visited[current] = true
        }
    }
}

Measured memory_bytes: 155960
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long
#define vint vector<int>
#define pint pair<int, int>
#define pb(a) push_back(a)
#define all(v) v.begin(), v.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl

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

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

	string S, T;
	cin >> S >> T;

	cout << T << S << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    char C[2][3];
    int i;
    
    scanf("%s", C[0]);
    scanf("%s", C[1]);
    
    for(i=0; i<3; i++){
        if(C[0][i] != C[1][2-i]){
            break;
        }
        if(i==2){
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}

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

int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
inline int read()
{
	int x=0,y=1;char ch=getchar();
	while (ch>'9'||ch<'0'){
		if (ch=='-')y=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*y;
}

int main()
{
	printf("%d",a[read()-1]);
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int n,k;
int main(){
	scanf("%d",&k);
	if (k==1){
		puts("1\n1");
		return 0;
	}
	n=(k+3)/4*2; printf("%d\n",n);
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++)
			if (i&1) printf("%d ",(i+j)%n+n<k?(i+j)%n+n+1:(i+j)%n+1);
			else printf("%d ",(i+j)%n+1);
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 1152
#include<stdio.h>
int min2(int a, int b){return a>b?b:a;}
int n, i;
int a, b, min;
long sum;
char is;
int main(void){
  min = 1000000000;
  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf("%d%d", &a, &b);
    sum += a;
    if(a>b){min=min2(min, b);}
    if(a!=b){is=1;}
  }
  if(is){
    printf("%ld\n", sum-min);
  }else{
    puts("0");
  }
}


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

int main() {
	int n,m,u,v,ans=0;
	cin>>n>>m;
	int ht[n+1];
	for(int i=1;i<=n;i++)
		cin>>ht[i];
	vector<int>g(n+1,0);
	while(m--){
		cin>>u>>v;
		g[u]=max(g[u],ht[v]);
		g[v]=max(g[v],ht[u]);
	}
	for(int i=1;i<=n;i++){
		if(ht[i]>g[i])
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4048
#include<stdio.h>
int a[1000000];
int main()
{
	int n,min,mint=0,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&a[i]);
	for(i=0;i<n;i++)
	{
		if(i==0)
		{
			min=a[i];
			mint++;
		}
		else
		{
			if(a[i]<=min)
			{
				min=a[i];
				mint++;
			}
		}
	}
	printf("%d",mint);
}

Measured memory_bytes: 896