akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int n, a[214514];
bool b[214514];
signed main() {
	cin >> n;
	REP(i, n + 1) {
		cin >> a[i];
	}
	vector<int>v;
	for (int i = n; i >= 1; i--) {
		if (a[i] != b[i]) {
			for (int j = 1; j * j <= i; j++) {
				if (i % j)continue;
				if (j * j == i)b[j] = (b[j] + 1) % 2;
				else {
					b[j] = (b[j] + 1) % 2;
					b[i / j] = (b[i / j] + 1) % 2;
				}
			}
			v.push_back(i);
		}
	}
	cout << v.size() << endl;
	for (int i : v)cout << i << " ";
	cout << endl;
}

Measured memory_bytes: 3828
s = input()
n = len(s)

def dfs(i, tmp):
    if i == n-1:
        return sum(list(map(int,tmp.split("+"))))
    
    return dfs(i+1, tmp + s[i+1]) + dfs(i+1, tmp + "+" + s[i+1])

print(dfs(0,s[0]))

Measured memory_bytes: 9196
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
const int MAX_W=8;

struct panel{
  panel(){}
  panel(const panel& pnl){
    REP(i,MAX_W)REP(j,MAX_W)p[j][i]=pnl.p[j][i];
  }
  int p[MAX_W][MAX_W];
};
int w,h,c;

void draw(panel* pnl,int x,int y,int nc){
  int cc=pnl->p[y][x];
  pnl->p[y][x]=nc;
  if(x>0&&pnl->p[y][x-1]==cc)draw(pnl,x-1,y,nc);
  if(x+1<w&&pnl->p[y][x+1]==cc)draw(pnl,x+1,y,nc);
  if(y>0&&pnl->p[y-1][x]==cc)draw(pnl,x,y-1,nc);
  if(y+1<h&&pnl->p[y+1][x]==cc)draw(pnl,x,y+1,nc);
}
int cntRecursive(panel* pnl,int x,int y){
  pnl->p[y][x]=-1;
  int sum=1;
  if(x>0&&pnl->p[y][x-1]==c)sum+=cntRecursive(pnl,x-1,y);
  if(x+1<w&&pnl->p[y][x+1]==c)sum+=cntRecursive(pnl,x+1,y);
  if(y>0&&pnl->p[y-1][x]==c)sum+=cntRecursive(pnl,x,y-1);
  if(y+1<h&&pnl->p[y+1][x]==c)sum+=cntRecursive(pnl,x,y+1);
  return sum;
}
int cnt(panel* pnl){
  panel check(*pnl);
  return cntRecursive(&check,0,0);
}
int dfs(panel* pnl,int depth=1){
  if(depth==5){
    panel pnl_(*pnl);
    draw(&pnl_,0,0,c);
    return cnt(&pnl_);
  }
  int result=0;
  for(int i=1;i<=6;i++){
    if(depth==4&&i==c)continue;
    if(pnl->p[0][0]==i)continue;
    panel pnl_(*pnl);
    draw(&pnl_,0,0,i);
    result=max(result,dfs(&pnl_,depth+1));
  }
  return result;
}
int main(){ _;
  while(cin>>h>>w>>c,(h|w|c)!=0){
    panel pnl;
    REP(i,h)REP(j,w)cin>>pnl.p[i][j];
    cout<<dfs(&pnl)<<endl;
  }
}

Measured memory_bytes: 1204
s = input()
n = len(s)
ans = 0
cntA = 0
for i in range(n-1):
    if s[i] == 'A':
        cntA += 1
    elif s[i: i+2] == 'BC':
        ans += cntA
    elif i > 0 and s[i-1: i+1] == 'BC':
        continue
    else:
        cntA = 0

print(ans)


Measured memory_bytes: 3500
#include <stdio.h>

int main() {
    int n, m, i, maior=0;
    double total=0, conta=0;
    scanf("%d %d", &n, &m);
    int votos[n];
    
    for(i=0; n>i; ++i){
        scanf("%d", &votos[i]);
        total = total + votos[i];
    }
    conta = (total*1)/(4*m);
    for(i=0; n>i; ++i){
        if(votos[i]>= conta){
            maior = maior + 1;
        }    
   }
   if(maior>=m){
       printf("Yes\n");
   }
   else{
       printf("No\n");
   }
    
    return 0;
}


Measured memory_bytes: 128
n,m,x = map(int,input().split())
books = []

for i in range(n):
    book = list(map(int,input().split()))
    books.append(book)

min_money = -1

#n冊あるとき、2**n通りの選び方
count = 0
for i in range(2**n):
    select = format(count, "0" + str(n) + "b")
    lst = []
    while "1" in select:
        index = select.index("1")
        lst.append(books[index])
        select = select.replace("1","0",1)
    for j in range(1,m+1):
        skill = sum([lst[k][j] for k in range(len(lst))])
        if skill < x:
            break
    else:
        sum_money = sum([lst[j][0] for j in range(len(lst))])
        if min_money != -1:
            min_money = min(min_money, sum_money)
        else:
            min_money = sum_money

    count += 1

print(min_money)

Measured memory_bytes: 75020
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
typedef long long ll;
const int mod = 1e9 + 7;
int main() {

    int a, b;
    cin >> a >> b;

    string sa = "";
    rep(i, b){
        sa += to_string(a);
    }

    string sb = "";
    rep(i, a){
        sb += to_string(b);
    }
    
    if(sa > sb)
        cout << sb << endl;
    else
    {
        cout << sa << endl;
    }
    
    return 0;
}

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

using i64 = long long int;

class UnionFindTree {
  private:
    vector<int> par;   // 親
    vector<int> depth; // 木の深さ

  public:
    // n要素で初期化
    UnionFindTree(int n) {
        for (int i = 0; i < n; i++) {
            par.push_back(i);
            depth.push_back(0);
        }
    }

    // 木の根を求める
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    // xとyの属する集合を併合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;

        if (depth[x] < depth[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (depth[x] == depth[y])
                depth[x]++;
        }
    }

    // xとyが同じ集合に属するか否か
    bool same(int x, int y) { return find(x) == find(y); }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> p;
    p.push_back(0);
    for(int i=0;i<n;++i){
        int tmp;
        cin >> tmp;
        p.push_back(tmp);
    }
    UnionFindTree uft = UnionFindTree(n+1);
    for(int i=0;i<m;++i){
        int x, y;
        cin >> x >> y;
        uft.unite(x, y);
    }

    int ans = 0;
    for(int i=1;i<=n;++i){
        if(uft.same(i, p[i]))ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1912
#include<stdio.h>
int main(){
	int a,b,k;
	scanf("%d%d%d", &k,&a,&b);
	
	if((b/k)*k >b || (b/k)*k <a){
		printf("NG");
	} else {
		printf("OK");
	}
	
	return 0;
}

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

using namespace std;

int main() {
	char str[20];

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

	map<string, int> cnt;

	int mx = 0;
	while(n--) {
		scanf(" %s", str);
		mx = max(mx, ++cnt[str]);
	}

	for(const auto &p : cnt) {
		if(p.second == mx) {
			printf("%s\n", p.first.c_str());
		}
	}	
}


Measured memory_bytes: 23808
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <utility>
#include <climits>
#include <iomanip>
using namespace std;
#define MAXSIZE 100005
#define MAXL 100
#define MOD_CONST 1000000007
typedef long long int lli;

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

    if(n <= 2){
        puts("0");
    }else{
        int ans = (n % 2 == 0) ? n / 2 - 1 : n / 2;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 888
from sys import setrecursionlimit
setrecursionlimit(10000000)

def solve():
    N = int(input())
    adj = [list() for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    # path
    goal = N-1
    path = [0]
    candidates = [adj[0][:]]
    while path[-1] != goal:
        while not candidates[-1]:
            candidates.pop()
            path.pop()
        u = candidates[-1].pop()
        candidates.append([n for n in adj[u] if n != path[-1]])
        path.append(u)

    black = path[(len(path)-1)//2]
    white = path[(len(path)-1)//2+1]

    # count
    path = [black]
    candidates = [[n for n in adj[black] if n != white]]
    cnt = 0
    try:
        while True:
            while not candidates[-1]:
                cnt += 1
                candidates.pop()
                path.pop()
            u = candidates[-1].pop()
            candidates.append([n for n in adj[u] if n != path[-1]])
            path.append(u)
    except IndexError:
        pass
    bscore = cnt
    print('Fennec' if bscore*2 > N else 'Snuke')


if __name__ == '__main__':
    solve()

Measured memory_bytes: 81952
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int fact(int n) {
	if (n == 0)return 1;
	return n * fact(n - 1);
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
int a[114514], ans[114514]; int n, k;
signed main() {
	cin >> n >> k;
	rep(i, n)cin >> a[i];
	if (n == 1) {
		if (a[0] == k)puts("POSSIBLE");
		else puts("IMPOSSIBLE");
	}
	else {
		sort(a, a + n);
		ans[0] = gcd(a[0], a[1]);
		for (int i = 1; i < n - 1; i++) {
			ans[i] = gcd(ans[i - 1], a[i + 1]);
		}
		if (a[n - 1] >= k && k%ans[n - 2] == 0)puts("POSSIBLE");
		else puts("IMPOSSIBLE");
	}
	getchar(); getchar(); return 0;
}

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

#define all(v) v.begin(), v.end()
typedef long long ll;
const int INT_INF = 1e9;
const ll INF = 1LL << 30;

int main() {
    int k; cin >> k;
    int a, b; cin >> a >> b;
    for(int i = a; i <= b; i++){
        if(i % k == 0){
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h> 
using namespace std;
//#define int long long
const int MOD=1000000007;
signed main(){
    int n;
    vector<string> s,c;
    string a;
    int m=0;
    map<string,int> q;
    cin>>n;
    for(int i=0;i<n;i++){
	cin>>a;
	s.push_back(a);
    }
    sort(s.begin(),s.end());
    for(int i=0;i<n;i++){
	q[s[i]]++;
	if(q[s[i]]==1) c.push_back(s[i]);
	m=max(m,q[s[i]]);
    }
    for(int i=0;i<c.size();i++){
	if(m==q[c[i]]) cout<<c[i]<<"\n";
    }
}


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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
	string S; cin >> S;
	string T, ans = "YES";
	int i = S.size() - 1;
	while(i >= 0) {
		if(S[i] != 'm' && S[i] != 'r' && S[i] != 'e') {
			ans = "NO"; break;
		}
		string s;
		if(S[i] == 'm') {
			if(i - 4 < 0) {
				ans = "NO"; break;
			}
			s = S.substr(i - 4, 5);
			if(s == "dream") i -= 5;
			else {
				ans = "NO"; break;
			}
		}
		else if(S[i] == 'e') {
			if(i - 4 < 0) {
				ans = "NO"; break;
			}
			s = S.substr(i - 4, 5);
			if(s == "erase") i -= 5;
			else {
				ans = "NO";
				break;
			}
		}
		else if(S[i] == 'r') {
			if(i - 5 < 0) {
				ans = "NO"; break;
			}
			else {
				s = S.substr(i - 5, 6);
				if(s == "eraser") i -= 6;
				else {
					if(i - 6 < 0) {
						ans = "NO"; break;
					}
					else {
						s = S.substr(i - 6, 7);
						if(s == "dreamer") i -= 7;
						else {
							ans = "NO"; break;
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3764
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PPI;
typedef pair<ll,P> PIP;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define PQ2(T) priority_queue<T>
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define REP(i,a,b) for(ll (i)=a;(i)<(ll)(b);++(i))
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) ((x)=min((x),(y)))
#define chmax(x,y) ((x)=max((x),(y)))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
#define DEBUG(x) cerr<<"line ("<<__LINE__<<")  "<<#x<<": "<<x<<endl;
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	ll n, k;
	cin>>n>>k;
	if(k==0){
		cout<<n*n<<endl;
		return 0;
	}
	ll res = 0;
	for(ll b = k+1; b <= n; b++){
		ll s = n/b;
		res += s*(b-k);
		ll t = n%b;
		if(t>=k) res += t-k+1;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split())) 
count = 0

for i in range(1,N-1):
  if(A[i]>A[i-1] and A[i]<A[i+1]):
    count+=1
  elif(A[i]<A[i-1] and A[i]>A[i+1]):
    count+=1
print(count)

Measured memory_bytes: 3060
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
def BFS(dq):
    while dq:
        e = dq.popleft()
        visited[e] = True
        for i in G[e]:
            if not visited[i]:
                P[i] += P[e]
                dq.append(i)

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N-1)]
PX = [tuple(map(int,input().split())) for _ in range(Q)]

G = [[] for _ in range(N)]
for a,b in AB:
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# 各頂点が "カウンター増加の根" として直接増加する数
P = [0]*N
for p,x in PX:
    P[p-1] += x

# 訪問済みフラグ
visited = [False]*N
visited[0] = True

Ans = [0]*N
from collections import deque
BFS(deque([0]))

print(*P)

Measured memory_bytes: 110472
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int n,k;
long long ans;
int a[200005];
int cmp(int a,int b)
{
	return a>b;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(i>k)
		ans+=a[i]; 
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

long long f(long long a) {
    long long k = (a+1) / 2;
    long long t, s;

    if (k%2 == 0) t = 0;
    else t = 1;
   
    if ((a+1)%2 == 0) s = 0;
    else s = a;

    return t ^ s;
}


int main() {
    long long a, b; cin >> a >> b;
    cout << (f(a-1) ^ f(b)) << endl;
    return 0;
}



Measured memory_bytes: 256
#include<iostream>

using namespace std;

int ans = 0;
void dfs(int n,int s,int d){
	if (s < 0) return;
	if (s == 0 and n == 0){
		ans++;
		return;
	}
	if (n == 0) return;	
	d++;
	if (d == 10)return;
//	cout << "n=" << n;
//	cout << " s=" << s;
//	cout << " d=" << d <<  endl;
	//???????????´???
	dfs(n-1,s-d,d);
	//?????°????????£?????´???
	dfs(n,s,d);
return;
}

int main(){
	int n,s; cin >> n >> s;
	while (!(n == 0 and s == 0)){
		dfs(n,s,-1);
		cout << ans << endl;
		ans = 0;
		cin >> n >> s;
	}

return 0;
}

Measured memory_bytes: 3088
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()

  if n==1:
    return m

  a=0
  for i in range(1,int(math.sqrt(m))+1):
    if m%i==0:
      if m>=i*n:
        a=max(a,i)
      if m>=m//i*n:
        a=max(a,m//i)

  return a

# main()
print(main())


Measured memory_bytes: 5460
from math import sqrt

N = int(input())

x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

sum = 0
for i in range(N):
    for j in range(N):
        if i != j:
            sum = sum + sqrt( (x[i] - x[j])*(x[i] - x[j])+(y[i] - y[j])*(y[i] - y[j]) )

print (sum/N)

Measured memory_bytes: 3064
n,k=map(int,input().split())

A=[int(i) for i in input().split()]
CP=A[:]
R=[0 for i in range(n)]

suma=sum(A)
cnt=0
for i in range(n):
    zak=A[i]*k//suma
    R[i]=zak
    cnt+=zak
    A[i]=A[i]/(zak+1)

A=[(-CP[i]/(R[i]+1),CP[i],R[i]) for i in range(n)]

import heapq
import math

heapq.heapify(A)
for i in range(k-cnt):
    now=heapq.heappop(A)
    newr=now[2]+1
    newz=now[1]/(newr+1)
    heapq.heappush(A,(-newz,now[1],newr))

print(math.ceil(-heapq.heappop(A)[0]))

Measured memory_bytes: 123184
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <map>
#include <fstream>
#include <array>
#include <utility>
#include <functional>

using namespace std;
typedef long long Int;
#define REP(i , x) for(int i = 0 ; i < x ; ++i)

typedef pair<int, int> P;

int main()
{
	int n, m;
	while (cin >> n >> m, n&&m){
		vector<P> dp(m);
		REP(i, m){
			dp[i].first = dp[i].second = 0;
		}
		REP(i, n){
			REP(j, m){
				int a;
				cin >> a;
				dp[j].first -= a;
				dp[j].second = j;
			}
		}
		sort(dp.begin(), dp.end());
		REP(i,m){
			cout << dp[i].second + 1;
			if (i != m - 1)
				cout << " ";
		}
		cout << endl;
	}
	return 0;
}

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#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 FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



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

    vector<ll> v(n);
    for(auto&& i : v) cin >> i;

    vector<vector<int>> cnt(n);

    REP(i, n){
        ll a = i - v[i];
        if(a >= 0) cnt[a].push_back(i);
    }
    
    ll ans = 0;

    REP(i, n){
        ll a = v[i] + i;
        if(a >= n) continue;
        ans += cnt[a].end() - upper_bound(all(cnt[a]), i);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 13360
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	int n,a,b,c,d,i;
	string s;
	cin >> n >> a >> b >> c >> d;
	cin >> s;
	--a; --b; --c; --d;
	s.push_back('.');
	if(c==d){
		cout << "No" << endl;
		return 0;
	}
	for(i=a; i<c; ++i){
		if(s[i]=='#' && s[i+1]=='#'){
			cout << "No" << endl;
			return 0;
		}
	}
	for(i=b; i<d; ++i){
		if(s[i]=='#' && s[i+1]=='#'){
			cout << "No" << endl;
			return 0;
		}
	}
	if(c<d){
		cout << "Yes" << endl;
		return 0;
	}
	for(i=b; i<=d; ++i){
		if(s[i-1]=='.' && s[i]=='.' && s[i+1]=='.'){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        int n = std.nextInt();
        int left = 1;
        int right = n - 1;
        if (n < 2) {
            System.out.println(0);
            return;
        }

        long ans = 0;
        while (left < right) {
            left++;
            right--;
            ans++;
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 22608
n = int(input())
xy = list(list(map(int, input().split())) for _ in range(n))

#print(n, xy)
x_minus_y = []
x_plus_y = []
for i in range(n):
    x_minus_y.append(xy[i][0] - xy[i][1])
    x_plus_y.append(xy[i][0] + xy[i][1])
x_max = max(x_minus_y)
x_min = min(x_minus_y)
y_max = max(x_plus_y)
y_min = min(x_plus_y)

if x_max - x_min >= y_max - y_min:
    print(x_max - x_min)
else:
    print(y_max - y_min)


Measured memory_bytes: 61396
#include <iostream>

int dice[3] = {1, 2, 3};


void cycle(int i, int j) {
  int temp;
  temp = dice[i];
  dice[i] = 7 - dice[j];
  dice[j] = temp;
}

void init() {
  for (int i = 0; i < 3; i ++)
    dice[i] = i + 1;
}


int main() {
  int n, i;
  int sum;
  std::string op;

  while (std::cin >> n) {
    if (n == 0) break;
    sum = 1;
    init();
    for (i = 0; i < n; i ++) {
      std::cin >> op;
      switch (op[0]) {
        case 'N':
          cycle(1, 0);
          break;
        case 'E':
          cycle(0, 2);
          break;
        case 'W':
          cycle(2, 0);
          break;
        case 'S':
          cycle(0, 1);
          break;
        case 'R':
          cycle(2, 1);
          break;
        case 'L':
          cycle(1, 2);
          break;
      }
      sum += dice[0];
    }
    std::cout << sum << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 3128
#include <iostream>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;
void tolow(char *a);
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int age,price;
  cin>>age>>price;
  if(age>=13)
    cout<<price<<'\n';
  else if(age>5 && age<13)
    cout<<price/2<<'\n';
  else
    cout<<"0\n";
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <vector>
#define N 100005
using namespace std;

int n, m, cnt, s, b[N], v[N];
vector<int> a[N];
void f(int p) {
	int i;
	if (v[p]) return;
	v[p] = cnt;
	for (i = 0; i < a[p].size(); i++) {
		f(a[p][i]);
	}
}
int main()
{
	int i, j, t1, t2;
	cin >> n >> m;
	for (i = 1; i <= n; i++) scanf ("%d", &b[i]);
	while (m--) {
		scanf ("%d %d", &t1, &t2);
		a[t1].push_back(t2);
		a[t2].push_back(t1);
	}
	for (i = 1; i <= n; i++) {
		if (!v[i]) {
			cnt++;
			f(i);
		}
	}
	for (i = 1; i <= n; i++) {
		if (v[b[i]] == v[i]) s++;
	}
	cout << s;
    return 0;
}


Measured memory_bytes: 8576
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cfloat>
#include <algorithm>
#include <numeric>
#include <vector>
#include <iterator>
#include <set>
#include <map>
using namespace std;

const double PI=acos(-1);

int main(){
    int n;
    cin >> n;
    long ans = 1;
    for(int i = 1; i <= n; i++){
        ans = (ans * i) % 1000000007;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c) 
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<string> svec;

int main(){
    ull n,p;
    int ans=0;
    cin>>n;
    for(ull i=(ll)sqrt(n);i>=1;i--){
        if(n%i==0){
            p=n/i;
            break;
        }
    }
    while(p!=0){
        p/=10;
        ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 256
import numpy as np
N =int(input())
A_B = []
for i in range(N):
    A_B.append(list(map(int,input().split())))
if N % 2 == 1:
    A_B = np.array(A_B).T.tolist()
    min_array = A_B[0]
    min_array.sort()
    min_ = min_array[N // 2]
    max_array = A_B[1]
    max_array.sort()
    max_ = max_array[N // 2]
    print(max_ - min_ + 1)
else:
    A_B = np.array(A_B).T.tolist()
    
    min_array = A_B[0]
    min_array.sort()
    min_ = [min_array[N // 2],min_array[N // 2 - 1]]
    max_array = A_B[1]
    max_array.sort()
    max_ = [max_array[N // 2],max_array[N // 2 - 1]]
    print(max_[0] + max_[1] - min_[0] - min_[1] + 1)

Measured memory_bytes: 82396
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const int EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M, K;
	cin >> N >> M >> K;
	REP(i, N + 1) {
		REP(j, M + 1) {
			int black = i * M + j * N - 2 * (i * j);
			if (black == K) {
				cout << "Yes" << endl;
				PAU;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 504
#include<bits/stdc++.h>
using namespace std;
//max=({});

int main() {
	int n;
	cin >> n;
	vector<long long>A(n);
	for (int i = 0;i < n;++i) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	long long ans = A[n-1] - A[0];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool fail() {
    cout << "UNSAFE" << endl;
    return true;
}

bool solve() {
    int N;
    cin >> N;
    if (N == 0) return false;

    string S;
    cin >> S;

    vector<vector<bool>> dp(1 << 10, vector<bool>(10, false));
    // dp[A][B] <=> Aをreserveした状態でBをlockしたいような状況にできる

    // 入力の処理
    int bit = 0;
    for (char c : S) {
        if (c == 'u') {
            bit = 0;
        } else {
            int ci = c - '0';
            int b = 1 << ci;

            // 同じ区間に同じ数字があったらアウト
            if ((b & bit) != 0) return fail();

            dp[bit][ci] = true;
            bit |= (1 << ci);
        }
    }

    // AとC: reserveしている資源
    // BとD: lockしたい資源
    // dp[A][B]かつdp[C][D]でB in Cならdp[A|C][D]もtrue
    for (int A = 0; A < (1 << 10); ++A) {
        for (int B = 0; B < 10; ++B) {
            if (!dp[A][B]) continue;

            for (int C = 0; C < (1 << 10); ++C) {
                if ((A & C) || !((C >> B) & 1)) continue;
                // reserveする資源が重複するケースを弾く

                for (int D = 0; D < 10; ++D) {
                    if (!dp[C][D]) continue;
                    dp[A | C][D] = true;
                }
            }
        }
    }

    // dp[A][B]かつdp[C][D]でB in C, D in Aならデッドロック
    for (int A = 0; A < (1 << 10); ++A) {
        for (int B = 0; B < 10; ++B) {
            if (!dp[A][B]) continue;

            for (int C = 0; C < (1 << 10); ++C) {
                if (A & C) continue;
                // reserveする資源が重複するケースを弾く
                for (int D = 0; D < 10; ++D) {
                    if (!dp[C][D]) continue;

                    if (((A >> D) & 1) && ((C >> B) & 1)) {
                        return fail();
                    }
                }
            }
        }
    }

    cout << "SAFE" << endl;
    return true;
}

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



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

typedef struct 
{
  char task[10];
  int time;
}t_queue;

t_queue q[100000];

int head = 0;
int tail = 0;

void enqueue(char name[], int time)
{
  strcpy(q[head].task, name);
  q[head].time = time;
  head++;
  if(head > 100000-1) head = 0;
}

t_queue deque(void)
{
  t_queue data;
  data = q[tail];
  tail++;
  if(tail > 100000-1) tail = 0;
  return data;
}

int main(int argc, char const *argv[])
{
  int n, quontime, task_time;
  char task_name[10];
  int total_time = 0;

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

  for(int i = 0; i < n; i++){
    scanf(" %s %d",task_name,&task_time);
    enqueue(task_name, task_time);
  }

  while(head != tail){
    t_queue now_q = deque();
    if(now_q.time - quontime > 0){
      total_time += quontime;
      now_q.time -= quontime;
      enqueue(now_q.task, now_q.time);
    } else {
      total_time += now_q.time;
      printf("%s %d\n", now_q.task, total_time);
    }
  }

  return 0;
}



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

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

    int A[110];
    for (int i=0; i < N; i++){
        cin >> A[i];
    }
    
    int max;
    int min;
    max = *max_element(begin(A), A+N);
    min = *min_element(begin(A), A+N);
    cout << (max - min) << endl;
}


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

struct node{
    int a;
    vector<int> to;
    int ans;
};
stack<pair<int,int>> s;
void dfs(int v, int p, vector<node> &nodes, vector<int> &dp){
    int changed=distance(dp.begin(),lower_bound(dp.begin(),dp.end(), nodes[v].a));
    s.push(make_pair(changed,dp[changed]));
    dp[changed]=nodes[v].a;
    for (int i = 0; i < nodes[v].to.size(); i++){
        int v_to=nodes[v].to[i];
        if(v_to==p)continue;
        dfs(v_to, v, nodes, dp);
    }
    nodes[v].ans=(int)distance(dp.begin(),lower_bound(dp.begin(),dp.end(),INF));
    dp[s.top().first]=s.top().second;
    s.pop();
}
int main() {
    int N;
    cin>>N;
    vector<node> nodes(N);
    vector<int> dp(N,INF);
    for (int i = 0; i < N; i++)cin>>nodes[i].a;
    for (int i = 0; i < N-1; i++){
        int u,v;
        cin>>u>>v;
        nodes[u-1].to.push_back(v-1);
        nodes[v-1].to.push_back(u-1);
    }
    dfs(0,-1,nodes,dp);
    for (int i = 0; i < N; i++){
        cout<<nodes[i].ans<<endl;
    }
}

Measured memory_bytes: 33660
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int s=0,a,b,c,x[1000000];
    cin>>a>>b>>c;
    for(int i=1;i<=a;i++)
    cin>>x[i];
    for(int i=1;i<=a;i++)
    {
        if(x[i]<b||x[i]>=c)
        s++;
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Work[] works = new Work[n];
		for (int i = 0; i < n; i++) {
			works[i] = new Work(sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(works, new Comparator<Work>() {
		public int compare(Work w1, Work w2) {
			return w1.end - w2.end;
		}
		});
		int total = 0;
		for (int i = 0; i < n; i++) {
			total += works[i].time;
			if (total > works[i].end) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}
	
	static class Work {
		int time;
		int end;
		
		public Work(int time, int end) {
			this.time = time;
			this.end = end;
		}
	}
}


Measured memory_bytes: 103444
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

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

	int a, b, h;
	cin >> a >> b >> h;
	cout << (a + b) *h / 2 << endl;



	return 0;
}

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

typedef long long ll;
typedef long double ld;

#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

int main(){

    string n;

    cin >> n;

    replace(all(n), '1', 't');
    replace(all(n), '9', '1');
    replace(all(n), 't', '9');

    cout << n << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)









int main(){
    ll n;
    string s, t;
    cin >> n >> s >> t;
    string ans = "";
    REP(i, n){
        ans += s[i];
        ans += t[i];
    }
    cout << ans << endl;
}

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

int h,w;
std::vector<std::vector<bool>> map;

struct Pt
{
    int y;
    int x;
    int depth;
};
std::vector<std::pair<int,int>> dir = {{0,1},{1,0},{-1,0},{0,-1}};

int bfs(int y, int x){
    std::vector<std::vector<bool>> seen(h + 2,std::vector<bool>(w + 2));
    std::queue<Pt> que;
    que.push({y,x,0});
    seen[y][x] = true;
    int max = 0;
    while(que.size()){
        Pt cur = que.front();
        que.pop();
        max = std::max(cur.depth,max);
        for(int i = 0; i < 4; i++){
            if(map[cur.y + dir[i].first][cur.x + dir[i].second] && !seen[cur.y + dir[i].first][cur.x + dir[i].second]){
            que.push({cur.y + dir[i].first, cur.x + dir[i].second, cur.depth + 1});
            seen[cur.y + dir[i].first][cur.x + dir[i].second] = true;
            }
        }
    }
    return max;
}


int main()
{
    std::cin >> h >> w;
    map.resize(h + 2, std::vector<bool>(w + 2));
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            char a;
            std::cin >> a;
            map[i][j] = a == '.';
        }
    }

    int max = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(map[i][j])
            max = std::max(max,bfs(i,j));
        }
    }
    std::cout << max << std::endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define what_is(x) cerr << #x <<" is " << x << endl;
typedef long long ll;
const int MOD = 998244353;
const double PI = 3.14159265358979;
const int INF =  1e9 + 7;
const int nax = 100005;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	// cin >> tc;
	while (tc--) {
		int n, k;
		cin >> k;
		string s;
		cin >> s;
		n = s.length();
		if (n <= k) {
			cout << s;
		}
		else {
			for (int i = 0; i < k; i++)
				cout << s[i];
			cout << "...";
		}


	}
	return 0;
}




















Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define int long long
#define moder (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), moder - 2, moder) % moder * mod_pow(kai(y), moder - 2, moder) % moder;
}
/*--------Library Zone!--------*/


signed main() {
	int k, s;
	int ans = 0;
	cin >> k >> s;
	rep(i, k + 1) {
		rep(j, k + 1) {
			if (s - i - j <= k && s - i - j >= 0) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
using System;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            var arg = Console.ReadLine().Split();
            var time = Double.Parse(arg[2]) + 0.5;
            var div = time / Double.Parse(arg[0]);
            var bisNumber = Math.Truncate(div);
            Console.WriteLine(int.Parse(arg[1]) * bisNumber);
        }
    }
}


Measured memory_bytes: 13140
import java.io.*;
import java.util.*;
 
public class Main {
    static ContestScanner in;
    static Writer out;
    public static void main(String[] args) {
        Main main = new Main();
        try {
            in = new ContestScanner();
            out = new Writer();
            main.solve();
            out.close();
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
 
    void solve() throws IOException {
    	String s = in.nextToken();
    	if (s.contains("9")) {
    		System.out.println("Yes");
    	} else {
    		System.out.println("No");
    	}
    }
 
}

@SuppressWarnings("serial")
class MultiSet<T> extends HashMap<T, Long>{
    @Override public Long get(Object key){return containsKey(key)?super.get(key):0L;}
    public void add(T key,long v){put(key,get(key)+v);}
    public void add(T key){put(key,get(key)+1);}
    public void sub(T key){final long v=get(key);if(v==1)remove(key);else put(key,v-1);}
    public MultiSet<T> merge(MultiSet<T> set)
    {MultiSet<T>s,l;if(this.size()<set.size()){s=this;l=set;}else{s=set;l=this;}
        for(Entry<T,Long>e:s.entrySet())l.add(e.getKey(),e.getValue());return l;}
}
 
class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException{super(System.out);}
}
class ContestScanner implements Closeable{
    private BufferedReader in;private int c=-2;
    public ContestScanner()throws IOException
    {in=new BufferedReader(new InputStreamReader(System.in));}
    public ContestScanner(String filename)throws IOException
    {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException
    {return Double.parseDouble(nextToken());}
    public void close() throws IOException {in.close();}
}

Measured memory_bytes: 23252
#include<iostream>
using namespace std;
int main(){
  int q,c[105],a[105],n[105],sum[105];
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>c[i]>>a[i]>>n[i];
    sum[i]=0;
    while(c[i]>=1 && a[i]>=1 && n[i]>=1){
      sum[i]++;
      c[i]--;
      a[i]--;
      n[i]--;
    }
    while(c[i]>=2 && a[i]>=1){
      sum[i]++;
      c[i]-=2;
      a[i]--;
    }
    while(c[i]>=3){
      sum[i]++;
      c[i]-=3;
    }
    cout<<sum[i]<<"\n";
  }
  return 0;
}


Measured memory_bytes: 3104
n = int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))
m = abs(t - 0.006*h[0] - a)
k = 0
for i in range(1, n):
 x = abs(t - 0.006*h[i] - a)
 if x < m:
  m = x
  k = i
print(k+1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define vl vector<ll>
#define pll pair<ll,ll>
#define mll map<ll, ll> 
#define rep(i,a)  for(ll i= 0;i < a;i++)
#define rep1(i,a) for(ll i= 1;i < a;i++)
#define foi(i, a, b)    for(ll i = a; i<b ; i++)
#define fod(i, a, b)    for(ll i = a; i>=b ; i--)
#define pb push_back
#define sz(v) v.size()
#define all(a) a.begin(), a.end()
#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)
#define MAX 1000005
#define MOD 1000000007
#define el "\n"
const ll INF = 2e9+5;
  
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}
ll isPrime(ll n){if(n<=3) return 1;if(n%2==0||n%3==0) return 0;
for(ll j=5;j*j<=n;j+=6){if(n%j == 0||n%(j+2) == 0) return 0;}return 1;}
 
using namespace std;
void solve(){
   ll n,w;
   cin>>n>>w;
   vl wt(n),v(n);
   rep(i,n)cin>>wt[i]>>v[i];
   vl dp(w+1,0);
   rep(i,n+1){
      for(ll j=w-wt[i];j>=0;j--)
         dp[wt[i]+j] = max(dp[wt[i]+j],v[i]+dp[j]);
   }
   cout<<*max_element(all(dp));
}
 
int main() {
   #ifndef ONLINE_JUDGE
      freopen("input.txt", "r" , stdin);
      freopen("output.txt", "w" , stdout);
   #endif
   ios::sync_with_stdio(0); 
   cin.tie(0); cout.tie(0);   
   ll t;
   // cin>>t;
   t = 1;
   ll tc=0;
   while(tc++<t){
      // cout<<"Case #"<<tc<<": ";
      solve();
   }
   cerr<<"Time taken : "<<(double)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
   return 0;
}

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<string> vs;
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);

int main() {
    int N, M;
    cin >> N >> M;
    vvi v(N + 1);
    rep(i, M){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<bool> checked(N + 1, false);
    queue<int> q;
    q.push(1);
    vi ans(N + 1);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        checked[now] = true;
        for (int x: v[now]){
            if (!checked[x]){
                ans[x] = now;
                checked[x] = true;
                q.push(x);
            }
        }
    }
    cout << "Yes" << endl;
    rep2(i, 2, N + 1){
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 10192
#include<cstdio>
#define neko 510
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
int n,m,h,w,a[neko][neko],sum,p=2333;
int main()
{
	//特殊点是h*w的时候，普通点的1权重较小，当特殊点数大于后面多余的格子个数的时候就凉了
	scanf("%d%d%d%d",&n,&m,&h,&w);
	for(register int i=h;i<=n;i+=h)
	 for(register int j=w;j<=m;j+=w)
	  a[i][j]=-(h*w-1)*p-1;
	f(i,1,n)
	 f(j,1,m)
	  if(!a[i][j])a[i][j]=p,sum+=p;
	  else sum+=a[i][j];
	if(sum<=0)return printf("No\n"),0;
	printf("Yes\n");
	f(i,1,n)
	 f(j,1,m)printf("%d%c",a[i][j],j^m?' ':'\n');
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
typedef long long ll;
int modpow(int a,int b){
    if(!b)return 1;
    if(b%2)return modpow(a,b-1)*a%MOD;
    return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int fac(int a){
    int Ans=1;
    for(int i=1;i<=a;i++){
        Ans*=i;
        Ans%=MOD;
    }
    return Ans;
}//kaijo
int comb(int a,int b){
    return fac(a)*modpow(fac(a-b),MOD-2)%MOD*modpow(fac(b),MOD-2)%MOD;
}
string s;
ll cnt=0;
ll ans=0;
int main(){
    cin>>s;
    rep(i,s.size()){
        if(s[i]=='B')cnt++;
        else ans+=cnt;
    }
    cout<<ans<<endl;
    return 0;
    
}

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

int main(void){
    int MOD = 1000000007;
    long long s,c,cc,ctc;
    cin>>s>>c;
    cc=c/2;
    if(s>=cc){
        cout<<cc<<endl;
    }else{
        cc-=s;
        s+=cc/2;
        cout<<s<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    // 順列の要素数、並べ替えの長さ
	int n,k;
	cin >> n >> k;

    // 入力値から想定順列数を作成
	int ans = n - k + 1;
    int last = n;
    int count = 0;
	bool t = false;
	vector<int> p(n);
	set<int> s;

    // pの数だけループする
	for (int i = 0; i < n; i += 1) {
		cin >> p[i];

        // 線形に参照してき、前の要素と比較して降順の場合カウントアップする
		if (p[i] > last) {
			count += 1;
		} else {
            count = 1;
        }
        last = p[i];

        // 並び替える範囲を維持する
		if(i >= k){
			s.erase(p[i-k]);
		}

        // ソートしなくても昇順に並んでいた場合
		if (count >= k) {
			t = true;
			ans--;

        // 昇順にならんでいない場合
		} else if(i >= k) {
            // ●[○ソート範囲□]■　←　●と○、□と■を比較する
            // ソートして一番小さい値と、直前まで入れていた要素を比較する
            // また、ソートして一番大きい値と、次にいれる要素を比較する。
			if (p[i-k] < *s.begin() && p[i] > *s.rbegin()) {
				ans--;
			}
		}
		s.insert(p[i]);
	}
	ans += t;
	cout << ans << endl;
}

Measured memory_bytes: 10368
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
As = set(As)
MOD = 1000000007

cache = dict()
def n_steps(n):
    if n not in cache:
        if n in As:
            value = 0
        
        elif n in {0, 1}:
            value = 1

        else:
            value = n_steps(n - 1) + n_steps(n - 2)
            value %= MOD

        cache[n] = value
    return cache[n]

for i in range(N):
    n_steps(i)
print(n_steps(N))

Measured memory_bytes: 25332
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    int n = 0;
    int w = 0;
    std::cin >> n >> w;
    
    std::vector<std::vector<long long>> total(n + 1, std::vector<long long>(w + 1));
    
    int weight = 0;
    int value = 0;
    
    for(int nindex = 1; nindex <= n; ++nindex)
    {
        std::cin >> weight >> value;
        for(int windex = 1; windex <= w; ++windex)
        {
            if(windex < weight)
            { // 入れられない
                total.at(nindex).at(windex) = total.at(nindex - 1).at(windex);
            }
            else
            { //入れられる
                total.at(nindex).at(windex)
                    = (std::max)(total.at(nindex - 1).at(windex),
                                 total.at(nindex - 1).at(windex - weight) + value);
            }
        }
    }
    std::cout << total.back().back() << std::endl;
}

Measured memory_bytes: 80256
from itertools import permutations
def main():
    N,M = map(int, input().split())
    edge = [[False]*N for _ in range(N)]
    for i in range(M):
        a,b = map(lambda x:x-1, map(int, input().split()))
        edge[a][b] = True
        edge[b][a] = True
    ans = 0
    for perm in permutations([i for i in range(1,N)]):
        arrived = [False]*N
        flag = False
        prev = 0
        for p in perm:
            # edgeが存在しない
            if not edge[prev][p]:
                flag = True
                break
            # edgeが存在
            else:
                # 過去に訪れた
                if arrived[p]:
                    flag = True
                    break
                else:
                    arrived[p] = True
            prev = p
        if not flag:
            ans += 1
    print(ans)
main()


Measured memory_bytes: 3064