akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

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

    int ans = 0;
    for(int i=1;i<n;i++){
        int cnt = 0;
        for(char c='a';c<='z';c++){
            bool left=false,right=false;
            for(int j=0;j<i;j++){
                if(s[j] == c){
                    left = true;
                }
            }
            for(int j=i;j<n;j++){
                if(s[j] == c){
                    right = true;
                }
            }
            if(left && right){
                cnt++;
            }
        }
        if(ans < cnt){
            ans = cnt;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 764
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
  int n; cin >> n;
  vector<ll> A(n); rep(i, n) cin >> A[i];

  int cnt = 0;
  rep(i, n){
    if(i%2==0 && A[i]%2==1)cnt++;
  }
  cout << cnt << ln;
}


Measured memory_bytes: 3628
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n; cin>>n;
    vector<int> ans(n,0);
    vector<pp> x(n);
    rep(i,n){
        int X; cin>>X;
        x[i]=mk(X,i);
    }
    sort(al(x));
    int l=x[n/2-1].first,r=x[n/2].first;
    rep(i,n){
        if(i<=n/2-1) ans[x[i].second]=r;
        else ans[x[i].second]=l;
    }
    rep(i,n) cout<<ans[i]<<endl;
}

Measured memory_bytes: 4480
import sys
input=sys.stdin.readline

n,x = map(int, input().split())
a = list(map(int, input().split()))

if sum(a) == x:
    print(n)
else:
    a.sort()
    s = 0
    for i,v in enumerate(a):
        s += v
        if s > x:
            print(i)
            exit()
    print(n-1)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;

int main() {
    int n,m;
    cin >> n >> m;
    priority_queue<ll> q;
    rep(i,n) {
        ll a;
        cin >> a;
        q.push(a);
    }
    rep(i,m) {
        ll now = q.top();
        q.pop();
        now /= 2;
        q.push(now);
    }
    ll ans = 0;
    while(!q.empty()) {
        ll l = q.top();
        ans += l;
        q.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 1400
#ifdef _DEBUG
#define _CRT_SECURE_NO_WARNINGS
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define MGN 8
#define LINF (LONG_MAX/2)
using namespace std;
typedef long long ll; typedef unsigned long long ull;
typedef vector<int> vi; typedef vector<vi> vvi;
typedef vector<ll> vl; typedef vector<vl> vvl;
typedef vector<double> vd; typedef vector<string> vs;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
typedef vector<bool> vb; typedef vector<vb> vvb;
template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
    return left.second > right.second;
}
vs split(string str, char sep) {
    vs v; stringstream ss(str); string t;
    while (getline(ss, t, sep)) v.push_back(t);
    return v;
}
vs re_search_g(string s, regex re) {
    vs ret; smatch mc; auto it = s.cbegin();
    while (regex_search(it, s.cend(), mc, re)) {
        ret.push_back(mc[0]);
        it += mc.position(0) + mc.length();
    }
    return ret;
}
#endif

void init_global_C() {}

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

    int N; cin >> N;
    vi a(N); REP(i, N) cin >> a[i];

    deque<int> dq;

    REP(i, N) {
        if (i % 2 == 0) {
            dq.push_front(a[i]);
        } else {
            dq.push_back(a[i]);
            if (i == N - 1) {
                reverse(dq.begin(), dq.end());
            }
        }
    }

    REP(i, N - 1) {
        cout << dq[i] << " ";
    }
    cout << dq[N - 1] << endl;

    return 0;
}

Measured memory_bytes: 3840
j,p[1<<20],n;
main(i)
{
	for(;++i<999;)
		for(j=i+i;!p[i]&j<1<<20;j+=i)
				p[j]=1;
	for(;scanf("%d",&n),j=0,n;printf("%d\n",j))
		for(i=2;i<=n/2;i++)if(!p[i]&!p[n-i])j++;
	exit(0);
}

Measured memory_bytes: 4504
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 1005
using namespace std;
int n,say;
char s[li];
unordered_map<char,int> tp;
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++){
		tp[s[i]]++;
	}
	if(tp['S']==0) say++;
	if(tp['N']==0) say++;
	if(say==1){
		printf("No\n");
		return 0;
	}
	say=0;
	if(tp['E']==0) say++;
	if(tp['W']==0) say++;
	if(say==1)
		printf("No\n");
	else printf("Yes\n");
	return 0;
}


Measured memory_bytes: 256
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
c = Counter(a)
flag = False

if c[0] == n:
    flag = True
elif c[0] == n/3 and len(c) == 2:
    flag = True
else:
    s = 0
    for num in c:
        s ^= num
        if c[num] != n/3: break
    else:
        if s == 0: flag = True

print("Yes" if flag else "No")

Measured memory_bytes: 14468
from collections import defaultdict

class LCM_mod:
    """
    最小公倍数の計算を行う
    オーバーフローが発生しないように素因数分解し,
    因数の積を逐次余りに置き換えて最小公倍数を導出する.
    """
    def __init__(self, max_num, p=10**9+7):
        self.max_num = max_num + 1
        self.p = p
        self.prime = [0 for _ in range(self.max_num)]
        self.max_map = defaultdict(int)
        self.sieve()

    def rep_sqr(self, base, k):
        # 繰り返し二乗法
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k / 2) ** 2) % self.p
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.p

    def sieve(self):
        """
        エラトステネスの篩　O(n)
        nまでに含まれる素数を導出
        """
        self.prime[0], self.prime[1] = 1, 1
        for i in range(2, self.max_num):
            if self.prime[i] == 0:
                for j in range(i * 2, self.max_num, i):
                    if self.prime[j] == 0:
                        self.prime[j] = i
                self.prime[i] = i

    def lcm_list_mod(self, arr):
        """
        listのそれぞれの要素について、素因数分解する
        それぞれの因数について最大であれば更新する
        """
        for i in range(len(arr)):
            num = arr[i]
            d = defaultdict(int)

            while num > 1:
                fact = self.prime[num]
                d[fact] += 1
                num //= fact

            for i in d.keys():
                self.max_map[i] = max(self.max_map[i], d[i])

        ans = 1
        for i in self.max_map.keys():
            ans = (ans * self.rep_sqr(i, self.max_map[i])) % self.p
        return ans


class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k // 2) ** 2) % self.mod
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.mod

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    MOD = 10**9+7

    lcm_mod = LCM_mod(max(a), MOD)
    lcm_all = lcm_mod.lcm_list_mod(a)
    flt = FLT(MOD)

    b = list(map(lambda x: lcm_all * flt.inv(x), a))
    ans = 0
    for i in range(len(b)):
        ans += b[i]
        ans %= MOD
    print(ans)

main()

Measured memory_bytes: 14996
#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
#include"map"
using namespace std;

const int MOD=1e9+7;

long long n;
map<long long,long long> f;

long long dfs(long long v)
{
	if(f[v]) return f[v];
	if(v==0) return 1;
	return f[v]=(dfs(v>>1)+dfs(v-1>>1)+dfs(v-2>>1))%MOD;
}

int main()
{
	f[1]=2;
	scanf("%lld",&n);
	printf("%lld\n",dfs(n));
	return 0;
}

Measured memory_bytes: 256
import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
ans=0
for b in B:
    ans+=bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b))
print(ans)

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

#define MAX 100000

int main(int, char**)
{
    int n, q;
    int s[MAX];

    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    cin >> q;

    int tmp;
    int count = 0;
    for (int i = 0; i < q; i++) {
        cin >> tmp;

        int left = 0;
        int right = n;
        int mid;

        while (left < right) {
            mid = (left + right) / 2;
            if (s[mid] == tmp) {
                count++;
                break;
            } else if (s[mid] < tmp) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3448
#include<bits/stdc++.h>
#define ll long long int
#define st string
#define con continue
#define br break
#define rt return 0
#define fr first
#define sec second
using namespace std;
int main(){
//ll tc; cin>>tc; while(tc--){
ll n,m,mn=INT_MAX,i,x,j,a=0,t,k,b=-1,mx=-1,cnt=0,c=0; 
 st s,str; char strn;
cin>>n; //a=n; n-=1; 
//ll ara[n+1],bra[n+1],taj[n+1];

//for(i=1;i<=n;i++) cin>>ara[i]; 
  for(i=1;i<=n;i++)
   {
     cin>>x;
    if(x%2 && i%2)a++;
   }      
              

        
     cout<<a<<endl;
    
 
    rt;
}

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

using namespace std;

typedef long long ll;

const int MAX = 100000;

int parent(int i) { return i / 2; }
int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }


int main() {
    int H; cin >> H;
    int A[MAX+1];

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

    for (int i = 1; i <= H; i++) {
        cout << "node " << i << ": key = " << A[i] << ", ";
        if (parent(i) >= 1) cout << "parent key = " << A[parent(i)] << ", ";
        if (left(i) <= H) cout << "left key = " << A[left(i)] << ", ";
        if (right(i) <= H) cout << "right key = " << A[right(i)] << ", ";
        cout << endl;
    }
}



Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
int k;
int main(){
cin>>k;
long long a=(k+2-1)/2;
if(k%2==0){
    cout<<(k/2)*(k/2)<<endl;
}
else{
    cout<<a*(k/2)<<endl;
}

return 0;
}


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

int main(){
    int a,b;
    cin >> a >> b;
    int c=0,x,y;
    for (int i=a;i<=b;i++){
        if(i%10==i/10000 && (i/10)%10==(i/1000)%10)
            
            c++;
    }
    cout << c << endl; 
}

Measured memory_bytes: 3612
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	long long n = 0; string s; cin >> s;
	for (int h = 0; h < 4; h++) {
		if (s[h] == '+') {
			n++;
		}
		if (s[h] == '-') {
			n--;
		}
	}
	cout << n << endl;
	cin >> n;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100
#define W 0
#define G 1
#define B 2

int n,M[N][N];
int color[N],d[N],f[N],tt;

void dfs_visit(int u){
  int v;
  color[u]=G;
  d[u]=++tt;

  for(v=0;v<n;v++){
    if(M[u][v]==0)
      continue;
    if(color[v]==W){
      dfs_visit(v);
    }
  }
  color[u]=B;
  f[u]=++tt;
}

void dfs(){
  int u;

  for(u=0;u<n;u++)
    color[u]=W;
  tt=0;

  for(u=0;u<n;u++){
    if(color[u]==W)
      dfs_visit(u);
  }
  for(u=0;u<n;u++){
    printf("%d %d %d\n",u+1,d[u],f[u]);
  }
}

int main(){
  int u,v,k,i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++)
      M[i][j]=0;
  }

  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    u--;

    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      M[u][v]=1;
    }
  }

  dfs();

  return 0;
}



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

using namespace std;

char a = 0, b = 0;

void input()
{
  scanf("%c %c", &a, &b);
}

void solve()
{
  int A = a;
  int B = b;
  printf(A < B ? "<" : A > B ? ">" : "=");
}

int main()
{
  input();
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <queue>
#include <numeric>
#include <stack>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  long n, k;
  cin >> n >> k;

  long ans=0, x;
  if (k%2==0) {
    x = (n+k/2)/(k);
    ans += x*x*x;
  }
  x = n/k;
  ans += x*x*x;

  cout << ans << endl;

  return 0;
}








Measured memory_bytes: 888
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

st = ''
for i in t:
    if i == 'r':
        st += 'p'
    elif i == 'p':
        st += 's'
    else:
        st += 'r'

stt = st[:k]

for i in range(k, n):
    if st[i] != stt[i - k]:
        stt += st[i]
    else:
        stt += 'x'

sum = 0
for i in stt:
    if i == 'r':
        sum += r
    elif i == 's':
        sum += s
    elif i == 'p':
        sum += p
    else:
        pass
print(sum)

Measured memory_bytes: 3444
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    X = int(readline())

    ans = 0
    ans += (X // 500) * 1000

    X %= 500
    ans += (X // 5) * 5

    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    xy = set(list(map(int, readline().split())))
    A = set([1,3,5,7,8,10,12])
    B = set([4,6,9,11])
    C = set([2])
    if xy<=A or xy<=B or xy<=C:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9256
n = int(input())
a_list = list(map(int, input().split()))

status = True
execute = 0
while status:
    for i in range(n):
        if a_list[i] % 2 == 1:
            status = False
            break
        else:
            a_list[i] = a_list[i] / 2
    if status:
        execute += 1
print(execute)


Measured memory_bytes: 9044
import java.util.Scanner;public class Main {	public static void main(String[] args) {		int n, sum = 0;		Scanner sc = new Scanner(System.in);		n = sc.nextInt();		int[] S = new int[100001];		for (int i = 0; i < n; i++) {			S[i] = sc.nextInt();		}		int q, key = 0;		q = sc.nextInt();		for (int i = 0; i < q; i++) {			key = sc.nextInt();			if (binarySearch(S, n, key))				sum++;		}		System.out.println(sum);	}	private static boolean binarySearch(int[] S, int n, int key) {		int left = 0;		int right = n - 1;		while (left <= right) {			int mid = (left + right) / 2;			if (key == S[mid])				return true;			else if (key > S[mid])				left = mid + 1;			else				right = mid - 1;		}		return false;	}}


Measured memory_bytes: 68680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll inf = 1e18;
ll mod = 1e9+7;

int main(){
    ll k;
    cin >> k;
    ll sum = 0;
    for (ll a = 1; a <= k; a++) {
        for (ll b = 1; b <= k; b++) {
            for (ll c = 1; c <= k; c++) {
                sum += __gcd(a,__gcd(b,c));
            }
        }
    }
    cout << sum << endl;
    return 0;
}

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

int main() {

  int N, T, A;
  cin >> N >> T >> A;

  vector<int> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }
  
  double answer = 0;
  double minDiff = 5000000;

  for (int i = 0; i < N; i++) {
    double a = T - H[i] * 0.006;
    double diff = abs(A - a);
    if (diff < minDiff) {
      answer = i;
      minDiff = diff;
    }
  }

  cout << answer+1 << endl;

}

Measured memory_bytes: 256
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


if __name__ == '__main__':
    s = input()
    ans = ""
    for i in s:
        if i == "0":
            ans += "0"
        if i == "1":
            ans += "1"
        if i == "B":
            if ans =="":
                ans =ans
            else:
               ans =ans[:len(ans)-1]
    print(ans)



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

static const int N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[N][N];
int color[N], d[N], f[N], tt;
int nt[N];

int next(int u) {
    for(int v=nt[u]; v<n; v++) {
      nt[u] = v + 1;
      if(M[u][v]) return v;
    }
    return -1;
}

void dfs_visit(int r) {
    for(int i=0; i<n; i++) nt[i] = 0;
    
    stack<int> S;
    S.push(r);
    color[r] = GRAY;
    d[r] = ++tt;
    
    while(!S.empty()) {
        int u = S.top();
        int v = next(u);
        if(v != -1) {
            if(color[v] == WHITE) {
                color[v] = GRAY;
                d[v] = ++tt;
                S.push(v);
            }
        } else {
            S.pop();
            color[u] = BLACK;
            f[u] = ++tt;
        }
    }
}

void dfs() {
    for(int i=0; i<n; i++) {
        color[i] = WHITE;
        nt[i] = 0;
    }
    tt = 0;
    
    for(int u=0; u<n; u++) {
        if(color[u] == WHITE) dfs_visit(u);
    }
    for(int i=0; i<n; i++) {
        cout << i+1 << " " << d[i] << " " << f[i] << endl;
    }
}

int main() {
    int u, k, v;
    
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) M[i][j] = 0;
    }
    
    for(int i=0; i<n; i++) {
        cin >> u >> k;
        u--;
        for(int j=0; j<k; j++) {
            cin >> v;
            v--;
            M[u][v] = 1;
        }
    }
    
    dfs();
    
    return 0;
}


Measured memory_bytes: 3088
package main

import(
    "fmt"
    "sort"
    "strings"
)



func main() {
    var h,w int
    fmt.Scan(&h,&w)
    s := scanString(h)
    for i:=0;i<h+2;i++{
        for j:=0;j<w+2;j++{
            if i==0 || j==0 || i==h+1 || j==w+1{
                fmt.Printf("#")
            } else {
                fmt.Printf("%c", s[i-1][j-1])
            }
        }
        fmt.Printf("\n")
    }
}





// Pairsort
type Pair struct {
    first,second int64
}

type By func(p1, p2 *Pair) bool

func (by By) Sort(pairs []Pair) {
    ps := &pairSorter{
            pairs : pairs,
            by: by,
    }
    sort.Sort(ps)
}

type pairSorter struct {
    pairs []Pair
    by func(p1, p2 *Pair) bool
}

func (s *pairSorter) Len() int {
    return len(s.pairs)
}

func (s *pairSorter) Swap(i, j int) {
    s.pairs[i], s.pairs[j] = s.pairs[j], s.pairs[i]
}

func (s *pairSorter) Less(i, j int) bool {
    return s.by(&s.pairs[i], &s.pairs[j])
}

func first (p1, p2 *Pair) bool {
        return p1.first < p2.first
}

func second (p1, p2 *Pair) bool {
        return p1.second < p2.second
}
// end



func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}

func scanNums(len int) (nums []int){
    var num int
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanNums64(len int) (nums []int64){
    var num int64
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanString(len int) (str []string){
    var s string
    for i:=0; i<len; i++{
        fmt.Scan(&s)
        str = append(str,s)
    }
    return
}

func makeTwoNums(n,m int) ([][]int){
    Nums := make([][]int, n)
    for i:=0; i<n; i++{
        Nums[i] = make([]int, m)
    }
    return Nums
}

func sortString(s string) string{
    t := strings.Split(s, "")
    sort.Strings(t)
    return strings.Join(t, "")
}

func reverseString(s string) string{
    t := []rune(s)
    for i,j := 0, len(s)-1 ; i < j ; i, j = i+1, j-1 {
        t[i], t[j] = t[j], t[i]
    }
    return string(t)
}

func inside(h,w,H,W int) bool{
    if h>=0 && h<H && w>=0 && w<W{
        return true
    }
    return false
}


Measured memory_bytes: 640
import java.util.*;
import java.util.Map;
import java.util.TreeMap;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] d = new int[N];

        for(int i=0; i<N; i++){
            d[i] = Math.abs(sc.nextInt() - X);
        }

        int k = d[0];

        for(int i=1; i<N; i++){
            for(int j=0; j<1000000; j++){
                if(d[i]>=k){
                    int a = d[i];
                    int b = k;
                    if(a % b==0){
                        break;
                    }
                    k = a % b;
                    d[i] = b;
                }
                else{
                    int a = k;
                    int b = d[i];
                    if(a % b==0){
                        k = b;
                        break;
                    }
                    d[i] = a % b;
                    k = b;
                }
            }
        }
        System.out.println(k);
    }
}

Measured memory_bytes: 48860
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read() {
	int x=0, f=1; char ch=' ';
	while(!isdigit(ch)) {ch=getchar(); if(ch=='-') f=-1;}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
	return x*f;
}
int n, a[200005], all;
int main() {
	cin>>n;
	for(int i=1;i<=n;i++) a[i]=read(), all^=a[i];
	for(int i=1;i<=n;i++) {
		printf("%d ", all^a[i]);
	} 
}
/*
10100 01011 01001 11000



*/




Measured memory_bytes: 4504
from collections import Counter

import scipy.misc as scm

n = int(input())
s = list(input())
tmp = len(set(s))
count_s = Counter(s)
count_s = count_s.most_common()
ans = 1
for i in range(tmp):
  if count_s[i][1] > 1:
    ans *= (count_s[i][1]+1)
    ans = ans % (10**9+7)
  else:
    ans *= 2
    ans = ans % (10**9+7)
ans -= 1
print(ans)


Measured memory_bytes: 14204
#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;

    rep(i, 2) {
        if (s[i] != s[i+1]) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    
    cout << "No" << endl;

    return 0;
}

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

using namespace std;

int main() {
  int n, m;
  string s;
  cin >> n >> m >> s;

  vector<int> diff;
  bool ok = true;
  for (int i = 1, j = 0; i < n + 1; i++) {
    if (s[i] == '0') {
      int d = i - j;
      ok &= (d <= m);
      diff.push_back(d);
      j = i;
    }
  }
  reverse(diff.begin(), diff.end());

  if (!ok) {
    cout << -1 << '\n';
    return 0;
  }

  int now = 0;
  vector<int> ans;
  for (auto w : diff) {
    if (now + w <= m) {
      now += w;
    } else {
      ans.push_back(now);
      now = w;
    }
  }
  if (now > 0) ans.push_back(now);
  reverse(ans.begin(), ans.end());
  
  for (int i = 0; i < (int) ans.size(); i++) {
    cout << ans[i] << " \n"[i + 1 == ans.size()];
  }
  return 0;
}


Measured memory_bytes: 1592
#include <iostream>
using namespace std;
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
    int w,h,c;
    cin>>w>>h>>c;
    if(w<h)swap(w,h);
    cout<<w*h/gcd(w,h)/gcd(w,h)*c<<endl;
}

Measured memory_bytes: 3108
def main():
    X = int(input())
    dp = [False] * (X + 1)
    dp[0] = True
    for i in range(X + 1):
        if dp[i]:
            for x in [100, 101, 102, 103, 104, 105]:
                if i + x <= X:
                    dp[i + x] = True
    print(1 if dp[X] else 0)


if __name__ == '__main__':
    main()


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


int main() {
  int64_t N,sum;
  cin >> N;
  sum = 0;
  
  for (int i = 1;i<N+1;i++) {
    if (i%3 !=0 && i%5 !=0) {
      sum += i;
    }
  }
  cout << sum << endl;
}

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

class calender{
public:
  string s;
  int ey,wy;
  bool operator<(const calender &a)const{
    return wy < a.wy;
  }
};
int main(){
  int n,q;
  while(cin>>n>>q,n){
    calender c[1005];
    for(int i=0;i<n;i++)cin>>c[i].s>>c[i].ey>>c[i].wy;
    sort(c,c+n);
    for(int i=0;i<q;i++){
      int query;
      cin>>query;
      for(int i=0;i<n;i++){
	if(query <= c[i].wy){
	  if(c[i].wy - query < c[i].ey){
	    cout << c[i].s << " " << c[i].ey - (c[i].wy - query)<< endl;
	  }else{
	    cout << "Unknown" << endl;
	  }
	  break;
	}
	if(i==n-1)
	    cout << "Unknown" << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
#include <string>
#include <vector>
#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(){
    int h,w,k;
    cin >> h >> w >> k;
    vector<string> G(h);
    vector<vector<int>> p(h,vector<int>(w,-1));
    vector<bool> sh(h,false);
    rep(i,h) {
        cin >> G[i];
        if(G[i].find('#') != string::npos) sh[i] = true;
    }

    int cnt = 0;
    bool seen = false;
    rep(i,h){
        if(sh[i]){
            cnt++;
            seen = false;
            rep(j,w){
                
                if(G[i][j]=='#') {
                    if(seen) cnt++;
                    seen = true;
                }
                p[i][j] = cnt;
            }
        }
    }

    rep(i,h-1){
        if(sh[i] && !sh[i+1]){
            p[i+1] = p[i];
            sh[i+1] = true;
        }
    }
    for(int i = h-1;i>=1;i--){
        if(sh[i] && !sh[i-1]){
            p[i-1] = p[i];
            sh[i-1] = true;
        }
    }

    rep(i,h){
        rep(j,w){
            cout << p[i][j] << " ";
        }
        cout << endl;
    }
}

Measured memory_bytes: 4164
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
int MOD=1000000007;
int inf=1e9+7;
signed main(){
    int n;cin>>n;
    int mx=-inf;int mx_ind;
    int mn=inf;int mn_ind;
    vector<int> a(n+1);
    rep1(i,n){
        cin>>a[i];
        if(mx<a[i]){
            mx=a[i];
            mx_ind=i;
        }
        if(mn>a[i]){
            mn=a[i];
            mn_ind=i;
        }
    }
    int m=0;
    vector<pair<int,int>> res;
    if(mx>=abs(mn)){
        rep1(i,n){
            ++m;
            res.push_back({mx_ind,i});
        }
        for(int i=2;i<=n;++i){
            ++m;
            res.push_back({i-1,i});
        }
    }
    else{
        rep1(i,n){
            ++m;
            res.push_back({mn_ind,i});
        }
        for(int i=n-1;i>0;--i){
            ++m;
            res.push_back({i+1,i});
        }
    }
    cout<<m<<"\n";
    for(auto& val:res){
        cout<<val.first<<" "<<val.second<<"\n";
    }
    return 0;
}

Measured memory_bytes: 256
# 木上の累積和

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


from collections import defaultdict

N, Q = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = read_ints()
    cnt[q - 1] += x

# dfsでcntに木に沿った累積和をsetしていく


def dfs(c, u, p):  # uは現在のノード、pは親のノード、cはuは含まない累積のスコア
    cnt[u] += c
    for nv in tree[u]:
        if nv == p:
            continue
        dfs(cnt[u], nv, u)


dfs(0, 0, -1)

print(*cnt)


Measured memory_bytes: 248496
import math.{ pow, sqrt }

object Main extends App {
  val src = io.Source.stdin.getLines.map(_.toDouble).grouped(2).map { case List(a, b) => (a, b) }

  for ((x, h) <- src if x != 0) println(sqrt(pow(x/2, 2) + pow(h, 2))*x*2 + x*x)
}



Measured memory_bytes: 43956
#include <iostream>

using namespace std;

int main() {
    string s[] = {"Sunny", "Cloudy", "Rainy"};
    string input;
    cin >> input;

    if(input==s[0])
        cout << s[1] << endl;
    else if(input==s[1])
        cout << s[2] << endl;
    else if(input==s[2])
        cout << s[0] << endl;

    return 0;
}





Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vvi edges(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    vi depth(n, -1);
    depth[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto &u : edges[v]) {
            if (depth[u] != -1)
                continue;
            depth[u] = depth[v] + 1;
            q.push(u);
        }
    }
    vector<pii> di;
    for (int i = 0; i < n; ++i) {
        di.emplace_back(depth[i], i);
    }
    sort(di.begin(), di.end());
    bool ok = true;
    for (int i = n - 1; i >= 0; --i) {
        int c = di[i].second;
        int d = di[i].first;
        vi childs;
        int maxi = 0;
        int sum  = 0;
        for (auto &u : edges[c]) {
            if (depth[u] < d)
                continue;
            childs.push_back(a[u]);
            chmax(maxi, a[u]);
            sum += a[u];
        }
        if (childs.size() == 0)
            continue;
        int amari = max(0, maxi - (sum - maxi));
        int mini  = (sum - amari) / 2 + amari;
        if (c == 0) {
            if (childs.size() == 1) {
                if (a[c] != sum)
                    ok = false;
            } else {
                if (amari != 0 || sum % 2 == 1 || sum / 2 != a[c])
                    ok = false;
            }
        }
        if (mini <= a[c] && a[c] <= sum) {
            a[c] = 2 * a[c] - sum;
        } else {
            ok = false;
            break;
        }
    }
    if (ok)
        cout << "YES"
             << "\n";
    else
        cout << "NO"
             << "\n";
    return 0;
}

Measured memory_bytes: 8064
input_str = input().split(" ")
input_int = list(map(int, input_str))
A = input_int[0]
B = input_int[1]
T = input_int[2]

bis_sum = 0
start = 0
end = A
while True:
    if start < T+0.5 and end > T+0.5:
        break
    start += A
    end += A
    bis_sum += B

print(bis_sum)

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

int main() {
  int N;
  cin >> N;
  
  vector<int> button(N,0);
  int j;
  for (int i=0; i<N; i++){
    cin >> j;
    button.at(i)=j;
  }
  
  int i=0, k=0;
  while (true) {
    i = button.at(i)-1;
    k++;
    if (i==1){
      cout << k << endl;
      break;
    }
    if (k==N){
      cout << "-1" << endl;
      break;
    }
  }
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int i,j,n,l=1000000000,a,b,c,m;
int main(){
  for(cin>>a>>b>>c>>n>>m;i<=max(n,m);i++)l=min(l,2*c*i+a*max(0,n-i)+b*max(0,m-i));
  cout<<l;
}

Measured memory_bytes: 256
#入力を受け取る
N,K=map(int,input().split())
a=list(map(int,input().split()))
#grundy[k]:=山にk(1≤k≤K)個石がある時のgrundy数
grundy=[0]*(K+1)
#DP(動的計画法)の考えかたを用いてGrundy数を求める
for j in range(K+1):
    s=set()
    for i in range(N):
        if a[i]<=j:
            s.add(grundy[j-a[i]])
    #mex()の動作
    g=0
    while g in s:g+=1 
    grundy[j]=g
if grundy[K]:print("First")
else:print("Second")



Measured memory_bytes: 75264
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;


int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  if(max(a, c) <= min(b, d)){
    cout << min(b, d) - max(a, c) << endl;
  }
  else{
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

void solve(int n){
    vector<vector<int>> cnt(21,vector<int>(21));
    rep(i,n){
        int x,y;
        cin>>x>>y;
        cnt[x][y]++;
    }
    int x=10,y=10;
    int ans=cnt[x][y];
    int m;
    cin>>m;
    int d[]{1,0,-1,0,1};
    rep(i,m){
        char c;cin>>c;
        int dir;
        if(c=='N')dir=3;
        if(c=='S')dir=1;
        if(c=='E')dir=0;
        if(c=='W')dir=2;
        int l;
        cin>>l;
        rep(j,l){
            x+=d[dir];
            y+=d[dir+1];
            ans+=cnt[x][y];
            cnt[x][y]=0;
        }
    }
    if(ans==n)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return;
}
int main(){
    int n;
    while(cin>>n,n!=0){
        solve(n);
    }
    return 0;
}


Measured memory_bytes: 3156
#include <iostream>
#include <cstring>

using namespace std;

#define MOD 10000
#define MAX 100

int dp[MAX+1][4][4],p[MAX],N;

int solve(int pos,int a,int b){
  if(pos == N) return 1; 
  if(dp[pos][a][b] != -1) return dp[pos][a][b];

  if(p[pos] > 0){
    if(a == b && b == p[pos]){
      return 0;
    }else{
      return solve(pos+1,b,p[pos]) % MOD;
    }
  }else{
    int res = 0;
    for(int i = 0 ; i < 3 ; i++){
      if(a == b && b == i+1) continue;
      res += solve(pos+1,b,i+1) % MOD;
    }
    return dp[pos][a][b] = res % MOD;
  }
}

int main(){
  int K,A,B;

  memset(p,-1,sizeof(p));
  memset(dp,-1,sizeof(dp));

  cin >> N >> K;
  for(int i = 0 ; i < K ; i++){
    cin >> A >> B;
    p[A-1] = B;
  }
  cout << solve(0,0,0) << endl;

  return 0;
}

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

#define REP(i, a, n) for(int i=a; i<n; i++)

int main() {
	int a, b, c, x;
	cin >> a >> b >>c >> x;
	int z=0;
	REP(i, 0, a+1){
      REP(j, 0, b+1){
        REP(k, 0, c+1){
          if(500*i+100*j+50*k==x)z++;
        }
      }
    }
  cout << z << endl;
}


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

int main(){
  int n,k;
  int s[100],b[100][100];
  bool f;

  while(1){
    cin >> n >> k;
    if(!n && !k)break;

    for(int i=0;i<k;i++)cin >> s[i];

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

    f = true;
    for(int i=0;i<k;i++){
      for(int j=0;j<n;j++){
	s[i] -= b[j][i];
	if(s[i] < 0){
	  f = false;
	  break;
	}
      }
    }
     
    if(f)cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
vector<ll> fac, finv, inv;


int main(){
    int h, w;  cin >> h >> w;
    vector<vector<int>> g(h, vector<int>(w));
    REP(i, h) REP(j, w) cin >> g[i][j];

    vector<pair<ll, ll>> bef, aft;
    vector<vector<bool>> seen(h, vector<bool>(w, false));

    bool flag=true;
    REP(i, h){
        if(flag){
            REP(j, w-1){
                if(g[i][j]%2){
                    g[i][j] -= 1;
                    g[i][j+1] += 1;
                    bef.push_back({i, j});
                    aft.push_back({i, j+1});
                }
            }   
            if(g[i].back()%2 && i<h-1){
                g[i].back() -= 1;
                g[i+1].back() += 1;
                bef.push_back({i, w-1});
                aft.push_back({i+1, w-1});
            } 
        }else{
            FORD(j, w-1, 1){
                if(g[i][j]%2){
                    g[i][j] -= 1;
                    g[i][j-1] += 1;
                    bef.push_back({i, j});
                    aft.push_back({i, j-1});
                }
            }   
            if(g[i][0]%2 && i<h-1){
                g[i][0] -= 1;
                g[i+1][0] += 1;
                bef.push_back({i, 0});
                aft.push_back({i+1, 0});
            }
        }
        flag = !flag;
    }
    cout << aft.size() << endl;
    REP(i, aft.size())
        cout << bef[i].first+1  << ' ' << bef[i].second+1 << ' ' <<
        aft[i].first+1  << ' ' << aft[i].second+1 <<  endl;

    

}


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        g[s].push_back(t);
    }
    
    vector<double> dp(n);

    double ans = 1e9;
    for (int r = -1; r <= n-2; r++) {

    dp[n-1] = 0;
    
    for (int i = n-2; i >= 0; --i) {
        double mv = 0;
        double sum = 0;
        for (auto t: g[i]) {
            sum += dp[t] + 1;
            mv = max(mv, dp[t]);
        }
        int d = g[i].size();
        if (i == r) {
            if (d == 1) dp[i] = 1e9;
            else dp[i] = (sum-mv-1)/(d-1);
        } else {
            dp[i] = sum/d;
        }
        
    }
    
    ans = min(ans, dp[0]);
    }
    
    cout << fixed << setprecision(20);
    cout << ans << endl;
    
    
    
    
    return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>
void fibonacci(int );
void fibonacci(int n){
  int i,F[45];
  F[0]=1;
  F[1]=1;
  for(i=2;i<=n;i++){
    F[i] = F[i-2] + F[i-1];
  }
  printf("%d\n",F[n]);
}

int main( ){
  int n;
  scanf("%d",&n);
  fibonacci(n);
  return 0;
}

Measured memory_bytes: 596
//ワーシャルフロイド

#include<bits/stdc++.h>
using namespace std;

const int MAX=100;
const long long INF=(1LL<<32);

int n;
long long dp[MAX][MAX];

void floyd(){
  for (int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      if(dp[i][k]==INF) continue;
      for(int j=0;j<n;j++){
	if(dp[k][j]==INF) continue;
	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	//         [i]から[j]に行く,[i]から[k]を通り、[k]から[j]に行く           
      }
    }
  }
}

int main(){
  int e,u,v,c;
  cin>>n>>e;

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      dp[i][j]=( (i==j) ? 0:INF );
      //        　 その場         
    }
  }

  for(int i=0;i<e;i++){
    cin>>u>>v>>c;
    dp[u][v]=c;//重み
  }

  floyd();

  bool nagative=false;
  
  for(int i=0;i<n;i++){
    if(dp[i][i]<0) nagative=true;
    //負の値がある
  }

  if(nagative){
    cout<<"NEGATIVE CYCLE"<<endl;

  }else{
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(j) cout<<" ";
	if(dp[i][j]==INF) cout<<"INF";
	else cout<<dp[i][j];
      }
      cout<<endl;
    }
  }

  return 0;
}



Measured memory_bytes: 3168
#include <iostream>

using namespace std;

int main(void){
  string s;
  cin >> s;

  for(int i=0; i<s.length(); i++)
    if(s[i] != ',')
      cout << s[i] ;
  //コンマならスペースに置き換えて出力する
    else
      cout << " ";

  //最後の改行
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) obj.begin(),obj.end()
#define pb(obj) push_back(obj)
#define REP(i,N) for(int i=0;i<N;i++)
typedef long long ll;
ll const MOD=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,Q;
    cin>>N>>Q;
    string S;
    cin>>S;
    vector<int>sum(N);
    int count=0;
    REP(i,N-1){
        if(S[i]=='A'&S[i+1]=='C')count++;
        sum[i+1]=count;
    }
    int l,r;
    vector<int>sub;
    REP(i,Q){
        cin>>l>>r;
        sub.pb(sum[r-1]-sum[l-1]);
    }
    REP(i,Q)cout<<sub[i]<<endl;
}


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


template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  int n;
  F f;
  G g;
  T d1;
  E d0;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int n_,F f,G g,T d1,
	      vector<T> v=vector<T>()):
    f(f),g(g),d1(d1){
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  inline T query(int a,int b){
    T vl=d1,vr=d1;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[(l++)-1]);
      if(r&1) vr=f(dat[(--r)-1],vr);
    }
    return f(vl,vr);
  }
  
};

int main(){
    int n;
    cin >> n;
    string S;
    cin >> S;
    SegmentTree<int,int> st(n,
            [](int a,int b){return a | b;},
            [](int a,int b){return b;},
            0);

    for (int i = 0; i < n; i++)
        st.update(i, 1 << (S[i] - 'a'));

    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++){
        int t;
        cin >> t;
        if (t == 1){
            int i;
            char c;
            cin >> i >> c;
            i--;
            st.update(i, 1 << (c - 'a'));
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            cout << __builtin_popcount(st.query(l, r)) << endl;
        }
    }
}

Measured memory_bytes: 5124
#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##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T1, class T2>bool chmax(T1& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<class T1, class T2>bool chmin(T1& a, const T2& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    rep(i, N) cin >> S[i];

    rep(i, N) sort(all(S[i]));

    sort(all(S));

    ll ans = 0;
    for (int i = 0, j; i < N; i = j) {
        for (j = i; j < N; ++j) {
            if (S[i] != S[j]) break;
        }

        ans += (ll)(j - i) * (j - i - 1) / 2;
    }

    write(ans);
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
int main(){
	int N, M, R; 
	long long int INF = 1145141919; 
	cin >> N >> M >> R; 
	long long int C[210][210] = {}; 
	int r[10] = {}; 	
	for(int i = 0; i < R; i++){
		cin >> r[i]; 
	}
    sort(r, r+R); 
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			if(i != j) C[i][j] = INF; 
		}
	}
	for(int i = 0; i < M; i++){
		int a, b;
        long long int c; 
		cin >> a >> b >> c;
		C[a][b] = c, C[b][a] = c; 
	}
	for(int k = 1; k <= N; k++){
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				C[i][j] = min(C[i][j], C[i][k] + C[k][j]); 
			}
		}
	}
	long long int ans = INF; 
	do{
		long long int kyori = 0; 
		for(int i = 0; i < R-1; i++){
			kyori += C[r[i]][r[i+1]];
		}
		ans = min(ans, kyori);
	} while (next_permutation(r, r+R));
	cout << ans << endl; 
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
int i,j,n,k;
char c[1000];
int main(){
	scanf("%s",c+1);n=strlen(c+1);
	for(i=n+1;i;--i){
		for(j=i==n+1?'a':c[i]+1;j<='z';++j){
			for(k=1;k<i;++k)if(c[k]==j)break;
			if(k==i)break;
		}
		if(j<='z')break;
	}
	if(i){
		c[i]=j;c[i+1]=0;puts(c+1);
	}else puts("-1");
	return 0;
}

Measured memory_bytes: 256
def ColIdxToXlName(idx):
    if idx < 1:
        raise ValueError("Index is too small")
    result = ""
    while True:
        if idx > 26:
            idx, r = divmod(idx - 1, 26)
            result = chr(r + ord('a')) + result
        else:
            return chr(idx + ord('a') - 1) + result

print(ColIdxToXlName(int(input())))

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

ll llsqrt(ll n) {
    ll i;
    for(i = 1; n > 0; i++) {
        n -= i * 2 + 1;
    }
    return i;
}

int main() {
    ll N;
    cin >> N;
    ll B;
    for (int A = llsqrt(N); A > 0; --A) {
        if(N % A == 0){
            B = N / A;
            break;
        }
    }
    ll ans = 0;
    while(1){
        ans++;
        B /= 10;
        if(B == 0){
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	intl i,j,n;
	cin>>n;
	intl ans1=0;
	intl ans=0;
	vector<intl> ar(1e5);
	for(i=1;i<1e5;i++){
		ar[i]=i;
		ar[i]*=(i+1);
		ar[i]/=2;
	}
	while(n%2==0){
		n/=2;
		ans+=1;
	}
	ans*=2;
	j=sqrt(ans);
	j*=(j+1);
	if(j<=ans){
		ans1+=sqrt(ans);
	}
	else{
		ans1+=(sqrt(ans)-1);
	}
	// cout<<ans1<<" "<<ans<<" "<<j<<"\n";
	for(i=3;i<=sqrt(n);i+=2){
		ans=0;
		while(n%i==0){
			n/=i;
			ans+=1;
		}
		ans*=2;
		intl y=sqrt(ans);
		y*=(y+1);
		if(y<=ans){
			ans1+=(sqrt(ans));
		}
		else{
			ans1+=(sqrt(ans)-1);
		}
	}
	if(n>1){
		ans1+=1;
	}
	cout<<ans1<<"\n";
}


Measured memory_bytes: 4004
import Control.Applicative
import Data.List

main = do
    getLine
    cs <- map words . lines <$> getContents
    let is = map (map (read :: String -> Int)) cs
    mapM_ putStrLn $ map rrow is ++ [rcol is]

rrow :: [Int] -> String
rrow is = intercalate " " (map show is) ++ " " ++ show (sum is)

rcol :: [[Int]] -> String
rcol is = let rvn = map sum (transpose is)
           in intercalate " " (map show rvn) ++ " " ++ show (sum rvn)


Measured memory_bytes: 5384