akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n;
string str;
int ans;
int size[50];

int check_tanka(int num,int count,int i,int *size){
    //cout << num <<endl;
    if(num ==0||num ==2){
        if(count+size[i]<5){
            return check_tanka(num,count+size[i],i+1,size);
        }else if(count+size[i]==5){
            return check_tanka(num+1,0,i+1,size);
        }else if(count+size[i]>5){
            return -1;
        }
    }else if(num==1||num == 3){
        if(count+size[i]<7){
            return check_tanka(num,count+size[i],i+1,size);
        }else if(count+size[i]==7){
            return check_tanka(num+1,0,i+1,size);
        }else if(count+size[i]>7){
            return -1;
        }

    }else if(num == 4){
        if(count+size[i]<7){
             return check_tanka(num,count+size[i],i+1,size);
        }else if(count+size[i]==7){
            return 0;
        }else if(count+size[i]>7){
            return -1;
        }
    }
    return -1;
}

int main(){
    while(1){
        cin >>n;
        if(!n)break;
        for(int i=0;i<50;i++){
            size[i] = 0;
        }
        for(int i=0;i<n;i++){
            cin >> str;
            size[i] = str.size();
        }
        for(int i = 0;i<n;i++){
            ans = check_tanka(0,0,i,size);
            if (ans!=-1){
                ans = i+1;
                break;
            }
        }
        cout << ans<<endl;
    }
   
}


Measured memory_bytes: 3152
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
ll n;
signed main(){
  init_io();
  cin >> n;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      ll dist = abs(i-j);
      for(int k=0;;k++){
        if(dist&(1ll<<k)){
          cout << k+1 << " ";
          break;
        }
      }
    }
    cout << endl;
  }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    PRINT((k/2)*(k/2+k%2));
}


Measured memory_bytes: 384
#include<stdio.h>

static const int A = 100;

int main(){
  int h, k, i, j, a, B[A + 1], C[A + 1][A + 1];
  scanf("%d",&a);
  for(i = 1; i <= a; i++){
    scanf("%d%d",&B[i - 1],&B[i]);
  }

  for(i = 1; i <= a; i++)C[i][i] = 0;
  for(j = 2; j <= a; j++){
    for(i = 1; i <= a - j + 1; i++){
      k = i + j - 1;
      C[i][k] = (1 << 21);
      for(h = i; h <= k - 1; h++){
	if(C[i][k] > C[i][h] + C[h + 1][k] + B[i - 1] * B[h] * B[k])
	  C[i][k] = C[i][h] + C[h + 1][k] + B[i - 1] * B[h] * B[k] ;
      }
    }
  }
  printf("%d\n",C[1][a]);

  return 0;
}



Measured memory_bytes: 2044
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

const int MOD = 1000000007;

int ans = 100000000;

int main(){
    int N; cin >> N;
    vector<pair<int, int>> ab, cd;
    rep(i,N){
        int a, b; cin >> a >> b;
        ab.emplace_back(a,b);
    }
    rep(i,N){
        int c, d; cin >> c >> d;
        cd.emplace_back(c,d);
    }

    sort(ab.begin(), ab.end());
    sort(cd.begin(), cd.end());

    vector<bool> ab_used(N, false);
    int ans = 0;
    rep(i,N){
        int used_index = -1;
        int prev_y2 = -1;
        int x = cd[i].first;
        int y = cd[i].second;
        rep(j,N){
            if (ab_used[j]) continue;
            int x2 = ab[j].first;
            int y2 = ab[j].second;
            
            if (x > x2 && y > y2){
                if (prev_y2 < y2){
                    prev_y2 = y2;
                    used_index = j;
                }
            }
        }
        if (used_index != -1) {
            ab_used[used_index] = true;
            ans++;
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;

int main()
{
    int n;
    cin>>n;
    vector<string>s(n);
    vector<int>t(n);
    vector<int>ruiseki(n);
    int sum=0;
    rep(i,n){
        cin>>s[i]>>t[i];
        sum+=t[i];
        ruiseki[i]=sum;
    }
    string x;
    cin>>x;
    int until=0;
    rep(i,n){
        if(s[i]==x){
            until=ruiseki[i];

        }
    }
    cout<<ruiseki[n-1]-until<<endl;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

for x in range(H):
    for y in range(W):
        if S[x][y] == ".":
            tmp = 0
            if x > 0 and S[x - 1][y] == "#":
                tmp = tmp + 1
            if x < H - 1 and S[x + 1][y] == "#":
                tmp = tmp + 1
            if y > 0 and S[x][y - 1] == "#":
                tmp = tmp + 1
            if y < W - 1 and S[x][y + 1] == "#":
                tmp = tmp + 1
            if x > 0 and y > 0 and S[x - 1][y - 1] == "#":
                tmp = tmp + 1
            if x > 0 and y < W - 1 and S[x - 1][y + 1] == "#":
                tmp = tmp + 1
            if x < H - 1 and y > 0 and S[x + 1][y - 1] == "#":
                tmp = tmp + 1
            if x < H - 1 and y < W - 1 and S[x + 1][y + 1] == "#":
                tmp = tmp + 1
            S[x][y] = str(tmp)

for i in S:
    print("".join(i))

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

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

/* 文字から数値に変換 */
int getChar(char ch)
{
    if (ch == 'A')
        return (1);
    else if (ch == 'C')
        return (2);
    else if (ch == 'G')
        return (3);
    else
        return (0);
}

/* 文字列から数値へ変換して keyを生成する */
long long getKey(char str[])
{
    long long sum = 0;
    long long p = 1;
    long long i;
    for (i = 0; i < strlen(str); i++) {
        sum += p*(getChar(str[i]));
        p *= 5;
    }
    return (sum);
}

int h1(int key) { return (key % M); }
int h2(int key) { return (1 + (key % (M - 1))); }

int find(char str[])
{
    long long key;
    long long i;
    long long h;

    key = getKey(str);  /* 文字列を数値に変換 */
    for (i = 0; ; i++) {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0)
            return (1);
        else if (strlen(H[h]) == 0)
            return (0);
    }
    return (0);
}

int insert(char str[])
{
    long long key;
    long long i;
    long long h;

    key = getKey(str);
    for (i = 0; ; i++) {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0) {
            return (1);
        }
        else if (strlen(H[h]) == 0) {
            strcpy(H[h], str);
            return (0);
        }
    }
    return (0);
}

int init()
{
    int i;
    for (i = 0; i < M; i++)
        H[i][0] = '\0';
}

int main()
{
    int i, n, h;
    char str[L], com[9];

    init();
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%s %s", com, str);

        if (strcmp(com, "insert") == 0) {
            insert(str);
        }
        else {
            if (find(str)) {
                puts("yes");
            }
            else {
                puts("no");
            }
        }
    }
    return (0);
}



Measured memory_bytes: 16092
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+11,INF=~0u>>2;
char s[N];
int k;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
int main(){
//	freopen("ex.in","r",stdin);
	scanf("%s",s);k=read();
	for(int i=0;s[i];++i){
		if(s[i]=='a') continue;
		int t='z'+1-s[i];
		if(k>=t){
			k-=t;
			s[i]='a';
		}
	}
	int len=strlen(s);
	while(k--){
		s[len-1]++;
		if(s[len-1]>'z') s[len-1]='a';
	}
	printf("%s",s);
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cstring>
#define N 200005
struct edge {
    int next, link, len;
} e[N * 2];
int n, tot, head[N], color[N], dis[N];
int u, v, w;
void add(int u,int v,int w) {
    e[++tot].link = v;
    e[tot].next = head[u];
    e[tot].len = w;
    head[u] = tot;
}

void DFS(int k) {
    for (int i = head[k]; i; i = e[i].next) 
        if (e[i].link != 0 && color[e[i].link] == -1) {
            dis[e[i].link] = (dis[k] + e[i].len) % 2;
            color[e[i].link] = dis[e[i].link] % 2;
            DFS(e[i].link);
        }
}

int main() {
    scanf("%d",& n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d",& u,& v,& w);
        add(u, v, w % 2);
        add(v, u, w % 2);
        
    }
    for (int i = 1; i <= n; i++) color[i] = -1;
    color[1] = 0;
    DFS(1);
    for (int i = 1; i <= n; i++) printf("%d\n", color[i]);
    return 0;
}

Measured memory_bytes: 7168
s = input()
n = len(s)
dp = [0]*(n+1) 
dp[0] = 0
for i in range(n):
    for j in range(i+1):
        dp[i+1] += dp[i-j] + int(s[i-j:i]+s[i])*(2**(i-j-1 if i-j-1 >= 0 else 0) )
print(dp[n])

Measured memory_bytes: 3060
package main

import (
	"fmt"
)

func main() {
  var n, m, p, x, sum, tmp int
  var t []int
  
  fmt.Scanf("%d", &n)
  for i := 0; i< n; i++ {
  	fmt.Scanf("%d", &tmp)
    t = append(t, tmp)
    sum += tmp
  }
  
  fmt.Scanf("%d", &m)
  for i := 0; i< m; i++ {
  	fmt.Scanf("%d %d", &p, &x)
    
    ans := sum - t[p-1] + x
	fmt.Printf("%d\n", ans)
  }
}

Measured memory_bytes: 1852
#include <iostream>
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
 
int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}
 
int main() {
  int n;
  cin>>n;
  vector<int> a(n);
  rep(i,n) cin>>a[i];
  vector<int> l(n), r(n);
  rep(i,n-1) l[i+1] = gcd(l[i], a[i]);
  for (int i = n-1; i >= 1; --i) r[i-1] = gcd(r[i], a[i]);
  int ans = 1;
  rep(i,n) ans = max(ans, gcd(l[i],r[i]));
  cout<<ans<<endl;
  return 0;
}

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

// int gcd(int x, int y) {
//     if (y == 0) return x;
//     return gcd(y, x%y);
// }
 
// int main() {
//     int n;
//     cin >> n;
//     vector<int> a(n);
//     rep(i,n) cin >> a[i];

// }

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int> > vvi;

int n,m,x;
int u,v;
int grp;

pll a[100005];
vvi f(100005);
int visited[100005];
int taken[100005];
pll mn;


void dfs(int u)
{
    visited[u] = 1;
    if(a[u].first<mn.first) mn.second = u, mn.first = a[u].first;
    for(int i=0;i<f[u].size();++i)
    {
        if(!visited[f[u][i]]) dfs(f[u][i]);
    }
}


int main()
{
    cin >> n >> m;

    for(int i=0;i<n;++i) cin >> x, a[i].first = x,a[i].second = i;

    if(m==n-1) {cout << 0;return 0;}

    int cnt = n-m;
    int edges = n - m - 1;

    if(n < 2*edges) {cout << "Impossible";return 0;}

    for(int i=0;i<m;++i)
    {
        cin >> u >> v;
        f[u].push_back(v);
        f[v].push_back(u);
    }


    ll res(0);
    for(int i=0;i<n;++i)
    {
        if(!visited[i])
        {
            mn.first = 10000000000;
            dfs(i);
            res += mn.first;
            taken[mn.second]=1;
            ++grp;
        }
    }
    sort(a,a+n);
    cnt = 2*edges - cnt;
    for(int i=0;i<n;++i)
    {
        if(!cnt) break;
        if(!taken[a[i].second])
        {
            res += a[i].first;
            --cnt;
            taken[a[i].second]=1;
        }
    }
    if(cnt) cout << "Impossible";
    else cout << res;

}






Measured memory_bytes: 8064
n = int(input())
s=str(n)

if len(s)==1:
	print(n)
if len(s)==2:
	print(9)
if len(s)==3:
	print(9+n-99)
if len(s)==4:
	print(909)
if len(s)==5:
	print(909+n-9999)
if len(s)==6:
	print(90909)

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

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

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

using namespace std;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, a;
	while (1) {
		cin >> n >> m >> a;
		if (!n) break;
		vector<int> v(n);
		vector<pair<int, pair<int, int> > > s(m);
		REP(i, n) {
			v[i] = i;
		}
		REP(i, m) {
			int h, p, q;
			cin >> h >> p >> q;
			s[i] = { h,{p,q} };
		}
		sort(ALL(s), greater<>());
		REP(i, m) {
			swap(v[s[i].second.first - 1], v[s[i].second.second - 1]);
		}
		cout <<find(ALL(v),a-1)-v.begin()+1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using mii = map<int, int>;
const int INF = 1e9;
const ll LINF = 1e18;
#define MP(a,b) make_pair((a),(b))
#define MT(...) make_tuple(__VA_ARGS__)

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

#define ALL(x) (x).begin(),(x).end()
#define IN(type,a) type a;cin >> a
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define COUT(x) cout << (x) << endl
#define DCOUT(x,n) cout << fixed << setprecision(n) << (x) << endl
int gcd(int x, int y){
    if ((x==1)||(y==1)) {
        return 1;
    }
    if (x>y) {
        if (x%y==0) {
            return y;
        }else{
            return gcd(y, x%y);
        }
    }else{
        if (y%x==0) {
            return x;
        }else{
            return gcd(x, y%x);
        }
    }
}
int main() {
    IN(double, a);
    DCOUT(2*a*3.14159, 15);
}




Measured memory_bytes: 3812
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Object o = run();
        if (o != null)
            System.out.println(o);
    }

    static Object run() {
        try (Scanner sc = new Scanner(System.in)) {
            long resultNum = 0;
            String resultStr = "";

            String s = sc.next();
            return s.substring(0, 3);
        }
    }
}

class ChenNumberUtil {
    static Collection<Integer> getDivisors(int n) {
        ArrayList<Integer> al = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                al.add(i);
                if (n / i != i)
                    al.add(n / i);
            }
        }
        Collections.sort(al);
        return al;
    }
}

class ChenBitUtil {
    static int popCount(int bit) {
        return Integer.bitCount(bit);
    }

    static boolean isFlag(int bit, int i) {
        return 0 != (bit & (1 << i));
    }

    static int setTrue(int bit, int i) {
        return bit |= (1 << i);
    }

    static int setFalse(int bit, int i) {
        return bit &= ~(1 << i);
    }

    static int setReverse(int bit, int i) {
        return isFlag(bit, i) ? setFalse(bit, i) : setTrue(bit, i);
    }

    static int reverseAll(int bit) {
        return ~bit;
    }
}

Measured memory_bytes: 27004
import math
import statistics

n = int(input())

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

my_mean = sum(li) / len(li)
ll = math.floor(my_mean)
lll = math.ceil(my_mean)

c = 0
for i in range(len(li)):
  c += (li[i] - ll)**2
  
cc = 0
for i in range(len(li)):
  cc += (li[i] - lll)**2
  
  
if c < cc:
  print(c)
else:
  print(cc)

#20

Measured memory_bytes: 5212
# エラトステネスの篩
def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def f(X):
    t = []
    a = X
    while a != 1:
        if len(t) != 0 and t[-1][0] == prime_table[a]:
            t[-1][1] += 1
        else:
            t.append([prime_table[a], 1])
        a //= prime_table[a]
    result = 1
    for _, n in t:
        result *= n + 1
    return result


N = int(input())

prime_table = make_prime_table(N)
result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)


Measured memory_bytes: 153332
#include<bits/stdc++.h>
#include<stdio.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
typedef pair<int , int > pii;
#define MOD 1000000007
#define MOD1 998244353
#define ff first
#define ss second
#define bn cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define sz(a) (a).size()
#define o(a) cout << a
#define MAX6 1000006
#define int ll
#define all(x) x.begin(), x.end()
#define ppii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define viii vector<ppii>
#define vs vector<string>
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define MAX5 300005
#define MAX7 10000007
#define rep(i,a,b)  for (__typeof((b)) i=(a);i<=(b);i++)
#define nrep(i,b,a)  for (__typeof((b)) i=(b);i>=(a);i--)
#define mem(a) memset(a,0,sizeof(a))
#define memneg(a) memset(a,-1,sizeof(a))
//#define se second
#define LN 14
#define LIM 22
#define MAX_ALPHA 26
const long long INF64 = 1e18;
const ll INF = 1e9;
const double PI = acos(-1);
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
inline void max_self(ll &a, ll b)
{
  a = max(a,b);
}
 
inline void min_self(ll &a,ll b)
{
  a = min(a,b);
}
 
inline void add_self(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
 
inline void sub_self(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}
 
inline int mul(int a, int b) {
  return (int) ((long long) a * b % MOD);
}
 
 
ll gcd(ll a,ll b)
{
  if(b == 0)
    return a;
  else 
    return gcd(b, a%b);
}
 
 
int countDigits(int x)
{
  int cnt = 0;
  while(x)
  {
    x /= 10;
    cnt++;
  }
  return cnt;
}
 
 
ll binExpo(ll a,ll b)
{
  ll res = 1;
  while(b)
  {
    if(b&1)
      res = (res * a)%MOD;
    a = (a * a)%MOD;
    b /= 2;
  }
  return res%MOD;
}
 
int sum(int a) {
    int result = 0;
    while (a > 0) {
        result += a % 10;
        a /= 10;
    }
    return result;
}


void solve(){
  int n;
  cin>>n;
  vector<vector<int > > can(n + 1, vector<int > (n + 1));
  rep(i, 0, n-1)
  {
    rep(j, 0, n-1)
    {
      cin>>can[i][j];
    }
  }

  vector<int > dp(1 << n);

  dp[0] = 1;

  for(int mask = 0;mask < (1 << n) - 1;mask++)
  {
    int a = __builtin_popcount(mask);
    for(int b = 0;b < n;b++)
    {
      if(!(mask & (1 << b)) and can[a][b])
      {
        int m2 = mask ^ ( 1 << b );
        add_self(dp[m2], dp[mask]);
      }
    }
  }
  cout<<dp[(1 << n) - 1]<<endl;
}


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

  int t = 1;
  //cin>>t;
  while(t--) solve();
  return 0;
}















Measured memory_bytes: 16640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1001001001;
const int MOD = 1000000007;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...)
#define print(...)
#endif

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

    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> s(n+1);
    rep(i, n) s[i+1] = s[i]+a[i];
    debug(s);
    map<ll, int> mp;
    rep(i, n+1) mp[s[i]]++;
    ll ans = 0;
    for(const auto& m: mp) {
        if (m.se>1) {
            ans += m.se*(m.se-1ll)/2ll;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 15104
n,m = map(int,input().split())
a = [input().split() for i in range(n)]
b = [input().split() for i in range(m)]

for i in range(n):
    distance = 10000000000
    for j in range(m):
        temp = abs(int(a[i][0]) - int(b[j][0])) + abs(int(a[i][1]) - int(b[j][1]))
        if distance > temp:
            ans = j + 1
        distance = min(temp,distance)
    print(ans)

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

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

	sort(v.rbegin(), v.rend());

	long long ans = (n > 1) ? v[0] : 0;
	for(int i = 2, k = 1; i < n; i++)
	{
		ans += v[k];
		
		if(i % 2)
			k++;
	}

	cout << ans;

	return 0;
}


Measured memory_bytes: 4024
mai, target = map(int, input().split(" "))
ans = 0
for i in range(mai + 1):
    for j in range(mai + 1 - i):
        k = mai - i - j
        if 1000 * i + 5000 * j + 10000 * k == target:
            print(k, j, i)
            ans = 1
            break
    if ans:
        break
else:
    print(-1, -1, -1)

Measured memory_bytes: 40684
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
using namespace std;
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007


int main(int argc, char const *argv[]) {
  int n,L[100];
  std::cin >> n;
  for(int i=0; i<n; i++)std::cin >> L[i];
  sort(L,L+n);
  int sum=0;
  for(int i=0; i<n-1; i++)sum+=L[i];

  if(sum>L[n-1])std::cout << "Yes" << '\n';
  else std::cout << "No" << '\n';
  return 0;
}


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

int main(){
  long long A,B; cin >> A >> B;
  
  priority_queue<long long> Ad,Bd;
  for(long long i=1; i<=sqrt(A); i++){
    if(A%i==0){
      Ad.push(i);
      if(i!=A/i) Ad.push(A/i);
    }
  }
  for(long long i=1; i<=sqrt(B); i++){
    if(B%i==0){
      Bd.push(i);
      if(i!=B/i) Bd.push(B/i);
    }
  }
  
  priority_queue<long long> Cd;
  while((!Ad.empty())&&(!Bd.empty())){
    if(Ad.top()==Bd.top()){
      Cd.push(Ad.top());
      Ad.pop();
      Bd.pop();
    }else if(Ad.top()<Bd.top()){
      Bd.pop();
    }else{
      Ad.pop();
    }
  }
  
  long long count=0;
  while(!Cd.empty()){
    long long d=Cd.top();
    bool f=true;
    for(long long j=2; j<=sqrt(d); j++){
      if(d%j==0){
        f=false;
        break;
      }
    }
    count+=(f?1:0);
    Cd.pop();
  }
  cout << count << endl;
}

Measured memory_bytes: 512
#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty ;; $n:expr) => {
        (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! get_char {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().chars().collect::<Vec<_>>()
        }
    };
}

fn main() {
    let (d, g) = get!(usize, i64);
    let pc_arr = get!(i64, i64; d);

    let pc_arr = pc_arr
        .into_iter()
        .enumerate()
        .map(|(i, (num, bonus))| ((i as i64 + 1) * 100, num, bonus))
        .rev()
        .collect::<Vec<_>>();

    let mut ans = i64::max_value();
    'outer: for bit in 0..(1 << d) {
        let mut total = 0;
        let mut count = 0;
        for (i, (point, num, bonus)) in pc_arr.clone().into_iter().enumerate() {
            if bit & (1 << i) != 0 {
                total += point * num + bonus;
                count += num;
            }
        }

        if total < g {
            let remain = g - total;
            for (i, (point, num, _)) in pc_arr.clone().into_iter().enumerate() {
                if bit & (1 << i) == 0 {
                    let n = (remain + point - 1) / point;
                    if n <= num {
                        count += n;
                        break;
                    } else {
                        continue 'outer;
                    }
                }
            }
        }
        ans = std::cmp::min(ans, count);
        continue;

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


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

#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(v) reverse((v).begin(),(v).end())
#define ANS(ans) cout<<(ans)<<endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  for (int i = 0; i < (n); ++i)

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

  int i =0;

  while (true)
  {
    if(pow(k,i-1)<= n && n<pow(k,i)){
      ANS(i);
      break;
    }
    else{
      i++;
    }
  }
  
  return 0;
}


Measured memory_bytes: 256
N=gets.to_i
s=gets.chomp

['SS','SW','WW','WS'].each do |c|
  ret = c.dup
  i = 2
  while i < N
    if (s[i-1]=='o' && ret[-1]=='S') || (s[i-1]=='x' && ret[-1]=='W')
      ret << (ret[-2] == 'S' ? 'S' : 'W')
    else
      ret << (ret[-2] == 'S' ? 'W' : 'S')
    end
    i += 1
  end
  if [
    s[-1]=='o'&&ret[-1]=='S' && ret[-2] == ret[0],
    s[-1]=='x'&&ret[-1]=='S' && ret[-2] != ret[0],
    s[-1]=='o'&&ret[-1]=='W' && ret[-2] != ret[0],
    s[-1]=='x'&&ret[-1]=='W' && ret[-2] == ret[0],
  ].any? && [
    s[0]=='o'&&ret[0]=='S' && ret[-1] == ret[1],
    s[0]=='x'&&ret[0]=='S' && ret[-1] != ret[1],
    s[0]=='o'&&ret[0]=='W' && ret[-1] != ret[1],
    s[0]=='x'&&ret[0]=='W' && ret[-1] == ret[1],
  ].any?
    puts ret
    exit 0
  end
end

puts -1


Measured memory_bytes: 2556
#include<map>
#include<string>
#include<iostream>

using namespace std;

int main()
{
	map<char,string> en;
	en['A']="00000";	en['B']="00001";	en['C']="00010";
	en['D']="00011";	en['E']="00100";	en['F']="00101";
	en['G']="00110";	en['H']="00111";	en['I']="01000";
	en['J']="01001";	en['K']="01010";	en['L']="01011";
	en['M']="01100";	en['N']="01101";	en['O']="01110";
	en['P']="01111";	en['Q']="10000";	en['R']="10001";
	en['S']="10010";	en['T']="10011";	en['U']="10100";
	en['V']="10101";	en['W']="10110";	en['X']="10111";
	en['Y']="11000";	en['Z']="11001";	en[' ']="11010";
	en['.']="11011";	en[',']="11100";	en['-']="11101";
	en['\'']="11110";	en['?']="11111";

	map<string,char> de;
	de["101"]=' ';		de["000000"]='\'';	de["000011"]=',';
	de["10010001"]='-';	de["010001"]='.';	de["000001"]='?';
	de["100101"]='A';	de["10011010"]='B';	de["0101"]='C';
	de["0001"]='D';		de["110"]='E';		de["01001"]='F';
	de["10011011"]='G';	de["010000"]='H';	de["0111"]='I';
	de["10011000"]='J';	de["0110"]='K';		de["00100"]='L';
	de["10011001"]='M';	de["10011110"]='N';	de["00101"]='O';
	de["111"]='P';		de["10011111"]='Q';	de["1000"]='R';
	de["00110"]='S';	de["00111"]='T';	de["10011100"]='U';
	de["10011101"]='V';	de["000010"]='W';	de["10010010"]='X';
	de["10010011"]='Y';	de["10010000"]='Z';

	string s;
	while(getline(cin,s)){
		string text;
		for(int i=0;i<s.length();i++)	text+=en[s[i]];
		for(int i=0,len;i<text.length();i+=len){
			bool found=false;
			for(len=3;i+len<=text.length();len++){
				if(de.count(text.substr(i,len))!=0){
					found=true;
					break;
				}
			}
			if(!found)	break;
			cout<<de[text.substr(i,len)];
		}
		cout<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

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

    string s;
    cin >> s;

    vector<int> c(n + 1);

    for(int i = 0; i < n; i++) {
        c[i + 1] = c[i] + (s[i] == 'E');
    }

    int ans = 1 << 26;
    for(int i = 0; i < n; i++) {
        ans = min(ans, (i - c[i]) + (c[n] - c[i + 1]));
    }

    cout << ans << endl;
}

Measured memory_bytes: 1916
let id x = x
let n = Scanf.scanf "%d\n" id
let string = Scanf.scanf "%s\n" id

let rec makestr str n =
  if n = String.length str - 1 then str else
    if str = "()" then "" else
      if str.[n] = '(' && str.[n+1] = ')' then
        makestr ((String.sub str 0 n) ^ (String.sub str (n+2) ((String.length str) - (n+2)))) 0 else makestr str (n+1)
  
let str = makestr string 0

let rec count x y str n =
  if n = String.length str then (x,y) else
  match str.[n] with
  | '(' -> count (x+1) y str (n+1)
  | ')' -> count x (y+1) str (n+1)

let (x,y) = count 0 0 str 0

let xlist = String.make x ')'
let ylist = String.make y '('
  
let () =
  Printf.printf "%s\n" (ylist ^ string ^ xlist)

Measured memory_bytes: 384
# https://atcoder.jp/contests/abc109/tasks/abc109_c

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)


def main():
    N, X = map(int, input().split())

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

    ans = abs(X - xl[0])
    for i in range(1, len(xl)):
        ans = gcd(max(ans, abs(X - xl[i])), min(ans, abs(X - xl[i])))

    print(ans)


main()


Measured memory_bytes: 14228
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define erep(i,a,b) for(int i=a;i<=(int)(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>(a);i--)
#define eper(i,a,b) for(int i=((int)(a));i>=b;i--)
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
const int INF=999999999;
const int MOD=1000000007;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int n, a[1000], ans = INF;

int main() {
    cin >> n; 
    rep(i, 0, n) {
        cin >> a[i];
    }
    erep(i, -100, 100) {
        int sum = 0;
        rep(j, 0, n) {
             sum += (a[j]-i) * (a[j]-i);
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;

namespace C___Coloring_Colorfully
{
    class Program
    {
        static void Main (string[] args)
        {
            var s = Console.ReadLine ();
            var a = 0;
            var b = 0;
            for (var i = 0; i < s.Length; i++)
            {
                if (i % 2 == 1)
                {
                    if (s[i] == '0')
                    {
                        a++;
                    }
                    else if (s[i] == '1')
                    {
                        b++;
                    }
                }
                else if (i % 2 == 0)
                {
                    if (s[i] == '1')
                    {
                        a++;
                    }
                    else if (s[i] == '0')
                    {
                        b++;
                    }
                }
            }
            Console.WriteLine (Math.Min (a, b));
        }
    }
}

Measured memory_bytes: 13140
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <stack>
#include <bitset>
#include <iomanip>
#include <list>
#include <sstream>
#include <fstream>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
#define ull unsigned long long
#define DEBUG(x) cout<<#x<<" : "<<x<<endl;
#define lowbit(x) x&(-x)
#define ls(u) u<<1
#define rs(u) u<<1|1
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double clf = 1e-8;
const int MMAX = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
ostream& operator <<(ostream &out, pii &p){
	return out<<p.first<<" "<<p.second;
}
istream& operator >>(istream &in, pii &p){
	return in>>p.first>>p.second;
}
int cnt[70];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//ifstream cin("C:\\Users\\LENOVO\\Desktop\\in.txt");
	//ofstream cout("C:\\Users\\LENOVO\\Desktop\\out.txt");
	ll n,t;cin>>n;
	for(int i=0;i<n;i++) {
		cin>>t;
		for(int j=0;j<62;j++){
			cnt[j]+=t&(1LL<<j)?1:0;
		}
	}
	ll res=0;
	for(int i=0;i<62;i++){
		res=(res+(((cnt[i]%mod*((n-cnt[i])%mod))%mod)*((1LL<<i)%mod))%mod)%mod;
	}
	cout<<res%mod<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, n, now = 1, ans;
  scanf("%lld", &n);
  ll a[n + 1], b[n + 1];
  for(i = 0; i <= n; ++i) {
    scanf("%lld", &a[i]);
    now -= a[i];
    if(now < 0) {
      printf("-1");
      return 0;
    }
    b[i] = now;
    now <<= 1ll;
    if(now > 1e16) now = 1e16;
  }
  now = ans = a[n];
  for(i = n; i; --i) {
    now = now < b[i - 1] ? now : b[i - 1], now += a[i - 1];
    ans += now;
  }
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 3292
# seishin.py
N = int(input())
*P, = map(int, input().split())
M = [0]*(N+1)
for i, p in enumerate(P):
    M[p] = i

INF = 10**9
def init(P, n):
    n0 = 2 ** (n-1).bit_length()
    data = [INF]*(n0*2)
    data[n0-1:n0+n-1] = P
    for i in range(n0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    return data

"""
def __get(data, a, b, k, l, r):
    if a <= l and r <= b:
        return data[k]
    if b <= l or r <= a:
        return INF
    vl = __get(data, a, b, 2*k+1, l, (l+r)//2)
    vr = __get(data, a, b, 2*k+2, (l+r)//2, r)
    return min(vl, vr)
"""

def get_data(data, l, r):
    n0 = len(data)//2
    l += n0
    r += n0
    while l < r:
        if r&1:
            r -= 1
            yield data[r-1]
        if l&1:
            yield data[l-1]
            l += 1
        l >>= 1
        r >>= 1
    yield INF

def get(data, l, r):
    #return __get(data, l, r, 0, 0, len(data)//2)
    return min(get_data(data, l, r))

d0 = init(P[0::2], N//2)
d1 = init(P[1::2], N//2)

def query_x(l, r):
    if l % 2 == 0:
        x = get(d0, l//2, r//2)
    else:
        x = get(d1, l//2, r//2)
    return x
def query_y(l, r):
    if l % 2 == 0:
        y = get(d1, l//2, r//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y

from heapq import heappush, heappop
que = [(query_x(0, N), 0, N)]
ans = []
while que:
    x, l, r = heappop(que)
    if l+2 < r:
        xi = M[x]
        y = query_y(xi, r)

        yi = M[y]

        # [l, xi)
        if l < xi:
            heappush(que, (query_x(l, xi), l, xi))
        # [xi+1, yi)
        if xi+1 < yi:
            heappush(que, (query_x(xi+1, yi), xi+1, yi))
        # [yi+1, r)
        if yi+1 < r:
            heappush(que, (query_x(yi+1, r), yi+1, r))
    else:
        y = P[r-1]

    ans.append("%d %d" % (x, y))
print(*ans)

Measured memory_bytes: 127880
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<vector>

#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define rep(i,a) repi(i,0,a)
#define repd(i,a,b) for(int i = int(a); i >= int(b); i--)
#define repit(i,a) for(__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
#define all(u) (u).begin(),(u).end()
#define rall(u) (u).rbegin(),(u).rend()
#define UNIQUE(u) (u).erase(unique(all(u)),(u).end())
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

using namespace std;

typedef long long ll;

void swap4(int &a, int &b, int &c, int &d) {
    int tmp = a;
    a = b;
    b = c;
    c = d;
    d = tmp;
}

void up(vector<int> &d) {
    swap4(d[0], d[2], d[5], d[4]);
}

void right(vector<int> &d) {
    swap4(d[4], d[3], d[2], d[1]);
}


void next_dice(vector<int> &d, int k) {
    up(d);
    if(k % 4 == 3) right(d);
    if(k == 15) {
        up(d);
        right(d);
    } else if(k == 19) right(d);
}


int n;
signed main(){
    while(cin >> n, n) {
        vector<vector<int> > d(4);
        map<string, int> table;
        int id = 0;
        rep(i, 4) d[i].resize(6);

        rep(i, n) {
            string ts;
            rep(j, 6) {
                cin >> ts;
                if(table.find(ts) == table.end()) table[ts] = id++;
                d[i][j] = table[ts];
            }
            swap(d[i][3], d[i][4]);
        }

        if(n == 1) {
            cout << 0 << endl;
            continue;
        }

        int ans = 1000;
        rep(i1, 24) {
            rep(i2, 24) {
                rep(i3, 24) {
                    int tmp = 0;
                    rep(k, 6) {
                        vector<int> cnt(id);
                        rep(i, n) {
                            cnt[d[i][k]]++;
                        }
                        tmp += n - *max_element(all(cnt));
                    }
                    ans = min(ans, tmp);
                    next_dice(d[3], i3);
                    if(n <= 3) break;
                }
                next_dice(d[2], i2);
                if(n <= 2) break;
            }
            next_dice(d[1], i1);
            if(n <= 1) break;
        }

        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
     
int main() {
    int   N,K;
    string S;
    cin >> N >> K >> S;
 	std::string data = S.substr(K-1,1); 
	std::transform(data.begin(), data.end(), data.begin(), ::tolower);
    
  	cout << S.replace(K-1, 1, data) << endl;
          
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad

pl :: [Int] -> IO ()
pl xs = putStrLn $ unwords $ map show xs

insertion :: Int -> [Int] -> [Int]
insertion i xs = [x | x <- p, x <= v] ++ [v] ++ [x | x <- p, v < x] ++ drop (i + 1) xs
    where
        p = take i xs
        v = xs !! i

solve :: Int -> [Int] -> [[Int]]
solve n xs = foldl (\l i -> insertion i (head l) : l) [xs] [1 .. n - 1]

main :: IO ()
main = do
    n  <- readLn
    xs <- map read <$> words <$> getLine
    mapM_ pl $ reverse $ solve n xs

Measured memory_bytes: 4076
//marico el que lo lea
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;

#define FOR(i,f,t) for(int i=f; i<(int)t; i++)
#define FORR(i,f,t) for(int i=f; i>(int)t; i--)
#define pb push_back
#define ms(obj, val) memset(obj, val, sizeof(obj))
#define ms2(obj, val, sz) memset(obj, val, sizeof(obj[0])*sz)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rii(x,y) ri(x), ri(y)
#define rll(x,y) rl(x), rl(y)

#define fst first
#define snd second
#define dprintf debug && printf
#define debug false

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;

const int MAXN = 1e5+5;
int N;
vi G[MAXN], T[MAXN];
int f[MAXN];

void make_T(int v, int p){
	FOR(i,0,G[v].size()){
		int u=G[v][i];
		if(u==p) continue;
		T[v].pb(u);
		make_T(u,v);
	}
}

void solve(int v){
	FOR(i,0,T[v].size()) solve(T[v][i]);
	if(T[v].size()==0) return;
	else{
		f[v] = f[T[v][0]]+1;
		FOR(i,1,T[v].size()) f[v] ^= (f[T[v][i]]+1);
	}
}

int main(){
	ri(N);
	FOR(i,0,N-1){
		int v, u; rii(v,u); v--; u--;
		G[v].pb(u);
		G[u].pb(v);
	}
	make_T(0,-1);
	solve(0);
	printf(f[0]?"Alice\n":"Bob\n");
}

Measured memory_bytes: 20992
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n=read(),m=read();
    for(int i=m-n+1;i<=m+n-1;i++)pr1(i);
    return 0;
}

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

int main() {
  string n;
  cin >> n;
  if (n[0] == '1') n[0] = '9'; else n[0] = '1';
  if (n[1] == '1') n[1] = '9'; else n[1] = '1';
  if (n[2] == '1') n[2] = '9'; else n[2] = '1';
  cout << n << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000;
int n, a[N], b[N], c[N];
double fx(int i, double x) {
	return (-a[i] * x + c[i]) / b[i];
}
vector<pair<double, int> > order;
int BIT[N + 1];
void add(int idx, int val) {
	++idx;
	while (idx <= n) {
		BIT[idx] += val;
		idx += idx&-idx;
	}
}
int get(int idx) {
	++idx;
	int ret = 0;
	while (idx) {
		ret += BIT[idx];
		idx -= idx&-idx;
	}
	return ret;
}
ll check(double x) {
	vector<pair<double, int> > q(n);
	for (int i = 0; i < n; ++i) {
		q[i].first = fx(i, x);
		q[i].second = i;
	}
	sort(q.begin(), q.end());
	vector<int> loc(n);
	for (int i = 0; i < n; ++i)
		loc[q[i].second] = i;
	memset(BIT, 0, sizeof(BIT));
	ll res = 0;
	for (int i = 0; i < n; ++i) {
		int x = loc[order[i].second];
		res += i - get(x);
		add(x, 1);
	}
	return n*(n - 1) / 2 - res;
}
double calc() {
	order.resize(n);
	for (int i = 0; i < n; ++i) {
		order[i].first = fx(i, 1e14);
		order[i].second = i;
	}
	sort(order.begin(), order.end());
	double l = -1e9, r = 1e9, m;
	for (int it = 0; it < 64; ++it) {
		m = (l + r) / 2;
		if (check(m) >= ((ll)n*(n - 1) / 2 + 1) / 2)
			r = m;
		else
			l = m;
	}
	return (l + r) / 2;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d%d%d", a + i, b + i, c + i);
	printf("%.12lf ", calc());
	for (int i = 0; i < n; ++i)
		swap(a[i], b[i]);
	printf(" %.12lf\n", calc());
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, h[200], maxx=0, sum=0;
    cin >> n;

    for(int i=0; i<n; i++){
       cin >> h[i];
       if(h[i] >= maxx){
            sum++;
            maxx = h[i];
       }
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,W = map(int,read().split())

if H > W:
    H,W = W,H

if H == 1:
    print(1)
else:
    N = H * W
    print((N+1)//2)

Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int num=sc.nextInt();
		int [][]array=new int[num][3];
		for(int i=0;i<num;i++){
			array[i][0]=sc.nextInt();
			array[i][1]=sc.nextInt();
			array[i][2]=sc.nextInt();
		}
		for(int i=0;i<num;i++){
			if(array[i][0]<array[i][1]+array[i][2]){
				System.out.println("No");
				return;
			}
		}
		boolean flag=true;
		for(int i=0;i<num;i++){
			if(array[i][0]%2!=(array[i][1]+array[i][2])%2){
				flag=false;
			}
		}
		if(flag){
			System.out.println("Yes");	
		}else{
			System.out.println("No");
		}
		
	}

}


Measured memory_bytes: 93804
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int main() {
  int h, w, k; cin >> h >> w >> k;
  vector<string> c(h);
  for(int i=0; i<h; i++) cin >> c[i];
  vector<pair<int, int>> p;
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      if (c[i][j] == '#') p.push_back({i, j});
    }
  }
  int m = p.size();

  int ans = 0;
  for(int i=0; i<(1<<h); i++) {
    for(int j=0; j<(1<<w); j++) {
      int cnt = 0;
      for(int k=0; k<m; k++) {
        if ((i&(1<<p[k].first)) == (1<<p[k].first)) continue;
        if ((j&(1<<p[k].second)) == (1<<p[k].second)) continue;
        cnt++;
      }
      if (cnt == k) ans++;
    }
  }

  cout << ans << endl;

  return 0;
}

// EOF

Measured memory_bytes: 3592
n,m=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)

print(len(uf.roots())-1)

Measured memory_bytes: 75064