akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const int N = 1e5, INF = 1e8;
VI e[N];
int c[N], dp[N][3];

bool dfs(int now, int past){
    bool ret = false;
    int cnt = 0, ma = 0, ma2 = 0;
    for (int next : e[now]){
        if (next == past) continue;
        bool f = dfs(next, now);
        if (f) {
            ret = true;
            cnt++;
            dp[now][2] += dp[next][2] + 2;
            int dif = dp[next][2] - dp[next][1];
            if (dif > ma){
                ma2 = ma;
                ma = dif;
            }else if (dif > ma2){
                ma2 = dif;
            }
        }
    }

    dp[now][0] = dp[now][1] = dp[now][2];

    if (cnt == 1){
        dp[now][1] -= ma + 1;
        dp[now][0] = dp[now][1];
        if (cnt % 2 == c[now]){
            dp[now][0]++;
            dp[now][2]++;
        }else{
            dp[now][1]++;
        }
    }else if (cnt >= 2){
        dp[now][1] -= ma + 1;
        dp[now][0] -= ma + ma2 + 2;
        if (cnt % 2 == c[now]){
            dp[now][0]++;
            dp[now][2]++;
        }else{
            dp[now][1]++;
        }
    }

    if (!ret && c[now]){
        dp[now][0] = dp[now][1] = 1;
        ret = true;
    }

    if (!ret) REP(j,3) dp[now][j] = -1;

    // cout << now << " " << ret << endl;
    return ret;
}

int main() {
    // int n;
    // cin >> n;
    // REP(i,n-1){
    //     int u = in() - 1, v = in() - 1;
    //     e[u].push_back(v);
    //     e[v].push_back(u);
    // }
    // string s;
    // cin >> s;
    // REP(i,n) if (s[i] == 'W') c[i] = 1;

    // int root = -1;
    // REP(i,n){
    //     if (c[i]) root = i;
    // }

    // // root = 0;

    // if (root == -1){
    //     cout << 0 << endl;
    //     return 0;
    // }

    // dfs(root, -1);
    // cout << dp[root][0] << endl;

    // cout << root << endl;
    // REP(i,n){
    //     cout << i + 1 << "  ";
    //     REP(j,3) cout << dp[i][j] << " ";
    //     cout << endl;
    // }

    int x;
    cin >> x;
    int ans = 1;
    FOR(i,2,x){
        int y = i * i;
        while (y <= x){
            ans = max(ans, y);
            y *= i;
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

const double PI = 3.141592653589;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define int long long
#define all(c) (c).begin(),(c).end()
#define M 1000000007
#define INF LLONG_MAX
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ", "; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
// Use pr(a,b,c,d,e) or cerr<<anything or prc(v.begin(),v.end()) or prc(v,v+n)
//  
int dp[100][100][2];

string s;
int k;
int f(int start, int zero, int tight)
{
    if(zero < 0) return 0;
    if(start >= (int)s.length()) 
    {
        if(zero == 0) return 1;
        else return 0;
    }
    if(dp[start][zero][tight] != -1)
        return dp[start][zero][tight];
    
    int curr = s[start] - '0';
    if(!tight) curr = 9;
    int ans = 0;
    for(int i=0;i<=curr;i++)
    {
        int curr_tight = 0;
        if(tight && i == curr) curr_tight = tight;
        if(!i) ans += f(start+1, zero, curr_tight);
        else ans += f(start+1, zero-1, curr_tight);
    }
    dp[start][zero][tight] = ans;
    return ans;
}



int32_t main()
{
    fastio;
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    cin >> s >> k;
    memset(dp, -1, sizeof(dp));
    cout << f(0, k, 1) << "\n";
    return 0;
}



Measured memory_bytes: 384
Scanf.scanf "%d" (fun n ->
    let a = Array.init n (fun _ -> Scanf.scanf " %d" (fun a -> a)) in
    let sum = Array.fold_left (+) 0 a in
    let g = n * (n + 1) / 2 in
    print_endline @@
        if sum mod g <> 0 then "NO" else (
            let k = sum / g in
            let d = Array.init n (fun i -> a.((i + 1) mod n) - a.(i) - k) in
            let rec loop i =
                if i = n then "YES" else
                    if d.(i) <= 0 && d.(i) mod n = 0 then loop (i + 1) else "NO"
            in
            loop 0
        )
)

Measured memory_bytes: 7408
#include<stdio.h>
int main()
{
	int a,b,n,sum,c,d,i,min=200;
	scanf("%d",&n);
	for(a=1;a<=n/2;a++)
	{   sum=0;
		b=n-a;
		c=a;
		d=b;
		for(i=5;i>0;i--)
		{
		    sum+=c%10;
		    sum+=d%10;
		    c=c/10;
		    d=d/10;
		}
	    if(min>sum)
	    min=sum;
	}
	printf("%d",min);
	return 0;
 } 

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

vector<int> p;
int f(int x) { return x == p[x] ? x : p[x] = f(p[x]); }

int main() {
  int ans = 0;
  int n, m;
  ios::sync_with_stdio(false);
  cin >> n >> m;
  p.resize(n + 1);
  iota(p.begin(), p.end(), 0);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    p[f(a)] = f(b);
  }
  unordered_map<int, int> sz;
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, ++sz[f(i)]);
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 12268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
ll k,a[N],L,R;
int main(){
    scanf("%d%lld",&n,&k);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    sort(a,a+n);
    L=-1e18,R=1e18;
    while(L+1!=R){
        ll Mid=(L+R)/2;
        ll cnt=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]<0){
                int l=i,r=n;
                while(l+1!=r){
                    int mid=(l+r)/2;
                    if(a[i]*a[mid]<=Mid) r=mid;
                    else l=mid;
                }
                cnt+=n-r;
            }
            else{
                int l=i,r=n;
                while(l+1!=r){
                    int mid=(l+r)/2;
                    if(a[i]*a[mid]<=Mid) l=mid;
                    else r=mid;
                }
                cnt+=l-i;
            }
        }
        if(cnt<k) L=Mid;
        else R=Mid;
    }
    printf("%lld",R);
    return 0;
}


Measured memory_bytes: 1792
import math
a,b = map(int,input().split())
x = math.ceil(a/0.08)
i,flag = 0,0
while(flag==0):
  if math.floor((x+i)*0.08) != a:
    flag = 1
    k = i
  else:
    i+=1
for j in range(k):
  if math.floor((x+j)*0.1) == b:
    print(x+j)
    exit()
print(-1)
    


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int n;
    cin >> n;
    vint a(n);
    rep(i, n) cin >> a[i];

    deque<int> q;
    rep(i, n) {
        if (i%2 == 0) q.push_front(a[i]);
        else q.push_back(a[i]);
    }
    vint ans;
    while(!q.empty()) {
        int a;
        if (n%2 == 0) {
            a = q.back();
            q.pop_back();
        }
        else {
            a = q.front();
            q.pop_front();
        }
        ans.push_back(a);
    }
    rep(i, n) printf("%d%s", ans[i], i != n-1 ? " " : "\n");
    return 0;
}

Measured memory_bytes: 4728
def lucas(n):
  if n==1:return 1
  l=[""]*(n+1)
  l[0]=2
  l[1]=1
  for i in range(2,n+1):
    l[i]=l[i-2]+l[i-1]
  return l[n]

n=int(input())
print(lucas(n))

Measured memory_bytes: 3064
import java.util.*;
import java.io.*;

class Main {

	void solve() {

		int n = inint();
		int pay = 800 * n;
		int give = n / 15 * 200;
		out.println(pay - give);

	}

	public static Scanner in = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		new Main().solve();
		out.flush();
	}

	public int inint() {
		return in.nextInt();
	}

	public long inlong() {
		return in.nextLong();
	}

	public String instr() {
		return in.next();
	}

	public char inchar() {
		return in.next().charAt(0);
	}

	public int[] inintar(int num) {
		int[] a = new int[num];
		for (int i=0; i<num; i++) {
			a[i] = in.nextInt();
		}
		return a;
	}

	public char[] incharar() {
		return in.next().toCharArray();
	}

	public char[][] incharmap(int h, int w) {
		char[][] a = new char[h][w];
		for (int i=0; i<h; i++) {
			String temp = in.next();
			for (int j=0; j<w; j++) {
				a[i][j] = temp.charAt(j);
			}
		}
		return a;
	}

}

Measured memory_bytes: 21844
n = int(input())
if n == 1:
    print(0)
    exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
fa = factorization(n)
ans = 0
rui = [0]*20
for i in range(1,20):
    rui[i] = i+rui[i-1]


for so,si in fa:
    for i in range(1,20):
        if rui[i]<= si <rui[i+1]:
            ans+= i
            break
print(ans)


Measured memory_bytes: 63388
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main()
{
string s;
cin>>s;
s[3]='8';
cout<<s<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;cin>>s;
  	multiset<char> m;m.insert({s[0],s[1],s[2],s[3]});
  	for(auto x:m){
    	if(m.count(x)!=2){cout<<"No";return 0;}
    }
  	cout<<"Yes";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int

ll dp[100005];
ll a[100005];
ll n;
ll jump(ll i)
{
    if(i==n)
    return 0;
    if(i>n)
    return 1000000009;
    
    
    if(dp[i]!=-1)
    return dp[i];
    
    dp[i]=min(abs(a[i]-a[i+1])+jump(i+1),abs(a[i]-a[i+2])+jump(i+2));
    
    return dp[i]; 
    
    
}
int main() 
{
    fio;
    memset(dp,-1,sizeof(dp));
    
    cin>>n;

    for(ll i=1;i<=n;i++)
    cin>>a[i];
    dp[0]=0;
    ll res=jump(1);
    cout<<res<<endl;
    

	return 0;
}

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

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

    ll m=1;
    while (true)
    {
        if (n <= (k-1)*m + 1){
            break;
        }
        m++;
    }

    cout << m << endl;
    

    return 0;
}


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

using namespace std;

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

	vector<long long> a(n);

	int zc = 0;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] == 0) {
			zc++;	
		}
	}

	if (zc) {
		cout << 0;
		return 0;
	}

	long long ans = 1;

	for (int i = 0; i < n; i++) {
		if (a[i] <= 1000000000000000000 / ans) ans *= a[i];
		else {
			cout << -1;
			return 0;
		}
	}

	cout << ans;
	return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> A;
  REP(i, 10) { A.push_back(111 * i); }
  for(auto x : A) {
    if(x >= N) {
      cout << x << endl;
      break;
    }
  }

  return 0;
}

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

using namespace std;
const long long mod = 1e9+7;
const int N = 2e5+5;

#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define fr(i,l,m) for(int i=l;i<m;i++)
int w[N],v[N];
//vector<int> v;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
// Code Here
int n,max_wt;
cin>>n>>max_wt;
fr(i,1,n+1)
{
    cin>>w[i]>>v[i];
}
ll dp[n+1][max_wt+1];
fr(i,0,n+1)
{
    fr(j,0,max_wt+1)
    {
        if(i==0 || j==0){dp[i][j]=0;}
        else if(w[i]<=j)
            dp[i][j]=max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);
        else
            dp[i][j]=dp[i-1][j];
    }
}
cout<<dp[n][max_wt]<<endl;
return 0;
}
/////////
/////////
////////



Measured memory_bytes: 79232
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

bool calc(VI x, VI y){
    int n = x.size();
    int d = 0;
    REP(i,n){
        d += (x[i] - y[i]) * (x[i] - y[i]);
    }
    int r = 0;
    while (r * r < d) r++;
    return r * r == d;
}

int main() {
    int n, d;
    cin >> n >> d;
    VVI x(n, VI(d));
    REP(i,n) REP(j,d) cin >> x[i][j];

    int ans = 0;
    REP(i,n) REP(j,i){
        ans += calc(x[i], x[j]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	ll m; cin >> m;
	vector<ll> A(n);
	rep(i, n) {
		ll a; cin >> a;
		A[i] = a / 2ll;
	}

	ll c = A[n - 1];
	rep(i, n - 1) {
		c = lcm(c, A[i]);
	}

	rep(i, n) {
		if ((c / A[i]) % 2 == 0) {
			dunk(0);
			return 0;
		}
	}

	ll ans = 0;
	ll k = c;
	while (c <= m) {
		ans++;
		c += k * 2;
	}

	dunk(ans);

	return 0;
}


Measured memory_bytes: 1024
/*
@author: sharrad99
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define mp make_pair
#define ff first
#define ss second
#define mll map<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mod 1000000007
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll a,b;
	cin>>a>>b;
	ll g = __gcd(a,b);
	ll m=g;
	ll res=1;
	for(ll i=2;i*i<=m;i++){
		if(g%i==0){
			res++;
		}
		while(g%i==0){
			g/=i;
		}
	}
	if(g>1){
		res++;
	}
	cout<<res<<"\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <set>
#include <climits>
#include <map>

using namespace std;

int adj_mat[100][100];
int dists[100][100];

void warshall_floyd(int N){
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(adj_mat[i][j] == 0){
        dists[i][j] = INT_MAX;
      } else {
        dists[i][j] = adj_mat[i][j];
      }
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      for(int k = 0; k < N; k++){
        if(dists[j][i] != INT_MAX && dists[i][k] != INT_MAX){
          dists[j][k] = min(dists[j][k], dists[j][i] + dists[i][k]);
        }
      }
    }
  }
}

int main(){
  int N;
  int M;
  cin >> N >> M;
  for(int i = 0; i < M; i++){
    int a;
    int b;
    int c;
    cin >> a >> b >> c;
    adj_mat[a - 1][b - 1] = c;
    adj_mat[b - 1][a - 1] = c;
  }

  warshall_floyd(N);

  int ans = 0;
  for(int i = 0; i < N; i++){
    for(int j = i + 1; j < N; j++){
      if(adj_mat[i][j] != 0){
        if(adj_mat[i][j] > dists[i][j]){
          ans ++;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  int N;
  cin>>N;
  long long int m=0,a=0,r=0,c=0,h=0;
  vector<string> S(N);
  for(int i=0;i<N;i++){
    cin>>S.at(i);
    switch (S.at(i).at(0)){
      case 'M':m++;break;
      case 'A':a++;break;
      case 'R':r++;break;
      case 'C':c++;break;
      case 'H':h++;break;
      default:break;
    }
  }
  cout<<m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h<<endl;
  
  
  
}

Measured memory_bytes: 6144
#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char nc() {
//	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x) {
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f;
}
int X;
inline int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}
int main() {
	read(X);
	printf("%d\n",360/gcd(360,X));
	return 0;
} 

Measured memory_bytes: 3716
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll n; cin>>n;
    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    sort(a.begin(),a.end());
    ll A=a[n-1];
    double b=A/2.0;
    ll c;
    rep(i,n){
        if(a[i]>=b){
            c=i;
            break;
        }
    }
    ll d=a[c];
    ll e=a[c-1];
    ll ans;
    if(d-b<b-e){
        cout<<A<<" "<<d<<endl;
    }
    else {
        cout<<A<<" "<<e<<endl;
    }
}



















































Measured memory_bytes: 1024
#!/usr/bin/python
import sys,math
if sys.version_info[0]>=3: raw_input=input
N=int(raw_input())
for i in range(N):
	x1,y1,x2,y2,x3,y3=[float(e) for e in raw_input().split()]
	a1=2*x2-2*x1
	b1=2*y2-2*y1
	c1=x1*x1-x2*x2+y1*y1-y2*y2
	a2=2*x3-2*x1
	b2=2*y3-2*y1
	c2=x1*x1-x3*x3+y1*y1-y3*y3
	x=(b1*c2-b2*c1)/(a1*b2-a2*b1)
	y=(c1*a2-c2*a1)/(a1*b2-a2*b1)
	print('%.3f %.3f %.3f'%(x,y,math.hypot(x1-x,y1-y)))

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

#define ll long long int

using namespace std;


vector<ll> Zalgo(const string & s) {
    ll n = s.size();
    vector<ll> res(n);
    res[0] = n;
    ll i = 1, j = 0;
    while (i < n) {
        while (i+j < n && s[j] == s[i+j]) ++j;
        res[i] = j;
        if (j == 0) {
            ++i;
            continue;
        }
        ll k = 1;
        while (i + k < n && k + res[k] < j) {
            res [i+k] = res[k];
            ++k;
        }
        i += k;
        j -= k;
    }
    return res;
}

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

    ll res = 0;
    for (ll i = 0; i < n; ++i) {
        string t = s.substr(i);

        auto lcp = Zalgo(t);

        for (ll j = 0; j < t.size(); ++j) {
            ll l = min(lcp[j], j);
            res = max(res, l);
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#define rad(x) (x)*M_PI/180.0
int main(void) {
    double theta1,phi1,theta2,phi2,alpha,x1,x2,y1,y2,z1,z2,r=6378.1;
    while (scanf("%lf%lf%lf%lf",&theta1,&phi1,&theta2,&phi2)!=EOF&&(theta1!=-1||theta2!=-1||phi1!=-1||phi2!=-1)) {
        x1=cos(rad(theta1))*cos(rad(phi1));
        x2=cos(rad(theta2))*cos(rad(phi2));
        y1=cos(rad(theta1))*sin(rad(phi1));
        y2=cos(rad(theta2))*sin(rad(phi2));
        z1=sin(rad(theta1));
        z2=sin(rad(theta2));
        alpha=acos(x1*x2+y1*y2+z1*z2);
        printf("%d\n",(int)(r*alpha+0.5));
    }
    return 0;
}

Measured memory_bytes: 680
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	Q = int(input())
	for i in range(Q):
		A, B = sorted(getlist())
		if A == B:
			print(2 * A - 2)
		elif B == A + 1:
			print(2 * A - 2)
		else:
			C = int(((A * B) ** 0.5) // 1)
			if A * B == C ** 2:
				C -= 1
			if C * (C + 1) >= A * B:
				print(2 * C - 2)
			else:
				print(2 * C - 1)



if __name__ == '__main__':
	main()

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

const int ALPHABET_SIZE = 26;
int glob_ans = 0;

int trie[1000001][26];
std::vector<int> v[200000];
int term[1000001]={0};
int nxt = 1;

void insert(string key, int k)
{
  int i, lvl=0;

  for(i=0;i<key.size();i++)
  {
    v[k].push_back(lvl);
    if(trie[lvl][key[i]-'a']==0) {
      trie[lvl][key[i]-'a'] = nxt++;
    }
    lvl = trie[lvl][key[i]-'a'];
  }
  term[lvl]++;
}

int main()
{
  int i, j, n;
  cin >> n;
    string arr[n];
  for(i=0;i<n;i++)
    cin>> arr[i];

  for(i=0;i<n;i++)
  {
      reverse(arr[i].begin(), arr[i].end());
      insert(arr[i], i);
  }
  int ans = 0;
  for(i=0;i<n;i++)
  {
    set<int> st;
    for(int j=(int)arr[i].size()-1; j>=0;j--)
    {
      int node = v[i][j];
      st.insert(arr[i][j]-'a');
      for(int c=0;c<ALPHABET_SIZE;c++)
        if(st.find(c) != st.end() && term[trie[node][c]])
          ans++;
    }
  }
  cout<< ans-n<<endl;
}


Measured memory_bytes: 119892
<>;
map{push@$_,$_[--$|]for@_=glob}<>;
$m=1e9+7;
sub f{
	my($x,$b,$w)=($_,1,1);
	for(@$x){
		($c,$d)=f($x),$b=$b*$c%$m,$w=$w*$d%$m if$_!="@_"
	}
	$w,$b+$w
}
print+(f++$_)[1]%$m

Measured memory_bytes: 185472
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	using ll = long long;
	ll k; cin >> k;
	const ll inf = 1ll<<60;
	vector<ll> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	ll lo = -inf, hi = inf, ans = 0;
	while(lo <= hi){
		ll mid = (lo + hi)>>1, cnt = 0;
		for(int i = 0; i < n; i++){
			if(a[i] < 0){
				int Lo = 0, Hi = n - 1, Ans = n;
				while(Lo <= Hi){
					int Mid = (Lo + Hi)>>1;
					if(a[Mid] * a[i] <= mid) Hi = Mid - 1, Ans = Mid;
					else Lo = Mid + 1;
				}
				cnt += n - Ans;
			} else {
				int Lo = 0, Hi = n - 1, Ans = -1;
				while(Lo <= Hi){
					int Mid = (Lo + Hi)>>1;
					if(a[Mid] * a[i] <= mid) Lo = Mid + 1, Ans = Mid;
					else Hi = Mid - 1;
				}
				cnt += Ans + 1;
			}
			if(a[i] * a[i] <= mid) cnt--;
		}
		cnt /= 2;
		if(cnt >= k) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
#ABC115C
import sys

tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n = hoge[0]
k = hoge[1]

h=[]
for i in range(0,n):
	tmp = int(input())
	h.append(tmp)

h.sort()
#print(h)
#print(n)
#print(k)

res=h[k-1]-h[0]
#print(res)

for i in range(1,n-k+1):
	res = min(res,h[k+i-1]-h[i])
	#print("i:{} res:{}".format(i,res))
print(res)



Measured memory_bytes: 7384
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
int h,w,n,cnt;
LL k,ans,p;
int ask(int a,int b,int c,int d){
	cout<<"? "<<a<<" "<<b<<" "<<c<<" "<<d<<"\n"<<flush;
	int res;
	cin>>res;
	return res;
}
int main() {
	cin>>h>>w>>n>>k;
	p=1;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			int flag=ask(i,j,i,j);
			cnt+=flag;
			if(flag)ans=(ans+p)%k;
			if(cnt==n)break;	
			p=p*2%k;
		}
	}
	cout<<"! "<<ans<<"\n"<<flush;
    return 0;
}


Measured memory_bytes: 3764
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define double long double
#define minheapair priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>> >
#define maxheapair priority_queue<pair<int,int>>
#define minheap priority_queue<int,vector<int>,greater<int>>
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define msi map<string,int>
#define set set<int>
#define u_set unordered_set<int>
#define pb push_back
#define endl "\n"
#define ll long long int
#define vll vector<long long int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define umap unordered_map
#define mod 1000000007
#define fori(a,n) for(int i=a;i<n;i++)
#define forj(a,n) for(int j=a;j<n;j++)
// #define MAX 300303
#define V vector
#define inf 9219999999999999999
using namespace std;
//  inline bool operator<(const data& lhs, const data& rhs)
//  {
//      if(lhs.val< rhs.val)return 1;
//      return 0;
//  }
// inline bool operator>(const data& lhs, const data& rhs)
//  {
//      if(lhs.val > rhs.val)return 1;
//      return 0;
//  }
ll modexp(ll x,ll y,ll m){
    ll ans = 1;
    while(y>0){
        if(y&1){
            ans *= x;
            ans %= m;
            --y;
        }
        else{
            y /= 2;
            x *= x;
            x %= m;
        }
    }
    return ans;
}
ll minv(ll a,ll m){
    return modexp(a,m-2,m);
}
void Z(string s,vector<int>&z){
    int L = 0, R = 0;
    int n = s.size();
    for (int i = 1; i < n; i++) 
    {
        if (i > R) 
        {
            L = R = i;
            while (R < n && s[R-L] == s[R]) 
            {
                R++;
            }
            z[i] = R-L; 
            R--;
        } 
        else 
        {
            int k = i-L;
            if (z[k] < R-i+1) 
            {
                z[i] = z[k];
            } 
            else 
            {
                L = i;
                while (R < n && s[R-L] == s[R]) 
                {
                    R++;
                }
                z[i] = R-L; 
                R--;
            }
        }
    }
}

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
class comp{
    public:
    bool operator () (pair<ll,ll>a,pair<ll,ll>b){return 1LL*a.first*a.second <= 1LL*b.first*b.second;}
};
using namespace std;

int main() {
    io
    int tt = 1;
    // cin>>tt;
    while(tt--){
        string s;
        cin>>s;
        ll n=0; for(auto car:s)n += car-'0';
        if(n%9)cout<<"No\n";
        else cout<<"Yes\n";
    }
}
/*
1                                 
7  
1 2
1 3  
2 4
2 5
3 6
3 7
0010010
*/










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

using namespace std;
#define ll long long
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
const ll mod = 1e9 + 7;

int main (){
    char b;
    cin >> b;
    if(b == 'A'){
        cout << 'T' << endl;
    }
    if(b == 'T') cout << 'A' << endl;
    if(b == 'C') cout << 'G' << endl;
        if(b == 'G') cout << 'C' << endl;



    

    return 0;
}

Measured memory_bytes: 256
line1 = gets.split(' ')
line2 = gets.split(' ')
 
newline2 = line2.sort {|a, b| b.to_i <=> a.to_i } 
counter = 0
h = 0
 
while h <= line1[0].to_i - 2
  i = 1
  while i <= line1[0].to_i - 2
    j = 1
    while i + j <= line1[0].to_i - 1
      if newline2[h].to_i >= newline2[i].to_i + newline2[i+j].to_i || h > i || h > i+j
      else
        if newline2[h].to_i == newline2[i].to_i || newline2[h].to_i == newline2[i+j].to_i || newline2[i].to_i == newline2[i+j].to_i
        else
          counter += 1
        end
      end
      j += 1
    end
    i += 1
  end
  h += 1
end
 
 
p counter

Measured memory_bytes: 14340
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,ans=0;
int n,num[15];
inline void dfs(int pos,ll sum){
	if(pos==n+1){ans+=sum;return;}
	ll tmp=0;
	for(int i=pos;i<=n;++i) {
        tmp=tmp*10+num[i];
        //cout <<endl<<num[pos] << ": "<< num[i] << ", " << tmp << endl;
        dfs(i+1,sum+tmp);
	}
	cout << endl;
}
int main(){
	cin>>x;
	while(x)num[++n]=x%10,x/=10;
	reverse(num+1,num+n+1);
	dfs(1,0);
	cout<<ans;
	return 0;
}


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

using namespace std;

typedef long long ll;
#define int ll
typedef long double ld;

typedef pair<int,int> pii;
#define x first
#define y second

const int N=3010,MOD=998244353;

int a[N],dp[N][N];

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

    int n,s;
    cin>>n>>s;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=s;j++)
            dp[i][j]=dp[i-1][j];
        dp[i][0]+=1;
        for(int j=s;j-a[i]>=0;j--)
            dp[i][j]+=dp[i][j-a[i]];
        for(int j=0;j<=s;j++)
            dp[i][j]%=MOD;
        ans+=dp[i][s];
//        for(int j=0;j<=s;j++)
//            cout<<dp[i][j]<<" ";
//        cout<<"\n";
    }
    cout<<ans%MOD;
}


Measured memory_bytes: 70784
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MOD2 1494318097
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 55

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int len,K;
ll dp[MAXN][MAXN][2*MAXN*MAXN];

inline int conv(int i){return i+MAXN*MAXN;}

ll solve(int idx, int unp, int K){
	if(idx == 0){
		if(unp == 0 && K == 0) return 1;
		return 0;
	}
	if(dp[idx][unp][conv(K)] != -1) return dp[idx][unp][conv(K)];
	ll res = solve(idx-1,unp,K);
	res = (res+solve(idx-1,unp+1,K-2*idx)*(unp+1)*(unp+1))%MOD;
	res = (res+solve(idx-1,unp-1,K+2*idx))%MOD;
	if(unp) res = (res+solve(idx-1,unp,K)*unp*2)%MOD;
	return dp[idx][unp][conv(K)] = res;
}

int main(){
	scanf("%d %d",&len,&K);
	memset(dp,-1,sizeof dp);
	printf("%lld\n",solve(len,0,K));
}
/*
4 8
ans=4
 */

Measured memory_bytes: 143232
#include <bits/stdc++.h>
#define NMAX 15
using namespace std;
vector < pair<int,int> > t[NMAX]; 
int n,maxim;
int nr_biti(int mask)
{
    int nr=0;
    do
    {
        nr++;
        mask&=(mask-1);
    } 
    while (mask);
    return nr;
}
int check(int mask)
{
    for(int i=0;i<n;i++)
    {
        if(mask&(1<<i))
        {
            for(int j=0;j<(int)t[i].size();j++)
            {
                if(t[i][j].second==1)
                {
                    int bit=(mask&(1<<(t[i][j].first)));
                    if(bit==0)
                        return 0;
                }
                if(t[i][j].second==0)
                {
                    int bit=(mask&(1<<(t[i][j].first)));
                    if(bit)
                        return 0;
                }
            }
        }
    }
    return nr_biti(mask);
}
int main()
{
    cin>>n;
     for(int i=0;i<n;i++)
    {
        int x,y,sz;
        cin>>sz;
        for(int j=0;j<sz;j++)
        {
            cin>>x>>y;
            x--;
            t[i].push_back({x,y});
        }
    }
    //cout<<check(1)<<" "<<check(2)<<" "<<check(4)<<"\n";
    //cout<<check(4);
    for(int mask=1;mask<(1<<n);mask++)
    {
        maxim=max(maxim,check(mask));
    }
    cout<<maxim;
    return 0;
}

Measured memory_bytes: 256
import math

def main(n, m):
    rissoku = min(m)

    retval = 4 + math.ceil(n/rissoku)
    
    return '{}'.format(int(retval))

if __name__ == '__main__':
    try:
        m = []
        n = int(input().strip())
        for i in range(5):
            m.append(int(input().strip()))
        print('{}'.format(main(n, m)))
    except EOFError:
        pass


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define IN freopen("C.in","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG pf("Hi\n")
#define i64 long long int
#define ui64 unsigned long long int
#define eps (1e-10)
#define xx first
#define yy second
#define ln 17
#define off 2

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL)


using namespace __gnu_pbds;
using namespace std ;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<int,int> pii;

#define log 20
#define mod 1000000007LL
#define maxn 2000005
#define INF 1000000000000000000LL

i64 dp[2][5005][5005] ;
i64 sum[5005] ;

i64 p2[5005] ;

int main()
{
    int n , a , b ;

    scanf("%d %d %d",&n,&a,&b) ;

    if( a<b ) swap(a,b) ;

    p2[0] = 1 ;
    for(int i=1 ; i<=n ; i++)
    {
        p2[i] = (2LL*p2[i-1])%mod ;
    }

    if(b==1)
    {
        printf("%lld\n",p2[n]) ;
        return 0 ;
    }

    for(int j=a ; j<=n ; j++)
    {
        dp[0][0][j] = 1 ;
        dp[1][0][j] = 1 ;
    }

    for(int i=1 ; i<=n ; i++)
    {
        for(int j=0 ; j<a ; j++)
        {
            if( i>=2 )
            {
                int mx = min( i , b ) ;
                dp[0][i][j] = sum[i-2] ;
                if( i-mx-1 >=0 ) dp[0][i][j] -= sum[ i-mx-1  ] ;
            }

            dp[0][i][j] += dp[0][i-1][j+1] ;
            if( b<=i ) dp[0][i][j] += dp[1][i-b][ j+b ] ;

            dp[0][i][j] %= mod ;

            dp[1][i][j] = ( dp[1][i-1][j+1] + dp[0][i-1][j+1] )%mod ;
        }
        for(int j=a ; j<=n ; j++)
        {
            dp[0][i][j] = dp[1][i][j] = p2[i] ;
        }
        sum[i] = (sum[i-1] + dp[0][i][1])%mod ;
    }

    printf("%lld\n" , (dp[0][n][0]%mod + mod)%mod ) ;

    return 0 ;
}


Measured memory_bytes: 395000
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

struct Cow{
	using D = int;
	const D inf = 1e9;
	struct Edge{
		int to;
		D cost;
		Edge(int to,D cost):to(to),cost(cost){}
	};
	int N,M;
	vector<vector<Edge>> G;
	vector<D> d;
	Cow(int N):N(N){
		G.assign(N,vector<Edge>());
		d.assign(N,inf);
	}
	void add_edge(int t,int s,D c){	// correspond to t-s <= c
//		printf("%d->%d   :%d\n",t,s,c);
		G[s].pb(Edge(t,c));
	}
	void add_edge(int t,int s,D clow,D chigh){	// clow <= t-s <= chigh
		add_edge(t,s,chigh);
		add_edge(s,t,-clow);
	}
	/*
		return the inequalities have a valid assignment
		if satisfiable, minimize d[T]-d[S]

		negative cycle    <=> unsatisfiable
		d[T] - d[S] = inf <=> feasible unboundedly

		d[S]=0

		T??????????????????????(?°???\???)
	*/
	bool IsValidAssign(int S = 0){
		vector<int> prev(N);
		d[S] = 0;
		rep(ph,N){
			bool update = 0;
			int v = -1;
			rep(s,N) for(auto e:G[s]){
				int t = e.to;
				D cost = e.cost;
				if(d[s]+cost < d[t]){
					update=1;
					v = t;
					d[t] = d[s]+cost;
					prev[t] = s;
				}
			}
			if(ph == N-1 && update){
				// vector<int> path;
				// path.pb(v);
				// int u = v;
				// do{
				// 	show(u);
				// 	u = prev[u];
				// 	path.pb(u);
				// }while(u!=v);
				// reverse(all(path));
				// show(path);
				// show(d[7]);
				// show(d[15]);
				return 0;
			}
			if(!update) break;
		}
		return 1;
	}
};

int W;
bool can(string s){
	int N = s.size();
	int V = N*2;
	Cow cow(V);
	rep(i,N){
		int clow = 0, chigh = 1;
		if(s[i]=='0') chigh = 0;
		if(s[i]=='1') clow = 1;
		cow.add_edge(i+N,i,clow,chigh);
		rep(t,2){
			int ni = (i*2+t)%N;
			cow.add_edge(ni,i+N,-t,-t);
		}
	}
	return cow.IsValidAssign();
}

string solve(){
	string s;
	cin>>W>>s;
	W = W*2+1;
	int N = s.size();
	if(can(s)) return s;
	int I = -1;
	for(int i=N-1;i>=0;i--){
		if(s[i]=='0'){
			s[i]='1';
			for(int j=i+1;j<N;j++) s[j]='*';
			if(can(s)){
				I = i;
				break;
			}
		}
	}
	if(I==-1) return "no";
	for(int i=I+1;i<N;i++){
		s[i]='0';
		if(can(s)) continue;
		else s[i]='1';
	}
	return s;
}
int main(){
	cout<<solve()<<endl;
}

Measured memory_bytes: 3196
#include<iostream>
    #include<string>
    #include<algorithm>
    #include<vector>
    #include<iomanip>
    #include<math.h>
    #include<complex>
    #include<queue>
    #include<deque>
    #include<stack>
    #include<map>
    #include<set>
    #include<bitset>
    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)
    typedef long long ll;
    typedef pair<int,int> pint;
    typedef pair<ll,int> pli;
    typedef pair<ll,ll> pll;
    const int inf=1e9+7;
    const ll longinf=1LL<<60 ;
    const ll mod=1e9+7 ;
        using namespace std;

        int main(){
          int n;
          cin >> n;
          double a[n];
          double b[n];
          rep(i,n){
            cin >> a[i];
          }
          double ave=0;
          rep(i,n)ave+=a[i];
          ave/=n;
          rep(i,n)b[i]=abs(ave-a[i]);
          sort(b,b+n);
          rep(i,n){
           if(abs(ave-a[i])==b[0]){
            cout << i << endl;
             return 0;
           }
          }
          return 0;}


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

using namespace std;
 
int main() {
    int A,B;
    cin >> A >> B;
    int sum ;
    sum = A;
    int legs;
    legs = B;
    for(int i = 0;i <= A;i++){
        for(int j = 0;j <=A ; j++){
            if(i + j == sum){
                int test = 0;
                test = 2*i + 4*j;
                if(test == legs){
                    cout <<"Yes"<<endl;
                    return 0;
                }
                
            }
        }
        
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3628
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;
typedef long long ll;

int main() {
    cout << fixed << setprecision(10);
    int n; cin >> n;
    double sum = 0;
    for (int i = 0; i < n; i++) {
        double a; cin >> a;
        sum += 1 / a;
    }
    cout << 1 / sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      if(n==i*j) {
        cout << "Yes";
        return 0;
      }
    }
  }
  cout << "No";
}

Measured memory_bytes: 256
function Main(input) {
    a = input.split("\n")[0];
    b = input.split("\n")[1];
    c = input.split("\n")[2];
    x = input.split("\n")[3];

    var count = 0;
    
    for (var i = 0; i <= a; i++) {
        for (var j = 0; j <= b; j++) {
            for (var k = 0; k <= c; k++) {
                if (500 * i + 100 * j + 50 * k == x ) {
                    count++;
                }
            }
        }
    } 

    console.log(count)
  
    }
  Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  

Measured memory_bytes: 7500
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18+1;
const ll DIV = 1000000007;
//#define TEST
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    long N;
    cin >> N;
    map<long, long> A;
    for(size_t i=0;i<N; i++)
    {
        long a;
        cin >> a;
        A[a]++;
    }
    ll max_area = 0;
    ll first_edge=0,second_edge =0;
    for(auto a:A)
    {
        if(a.second >=2)
        {
            if(first_edge == 0) first_edge = a.first;
            if(a.second >= 4)
            {
                first_edge = a.first;
                second_edge = a.first;
            }else
            {
                first_edge = second_edge;
                second_edge = a.first;
            }

        }
        if(first_edge != 0 && second_edge != 0) max_area = max(max_area, first_edge * second_edge);
    }
    cout << max_area << endl;
#ifdef TEST
    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << "[ms]" << endl;
#endif
    return 0;
}

Measured memory_bytes: 9788
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


template<class Abel> struct UnionFind{
    VI par, rank;
    vector<Abel> diff_weight;
    UnionFind(int n=1, Abel SUM_UNITY=0){
        init(n, SUM_UNITY);
    }
    void init(int n=1, Abel SUM_UNITY=0){
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        rep(i,n) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }
    int root(int x){
        if(par[x]==x) return x;
        int r = root(par[x]);
        diff_weight[x] += diff_weight[par[x]];
        return par[x] = r;
    }
    Abel weight(int x){
        root(x);
        return diff_weight[x];
    }
    bool issame(int x, int y){
        return root(x)==root(y);
    }
    bool merge(int x, int y, Abel w){
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if(x==y) return false;
        if(rank[x]<rank[y]) swap(x, y), w = -w;
        if(rank[x]==rank[y]) rank[x]++;
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }
    Abel diff(int x, int y){
        return weight(y)-weight(x);
    }
};

int main() {
    int n,m; cin>>n>>m;
    UnionFind<int> uf(n);
    rep(i,m){
        int l,r,d; cin>>l>>r>>d; l--; r--;
        if(uf.issame(l,r)){
            int diff=uf.diff(l,r);
            if(diff!=d){
                cout << "No" << endl;
                return 0;
            }
        }
        else{
            uf.merge(l,r,d);
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w[1<<16], v[16][16], dp[1<<16];
int main() {
	int n;
	cin >> n; 
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> v[i][j];
		}
	}
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			for (int k = j + 1; k < n; ++k) {
				if ((i >> j) & 1 & (i >> k)) {
					w[i] += v[j][k];
				}
			}
		}
	}
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = i; j; j = (j - 1) & i) {
			dp[i] = max(dp[i], w[j] + dp[i ^ j]);
		}
	}
	cout << dp[(1 << n) - 1] << endl;
	return 0;
}

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

int main(){
    int n,k;
    string s;
    cin >> n >> k;
    cin >> s;
    int count=0;
    for(int i=0; i<n-1; i++){
        if(s.at(i) != s.at(i+1)) count++;
    }
    cout << n-1-max(count-2*k, 0) << endl;
}


Measured memory_bytes: 3728
N=int(input())
A=list(map(int,input().split()))
s=sum(A)
num=[0]*100001
for i in A:
    num[i]+=1
for _ in range(int(input())):
    B,C=map(int,input().split())
    s+=(C-B)*num[B]
    num[C]+=num[B]
    num[B]=0
    print(s)

Measured memory_bytes: 20992