akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007
int main()
{
        fast;
       ll n;
       cin>>n;
       ll arr[n];
       for(int i=0;i<n;i++)
    	cin>>arr[i];
	   ll b[64]={0},ans=0,m=1e9+7,p=1;
		for(ll i=0;i<64;i++)
			for(ll j:arr) 
				if(j & (1ll<<i))
					b[i]++;
		 for(ll i=0;i<64;i++)
	    {
	        p=pow(2,i);
	        p%=MOD;
	        ans+=((((n-b[i])*b[i])%MOD)*p%MOD);
	        ans%=MOD;
		}
		cout<<ans;
        return 0;
}


Measured memory_bytes: 6352
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " <<
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

signed main(){
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);

  string s;
  cin >> s;
  set<char> se;
  REP(i, s.length()){
    se.insert(s[i]);
  }

  cout << (se.size() == 2 ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <stack>
#include <queue>
#include <numeric>
#include <cstring>

using namespace std;

#define REP(i, a, b) for(i = a; i < b; i++)
#define rep(i, n) REP(i, 0, n)

int main(){
  int m;

  cin >> m;

  while(m--){
    set<string> s;
    string src;
    cin >> src;
    
    int i, n = src.size();
    
    rep(i, n){
      int j, k;
      string str, str1, str2;
      
      rep(j, i) str1 += src[j];
      REP(k, i, n) str2 += src[k];

      string rstr1 = str1, rstr2 = str2;
      
      reverse(rstr1.begin(), rstr1.end());
      reverse(rstr2.begin(), rstr2.end());

      str += str1;
      str += str2;
      s.insert(str);

      str = "";

      str += str2;
      str += str1;
      s.insert(str);

      str = "";

      str += str1;
      str += rstr2;
      s.insert(str);

      str = "";

      str += rstr2;
      str += str1;
      s.insert(str);

      str = "";

      str += rstr1;
      str += str2;
      s.insert(str);

      str = "";

      str += str2;
      str += rstr1;
      s.insert(str);

      str = "";

      str += rstr1;
      str += rstr2;
      s.insert(str);

      str = "";

      str += rstr2;
      str += rstr1;
      s.insert(str);
    }
    cout << s.size() << endl;
  }
  return 0;
}

Measured memory_bytes: 1000
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	long long s;
	int a[12]={0};
	cin>>s;
	int n=0;
	for(int i=0;;i++)
	{
		a[i]=s%10;
		n++;
		s/=10;
		if(s==0)break;
	}
	int m=1e4;
	for(int i=n-1;i>1;i--)
	{
		m=min(m,abs(a[i]*100+a[i-1]*10+a[i-2]-753));
	}
	cout<<m<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
const int maxn=200005;
int n,K,a[maxn],ans,flg;
struct ltl{
	int hed,til,Q[maxn];
}A,B;
inline int read(){
	int ret=0;bool f=0;char ch=getchar();
	while(ch>'9'||ch<'0') f^=ch=='-',ch=getchar();
	while(ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
	return f?-ret:ret;
}
int main(){
	n=read(),K=read();ans=n-K+1;
	for (int i=1;i<=n;i++) a[i]=read();
	A.hed=B.hed=1;
	for (int i=1;i<=n;i++){
		while(A.hed<=A.til&&A.Q[A.hed]<i-K) A.hed++;
		while(A.hed<=A.til&&a[A.Q[A.til]]>a[i]) A.til--;
		A.Q[++A.til]=i;
		while(B.hed<=B.til&&B.Q[B.hed]<i-K) B.hed++;
		while(B.hed<=B.til&&a[B.Q[B.til]]<a[i]) B.til--;
		B.Q[++B.til]=i;
		if(A.til-A.hed+(A.Q[A.hed]!=i-K)==K)
		if(!flg) flg=1;else ans--;else
		if(A.Q[A.hed]==i-K&&B.Q[B.hed]==i) ans--;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b,c,ans;
  cin >> a>>b>>c;
  if(a == b){
    if(b == c){
      ans = 1;
    }
    else ans =2;
  }
  else{
    if(b == c) ans =2;
    else{
      if(a == c) ans = 2;
      else ans = 3;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int main(void) {
    int L,R;

    cin>>L>>R;

    Int ans = TEN(18);
    if(R-L >= 5000) {
        cout<<0<<endl;

        return 0;
    }

    for(Int i = L;i < R;i++) {
        for(Int j = i+1;j <= R;j++) {
            Int s = (i*j) % 2019;
            ans = min(ans,s);
        }
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
#include <climits>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> P;

vector<int> bin(int n){
    vector<int> rtn(10);
    REP(i,10){
        rtn[i]=n%2;
        n/=2;
    }
    return rtn;
}

int n;
int main() {
    cin >> n;
    vector<vector<int>> f(n);
    vector<vector<int>> p(n);
    REP(i,n){
        REP(j,10){
            int f1;
            cin >> f1;
            f[i].push_back(f1);
        }
    }
    REP(i,n){
        REP(j,11){
            int p1;
            cin >> p1;
            p[i].push_back(p1);
        }
    }
    
    int res = INT_MIN;
    FOR(i,1,1024){
        int s = 0;
        vector<int> ps(n,0);
        vector<int> b = bin(i);
        REP(j,n){
            REP(k,10){
                if(f[j][k]==b[k] && b[k]==1){
                    ps[j]++;
                }
            }
            s += p[j][ps[j]];
        }
        res = max(res,s);
    }
    put(res);
    return 0;
}


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

const int INF = pow(2, 31) - 1;
#define ll long long
#define DEBUG(x) cout << "DEBUG>" << #x << ":" << x << endl;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main() {
  vector<vector<int>> c(3, vector<int>(3));
  REP(i, 3) {
    REP(j, 3) {
      cin >> c[i][j];
    }
  }
  if(c[0][1] - c[0][0] == c[1][1] - c[1][0] && c[2][1] - c[2][0] == c[0][1] - c[0][0] && c[0][2] - c[0][0] == c[1][2] - c[1][0] && c[2][2] - c[2][0] == c[0][2] - c[0][0]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


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

#define debug(x) cout << x << "\n";
#define debug2(x,y) cout << x << " " << y << "\n"
#define fi first
#define se second
#define pb push_back
#define ll long long 
const ll mod = 1e9+7;
const int MAX = 2e5+5;


bool mx(int a, int b, int c){
    if(a < b and b < c)
        return true;
    else if(a > b and b > c)
        return true;
    return false;
}
int main() {
    int n; cin >> n;
    vector<int> arr(n,0);
    for(int i = 0; i < n ; i++)
        cin >> arr[i];
    int count = 0;
    for(int i = 1; i < n-1; i++){
        if(mx(arr[i-1],arr[i],arr[i+1]))
            count++;
    }
    cout << count << endl;
}






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

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


Measured memory_bytes: 1792
import math
a,b,x = map(int,input().split())
def f(t):
    t = math.radians(t)
    if a * math.tan(t) <= b:
        return a**2 * b - a**3 * math.tan(t) / 2
    else:
        return b**2 / math.tan(t) * a / 2
tmax = 90
tmin = 0
while True:
    tmid = tmin + (tmax-tmin) / 2
    if abs(f(tmid)-x) <= 10**(-9):
        break
    if f(tmid) < x:
        tmax = tmid
    else:
        tmin = tmid
print(tmid)

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    
    vector<int> mtn(N);
    for (int i = 0; i < N; i++) cin >> mtn[i];
    
    int max_height = mtn[0];
    int ans = 1;
    
    for (int i = 1; i < N; i++){
        if (mtn[i] >= max_height) {
            max_height = mtn[i];
            ans += 1;
        }   
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
import bisect
s = input()*2
lens = len(s)//2
t = input()
appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
cnt = -1
bis = bisect.bisect_right
ans = 0

for i, ch in enumerate(s):
  appear[ch].append(i)
  
for j in t:
  if appear[j]:
    idx = bis(appear[j],cnt)
    ans += appear[j][idx] - cnt
    cnt = appear[j][idx]%lens
  else:
    print(-1)
    exit()
print(ans)

Measured memory_bytes: 11812
#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;

typedef pair<string, int> P;

int bfs(string worm){
	queue<P> que;
	que.push(P(worm, 0));

	map<string, int> d;
	
	while(!que.empty()){
		P p = que.front();
		que.pop();

		//d¡p^[Ícontinue
		if(d[p.first]) continue;

		string str = p.first;

		//SF¯¶©Ç¤©Ì`FbN
		bool flag = false;
		for(int i=0;i<str.size()-1;i++){
			if(str[i] != str[i+1]){
				flag = true;
				break;
			}
		}
		//¯¶Èçreturn
		if(!flag) return p.second;

		//d¡p^[»Êp
		d[p.first] = p.second;

		for(int i=0;i<str.size()-1;i++){
			//×èí¹ÅFªÙÈéÆ«
			if(str[i] != str[i+1]){
				char temp;
				string next;

				//tempÉÜÜêÈ¢êFðãü
				if(str[i] != 'b' && str[i+1] != 'b'){
					temp = 'b';
				}else if(str[i] != 'g' && str[i+1] != 'g'){
					temp = 'g';
				}else{
					temp = 'r';
				}

				//Ï»ãÌÔðnextÉlßÞ
				next = str;
				next[i] = next[i+1] = temp;

				//L[ÉvbV
				que.push(P(next, p.second+1));
			}
		}
	}
	return -1;
}

int main(){
	string worm;
	while(cin >> worm && worm != "0"){
		int ret = bfs(worm);
		if(ret>=0) cout << ret << endl;
		else cout << "NA" << endl;
	}
}

Measured memory_bytes: 2196
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int sum;
  sum = 0;
  cin >> N;
  for (int i = 0; i < N; i++) {
    int r,l;
    cin >> r >> l;
    sum += (l - r + 1);
  }
    cout << sum << endl;
 }

Measured memory_bytes: 256
import itertools

n,m=map(int,input().split())
L=[list(map(int,input().split())) for i in range(m)]
LL=[]
cnt=0
for i in range(len(L)):
    LL.append([L[i][1],L[i][0]])
Node=L+LL
Ans=[int(i)+1 for i in range(n)]
for v in itertools.permutations(Ans):
    v=list(v)
    if v[0]!=1:
        break
    tmp=0
    for i in range(n-1):
        if [v[i],v[i+1]] in Node:
            tmp+=1
    if tmp==n-1:
        cnt+=1
print(cnt)

Measured memory_bytes: 3064
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        PrintWriter out = new PrintWriter(System.out);

        if (a == b + c || b == a + c || c == a + b) {
            out.println("Yes");
        } else {
            out.println("No");
        }

        out.flush();
        sc.close();
    }
}

Measured memory_bytes: 35608
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N= N
        self.G = [[] for i in range(N)]
    def add_edge(self,fr,to,cap=1): #つなぐノード2つ、容量
        forward=[to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = inf
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow
n=int(input())
dinic=Dinic(2*n+2)


A=[] ; B=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
for i in range(n):
    a,b=map(int,input().split())
    B.append([a,b])
for i in range(n):
    dinic.add_edge(2*n,i,1)
    dinic.add_edge(i+n, 2*n+1,1)
for i in range(n):
    for j in range(n):
        if A[i][0]<B[j][0] and A[i][1]<B[j][1]:
            dinic.add_edge(i,j+n)

print(dinic.flow(2*n,2*n+1))

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

int main(){
    ll n,k,x=0,ans=0;
    cin>>n>>k;
    vector<ll> a(n);
    ll bitcnt[50];
    for(int i = 0; i < 50; i++)
    {
        bitcnt[i]=0;
    }
    

    for(ll i = 0; i < n; i++)
    {
        cin>>a[i];
        for(ll j = 0; j < 50; j++)
        {
            if(((1L<<j)&a[i])>0)  //j=0 -> 1 no keta
            {
                bitcnt[j]++;
            }
        }        
    }
    //ll kp = k+1;
    for(int i = 50 - 1; i >= 0; i--)
    {
        if((bitcnt[i]<n-bitcnt[i]) && (x|(1LL<<i))<=k)
        {
            x|=(1LL<<i);
        }
    }
    for(ll i = 0; i < n; i++)
    {
        ans+=(x^a[i]);
    }

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

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
s = input()
#開業されたN個要素を受け付ける
#input_list = [list(map(int, input().split())) for i in range(N)]

print(s[0:3])


Measured memory_bytes: 9040
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <regex>
#include <set>
#include <cmath>
#include <numeric>

using namespace std;

struct Elem
{
    int x;
    int y;
};

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

    int turn = 0;
    while(a > 0 && c > 0)
    {
        if(turn % 2 == 0)
        {
            c -= b;

        }else
        {
            a -= d;
        }
        turn++;
    }

    if( a > 0)
    {
        std::cout << "Yes";
    } else
    {
        std::cout << "No";
    }
    
 
    return EXIT_SUCCESS;
} 

Measured memory_bytes: 3040
#include <cstdio>
using namespace std;
typedef long long ll;
ll min(ll a,ll b){
    return a<b?a:b;
}
int main(){
    ll N,A,B;
    scanf("%lld%lld%lld",&N,&A,&B);
    if(B%2==A%2)printf("%lld\n",(B-A)/2);
    else printf("%lld\n",min((N-A-B+N)/2+1,(A+B-2)/2+1));
    return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;

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

#define ALL(a) (a).begin(),a.end()
#define MAXE(a) *max_element(ALL(a))
#define MINE(a) *min_element(ALL(a))

ll dist(ll a,ll b,ll c,ll d){
	return abs(a-c) + abs(b-d);
}

int main(){
	int N,M;
	cin >> N >> M;
	ll a[100];
	ll b[100];
	ll c[100];
	ll d[100];

	ll out[100];

	

	REP(i,N){
		cin >> a[i];
		cin >> b[i];
	}
	REP(i,M){
		cin >> c[i];
		cin >> d[i];
	}

	REP(j,N){
		ll min = 9999999999;
		REP(i,M){
			if ( min > dist(a[j],b[j],c[i],d[i])){
				out[j] = i+1;
				min = dist(a[j],b[j],c[i],d[i]);
			}
		}
	}

	REP(i,N){
		cout << out[i] << endl;
	}

}

Measured memory_bytes: 256
import fractions
import functools
from operator import mul

n=int(input())
aas=list(map(int,input().split()))

def gcdmult(lis):
    return(functools.reduce(fractions.gcd,lis))

lcmmult = lambda x: (functools.reduce(mul,x))//gcdmult(x)
lcma = lcmmult(aas)

ans = sum(map(lambda x: (lcma-1)%x,aas))
print(ans)


Measured memory_bytes: 5460
N=int(input())
h=[int(i) for i in input().split()][:N]
dp=[float('inf')]*N
dp[0]=0
for i in range(N-1):
    if i+1<N:
        dp[i+1]=min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
    if i+2<N:
        dp[i+2]=min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
print(dp[-1])

Measured memory_bytes: 20532
N,M = map(int,input().split())
edges = []
for _ in range(M):
    a,b,c = map(int,input().split())
    edges.append((a,b,-c))
INF = 10**9*M*10*2
d = [INF for _ in range(N+1)]
d[1] = 0
def update():
    for edge in edges:
        a,b,c = edge
        d[b] = min(d[b],d[a]+c)
for _ in range(N-1):
    update()
ansA = d[N]
for _ in range(N):
    update()
ansB = d[N]
if ansA == ansB:
    answer = -ansA
else:
    answer = 'inf'
print(answer)



Measured memory_bytes: 3316
#include<iostream>
#include<vector>
#include<map>

using namespace std;

const int LIM = (1<<11);

map<char,bool> M;


bool isalf(string s){
  return(s.size() == 1 && 'a' <= s[0] && s[0] <= 'k');
}

bool ispara(string s){
  int p = 0;

  // if(s[0] != '(' || s[s.length()-1] != ')') return false;

  for(int i = 0; i < s.length()-1; i++){
    if(s[i] == '(') p++;
    if(s[i] == ')') p--;
    if(p == 0) return false;
  }
  return true;
}

bool isdeny(string s){

  if(s.length() < 2) return false;

  return (s[0] == '-' && s[1] != '>');
}

bool solve(string s){
  // cout << "s " << s << endl;
  if(isalf(s)) return M[s[0]];
  else if(s == "T") return true;
  else if(s == "F") return false;
  else if(ispara(s)) return solve(s.substr(1,s.length()-2));
  else{
    int p = 0;

    for(int i = 0; i < s.length(); i++){
      if(s[i] == '(') p++;
      if(s[i] == ')') p--;
      if(p == 0 && s[i] == '+') return (solve(s.substr(0,i))||solve(s.substr(i+1)));
      if(p == 0 && s[i] == '*') return (solve(s.substr(0,i))&&solve(s.substr(i+1)));
      if(p == 0 && s[i] == '-' && s[i+1] == '>' ) return !(solve(s.substr(0,i))==true
							  && solve(s.substr(i+2)) == false);
    }
    if(isdeny(s)) return !solve(s.substr(1));
  }
}

void print(){

  cout << endl;
  for(char c = 'a'; c <= 'k'; c++)
    cout << c << " " << M[c] << " ";

  cout  << endl << endl;
}
void makemap(int n){
  
  for(int i = 0; i < 11; i++){
    if((n&(1<<i)))M['a'+i] = true;
    else M['a'+i] = false;
  }
}

bool check(string s){
  
  int pos;
  
  for(int i = 0; i < s.length(); i++)
    if(s[i] == '='){
      pos = i;
      break;
    }
  
  for(int i = 0; i < LIM; i++){
    makemap(i);
    // print();
    if(solve(s.substr(0,pos)) != solve(s.substr(pos+1))) return false;
  }
  
  return true;
}
int main(){

  string s;
  while(getline(cin,s) && s != "#"){
    if(check(s)) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}

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

using namespace std;

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define REP(i,n) rep(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<int> Array;
typedef vector<Array> Matrix;
const int loose = 0;
const int tight = 1;

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;
}


struct Edge {
    int to, cap, rev;
    Edge(int _to, int _cap, int _rev) {
        to = _to; cap = _cap; rev = _rev;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, int from, int to, int cap, bool revFlag, int revCap) {
    G[from].push_back(Edge(to, cap, G[to].size()));
    if (revFlag)G[to].push_back(Edge(from, revCap, G[from].size() - 1));
}


class UnionFind {
 vector<int> data;
 int num;
public:
 UnionFind(int size) : data(size, -1), num(size) { }
 bool unionSet(int x, int y) {
  x = root(x); y = root(y);
  if (x != y) {
   if (data[y] < data[x]) swap(x, y);
   data[x] += data[y]; data[y] = x;
   num--;
  }
  return x != y;
 }
 bool findSet(int x, int y) {
  return root(x) == root(y);
 }
 int root(int x) {
  return data[x] < 0 ? x : data[x] = root(data[x]);
 }
 int size(int x) {
  return -data[root(x)];
 }
 int numSet() {
  return num;
 }
};

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

	ll n;
	cin>>n;

	Array x(n),y(n);
	Graph g(201010);
	REP(i,n){
		cin>>x[i]>>y[i];
		y[i]+=100000;
		add_edge(g,x[i],y[i],1,true,1);
	}

	UnionFind uni(201010);
	REP(i,n){
		for(auto e:g[x[i]]){
			uni.unionSet(e.to,y[i]);
		}
		for(auto e:g[y[i]]){
			uni.unionSet(e.to,x[i]);
		}
	}

	Array used(201010,false);

	ll ans=0;

	REP(i,n){
		if(!used[uni.root(x[i])]){
			ll nx = uni.size(x[i]);
			ll ny = uni.size(y[i]);
			ans+=nx*ny;
			used[uni.root(x[i])]=true;
		}
	}

	ans-=n;

	cout<<ans<<en;

    return 0;
}

Measured memory_bytes: 11392
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::cout.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::fixed<<std::setprecision(15);}}fIO;
/*-*/

template <typename T>
std::vector<int> sort_indexes(const std::vector<T> &v) {
	std::vector<int> idx(v.size());
	std::iota(idx.begin(), idx.end(), 0);
	std::sort(idx.begin(), idx.end(), [&v](int i1, int i2) {return v[i1] < v[i2];});
	return idx;
}


int main() {
	int d;
	std::cin >> d;
	int N=26;
	std::vector<lnt> c(N);
	std::vector<std::vector<lnt> > v(d,std::vector<lnt>(N));
	rep(i,N) std::cin >> c[i];
	rep(i,d) {
		rep(j,N) {
			std::cin >> v[i][j];
		}
	}
	lnt best=-10000000;
	std::vector<int> besta;
	for(int y=1;y<10;y++) {
		std::vector<int> ans; ans.reserve(d);
		std::vector<int> last(N,-1);
		rep(i,d) {
			std::vector<int> idx(N);
			std::iota(idx.begin(), idx.end(), 0);
			double X=1; double Y=y;
			auto f = [&](int ix) -> double {
				return c[ix]*(i-last[ix]+X)*Y+v[i][ix];
			};
			std::sort(idx.begin(), idx.end(), [&](int i1, int i2) {return f(i1) > f(i2) ;});
			last[idx[0]]=i;
			ans.emplace_back(idx[0]);
			//print(idx[0]+1);
		}
		{
			lnt sum=0;
			std::vector<int> last(N,-1);
			rep(i,d) {
				int t=ans[i];
				sum+=v[i][t];
				last[t]=i;
				rep(j,N) sum-=(i-last[j])*c[j];
			}
			if(sum>best) {
				besta=ans;
			}
		}
	}
	rep(i,d) {
		print(besta[i]+1);
	}
}


Measured memory_bytes: 3748
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {//
       mut a:i64,mut b:i64,
    }
    // |a-k| = |b-k|
    // +-(a-k) = +-(b-k)
    //
    // a < b を仮定
    // 負にするしかない?
    // a < 0  , b > 0  にする
    if a > b {
        swap(&mut a, &mut b);
    }
    if (b - a) % 2 != 0 {
        println!("IMPOSSIBLE");
    } else {
        println!("{}", (b + a) / 2);
    }
}


Measured memory_bytes: 2172
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i)
#endif

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 ALL(s) (s).begin(), (s).end()
#define dis distance
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define pub push_back
#define sec second
#define fir first

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

bool isLower(char c){
	if(c-'a' < 0 || c-'a' >= 26)return false;
	return true;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	bool b = true;
	if(s[0] != 'A')b =  false;
	if(!isLower(s[1]))b = false;
	DUMP(b);
	int ind = -1;
	FOR(i,2,SZ(s)-1){
		if(s[i] == 'C'){
			if(ind == -1)ind = i;
			else b = false;
		}
		else{
			if(!isLower)b = false;
		}
	}
	if(ind == -1)b = false;
	if(!isLower(s[SZ(s)-1]))b = false;
	if(b)cout << "AC" << endl;
	else cout << "WA" << endl;
	return 0;
}


Measured memory_bytes: 256
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;
// const int imax = 100000;

int main(){
	int n,m;
	cin >> n >> m;
	int check[m] = {0};
	int k,a;
	rep(i,n){
		cin >> k;
		rep(j,k){
			cin >> a;
			check[a-1]++;
		}
	}
	int ans = 0;
	rep(i,m){
		if(check[i] == n) ans++;
	}
	printf("%d",ans);
	return 0;
}




Measured memory_bytes: 3764
#include<cstdio>
#include<algorithm>
using namespace std;

int n, k;

int main() {
	scanf("%d%d", &n, &k);
		
	double ans=0;
	for(int i=1;i<=n;i++) {
		double v = 1./n;
		int x = i;
		while(x<k) {
			x*=2;
			v/=2;
		}
		ans += v;
	}
	printf("%.12lf\n", ans);
	
	return 0;
}

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

typedef long long ll;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007


#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define sa(v) sort(v.begin(),v.end())
#define sd(v) sort(v.begin(),v.end(),greater<>())
#define rev(s) reverse(s.begin(),s.end())
#define tt int t; cin>>t; while(t--)
#define lo(i,a,b) for(ll i=a;i<b;i++)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()

#define sqr(a) ((a) * (a))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define mem(a,b) memset(a,b,sizeof(a))

#define yes cout<<"YES"<<nl;
#define no cout<<"NO"<<nl;

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}


int main()
{
   su;
   string s,t;
   cin>>s>>t;
   int c=0;
   for(int i=0;i<sz(t);i++)
   {
      if(s[i]==t[i])
         continue;
      else
         c++;
   }
   cout<<c<<nl;
   return 0;
}


Measured memory_bytes: 3784
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(){
	ll n,m,d;
	cin >> n >> m >> d;
	if(d == 0){
		printf("%.14lf\n",(double)(m-1)/n);
	}
	else{
		printf("%.14lf\n",(double)(m-1)*2*(n-d)/(n*n));
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 10000000000000000; //10^16
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int N,M;
    cin >> N >> M;
    vector<vector<int>> graph(N+1);
    int tmp1,tmp2;
    for (int i = 0; i < M; i++) {
        cin >> tmp1 >> tmp2;
        graph[tmp1].push_back(tmp2);
        graph[tmp2].push_back(tmp1);
    }

    queue<int> bfs;
    vector<int> ans(N+1,-1);
    ans[1] = 0;
    bfs.push(1);
    int tmp;
    while(!bfs.empty()){
        tmp = bfs.front();
        bfs.pop();
        for(int i : graph.at(tmp)){
            if(ans[i] != -1){
                continue;
            }
            else{
                ans[i] = tmp;
                bfs.push(i);
            }
        }
    }

    printf("Yes\n");
    for(int i = 2; i <= N; i++){
        printf("%d\n", ans[i]);
    }


}

Measured memory_bytes: 10124
N,A = map(int,input().split())

lis = []

for i in range(51):
    lis.append([0] * 2501)

lis[0][0] = 1

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


for x in X:

    nlis = []
    for k in range(51):
        new = lis[k].copy()
        nlis.append(new)

    for i in range(51):

        for j in range(2501):

            if i+1 <= 50 and j+x <= 2500 and nlis[i][j] > 0:

                lis[i+1][j+x] += nlis[i][j]

ans = 0
for i in range(51):

    for j in range(2501):

        if i != 0 and j % i == 0 and j // i == A:
            #print (i,j,lis[i][j])
            ans += lis[i][j]

print (ans)


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

void swap(int *a,int *b)
{
  int temp=*a;
  *a=*b;
  *b=temp;
}
void sort(int *a,int *b,int *c)
{
  if(*a>*b)
  swap(a,b);
  if(*b>*c)
  swap(b,c);
  if(*a>*b)
  swap(a,b);
}
int main(void)
{
  int a,b,c;
  cin>>a>>b>>c;
  sort(&a,&b,&c);

  int i=b-a,m=c-b;
  if(i<0)
    i=-i;
  if(m<0)
    m=-m;
  
  cout<<i+m<<endl;
  
}


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

using namespace std;

#define MAX_V 3000
#define INF 1e9

struct edge{ int to,cap,rev; };

vector<edge> G[MAX_V];
int level[MAX_V],iter[MAX_V];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> Q;
  level[s] = 0;
  Q.push(s);
  while(!Q.empty()){
    int v = Q.front(); Q.pop();
    for(int i = 0 ; i < (int)G[v].size() ; i++){
      edge &e = G[v][i];
      if(e.cap > 0 && level[e.to] < 0){
        level[e.to] = level[v] + 1;
        Q.push(e.to);
      }
    }
  }
}

int dfs(int v,int t,int f){
  if(v == t) return f;
  for(int &i = iter[v] ; i < (int)G[v].size() ; i++){
    edge &e = G[v][i];
    if(e.cap > 0 && level[v] < level[e.to]){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    bfs(s);
    if(level[t] < 0) return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f = dfs(s,t,INF)) > 0){
      flow += f;
    }
  }
}

int main(){
  int N;
  while(cin >> N,N){
    for(int i = 0 ; i < MAX_V ; i++){
      G[i].clear();
    }
    int k,x,n;
    cin >> n;
    int S = N+n,T = S+1;
    map<int,int> mp;
    for(int i = 0 ; i < n ; i++){
      cin >> x;
      mp[x] = i;
    }
    map<int,int>::iterator it;
    for(it = mp.begin() ; it != mp.end() ; ++it){
      add_edge(S,it->second,1);
    }
    for(int i = 0 ; i < N ; i++){
      cin >> k;
      for(int j = 0 ; j < k ; j++){
        cin >> x;
        if(mp.find(x) != mp.end()){
          add_edge(mp[x],n+i,1);
        }
      }
      add_edge(n+i,T,1);
    }
    cout << max_flow(S,T) << endl;
  }
  return 0;
}

Measured memory_bytes: 1532
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll a,b,k;cin>>a>>b>>k;
  lvector v;
  for(ll i=1;i<=max(a,b);++i) {
    if(a%i==0&&b%i==0) v.push_back(i);
  }
  ll ans=v[v.size()-k];
  print(ans);
  return 0;
}

Measured memory_bytes: 256
import sys
from itertools import accumulate
input = sys.stdin.readline

n,k=map(int,input().split())
L=list(map(int,input().split()))
M=[(1+i)/2 for i in L]
N=[0]+list(accumulate(M))
ans = 0
for i in range(k,n+1):
    val = N[i]-N[i-k]
    ans = max(val,ans)
print("%.6f"%ans)


Measured memory_bytes: 115652
c_li = [list(map(int,input().split())) for _ in range(3)]
res = 0

for i in range(c_li[0][0]+1):
    a1 = i
    b1 = c_li[0][0] - a1
    b2 = c_li[0][1] - a1
    b3 = c_li[0][2] - a1
    
    a2 = c_li[1][0] - b1
    a3 = c_li[2][0] - b1
    
    if c_li[1][1] != a2+b2:
        continue
    if c_li[1][2] != a2+b3:
        continue
    if c_li[2][1] != a3+b2:
        continue
    if c_li[2][2] != a3+b3:
        continue
    
    res = 1
    
if res == 0:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
vector<int> dy = {1, 0, -1, 0};
vector<int> dx = {0, 1, 0, -1};
int main(){
  while (1){
    int W, H;
    cin >> W >> H;
    if (W == 0 && H == 0){
      break;
    }
    vector<vector<char>> c(H + 2, vector<char>(W + 2, '#'));
    for (int i = 1; i <= H; i++){
      for (int j = 1; j <= W; j++){
        cin >> c[i][j];
      }
    }
    int sy, sx;
    for (int i = 1; i <= H; i++){
      for (int j = 1; j <= W; j++){
        if (c[i][j] == '@'){
          sy = i;
          sx = j;
        }
      }
    }
    c[sy][sx] = '.';
    int ans = 0;
    vector<vector<bool>> used(H + 2, vector<bool>(W + 2, false));
    used[sy][sx] = true;
    queue<pair<int, int>> Q;
    Q.push(make_pair(sy, sx));
    while (!Q.empty()){
      int y = Q.front().first;
      int x = Q.front().second;
      Q.pop();
      ans++;
      for (int i = 0; i < 4; i++){
        int y2 = y + dy[i];
        int x2 = x + dx[i];
        if (!used[y2][x2] && c[y2][x2] == '.'){
          used[y2][x2] = true;
          Q.push(make_pair(y2, x2));
        }
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3168
#include<bits/stdc++.h>
/* 
*    coder :: ATUL_PANDEY_2608
*        >>> INDIA <<<
*/
using namespace std;

// #define  part ..
#define listi vector<int > 
#define listll vector<long long >
#define pii pair<int ,int > 
#define pll pair<long long ,long long >
#define heap priority_queue<long long >

#define pb(a) push_back(a)
#define mod 1000000007
#define maxx 200006
#define ll long long 
#define quick  	ios_base::sync_with_stdio(NULL),cin.tie(0);
#define rep(i,a,b) for(int i=a;i<b;i++)
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// #define test int t;cin>>t;while(t--)
// end of #define 

// define globals ...









//write function from here ...









int Main(){


string s;
cin>>s;
int n= s.length();
if(s[0]=='?'){
	if(1>n &&(s[1] =='D'||s[1]=='?'))
	{
		s[0]='P';
	}
	else{
		s[0]='D';
	}
}

for(int i=1;i<n;i++){
	if(s[i]=='?'){
		if(s[i-1]=='P'){
		s[i]='D';
		}
		else if( i+1<n && s[i+1]=='D')
		{
			s[i]='P';
		}
		else
			s[i]='D';

	}
}



cout<<s;


return 0;



}
























// main function..
int main(){
	quick;  
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif

    Main();
    
    
}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

int main(){
	int X, Y, A, B, C;
	cin >> X >> Y >> A >> B >> C;
	vector<ll> P(A), Q(B), R(C);
	for(int i=0; i<A; i++) cin >> P[i];
	for(int i=0; i<B; i++) cin >> Q[i];
	for(int i=0; i<C; i++) cin >> R[i];

	vector<pair<ll, int>> xs(A+B+C);
	for(int i=0; i<A; i++) xs[i]={P[i], 0};
	for(int i=0; i<B; i++) xs[i+A]={Q[i], 1};
	for(int i=0; i<C; i++) xs[i+A+B]={R[i], 2};

	sort(xs.begin(), xs.end());
	reverse(xs.begin(), xs.end());

	ll ans = 0;
	int na=0, nb=0, nc=0;
	for(int i=0; i<xs.size(); i++){
		ll x = xs[i].first;
		ll t = xs[i].second;
		debug(i, x, t);
		if(t==0 && na<X){
			ans += x;
			na++;
		} else if(t==1 && nb<Y){
			ans += x;
			nb++;
		} else if(t==2 && na+nb+nc<X+Y){
			ans += x;
			nc++;
		}
		if(na+nb+nc==X+Y) break;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define NMAX (int)(12)
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for(int i = l; i < r; ++i)
#define rev(i, r, l) for(int i = r - 1; i >= l; --i)
#define ft first
#define sd second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

int k,sz,cnt,dp[NMAX][NMAX];
ll sol;

int main(){
    cin>>k;
    rep(i, 0, 10)
        dp[1][i]=1;
    if(k <= 9){
        cout<<k;
        return 0;
    }
    k-=9;
    rep(len, 2, 11){
        cnt=0;
        rep(i, 1, 10){
            dp[len][i]=dp[len-1][i-1]+dp[len-1][i]+dp[len-1][i+1];
            cnt+=dp[len][i];
        }
        dp[len][0]=dp[len-1][0]+dp[len-1][1];
        if(k <= cnt){
            sz=len;
            break;
        }
        k-=cnt;
    }
    rev(i, sz+1, 1){
        int digit=max(sol%10-1, 0LL);
        if(i == sz)
            digit=1;
        while(k > dp[i][digit]){
            k-=dp[i][digit];
            ++digit;
        }
        sol=sol*10LL+digit;
    }
    cout<<sol;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace jugyo1024
{
    class Program
    {
        static void Main(string[] args)
        {
            var _ = Console.ReadLine();
            var arr = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).OrderBy(x => x).ToArray();

            int cnt = 0;
            var comp = Comparer<int>.Default;
            for (int i = 0; i < arr.Length; i++)
                for (int j = i + 1; j < arr.Length; j++)

                {
                    int c = arr[i] + arr[j];
                    int n = LowerBound(arr, j + 1, arr.Length, c, comp) - j - 1;
                    if (n > 0)
                        cnt += n;
                }
            Console.WriteLine(cnt);
        }

        static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
        {
            int low = start;
            int high = end;
            int mid;
            while (low < high)
            {
                mid = ((high - low) >> 1) + low;
                if (comparer.Compare(arr[mid], value) < 0)
                    low = mid + 1;
                else
                    high = mid;
            }
            return low;
        }
    }
}


Measured memory_bytes: 13416
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void print_YES_NO(bool answer){cout<<(answer?"YES":"NO")<<endl;}
void print_Yes_No(bool answer){cout<<(answer?"Yes":"No")<<endl;}
void print_POSSIBLE_IMPOSSIBLE(bool answer){cout<<(answer?"POSSIBLE":"IMPOSSIBLE")<<endl;}

bool used[200005];
int s[200005];
typedef tuple<int,int,int> T;
priority_queue<T> q1;
priority_queue<P,vector<P>,greater<P> > q2;

int main(){
	int n,m;
	int a,b,c;
	int i,j,k;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>a>>b>>c;
		q1.push(make_tuple(a-c,-c,i));
		q1.push(make_tuple(b-c,-c,i));
	}
	for(i=0;i<m;i++){
		cin>>a;
		q1.push(make_tuple(a,0,i));
	}
	while(!q1.empty()){
		tie(a,b,c)=q1.top(),q1.pop();
		if(b!=0){
			b=-b;
			if(used[c]){
				used[c]=false;
				while(!q2.empty() && !used[q2.top().second])q2.pop();
			}else{
				used[c]=true;
				q2.push(make_pair(b,c));
			}
		}else{
			if(q2.empty())s[c]=-1;
			else s[c]=q2.top().first;
		}
	}
	array_show(s,m,'\n');
}
			
			
		


Measured memory_bytes: 14700
#include<bits/stdc++.h>
using namespace std;
#define mx 200003
#define s second
#define f first
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define ll long long

long long n,a[mx],pref[mx],prex[mx],jaw;
 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		pref[i]=pref[i-1]+a[i];
		prex[i]=prex[i-1]^a[i];
	}
	int now=0;
	for(int i=1;i<=n;i++){
		while(now+1<=n && pref[now+1]-pref[i-1]==(long long)(prex[now+1]^prex[i-1])){
			now++;
		}
		//cout<<pref[now]-pref[i-1]<<" and "<<(long long)(prex[now]^prex[i-1])<<endl;
		//cout<<i<<' '<<now<<endl;
		jaw=jaw+now-i+1;
	}
	cout<<jaw;
}

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

int C[1009][1009];

int main() {
    int H, W, A, B; scanf("%d%d%d%d",&H,&W,&A,&B);
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            if(j < A) C[i][j] = 1;
            else C[i][j] = 0;
        }
        if(i >= B) for(int j=0; j<W; j++) C[i][j] ^= 1;
    }
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            printf("%d", C[i][j]);
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 5120
#include<iostream>
#include<algorithm>
#include<map>
#include<string> 
#include<set>

using namespace std;
typedef long long ll;
int main()
{
	int n;
	cin>>n;
	map<string,int>mp;
	set<string>str;
	string s;
	for(int i=1;i<=n;i++){
		cin>>s;
		mp[s]++;
		str.insert(s);
	}
	int maxn=0;
	map<string,int>::iterator it=mp.begin();
	while(it!=mp.end()){
		maxn=max(maxn,it->second);
		it++;
	}
	set<string>::iterator itt=str.begin();
	while(itt!=str.end()){
		if(mp[*itt]==maxn)
		cout<<*itt<<endl;
		itt++;
	}
	return 0;
 } 

Measured memory_bytes: 30080
dic={}
while pair = STDIN.gets
  pair.chomp!
  word, page = pair.split(" ")
  if dic.has_key?(word) then
    dic[word] += ' '+page
  else
    dic[word] = page
  end
    
end

dic.keys.sort.each do |k|
  puts k
  pages = dic[k]
  pages = pages.split(" ").map { |item| item.to_i }
  pages = pages.sort.join(" ")
  puts pages 
end

Measured memory_bytes: 8756
#include <iostream>

using namespace std;

int main(void)
{
	int x, y;

	while (1) {
		cin >> x >> y;
		
		if (x == 0 && y == 0)
			break;

		if (x > y) {
			int tmp = x;
			x = y;
			y = tmp;
		}

		cout << x << ' ' << y << endl;
	}
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
string s[10]={"SUN", "MON", "TUE", "WED", "THU", "FRI","SAT"};
int main()
{
	string s1;
	cin>>s1;
	int num=0;
	for(int i=0;i<7;i++){
		if(s[i]==s1){
			num=7-i;
			break;
		}
	}
	if(num==0)num+=7;
	cout<<num<<endl;
}


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

char str[105];
int n;

int main()
{
	scanf("%s",str);
	n=strlen(str);
	if(n%2)
	{
		printf("No\n");
		return 0;
	}
	for(int i=1;i<=n;i+=2)
	{
		if(str[i-1]!='h'||str[i]!='i')
		{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
__DEUBG__ = 0
num = input()
pattern = len(num) -1

if pattern == 0:
    print(num)
    exit(0)
total = 0
fmt = '0' + str(pattern) + 'd'
if __DEUBG__:
    print(fmt)
total = 0
for i in range(2**pattern):
    binary = format(int(bin(i)[2:]), fmt)
    if __DEUBG__:
        print('binary', binary)

    equation = ''
    for idx, sign in enumerate(binary):
        equation += num[idx] + ('+' if sign == '1' else '')
        if __DEUBG__:
            print(equation)

    equation += num[-1]
    if __DEUBG__:
        print(equation, eval(equation))
        print()
    total += eval(equation)

print(total)

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

int main(){
    int N; cin >> N;
    int a;
    int prev;
    enum {
        FLAT = 0,
        UP = 1,
        DOWN = 2
    };
    int status = FLAT;
    cin >> prev;
    
    int ans = 0;
    for (int i = 0; i < N-1; i++) {
        cin >> a;
        if (status == FLAT) {
            if (prev < a) {
                status = UP;
                ans++;
            } else if (prev == a) {
                status == FLAT;
            } else {
                status = DOWN;
                ans++;
            }
        } else {
            if (prev < a && status == DOWN) {
                status = FLAT;
            } else if (a < prev && status == UP) {
                status = FLAT;
            }
        }
        prev = a;
    }
    if (status == FLAT) {
        ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public int getTime(int n, int x, int t) {
        if (n % x == 0) return (n / x) * t;
        else return (n / x + 1) * t;
    }

    public static void main(String[] args) throws Exception {
        Main solution = new Main();

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();
        int t = scanner.nextInt();

        int answer = solution.getTime(n, x, t);
        System.out.println(answer);
    }
}

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


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

	if (N % 2 == 1)
	{
		cout << "No" << endl;
		return 0;
	}

	if (S.substr(0, N / 2) == S.substr(N / 2, N / 2))
	{
		cout << "Yes" << endl;
		return 0;
	}

	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#ABC138_C
#大きい数字を残して小さい数字通しを混ぜて行けば良い
n=int(input())
arr=list(map(int,input().split()))
while len(arr)>1: #最後の1つになるまで操作を続ける
 arr=sorted(arr) #配列を昇順ソート
 v1=arr.pop(0) #最小の2数を取り出し、それらを合成したものを配列に追加する
 v2=arr.pop(0)
 arr.append((v1+v2)/2)
print(arr[0])

Measured memory_bytes: 2940