akhauriyash/Code-Regression huggingface dataset:
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    N = ii()
    H = lmi()
    F = [0] * N # flowers

    cnt = 0
    l, r = 0, 0
    while True:
        while H[l] == F[l]:
            l += 1
            if l == N:
                break
        if l == N:
            break
        for i in range(l, N):
            if H[i] == F[i]:
                r = i
                break
            if i == N-1:
                r = N
        for i in range(l, r):
            F[i] += 1
        cnt += 1
    
    print(cnt)

    return

main()


Measured memory_bytes: 9164
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<string>
#include<stack>
#include<queue>
using namespace std;

typedef long long ll;

template<class T>inline bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

ll N,W;
ll w[110],v[110];
ll dp[110][100010];

int main(){
	cin>>N>>W;
	for(int i=0;i<N;i++)cin>>w[i]>>v[i];
	for(int i=0;i<N;i++){
		for(int sum=0;sum<=W;sum++){
			if(sum-w[i]>=0){
				chmax(dp[i+1][sum],dp[i][sum-w[i]]+v[i]);
			}
			chmax(dp[i+1][sum],dp[i][sum]);
		}
	}
	cout<<dp[N][W]<<endl;
}

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

int main() {
  int n, k;
  int x[100];

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

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

  int cost = 0;
  for (int i = 0; i < n; i++) {
    cost += 2 * (abs(x[i] - k) < x[i] ? abs(x[i] - k) : x[i]);
  }

  printf("%d\n", cost);
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<string> s(n);
        for(int i=0; i<n; ++i){
            cin >> s[i];
            replace(s[i].begin(), s[i].end(), '.', ' ');
        }

        for(int i=n-1; i>=0; --i){
            int j = s[i].rfind(' ');
            if(j == string::npos)
                continue;

            s[i][j] = '+';
            for(int k=i-1; ; --k){
                if(s[k][j] != ' ' || s[k][j+1] != ' ')
                    break;
                s[k][j] = '|';
            }
        }

        for(int i=0; i<n; ++i)
            cout << s[i] << endl;
    }
}

Measured memory_bytes: 1852
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    A, B, C, D = map(int, input().split())
    for i in range(1000):
        C -= B
        if C<=0:
            fg = True
            break
        A -= D
        if A<=0:
            fg = False
            break
    if fg:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Measured memory_bytes: 9184
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i>n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない


int n;
int ans = INF;

void bank(int rest, int time) {

	int six = 6, nine = 9;

	if (rest <= 5) {
		if (rest < 0) { cout << rest << endl; }
		ans = min(ans, time + rest);
		return;
	}
	else {
		while (six * 6 <= rest) { six = six * 6; }
		while (nine * 9 <= rest) { nine = nine * 9; }
		if(rest-nine>=0)bank(rest - nine, time + 1);
		if(rest-six>=0)bank(rest-six, time+1);
	}

	return;
}

int main() {

	cin >> n;

	if (n <= 5) {
		ans = n;
	}
	else {
		bank(n,0);
	}

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

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int i, j;
	int a[2][102];
	for (i = 0; i < 2; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &a[i][j]);
	int ans = 0, x;
	for (i = 0; i < n; i++)
	{
		x = 0;
		for (j = 0; j <= i; j++)
			x += a[0][j];
		for (j = i; j < n; j++)
			x += a[1][j];
		if (ans < x)
			ans = x;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
inline void read(rel &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  x=f?x:-x;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;

int main(){
int a=read(),b=read();
write(a*a-b);
}

Measured memory_bytes: 256
parseInt(x) = parse(Int,x)
function division(x)
	y = Int[]
	i = 2
	while x > 1 || i <= sqrt(x)
		if x%i == 0
			push!(y, i)
			x = div(x, i)
		else
			i += 1
		end
	end
	return(y)
end

function main()
	n = parseInt(readline())
	x = Int[]
	for i in 1:n
		append!(x,division(i))
	end
	d = Dict{Int,Int}()
	for i in 1:length(x)
		if haskey(d,x[i])
			d[x[i]] += 1
		else
			d[x[i]] = 1
		end
	end
	two = 0
	four = 0
	ft = 0
	tf = 0
	sf = 0
	for i in values(d)
		if i >= 74
			sf += 1
		end
		if i >= 24
			tf += 1
		end
		if i >= 14
			ft += 1
		end
		if i >= 4
			four += 1
		end
		if i >= 2
			two += 1
		end
	end
	a0 = max(tf * (two-1),0)
	a1 = max(ft * (four-1),0)
	a2 = max(div((four)*(four-1),2)*(two-2),0)
	print(a0+a1+a2+sf)
end
main()

Measured memory_bytes: 112388
#![allow(non_snake_case)]

use std::io::*;

#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

pub fn main() {
    let S = rl();
    let T = rl();
    println!(
        "{}",
        if format!("{}{}", S, S).contains(&T) {
            "Yes"
        } else {
            "No"
        }
    );
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <ctype.h>

int main(void) {
  char s[3][101];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 101; j++) {
      s[i][j] = '\0';
    }
  }

  scanf("%s", s[0]);
  scanf("%s", s[1]);
  scanf("%s", s[2]);

  char player[4] = "abc";
  char turn = player[0];
  for ( ; ; ) {
    for (int i = 0; i < 3; i++) {
      if (turn == player[i]) {
	if (s[i][0] == '\0') {
	  printf("%c\n", toupper(player[i]));
	  return 0;
	}
	turn = s[i][0];
	for (int j = 0; j + 1 < 101; j++) {
	  s[i][j] = s[i][j + 1];
	}
	s[i][100] = '\0';
	break;
      }
    }
  }
  
  return 0;
}


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

int main() {
  int a,b,c;cin >> a >> b >> c;
  if(b>=a*c){
    cout << c << endl;
  }else{
    cout << b/a << endl;
  }
}

Measured memory_bytes: 256
using System;

namespace aoj6
{
    class Program
    {
        static void Main(string[] args)
        {
            /*S:0 H:1 C:2 D:3*/

            int n = int.Parse(Console.ReadLine());
            bool[,] cardset = new bool[4,13];

            for( int i = 0; i < n; i++)
            {
                string[] card = (Console.ReadLine()).Split(' ');
                int num = int.Parse(card[1]) - 1;
                switch (card[0])
                {
                    case "S":
                        cardset[0, num] = true;
                        break;
                    case "H":
                        cardset[1, num] = true;
                        break;
                    case "C":
                        cardset[2, num] = true;
                        break;
                    case "D":
                        cardset[3, num] = true;
                        break;
                }
            }

            /*????????????*/
            for(int i = 0; i < 13; i++)
            {
                if (!(cardset[0,i]))
                {
                    Console.WriteLine("S {0}",i+1);
                }
            }
            /*?????????*/
            for (int i = 0; i < 13; i++)
            {
                if (!(cardset[1, i]))
                {
                    Console.WriteLine("H {0}", i + 1);
                }
            }
            /*?????????*/
            for (int i = 0; i < 13; i++)
            {
                if (!(cardset[2, i]))
                {
                    Console.WriteLine("C {0}", i + 1);
                }
            }
            /*?????????*/
            for (int i = 0; i < 13; i++)
            {
                if (!(cardset[3, i]))
                {
                    Console.WriteLine("D {0}", i + 1);
                }
            }


        }
    }
}

Measured memory_bytes: 9128
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

unordered_map<string, int> map;
vector<unordered_map<string, int>> v;

int main() {
	int n;
	string input;

	cin >> n;
	v.resize(n);

	int maxValue = 0;

	for (int i = 0; i < n; i++) {
		cin >> input;

		if (map.count(input)) {
			map[input]++;
			if (maxValue < map[input]) {
				maxValue = map[input];
			}
		}
		else {
			map[input] = 0;
		}
	}

	vector<string> result;

	unordered_map<string, int>::iterator it; 
	for (it = map.begin(); it != map.end(); it++) {
		if (it->second == maxValue) {
			result.push_back(it->first);
		}
	}

	sort(result.begin(), result.end());

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}



}

Measured memory_bytes: 37572
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int N;
	cin >> N;
	vector<long long int> a(N);
	for(auto itr = a.begin(); itr != a.end(); itr++){
		long long int temp;
		cin >> temp; 
		*itr = temp;
	}
	vector<long long int> b(N);
	for(auto itr = b.begin(); itr != b.end(); itr++){
		int temp;
		cin >> temp; 
		*itr = temp;
	}
	long long int asum = 0;
	long long int bsum = 0;
	int i;
	long long int Moroje;
	for(i=0;i<N;i++){
		if( a[i] > b[i] ) bsum += ( a[i] - b[i] );
		else if( a[i] < b[i] ){
			Moroje = b[i] - a[i];
			if( Moroje % 2 == 1 ){
				Moroje--;
			}
			asum += Moroje;		
		}
	}
	if( asum < bsum * 2 ){
		cout << "No" << endl;
	} else {
		cout << "Yes" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 384
N, M = map(int, input().split())

from collections import defaultdict, deque

G = defaultdict(set)


results = [-1]*N
flags   = [False]*N

for _ in range(M):
    A, B = map(int, input().split())
    G[A-1].add(B-1)
    G[B-1].add(A-1)

seen    = [False]*N
partner = [0]*N

q = deque([0])
seen[0] = True


while q:
    now = q.popleft()
    for i in G[now]:
        if seen[i]:
            continue
        seen[i] = True
        partner[i] = now
        q.append(i)

if len(seen) != N:
    print('No')
else:
    print('Yes')
    for i in partner[1:]:
        print(i+1)

Measured memory_bytes: 73464
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,m,K;
    cin>>n>>m>>K;
    vector<long long> a(n+1,0),b(m+1,0);
    // vector <int> in(n+m);
    for(int i = 1;i<=n;i++)
    {
    cin>>a[i];
    a[i] += a[i-1];
    }
    for(int i = 1;i<=m;i++)
    {
    cin>>b[i];
    b[i] += b[i-1];
    }
    vector<long long>::iterator it;
    long long count  =0;
    long long  ans = 0;
    long long max = m;
    int j = max;
    for(long long i = 0;i<=n;i++)
    {
        // if(a[i]<=k)
        // {
        //     it =  lower_bound(b.begin(), b.end(), k-a[i]);
        //    if(a[i]+*it>k)
        //   it--;
        //   count = i+(it - b.begin());
        // //   cout<<i<<endl;

        // }
        // else
        // {
        //  it = lower_bound(b.begin(), b.end(), k);
        //  if(*it>k)
        //  it--;
        //  count =  it - b.begin();
        // //  cout<<*it<<endl;

        // }
        // if(count > max)
        // max = count;
          while(a[i] + b[j] > K) {
        j--;
        if(j < 0) { j = max; break; }
      }
      if(a[i] + b[j] <= K) {
         max = j; 
        if(ans < i + j) ans = i + j;
         }
    }
    cout<< ans;
   

    return 0;
}

Measured memory_bytes: 6428
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,strt,end) for(long long i = strt;i < end;i++)


int main(){
    int n;
    cin >> n;
    long long point[n][3];
    long long dp[n][3];
    rep(i,0,n){
        rep(j,0,3){
            cin >> point[i][j];
            if(i == 0){
                dp[0][j] = point[i][j];
            }
        }
    }
    rep(i,1,n){
        dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + point[i][0];
        dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + point[i][1];
        dp[i][2] = max(dp[i-1][1],dp[i-1][0]) + point[i][2];
    }
    long long a = 0;
    rep(i,0,3){
        a = max(a,dp[n-1][i]);
    }
    cout << a << endl;
    //--------------
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define int long long
#define double long double
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define td(v) v.begin(),v.end()
#define tdr(v) v.rbegin(),v.rend()
#define endl "\n"
#define Matrix vector<vector<int> >
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 2e18;

int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int lcm(int a,int b){return (a*b)/gcd(a,b);}

inline long long mod(long long n, long long m){
    long long ret = n%m;
    if(ret < 0) ret += m;
    return ret;
}

int exp(int a, int b){
    int result = 1;
    while (b > 0){
        if (b & 1)
            result = mod(result*a,MOD);
 
        b >>= 1;
        a = mod(a*a,MOD);
    }
    return result;
}

void solve(){
    int k,n; cin>>k>>n;
    vector<int>vet(n);
    for(int &i : vet) cin>>i;
    vet.push_back(k+vet[0]);
    int maior=-INF;
    for(int i=1;i<=n;i++){
        maior = max(maior,vet[i]-vet[i-1]);
    }
    cout<<k-maior<<endl;
}

main(){
    fastio;
    solve();
}

Measured memory_bytes: 4992
#include <stdio.h>
#include <stdlib.h>

int fib(int );

int main(){
  int n;

  scanf("%d", &n);
  if(n<0 || n>44) exit(1);

  n = fib(n);
  printf("%d\n",n);

  return 0;
}

int fib(int n){
  int i, x, y, z;
  
  if(n == 0) return 1;
  else if(n == 1) return 1;
  else{
    x=1;
    y=1;
    for(i=2; i<=n; i++){
      z = x + y;
      x = y;
      y = z;
    }
    return z;
  }
}



Measured memory_bytes: 2048
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
num1=0
num2=0
ans=1
for i in range(n):
    if a[i]==num1:
        ans*=a[i]
        num2+=1
        num1=0
    else:
        num1=a[i]
    if num2==2:
        break
if num2==2:
    print(ans)
else:
    print(0)


Measured memory_bytes: 20024
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
t = [tuple(map(int, input().split())) for _ in range(M)]
if M == 0 and (N > 1):
  print(10 ** (N - 1))
  exit(0)
for x in range(10 ** N):
  f = 1
  for i in range(M):
    s = str(x)
    y, c = t[i]
    if len(s) < y or (len(s) < N):
      f = 0
      break
    if int(s[y - 1]) != c:
      f = 0
      break
  if f:
    print(x)
    exit(0)
print(-1)

Measured memory_bytes: 38256
N = int(input())
num = sorted([int(e) for e in input().split(" ")])
lim = 10 ** 18
i = -1
ans = 1
for a in num:
    ans *= a
    if(ans > lim):
        print(-1)
        break
    elif(ans == 0):
        print(0)
        break
else:
    print(ans)

Measured memory_bytes: 21624
def draw(h, w):
    for i in range(h):
        s = ""
        for j in range(w):
            s += ("#" if (i + j) % 2 == 0 else ".")
        print(s)
    print("")
 
while True:
    h, w = map(int, raw_input().split())
    if h == 0 and w == 0:
        break
    draw(h, w)

Measured memory_bytes: 6336
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int > pp;
typedef long long ll;
 
#define sz(x) (int)x.size() 
int const N=5e5+10;

int n,q;
int dep[N],dp[N][20],cost[N],freq[N],cc[N];
vector<vector<int > > adj[N];
vector<vector<int > > qs;
set<int > pq[N];
map<int,pp > sv[N];
void dfs(int u,int p){
	dp[u][0]=p;
	for(auto v:adj[u]){
		if(v[0]==p)continue;
		dep[v[0]]=dep[u]+1;
		cost[v[0]]=cost[u]+v[2];
		dfs(v[0],u);
	}
}

void DFS(int u,int p){
	for(auto r:pq[u])sv[u][r] = {freq[r],cc[r]};
	for(auto v:adj[u]){
		if(v[0]==p)continue;
		freq[v[1]]++;
		cc[v[1]]+=v[2];
		DFS(v[0],u);
		freq[v[1]]--;
		cc[v[1]]-=v[2];
	}
}
int LCA(int a,int b){
	if(dep[b]<dep[a])swap(b,a);
	for(int i=18;i>-1;i--)if(dep[b]-(1<<i)>=dep[a])b=dp[b][i];
	if(a==b)return a;
	for(int i=18;i>-1;i--)if(dp[a][i]!=dp[b][i])b=dp[b][i],a=dp[a][i];
	return dp[b][0];
}
int getCost(int a,int b){
	return cost[a]+cost[b]-2*cost[LCA(a,b)];
}
int main() {
	scanf("%d%d",&n,&q);
	for(int i=0;i<n-1;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		adj[a].push_back({b,c,d});
		adj[b].push_back({a,c,d});		
	}
	dfs(1,0);
	for(int j=1;j<19;j++)for(int i=1;i<=n;i++)dp[i][j]=dp[dp[i][j-1]][j-1];
	for(int i=0;i<q;i++){
		int x,y,u,v;
		scanf("%d%d%d%d",&x,&y,&u,&v);
		qs.push_back({x,y,u,v});
		int lca=LCA(u,v);
		pq[lca].insert(x);
		pq[u].insert(x);
		pq[v].insert(x);				
	}
	DFS(1,0);
	for(int i=0;i<q;i++){
		int x=qs[i][0],y=qs[i][1],u=qs[i][2],v=qs[i][3],lca;
		lca=LCA(u,v);
		printf("%d\n",getCost(u,v)-(sv[u][x].second+sv[v][x].second-2*sv[lca][x].second)+
			(sv[u][x].first+sv[v][x].first-2*sv[lca][x].first)*y);
	}
    return 0;
}



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

int N;

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    if (N%2==1) {
        cout << 0 << endl;
        exit(0);
    }
    int two = 0;
    int p = 2;
    while (p<=N) {
        two += N/p;
        p *= 2;
    }
    int five = 0;
    p = 10;
    while (p<=N) {
        five += N/p;
        p *= 5;
    }
    cout << min(two, five) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

int main() {
	cout << fixed;
	double a, b, x;
	cin >> a >> b >> x;
	if(a * a * b / 2 <= x) {
		x = a * a * b - x;
		cout << setprecision(10) << atan((2 * x) / (a * a * a)) * 180 / M_PI << "\n";
	} else {
		cout << setprecision(10) << 90.0 - (atan((2 * x) / (a * b * b)) * 180) / M_PI << "\n";
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int,input().split()))
count = 0
for j in range(n):
    for i in range(n-1):
        if l[i]>l[i+1]:
            t = l[i]
            r = l[i+1]
            l[i] = r
            l[i+1] = t
            count += 1
for s in range(n-1):
        print(l[s],end=' ')
print(l[-1])
print(count)


Measured memory_bytes: 5604
import sys
input = sys.stdin.readline
n,q=[int(j) for j in input().split()]
l=[]
for i in range(n):
    s,t,x=[int(j) for j in input().split()]
    l.append((s-x,1,x))
    l.append((t-x,0,x))

for i in range(q):
    d=int(input())
    l.append((d,2,i))

l.sort()

ans=[-1]*q
ll=set()
m=10**18
p=False
for i,j,x in l:
    if j==1:
        ll.add(x)
        if m>x:
            m=x
            p=True
    elif j==0:
        ll.remove(x)
        if x==m:
            p=False
    else:
        if not p:
            if ll:
                p=True
                m=min(ll)
            else:
                m=-1
        ans[x]=m
print('\n'.join(map(str,ans)))



Measured memory_bytes: 105716
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <set>
#include <deque> 
#include <string>


using namespace std;

char s[200010];
int szS;


int main()
{
	scanf("%s\n", s);
	
	szS = strlen(s);
	int fullSum = 0;
	for (int i = 0 ; i < szS ; i++) {
		fullSum = fullSum + s[i] - '0';
	}
	
	if (fullSum % 9 == 0) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}

	return 0;
}




Measured memory_bytes: 1760
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define regsiter register
#define CL fclose(stdin),fclose(stdout)
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
	long long G()
	{
		long long n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
}
int m[666666];
int* a=m;
int op[111111],pop;
int main()
{
	int n=io::F();
	for(register int i=1;i<=n;++i)a[i]=io::F();
	int cnt=0;
	if(a[1]==n-1)a[n+1]=a[1],++a,op[++pop]=1;
	while(1)
	{
		if(cnt%n==0)
		{
			int fl=1;
			for(register int i=1;i<n;++i)if(a[i]>a[i+1])fl=0;
			if(fl)break;
		}
		else if(a[1]<a[n])std::swap(a[1],a[n]),op[++pop]=n-1;
		a[n+1]=a[1];
		++a;
		op[++pop]=1;
		++cnt;
	}
	printf("%d\n",pop);
	for(register int i=1;i<=pop;++i)printf("%d\n",op[i]);
	return 0;
}




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

ll inf =1e9+7;

#define pi 3.14159265358979323846L
bool isprime(ll a)
{
	
	ll cnt=0;	
	for(ll i=1;i*i<a;i++)
	{
		
	 	if(a%i==0)
	 	{
	 		cnt+=2;
		 }
		
		
	}
	
		if(cnt==2)
		return true;
		else
		return false;
		
}
ll mod(ll a)
{
	if(a<inf)return a;
	else
	return a%inf;
}
void solve()
{


	ll n;
	cin>>n;
	
	ll a[n+1],b[n+1];
	map<ll,ll>m;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		m[i+a[i]]++;
		b[i]=i-a[i];
	}

	ll ans=0;
	for(ll i=1;i<=n;i++)
	{
		ans+=m[b[i]];
	}
	
	cout<<ans;


}

int main()
{


ios::sync_with_stdio(0); 
	cin.tie(0);

	
		solve();
	
return 0;

		
	}
	
	
	


Measured memory_bytes: 29488
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

int main()
{
	vector<double> v;
	double d;
	while(cin>>d) v.push_back(d);
	printf("%.2lf",*max_element(v.begin(),v.end()) - *min_element(v.begin(),v.end()));
}

Measured memory_bytes: 0
using System;

namespace A___Infinite_Coins
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var a = int.Parse(Console.ReadLine());
            var b = n % 500;
            if(a>=b)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cassert>
using namespace std;

const double EPS=1e-8;

struct pt {
	double x,y;
	pt() {}
	pt(double x_, double y_) : x(x_), y(y_) {}
	pt operator + (const pt& p) const { return pt(x+p.x,y+p.y); }
	pt operator - (const pt& p) const { return pt(x-p.x,y-p.y); }
	double mod2() const { return x*x+y*y; }
	double mod() const { return sqrt(mod2()); }
	double arg() const { return atan2(y,x); }
	static pt polar(double r, double theta) { return pt(r*cos(theta),r*sin(theta)); }
	bool operator == (const pt& p) const { return x==p.x && y==p.y; }
	bool operator < (const pt& p) const { return false; }
};

istream& operator >> (istream& i, pt& p) { return i >> p.x >> p.y; }

typedef vector<pt> VP;
typedef vector<int> VI;
typedef vector<double> VD;
typedef pair<double,pt> PDP;
typedef vector<PDP> VC;

inline double sq(double x) { return x*x; }

int main() {
	int n,R;
	while(cin >> n >> R && n) {
		double o=0;
		double ret=0;
		double rem=2*M_PI;
		bool exists=false;
		VC cc(n);
		for (int i=0;i<n;++i) {
			cin >> cc[i].second >> cc[i].first;
			cc[i].first=R-cc[i].first;
		}
		sort(cc.begin(),cc.end());
		VP c;
		VD r;
		for (int i=0;i<n;++i) {
			if (cc[i].first<0) goto res;
			for (int j=0;j<i;++j) {
				if ((cc[i].second-cc[j].second).mod2()<=sq(cc[i].first-cc[j].first)) goto redundant;
			}
			r.push_back(cc[i].first);
			c.push_back(cc[i].second);
			redundant:;
		}
		n=c.size();
		for (int i=0;i<n;++i) {
			VD alpha;
			alpha.push_back(0);
			alpha.push_back(2*M_PI);
			for (int j=0;j<n;++j) {
				if (j==i) continue;
				pt v=c[j]-c[i];
				if (v.mod2()>sq(r[i]+r[j])) goto res;
				if (v.mod2()<sq(r[i]-r[j])) continue;
				double theta=v.arg();
//				cerr << (v.mod2()+sq(r[i])-sq(r[j])) << " / " << (2*v.mod()*r[i]) << endl;
				double co=(v.mod2()+sq(r[i])-sq(r[j]))/(2*v.mod()*r[i]);
				//assert(co>=-1);
				//assert(co<=1);
				if (co<-1) co=-1;
				if (co>1) co=1;
				double phi=acos(co);
//				cerr << i << " intersects with " << j << " at " << theta-phi << " and " << theta+phi << endl;
				alpha.push_back(theta+phi-2*M_PI);
				alpha.push_back(theta+phi);
				alpha.push_back(theta+phi+2*M_PI);
				alpha.push_back(theta-phi-2*M_PI);
				alpha.push_back(theta-phi);
				alpha.push_back(theta-phi+2*M_PI);
			}
			sort(alpha.begin(),alpha.end());
			for(int k=0;alpha[k]<2*M_PI;++k) {
				if (alpha[k]<0) continue;
				double delta=alpha[k+1]-alpha[k];
				double beta=(alpha[k]+alpha[k+1])/2;
				pt mid=c[i]+pt::polar(r[i],beta);
				for (int j=0;j<n;++j) {
					if ((mid-c[j]).mod()-EPS>r[j]) goto skip;
				}
//				cerr << "added an interval " << alpha[k] << " -- " << alpha[k+1] << " at " << i << " w/radius " << r[i]+R << endl;
				exists=true;
				ret+=(r[i]+R)*delta;
				rem-=delta;
				skip:;
			}
		}
		if (exists) o=ret+R*rem;
		res:
		if (o) printf("%.3f\n",o);
		else printf("0.0\n");
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
//setprecision(12)
#include <cassert>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define Cout(x) cout << x << endl;
#define check(v) rep(i,v.size()) cout << v[i] << endl;
#define vint(x) vector<int> x
#define vll(x) vector<long long> x
#define vstr(x) vector<string> x
const long long LLINF = 1LL<<60;
const int INF = 1e9;
const long long MOD = 1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
#define pint pair<int,int>
#define pll pair<ll,ll>
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; cin >> n >> k;
    vector<ll> v(n);
    rep(i,n) {
        cin >> v[i];
    }
    
    REP(i,k,n) {
        if(v[i-k]>=v[i]) cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
}

Measured memory_bytes: 4764
fn main() {
    let mut v: Vec<Vec<char>> = Vec::new();
    v.resize(2, Vec::new());
    for i in 0..2 {
        let mut buff = String::new();
        std::io::stdin().read_line(&mut buff).ok();
        v[i] = buff.trim().chars().collect::<Vec<char>>();
    }

    if (0..2).all(|i| (0..3).all(|j| v[i][j] == v[1 - i][2 - j])) {
        println!("YES");
    } else {
        println!("NO");
    }
}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;

// 入力
int N, M;
vector<vector<int> > G; // グラフ

// メモ化再帰
int dp[100100];
int rec(int v) {
    if (dp[v] != -1) return dp[v]; // 既に更新済み

    int res = 0;
    for (auto nv : G[v]) {
        chmax(res, rec(nv) + 1);
    }
    return dp[v] = res; // メモしながらリターン
}


int main() {
    // 入力受け取り
    cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        --x, --y; // 0-indexed にする
        G[x].push_back(y);
    }

    // 初期化
    for (int v = 0; v < N; ++v) dp[v] = -1;

    // 全ノードを一通り更新しながら答えを求める
    int res = 0;
    for (int v = 0; v < N; ++v) chmax(res, rec(v));
    cout << res << endl;
}

Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define ll  long long
#define endl '\n'
#define pi 3.14159265
int32_t main()
{           
    IOS;   
    ll n,k;
    cin>>n>>k;
    cout<<n-k+1;
}

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

/*string rec(string s, string t, string **mem)
{
  if(s.size()==0 or t.size()==0)
    return "";
  int i=s.size(),j=t.size();
  if(mem[i][j]!="!")
  	return mem[i][j];
  if(s[0]==t[0])
  {
    mem[i][j]=s[0]+rec(s.substr(1),t.substr(1),mem);
    return mem[i][j];
  }
  string a=rec(s.substr(1),t,mem);
  string b=rec(s,t.substr(1),mem);
  if(a.size()>b.size())
    mem[i][j]=a;
  else
    mem[i][j]=b;
  return mem[i][j];
}*/

int main(){
  string s,t;
  cin>>s>>t;
  int n=s.size(),m=t.size();
  /*string **mem=new string*[s.size()+1];
  for(int i=0;i<=s.size();i++)
  {
    mem[i]=new string[t.size()+1];
    for(int j=0;j<=t.size();j++)
      mem[i][j]="!";
  }
  cout<<rec(s,t,mem);*/
  
  int dp[n+1][m+1];
  for(int i=0;i<=n;i++)
    dp[i][0]=0;
  for(int j=0;j<=m;j++)
    dp[0][j]=0;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    {
      if(s[i-1]==t[j-1])
        dp[i][j]=dp[i-1][j-1]+1;
      else
      	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
  }
  
  string ans="";
  int i=n,j=m;
  while(i>0&&j>0)
  {
    if(s[i-1]==t[j-1])
    {
      ans=s[i-1]+ans;
      i--;
      j--;
    }
    else
    {
      if(dp[i-1][j]>dp[i][j-1])
        i--;
      else 
        j--;
    }
  }
  cout<<ans;
  
}

Measured memory_bytes: 35456
from collections import defaultdict
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    UF.union(x, y)

UF.all_find()

# グループに分解
D = defaultdict(list)
for i in range(N):
    D[UF.par[i]].append(A[i])

# グループ数
group = len(D)
if group == 1:
    print(0)
    exit()

# 優先度付きキュー
for key in D.keys():
    heapq.heapify(D[key])

# 各グループから最低1つは選ぶ必要がある
ans = 0
for key in D.keys():
    ans += heapq.heappop(D[key])

# 残り物から小さい順に足りない分を補充（必要な辺の数: group-1, 必要な頂点数2*group-2, 不足分group-2)
remain = []
for value in D.values():
    remain.extend(value)

remain.sort()
if len(remain) < group - 2:
    print("Impossible")
else:
    ans += sum(remain[:group - 2])
    print(ans)


Measured memory_bytes: 31776
#include <iostream>

using namespace std;

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  while (1) {
    if (b != a + 1) {
      a++;
    } else if (a > 1) {
      a--;
    } else {
      cout << "Borys\n";
      return 0;
    }
    if (b - 1 != a) {
      b--;
    } else if (b + 1 <= n) {
      b++;
    } else {
      cout << "Alice\n";
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
S = input()
a = []
z = []

for i in range(len(S)):
    if S[i] == 'A':
        a.append(i)

    if S[i] == 'Z':
        z.append(i)

a = min(a)
z = max(z)

if z<=a:
    print('0')
else:
    print(len(S[a:z+1]))





Measured memory_bytes: 11180
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define INF (1<<28)
#define DEKAI 1000000007
#define FDST int hogehogehoge;cin>>hogehogehoge;
#define int long long

signed main(){
	int k,a,b;
	cin>>k>>a>>b;
	if(b-a>2){
		int ans=1;
		if(a-1>=k){
			cout<<1+k<<endl;
			return 0;
		}
		ans=a;
		k-=a-1;
		if(k%2==1) ans++;
		int cnt=k/2;
		ans+=cnt*(b-a);
		cout<<ans<<endl;
	}
	else{
		cout<<1+k<<endl;
	}
	return 0;
}



Measured memory_bytes: 384
import java.util.*;
	import java.util.Map.Entry;
	 
	 
	 class Main {
		 static int mod =  (int) (Math.pow(10,9)+7);
//		 static int mod =  (int) 998244353;
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);
	        double n = sc.nextInt();
	        double m = sc.nextInt();
	        double d = sc.nextInt();
	        double ans=2*(n-d)/n;
	        if(d==0) {
	        	ans=1;
	        }
	        ans=ans*(m-1)/n;
	        
	        System.out.println(ans);
	    }
	}

Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    while (a > 0 && c > 0){
        c -= b;
        if (c <= 0) break;
        a -= d;

    }
    if (a <= 0){
        printf("No");
    }
    else printf("Yes");
}


Measured memory_bytes: 3804
D, G = map(int, input().split())

question_list = []

for i in range(D):
    p, c = map(int, input().split())
    question_list.append([p, c])


ans = 10 ** 5

for i in range(2 ** D):
    bit = format(i, "0" + str(D) + "b") # 完全に解く問題にビットを立てる

    total = 0
    num_q = 0
    for j in range(len(bit)):
        if bit[j] == "1":
            total += question_list[j][0] * 100 * (j + 1) + question_list[j][1]
            num_q += question_list[j][0]
    
    res = max(0, G - total)

    if res > 0:
        ind = bit.rfind("0")
        res_q = res // (100 * (ind + 1)) + (1 if (res % (100 * (ind + 1)) != 0) else 0)
        if res_q > question_list[ind][0]:
            continue
        num_q += res_q
    
    ans = min(ans, num_q)

print(ans)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;

class Main {
    public static void main(final String[] args) throws Exception {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
            br.readLine();
            List<String> inputString = Arrays.asList(br.readLine().split(""));
            int max = 0;
            int currentNumber = 0;
            for (String str : inputString) {
                if (str.equals("I")) {
                    currentNumber++;
                } else {
                    currentNumber--;
                }

                if (max < currentNumber) {
                    max = currentNumber;
                }
            }

            System.out.println(max);
        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 22228
#include <stdio.h>

main(){
  char class[20];
  int  i, a, b, j;

  for(i=0;i<9;i++){
    for(j=0;;j++){
      scanf("%c", &class[j]);
      printf("%c", class[j]);
      if(class[j]==' '){
	class[j]='\0';
	break;
      }
    }
    scanf("%d %d", &a, &b);
    getchar();
    //   printf("%s");
    printf("%d %d\n", a+b, 200*a+300*b);
  }
  return 0;
}

Measured memory_bytes: 0
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

const int MaxN = 1000000+64;
int p[MaxN],siz[MaxN],top[MaxN],son[MaxN],dep[MaxN];
int anss[MaxN];
queue<int> que;
vector<int>edg[MaxN];
typedef vector<int>::iterator ITER;
int n;

void DFS(int x);
void DFS2(int x);
int get_dis(int u,int v);
int LCA(int u,int v);

int main(){
	scanf("%d",&n);
	for(int i = 2;i <= n;i++){
		scanf("%d",&p[i]);
		edg[p[i]].push_back(i);
	}
	top[1] = 1;
	DFS(1);
	DFS2(1);
	que.push(1);
	while(!que.empty()){
		int u = que.front();
		for(ITER it = edg[u].begin();it != edg[u].end();++it){
			anss[*it] = get_dis(que.back(),*it);
			que.push(*it);
		}
		que.pop();
	}
	long long ans = 0LL;
	for(int i = 2;i <= n;i++)
		ans += (long long)anss[i];
	printf("%lld\n",ans);
	return 0;
}

void DFS(int x){
	siz[x] = 1;
	for(ITER it = edg[x].begin();it != edg[x].end();++it){
		dep[*it] = dep[x]+1;
		DFS(*it);
		siz[x] += siz[*it];
		if(siz[son[x]] < siz[*it])  son[x] = (*it);
	}
}

void DFS2(int x){
	if(son[x]){
		top[son[x]] = top[x];
		DFS2(son[x]);
	}
	for(ITER it = edg[x].begin();it != edg[x].end();++it){
		if(son[x] != (*it)){
			top[*it] = (*it);
			DFS2(*it);
		}
	}
}

int get_dis(int u,int v){
	return dep[u]+dep[v]-(dep[LCA(u,v)]<<1);
}

int LCA(int u,int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]] )  swap(u,v);
		u = p[top[u]];
	}
	if(dep[u] > dep[v])  swap(u,v);
	return u;
}

Measured memory_bytes: 34780
#include <stdio.h>

int main()
{
	int a1, a2;
	int h1, h2;

	scanf("%d %d %d %d", &h1, &a1, &h2, &a2);

	while (h1 > 0 && h2 > 0) {
		h2 -= a1;
		if (h2 <= 0)
			break;
		h1 -= a2;
	}

	if (h1 > h2)
		printf("Yes\n");
	else
		printf("No\n");

	return 0;
}

Measured memory_bytes: 1660
import itertools

def main():
    while True:
        n, x = map(int, input().split())
        if n == 0 and x == 0:
            break
        ans = 0
        for iters in itertools.combinations(range(1,n+1), 3):
            ans += (sum(iters) == x)
        print(ans)


if __name__ == "__main__":
    main()



Measured memory_bytes: 5636
from math import sqrt
from heapq import heappush, heappop

while 1:
    N = int(input())
    if N == 0:
        break
    G = [[] for i in range(N)]
    P = [None]*N
    for i in range(N):
        b, x, y = map(int, input().split())
        P[b-1] = (x, y)

    for i in range(N):
        xi, yi = P[i]
        for j in range(i):
            xj, yj = P[j]
            dd = (xi - xj)**2 + (yi - yj)**2
            if dd <= 2500:
                d = sqrt(dd)
                G[i].append((j, d))
                G[j].append((i, d))

    INF = 10**18
    M = int(input())
    for i in range(M):
        s, t = map(int, input().split()); s -= 1; t -= 1

        que = [(0, s)]
        dist = [INF]*N
        prv = [0]*N
        dist[s] = 0
        while que:
            cost, v = heappop(que)
            if dist[v] < cost:
                continue
            for w, d in G[v]:
                if dist[v] + d < dist[w]:
                    dist[w] = r = dist[v] + d
                    heappush(que, (r, w))
                    prv[w] = v
        if dist[t] == INF:
            print("NA")
        else:
            ans = []
            v = t
            while v != s:
                ans.append(v+1)
                v = prv[v]
            ans.append(s+1)
            ans.reverse()
            print(*ans)


Measured memory_bytes: 5768
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <utility>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1e9 + 7
#define INF 1e9
#define PIE 3.14159265358979323

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;}
template <class T>
T GCD(T a, T b) {if (b == 0) return a; else return GCD(b, a % b);}
template <class T>
inline T LCM(T a, T b) { return (a * b) / GCD(a, b);}

int main(){
    string s;
    ll k;
    cin >> s >> k;
    int i = 0;
    while(s[i]=='1'){
        i++;
    }
    if (i==0){
        cout << s[0] << endl;
    }
    else if (i>=k){
        cout << 1 << endl;
    }
    else{
        cout << s[i] << endl;
    }
}

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

using namespace std;

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

	vector<long long> a = {0}, b = {1};
	for(long long i =1; b.size() < 13; ++i) {
		a.push_back(a.back() + b.back());
		b.push_back(b.back() * 26);
	}
	long long n, len = 12;
	cin >> n;
	string ans(11, 'a');
	while(n > 0) {
		auto lb = upper_bound(a.begin(), a.end(), n) - a.begin() - 1;
		len = min<int>(len, 11 - lb);
		ans[11 - lb] = 'a' + (n - a[lb]) / b[lb - 1];
		n -= ((n - a[lb]) / b[lb - 1] + 1) * b[lb - 1];
	}
	cout << ans.substr(len);
}

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

int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}

int main(){
    int x,y;
    cin>>x>>y;
    cout<<x+y+1-gcd(x,y)<<endl;
    return 0;
}


Measured memory_bytes: 3104
using System;
using System.Linq;

namespace ABC142
{
    class C
    {
        static void Main(string[] args)
        {

            int N = int.Parse(Console.ReadLine());
            int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();

            int[] res = new int[N];
            for (int i = 0; i < N; i++)
            {
                res[a[i] - 1] = i + 1;
            }

            foreach (var item in res)
            {
                Console.Write(item);
                Console.Write(' ');
            }
            Console.WriteLine();

        }
    }
}


Measured memory_bytes: 28124
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(void){
  int a = 0; string s;
  cin >> s;
  for(int i = 0; i < 4; i++){
    if(s[i]=='+') a++;
    else a--;
  }
  cout<<a<<endl;
  return 0;
}


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

using namespace std;
int a[10005];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    memset(a,0,sizeof(a));
    for(int i=1; i<sqrt(n+0.5); i++)
        for(int j=1; j<sqrt(n+0.5); j++)
            for(int k=1; k<sqrt(n+0.5); k++)
                if(i*i+j*j+k*k+i*j+i*k+j*k<=n)
                    a[i*i+j*j+k*k+i*j+i*k+j*k]++;
    for(int i=1; i<=n; i++)
        cout<<a[i]<<endl;
    return 0;
}


Measured memory_bytes: 3728
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int n,a,b,i;
    cin>>n;
    cin>>a>>b;
    int p,mark[3]={0};
    for (i=0;i<n;i++)
    {
        cin>>p;
        if (p<=a)
            mark[0]++;
        else if (p>=(a+1) && p<=b)
            mark[1]++;
        else
            mark[2]++;
    }
    cout<<min({mark[0],mark[1],mark[2]})<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int main() 
{
    int s, m, h;
    cin >> s;
    m = s/60;
    s = s%60;
    h = m/60;
    m = m%60;
    printf("%d:%d:%d\n", h, m, s);

}



Measured memory_bytes: 3156
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int N;
	while(~scanf("%d", &N)) {
		vector<long long> As(N);
		for(int i = 0; i < N; ++ i)
			scanf("%lld", &As[i]);
		ll P = 1;
		int ans = 0;
		rep(p, 17) {
			vector<pair<ll, int>> intervals, events;
			rep(d, 10)
				intervals.emplace_back(P * d, d);
			intervals.emplace_back(P * 10, -1);
			const ll M = P * 10;
			for(ll A : As) {
				events.clear();
				ll a = (M - A % M) % M;
				rep(i, intervals.size() - 1) {
					ll L = intervals[i].first, R = intervals[i + 1].first;
					int d = intervals[i].second;
					events.emplace_back(L, d * 2 + 0);
					events.emplace_back(R, d * 2 + 1);
					ll nL = L + a, nR = R + a;
					if(nL + M <= nR) {
						events.emplace_back(0, d * 2 + 0);
						events.emplace_back(M, d * 2 + 1);
					} else if(nL % M <= nR % M) {
						events.emplace_back(nL % M, d * 2 + 0);
						events.emplace_back(nR % M, d * 2 + 1);
					} else {
						events.emplace_back(nL % M, d * 2 + 0);
						events.emplace_back(M, d * 2 + 1);
						events.emplace_back(0, d * 2 + 0);
						events.emplace_back(nR % M, d * 2 + 1);
					}
				}
				events.emplace_back(M, 2);
				sort(events.begin(), events.end());
				intervals.clear();
				int count[10] = {};
				int currentMask = 0;
				ll curL = 0;
				int curVal = -1;
				rep(ix, events.size() - 1) {
					int d = events[ix].second / 2;
					if(events[ix].second % 2 == 0) {
						if(count[d] ++ == 0)
							currentMask |= 1 << d;
					} else {
						if(-- count[d] == 0)
							currentMask &= ~(1 << d);
					}
					ll L = events[ix].first, R = events[ix + 1].first;
					if(L < R) {
						assert(currentMask != 0);
						int maxD = 9;
						while(~currentMask >> maxD & 1) -- maxD;
						if(curVal != maxD) {
							if(curVal != -1)
								intervals.emplace_back(curL, curVal);
							curL = L;
							curVal = maxD;
						}
					}
				}
				intervals.emplace_back(curL, curVal);
				intervals.emplace_back(M, -1);
			}
			int d = intervals[0].second;
			ans += d;
			P *= 10;
		}
		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 512
inpl = lambda: list(map(int,input().split()))
H, W, N = inpl()
Sr, Sc = inpl()
S = input()
T = input()

Hmin = 0
Hmax = H-1
Wmin = 0
Wmax = W-1
for i in range(N-1):
    s = S[-1-i]
    if s == 'U':
        Hmin += 1
    elif s == 'D':
        Hmax -= 1
    elif s == 'L':
        Wmin += 1
    else: # s == 'R'
        Wmax -= 1

    t = T[-2-i]
    if t == 'D' and Hmin > 0 and Hmin<=Hmax:
        Hmin -= 1
    elif t == 'U' and Hmax < H-1 and Hmin<=Hmax:
        Hmax += 1
    elif t == 'R' and Wmin > 0 and Wmin<=Wmax:
        Wmin -= 1
    elif t == 'L' and Wmax < W-1 and Wmin<=Wmax:
        Wmax += 1

s = S[-N]
if s == 'U':
    Hmin += 1
elif s == 'D':
    Hmax -= 1
elif s == 'L':
    Wmin += 1
else: # s == 'R'
    Wmax -= 1

if Hmin <= Sr-1 <= Hmax and Wmin <= Sc-1 <= Wmax:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 3788