akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <fstream>

#define SMAX 1000
#define QMAX 150

using namespace std;

int main()
{
  int q;
  cin >> q;
  
  char X[SMAX], Y[SMAX];
  int LCS[SMAX+1][SMAX+1] = {0};
  int Anwser[QMAX];
  for(int i = 0; i<q; i++) {
    scanf("%s",X);
    scanf("%s",Y);
    int size_X = strlen(X);
    int size_Y = strlen(Y);
    for(int j = 0; j <= size_X; j++) LCS[j][0] = 0;
    for(int j = 0; j <= size_Y; j++) LCS[0][j] = 0;

    for(int j = 1; j <= size_X; j++) {
      for(int k = 1; k <= size_Y; k++) {
	if(X[j-1] == Y[k-1]) LCS[j][k] = LCS[j-1][k-1] + 1;
	else LCS[j][k] = max(LCS[j-1][k], LCS[j][k-1]);
      }
    }
    Anwser[i] = LCS[size_X][size_Y];
  }

  for(int i = 0; i<q; i++) cout << Anwser[i] << endl;

  return 0;
}


Measured memory_bytes: 7068
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <climits>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i, 0, n)

typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;

int main() {
	int W, H;
	while (cin >> W >> H, W || H) {
		vvi visited = vvi(H, vi(W, false));
		vvvvi wall = vvvvi(H, vvvi(W, vvi(H, vi(W, false))));
		REP(i, H) {
			REP(j, W-1) {
				bool b; cin >> b;
				if (b) {
					wall[i][j][i][j+1] = true;
					wall[i][j+1][i][j] = true;
				}
			}
			if (i == H-1) break;
			REP(j, W) {
				bool b; cin >> b;
				if (b) {
					wall[i][j][i+1][j] = true;
					wall[i+1][j][i][j] = true;
				}
			}
		}



		int ans = 0;
		// < y, x >, steps
		queue<pair<pii, int> > q;
		q.push(make_pair(pii(0, 0), 1));
		while(!q.empty()) {
			pair<pii, int> t = q.front(); q.pop();
			int y = t.first.first, x = t.first.second;
			int cost = t.second;

			if(visited[y][x]) continue;
			visited[y][x] = true;

			// fprintf(stderr, "visiting (%d, %d)\n", y, x);
			// Goal
			if (y == H-1 && x == W-1) {
				// cerr << "Goal" << endl;
				ans = cost;
				break;
			}

			int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1};
			REP(d, 4) {
				int ny = y + dy[d], nx = x + dx[d];
				if ( !((0 <= ny && ny < H) && (0 <= nx && nx < W)) ) {
					continue;
				}
				if ( wall[y][x][ny][nx] ) continue;

				q.push(make_pair(pii(ny, nx), cost + 1));
			}
		}

		cout << ans << endl;
	}
}

Measured memory_bytes: 5564
#include <iostream>
#include <vector>
using namespace std;
int x[110];
vector<int> v,a,b;
int main(){
	int i,n,m,j;
	cin >> n >> m;
	for(i=0;i<m;i++){
		cin >> x[i];
		if(x[i]&1){
			v.push_back(x[i]);
		}
	}
	if(v.size()>2){
		cout << "Impossible" << endl;
		return 0;
	}
	if(v.size()){
		a.push_back(v.back());
		v.pop_back();
	}
	for(i=0;i<m;i++){
		if(!(x[i]&1)) a.push_back(x[i]);
	}
	if(v.size()){
		a.push_back(v[0]);
	}
	for(i=0;i<m;i++){
		cout << a[i] << " ";
	}
	cout << endl;
	if(m==1){
		if(n==1){
			cout << 1 << endl;
			cout << 1 << endl;
		}else{
			cout << 2 << endl;
			cout << 1 << " " << n - 1 << endl;
		}
		return 0;
	}
	b.push_back(a[0] + 1);
	for(i=1;i<m-1;i++){
		b.push_back(a[i]);
	}
	if(a[m - 1]!=1) b.push_back(a[m - 1] - 1);
	cout << b.size() << endl;
	for(i=0;i<b.size();i++){
		cout << b[i] << " ";
	}
	cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
typedef pair<ll, ll> Pair;
template <class T> T input() {T t; cin>>t; return t;}
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define FIND(x,key) x.find(key) != x.end()
#define IN_RANGE_V2(v,k,x,y) (0<=x+dx[k]&&x+dx[k]<v[y].size()&&0<=y+dy[k]&&y+dy[k]<v.size())
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define PRINT_ARRAY_H(a) REPALL(__i,a) {cout<<a[__i]<<(__i != a.size()-1 ? " " : "");} newline;
#define PRINT_ARRAY_V(a) REPALL(__i,a) {cout<<a[__i]<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
#define cspace ' '
#define sspace " "
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};
//const VI dx = {1, 1, 0, -1, -1, -1, 0, 1};
//const VI dy = {0, 1, 1, 1, 0, -1, -1, -1};

void solve()
{
    ll a, b, c, d, n, m, l, r, k, x, y, z, ans = 0ll;
    string s, t;
    cin>>a>>b>>c>>k;
    REP(i,k) {
        if (a >= b) b *= 2;
        else c *= 2;
    }
    Yes(a<b&&b<c);
}

int main()
{
    cout<<fixed<<setprecision(20);
    int __t = 1;
    //cin>>__t;
    REP(i,__t) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3628
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, L: "List[int]"):
    m = max(L)
    print(YES if m < sum(L) - m else NO)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
/*input
6
3 2 2 2 2 2
1 2
2 3
1 4
1 5
4 6
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}

//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}
int a[maxn];
int up[maxn];
bool vis[maxn];
vector<int> edge[maxn];
int leaf=0;
void dfs(int u){
	// cout<<u<<'\n';
	vis[u]=1;
	ll sum=0;
	int mx=0;
	bool isleaf=1;
	for(int v:edge[u]) if(!vis[v]){
		isleaf=0;
		dfs(v);
		sum+=up[v];
		mx=max(mx,up[v]);
	}
	if(isleaf){
		up[u]=a[u];
		return;
	}
	if(sum<a[u]){
		cout<<"NO\n";
		exit(0);
	}
	if(a[u]+a[u]<sum){
		cout<<"NO\n";
		exit(0);
	}
	if(mx>a[u]){
		cout<<"NO\n";
		exit(0);
	}
	up[u]=sum-2*(sum-a[u]);
	// cout<<u<<' '<<up[u]<<'\n';
	if(u==leaf){
		if(up[u]==a[u]) cout<<"YES\n";
		else cout<<"NO\n";
		exit(0);
	}
}

int main(){
	IOS;
	int n;
	cin>>n;
	REP(i,n) cin>>a[i];
	REP(i,n-1){
		int u,v;
		cin>>u>>v;
		u--;v--;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	while(SZ(edge[leaf])!=1) leaf++;
	dfs(leaf);
	return 0;
}


Measured memory_bytes: 19712
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    int a, b, k; cin>>a>>b>>k;
    vector<int> v;
    for(int i=1; i<=100; i++){
        if(a%i==0 && b%i==0) v.push_back(i);
    }
    reverse(v.begin(), v.end());

    cout << v[k-1] << endl;
}

Measured memory_bytes: 256
n,x = map(int, input().split())
l = list(map(int, input().split()))


dList = [0]
c = 1
for i in range(n):
  addElm = dList[i]+l[i]
  if addElm <= x:
    c += 1
    dList.append(addElm)
  else:
    break
  
print(c)

Measured memory_bytes: 38256
#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    int a, b, c, d;
    
    scanf("%d %d", &a,&b);
    c = a*b;
    d = a*2+b*2;
    printf("%d %d\n", c, d);
    
    return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
int GCD(int A,int B)
{
  if(!B)
    return A;
  return GCD(B,A%B);
}
int main()
{
  int N;
  cin>>N;
  cout<<360/GCD(360,N)<<endl;
  return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String p = scanner.nextLine();	//vanceknowledgetoad
		String _p = p+p;				//vanceknowledgetoadvanceknowledgetoad
		String s = scanner.nextLine();	//advance
		if (_p.contains(s)) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
		scanner.close();
	}
}


Measured memory_bytes: 26292
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
const int N=55556;
vector<int> isprime(N,1);
vector<int> prime;
void  solve(){
	rep(i,2,N){
		for(int j=2*i;j<N;j+=i) isprime[j]=0;
	}
	rep(i,2,N) if(isprime[i]) prime.pb(i);
	int n,i=0;
	cin>>n;
	while(n>0 && i<prime.size()){
		if(prime[i]%5==2) cout<<prime[i]<<" ",n--;
		i++;
	}
	cout<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}


Measured memory_bytes: 3660
/*
 * Dessert Witch
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311
 */

#include <bits/stdc++.h>

using namespace std;

// #define LOG(...) fprintf(stderr, __VA_ARGS__)
#define LOG(...)
#define FOR(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SQ(n) (n) * (n)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

struct P {
  int x, y;
  vpi l;
  int score;
};

char field[8][8];

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

template <typename T> bool select(T t, char c1, char c2){
  vector<P> v;

  REP(y, 8) REP(x, 8){
    if(field[y][x] != '.') continue;

    vpi l;
    REP(i, 8){
      int sx = x + dx[i];
      int sy = y + dy[i];
      if(0 <= sx && sx < 8 && 0 <= sy && sy < 8 && field[sy][sx] == c2) {
        vpi ll;
        while(0 <= sx && sx < 8 && 0 <= sy && sy < 8 && field[sy][sx] == c2) {
          ll.push_back({sx, sy});
          sx += dx[i];
          sy += dy[i];
        }
        if(0 <= sx && sx < 8 && 0 <= sy && sy < 8 && field[sy][sx] == c1) {
          for(pii p : ll) {
            l.push_back(p);
          }
        }
      }
    }

    if (!l.empty()) {
      LOG("(%d %d) %d\n", x, y, (int)l.size());
      l.push_back({x, y});
      v.push_back({x, y, l, (int)l.size()});
    }
  }

  LOG("size() %d\n", (int)v.size());
  if (v.empty()) return true;
  sort(RALL(v), t);
  LOG("(%d %d)\n", v[0].x, v[0].y);
  for(pii p : v[0].l) {
    LOG("\t(%d %d) %c\n", p.first, p.second, c1);
    field[p.second][p.first] = c1;
  }
  return false;
}

void printWorld(){
  REP(y, 8) {
    REP(x, 8){
      cout << field[y][x];
    }
    cout << endl;
  }
}

int main() {
  auto A = [](P a, P b){
             return a.score * 1000 - a.y * 10 - a.x < b.score * 1000 - b.y * 10 - b.x;
           };
  auto B = [](P a, P b){
             return a.score * 1000 + a.y * 10 + a.x < b.score * 1000 + b.y * 10 + b.x;
           };

  REP(y, 8) REP(x, 8){
    cin >> field[y][x];
  }

  while(1) {
    int flag = 0;

    if(select(A, 'o', 'x')) flag |= 1;
    if(select(B, 'x', 'o')) flag |= 2;

    if(flag == 3) break;
  }

  printWorld();
}

Measured memory_bytes: 3120
N, Y = input().strip().split(' ')
N, Y =[int(N),int(Y)]

x = -1
y = -1
z = -1

for i in range(0,N+1):
    for j in range(0,N-i+1):
        if 4*i+9*j == Y/1000 - N:
            x = N - i - j
            y = i
            z = j
print(z,y,x)

Measured memory_bytes: 3064
#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;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
int x[501];
int a[250001];
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	deque<ii> require;
	deque<ii> require2;
	vector<ii> v;
	for(int i = 1; i <= n; i++)
	{
		cin>>x[i];
		x[i]--;
		if(a[x[i]]!=0)
		{
			cout<<"No\n"; return 0;
		}
		a[x[i]]=i;
		v.pb(mp(x[i],i));
	}
	sort(v.begin(),v.end());
	for(int i = 0; i < n; i++)
	{
		if(v[i].se>1) require.pb(mp(v[i].se-1,v[i].se));
	}
	int ptr = 0;
	for(int i = 0; i < n; i++)
	{
		while(ptr<v[i].fi)
		{
			if(require.empty()&&require2.empty())
			{
				cout<<"No\n"; return 0;
			}
			if(!require.empty())
			{
				a[ptr] = require.front().se;
				require.front().fi--;
				if(require.front().fi==0) require.pop_front();
			}
			else
			{
				a[ptr] = require2.front().se;
				require2.front().fi--;
				if(require2.front().fi==0) require2.pop_front();
			}
			ptr++;
		}
		ptr++;
		if(n-v[i].se>0) require2.pb(mp(n-v[i].se,v[i].se));
	}
	if(!require.empty())
	{
		cout<<"No\n"; return 0;
	}
	while(ptr<n*n)
	{
		if(require2.empty())
		{
			cout<<"No\n"; return 0;
		}
		a[ptr] = require2.front().se;
		require2.front().fi--;
		if(require2.front().fi==0) require2.pop_front();
		ptr++;
	}
	int cnt[n+1];
	memset(cnt,0,sizeof(cnt));
	for(int i = 0; i < n*n; i++)
	{
		cnt[a[i]]++;
		if(cnt[a[i]]>n)
		{
			cout<<"No\n"; return 0;
		}
		if(cnt[a[i]]==a[i]&&i!=x[a[i]])
		{
			cout<<"No\n"; return 0;
		}
	}		
	
	cout<<"Yes\n";
	for(int i = 0; i <n*n;i++)
	{
		cout<<a[i];
		if(i<n*n-1) cout<<' ';
	}
	cout<<'\n';
}

Measured memory_bytes: 2176
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;
int main()
{
	int r, c;
	int sum = 0;
	int sum2 = 0;
	cin >> r >> c;
	int a[200][200];
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> a[i][j];
		}
	}
	int b[200][200];
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << a[i][j] << " ";
			sum+= a[i][j];
			if (j == c - 1) {
				cout << sum << endl;
				sum2+= sum;
				sum = 0;
			}
		}
	}
	for (int j = 0; j < c; j++) {
		for (int i = 0; i < r; i++) {
			sum += a[i][j];
		}	
		cout << sum << " ";
		sum = 0;
	}
	cout << sum2 << endl;
}




Measured memory_bytes: 3084
p,h,l,s,w,b=print,80,40,list,'.','#'
W,B=s(map(int,input().split()))
ret=s(map(list,zip(*[iter(w*h*l+b*h*l)]*h)))

for bidx in range(B-1):
 ret[bidx//l*2][bidx%l*2]=b

for widx in range(W-1):
 ret[79-widx//l*2][79-widx%l*2]=w

p(h,h)
[p(''.join(line)) for line in ret]


Measured memory_bytes: 38256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int q;
    while(cin >> q, ~q){
        double x = q/2.0;
        while(abs(x*x*x-q) >= 0.00001*q){
            x = x-(x*x*x-q)/(3*x*x);
        }
        printf("%.10lf\n", x);
    }
    return 0;
}


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

int main(){
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++){
		if(i % 3 == 0){
			cout<<" "<<i;
			continue;
		}
		int j = i;
		while(j>0){
			if(j % 10 == 3){
				cout<<" "<<i;
				break;
			}else j /= 10;
		}
	}
	cout<<endl;

	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
double PI=acos(-1);

int n,m;
struct node{
    int x,y;
}a[55],b[55];

int f(int a,int b)
{
    return a-b>0? a-b:b-a;
}


int main()
{
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        for(int i=0;i<m;i++){
            scanf("%d%d",&b[i].x,&b[i].y);
        }
        node s;
        for(int i=0;i<n;i++){
            s.x=INF;
            for(int j=0;j<m;j++){
                if(f(a[i].x,b[j].x)+f(a[i].y,b[j].y)<s.x){
                    s.x=f(a[i].x,b[j].x)+f(a[i].y,b[j].y);
                    s.y=j+1;
                }
            }
            cout<<s.y<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
##https://atcoder.jp/contests/dp/tasks/dp_a

N = int(input())
##N, M = map(int, input().split())

H = list(map(int, input().split()))
C = [0]*N#Nに飛ぶ時の最小コストの格納


C[0] = 0
C[1] = abs(H[0] - H[1])

for i in range(2, N):
    if C[i-2] + abs(H[i] - H[i-2]) > C[i-1] + abs(H[i] - H[i-1]):
        C[i] = C[i-1] + abs(H[i] - H[i-1])
    elif C[i-2] + abs(H[i] - H[i-2]) < C[i-1] + abs(H[i] - H[i-1]):
        C[i] = C[i-2] + abs(H[i] - H[i-2])
    else:
        C[i] = C[i-2] + abs(H[i] - H[i-2])        
print(C[N-1])


Measured memory_bytes: 13924
#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 all(v) v.begin(),v.end()
#define ll long long
#define pb(a) push_back(a)
#define pf(a) push_flont(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int main(){
        
        int d;
        cin >> d;
        cout << "Christmas" ;
        REP(i,25-d){
                cout << " Eve";
        }
        cout << endl;

        return 0;
}


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

int main() {
	int N;
	cin >> N;
	vector<int> A(N), ded(1e6+5), done(1e6+5);
	for (int& e : A) cin >> e;
	sort(A.begin(), A.end());
	int ans = 0, dups = 0;
	for (int a : A) {
		if (!ded[a]) ++ans;
		if (done[a]) {
			if (done[a] == 1) {
				done[a] = 2;
				++dups;
			}
			continue;
		}
		done[a] = ded[a] ? 2 : 1;
		int mult = a;
		// cout << a << endl;
		while (mult <= 1e6) {
			ded[mult] = 1;
			mult += a;
		}
	}
	cout << ans-dups << endl;
}

Measured memory_bytes: 11900
#include<stdio.h>
int main(){
	char s[10][10];
	int i,j,k;
	int x[7][3]={0,1,1, 0,0,0, 1,2,3, 0,-1,-1, 1,1,2, 0,1,1, -1,0,1};
	int y[7][3]={1,0,1, 1,2,3, 0,0,0, 1,1,2, 0,1,1, 1,2,2, 1,1,0};
	while(scanf("%s\n",s[0])!=EOF){
		for(i=1;i<8;i++)scanf("%s\n",s[i]);
		scanf("\n");
		for(i=0;i<8;i++){for(j=0;j<8;j++){
			if(s[i][j]=='1'){
				for(k=0;k<7;k++){
					if(s[i+y[k][0]][j+x[k][0]]=='1' && 
					   s[i+y[k][1]][j+x[k][1]]=='1' && 
					   s[i+y[k][2]][j+x[k][2]]=='1'){
						printf("%c\n",'A'+k);
						break;
					}
				}
			}
		}
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = LLONG_MAX;
const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    string S;
    cin >> S;
    char cur = 'A';
    int cnt = 0;
    for (auto s : S) {
        if (cur != s) {
            cur = s;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

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

n=int(input())
t,a=map(int,input().split())
l=list(map(int,input().split()))
for i in range(n):
    l[i]=abs(a-t+0.006*l[i])
    #print(l)
b=10**3   
for i in range(0,n):
    b=min(b,l[i])
print(l.index(b)+1)

Measured memory_bytes: 3064
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#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)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void Taka() { cout << "Takahashi" << endl; }
void Aoki() { cout << "Aoki" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

int main() {
	int h, w;
	string s;
	cin >> h >> w;
	cout << string(w + 2, '#') << endl;
	for (int i = 0; i < h; ++i) {
		cin >> s;
		cout << '#' << s << '#' << endl;
	}
	cout << string(w + 2, '#') << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;

int main() {
  int n; cin >> n;
  string s; cin >> s;
  if (n == 1 || n%2 == 1) {
    cout << "No" << endl;
    return 0;
  }
  string t = "";
  for(int i = 0; i < n/2; i++) t += s[i];
  t = t + t;
  if (s == t) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<stdio.h>
#include <sstream>
#define pi 3.141592653589793238462
#define limit 100005
#define mo 1000000007;
typedef long long int lli;
typedef unsigned long long int ulli;
const lli mod=9999999999999983;
lli primes[6]={1125899906842597,1495921043,1005985879,1495921043,1005985879,1495921043};
using namespace std;
vector<lli>adj[2000009];
lli parent[2000009];
lli vis[2000009];
lli level[2000009];
lli dist[2000009];
lli dp[2000009];
lli arr[2000009];
lli brr[2000009];
lli crr[2000009];
lli hashing[2000009];
lli ar[509][509];
lli br[509][509];
lli cr[509][509];



lli solve(lli n)
{
    if(n<=0)
        return 0;

    if(dp[n]!=-1)
        return dp[n];

    return dp[n]=min((abs(arr[n]-arr[n-1])+solve(n-1)),(abs(arr[n]-arr[n-2])+solve(n-2)));
}


int main()
{
    //freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    int start_s = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    vector<lli>vect,vt,vct;
    vector<lli>::iterator itt;
    set<lli>st;
    set<lli>::iterator itr;
    map<lli,lli>mp;
    map<lli,lli>::iterator it;
    string str;

    lli i,j,n,k,m,q,t,a,b,c,maxi=INT_MIN,mini=INT_MAX,sum=0,ans=0,res=0,val=0,ans1=0,ans2=0,rem=0,diff=0,cnt=0,l,r,flag=0,e,index,val1=0,val2=0,x,y,z,h=0,u,v,mid,len,tot,fl=0;

    cin>>n;

    for(i=1;i<=n;i++)
    {
        cin>>arr[i];
    }

    arr[0]=arr[1];

    memset(dp,-1,sizeof(dp));
    cout<<solve(n);

    //for(i=1;i<=n;i++)
        //cout<<"i="<<i<<" "<<"dp="<<dp[i]<<endl;

}


Measured memory_bytes: 72576
#include<cstdio>
#include<iostream>
using namespace std;
#define max hgahkjgh
int main(void){
	int i,j,n,p[100],cnt,max;
	cin>>n;
	for(i=0;i<n;i++) cin>>p[i];
	max=-1;
	for(i=1;i<=n;i++){
		cnt=0;
		for(j=0;j<n;j++){
			if(i<=p[j]) cnt++;
		}
		if(i<=cnt&&max<i) max=i;
	}
	cout<<max<<endl;
	return 0;
}

Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int main()
{
	#define int long long
	int k,x;
	cin >> k >> x;
	for(int i = x-k+1; i < x+k; i++)
	cout << i << " ";
	cout << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(int i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(int i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(long long N, std::vector<long long> A, std::vector<long long> B){
  ll x=0,ans=0;
  REP(N){
    if(B[i]>=A[i]+A[i+1]){
      ans+=A[i]+A[i+1];
      A[i]=A[i+1]=0;
    }else if(B[i]>=A[i]){
      ans+=B[i];
      A[i+1]-=B[i]-A[i];
      A[i]=0;
    }else{
      ans+=B[i];
      A[i]-=B[i];
    }
  }
  cout<<ans<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N+1);
    for(int i = 0 ; i < N+1 ; i++){
        scanf("%lld",&A[i]);
    }
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&B[i]);
    }
    solve(N, std::move(A), std::move(B));
    return 0;
}


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

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
inline int in() { int x; cin >> x; return x; }

int cnt;
vector<bool> seen;
vector<bool> grp;
vector<int> grp_member;
vector<int> F[100100];
vector<int> B[100100];
int ans[100100];
void dfs(int v) {
  if (!seen[v]) {
    cnt++;
    grp_member.push_back(v);
  }
  seen[v] = true;
  grp[v] = true;
  for (auto next_v : F[v]) if (!seen[next_v]) dfs(next_v);
}

int main(){
  int N = in(), M = in(), K = in();
  grp.assign(N,false);
  REP(i,M+K) {
    int a = in()-1, b = in()-1;
    if (i<M) {
      F[a].push_back(b);
      F[b].push_back(a);
    }
    B[a].push_back(b);
    B[b].push_back(a);
  }
  REP(i,N) {
    if (grp[i]) continue;
    cnt = 0;
    seen.assign(N,false);
    grp_member.assign(0,0);
    dfs(i);
    REP(j,cnt) {
      int exclude = 0;
      int gm = grp_member[j];
      REP(l,B[gm].size()) if (seen[B[gm][l]]) exclude++;
      ans[gm] = cnt - exclude - 1;
    }
  }
  REP(i,N) cout << ans[i] << endl;
}


Measured memory_bytes: 14584
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;
    Func cin2;
    void calc()
    {
        cin = new Scanner();
        int[]x=cin.ArrayInt(3,0);
      Array.Sort(x);
      Console.WriteLine(x[0]+x[1]);
        
    }
}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Answer
{
    public static void Int2DArrayAns(int[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }//Answer.IntArrayAns(x);
    public static void Char2DArrayAns(char[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
}

class Func
{
    public long GCDLong(long a, long b)
    {
        while(a!=0)
        {
          long t=a;
          a=b%a;
          b= t;
        }
      
        return b;        
    }
}










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

int main(){
  int N, W;
  int v[1000], w[1000];
  int dp[10001];

  //??\???
  cin >> N >> W;
  for(int i = 0; i < N; i++){
    cin >> v[i] >> w[i];
  }

  //dp?????????
  memset(dp, 0, sizeof(dp));
  for(int i = 0; i <= W; i++){
    if(w[0] <= i) dp[i] = v[0];
  }

  //???????¨?????????§?§£???
  for(int i = 1; i < N; i++){
    for(int j = W; j >= 0; j--){
      if(j >= w[i]) dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
  }

  int ans = 0;
  for(int i = 0; i <= W; i++) ans = max(ans, dp[i]);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

// c が得する場合、c を優先的に買う形に最適化
int solve2(int a, int b, int c, int x, int y)
{
    // c が得でない場合は、a, b をそのまま買っておしまい
    if(a + b <= c * 2)
    {
        return a * x + b * y;
    }

    auto cCount = min(x, y) * 2;

    if(x == y)
    {
        return cCount * c;
    }
    else if(x > y)
    {
        auto shortageA = x - y;
        auto perCost = min(c * 2, a);
        return perCost * shortageA + cCount * c;
    }
    else
    {
        auto shortageB = y - x;
        auto perCost = min(c * 2, b);
        return perCost * shortageB + cCount * c;
    }
}

// 単純な全探索
int solve(int a, int b, int c, int x, int y)
{
    int minCost = numeric_limits<int>::max();
    for(int i = 0; i <= x; ++i)
    {
        for(int j = 0; j <= y; ++j)
        {
            int shortageA = x - i;
            int shortageB = y - j;
            int abCount = max(shortageA, shortageB) * 2;

            int cost = a * i + b * j + c * abCount;
            minCost = min(minCost, cost);
        }
    }
    return minCost;
}

int main(int argc, const char* argv[])
{
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    cout << solve2(a, b, c, x, y) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <sstream>

using namespace std;

int main() {
    string c;

    cin >> c;

    c[5] = ' ';
    c[13] = ' ';

    cout << c << endl;
    return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	var max, ans, h int
	for i := 0; i < n; i++ {
		fmt.Scan(&h)
		if h >= max {
			max = h
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
n, m= map(int,input().split())
x=list(map(int,input().split()))
x.sort()
dif=[""]*(m-1)
for i in range(m-1):
  dif[i]=abs(x[i+1]-x[i])
dif.sort()
if n==1:
  print(sum(dif))
else:
  print(sum(dif[:-n+1]))
      

Measured memory_bytes: 13968
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF=10 ** 10
N = int(input())
XL = [list(map(int,input().split())) for _ in range(N)]
XLs =sorted([ [xl[0]+xl[1],xl[0]-xl[1]] for xl in XL ])
# print(N,XL,XLs)

t = -INF 
n = 0

for xl in XLs:
    if t <= xl[1]:
        t = xl[0]
        n = n + 1
print(n)


Measured memory_bytes: 42208
a, b = map(int, input().split())
a -= 1
b -= 1
size = 100
grid = [[['.'], ['#']][h >= size//2] * size for h in range(size)]
for i in range(a):
    grid[size - 1 - (i // (size//2)) * 2][size - 1 - (i % (size//2)) * 2] = '.'
for i in range(b):
    grid[(i // (size//2)) * 2][(i % (size//2)) * 2] = '#'
print(size, size)
for i in range(size):
    for j in range(size):
        print(grid[i][j], end = '')
    print()


Measured memory_bytes: 4468
#include <iostream>
#include <stdlib.h>

using namespace std;

int main(int argc, char **argv)
{
	int n, tmp, *array;
	
	while(1){
		cin >> n;
		if(n == 0){
			break;
		}
		array = (int *)calloc(7, sizeof(int));
		for(int i = 0; i < n; i++){
			cin >> tmp;
			
			if(tmp > 60){
			tmp = 60;
			}
			array[tmp/10]++;
		}
		for(int i = 0; i < 7; i++){
			cout << array[i] << endl;
		}
		
		free(array);
	}
	
	return 0;
}

Measured memory_bytes: 904
import math
A, B, H, M = map(int, input().split())

b = M * 6
a = H*30 + M/2

c = min(abs(a-b), 360-abs(a-b))

print((A**2 + B**2 - 2*A*B*math.cos(math.radians(c)))**0.5)

Measured memory_bytes: 9508
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Cin(T, x) T x; cin >> x;
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i];
#define Cout(val) cout << (val) << "\n";
#define Sort(a) sort(Range(a));
#define DeSort(a) sort(RevRange(a));

using namespace std;
using ll = long long;

int main(void){
    Cin(int, a);
    Cin(int, b);
    Cin(int, c);
    Cin(int, d);
    Cout(b % a ? b-a : a+b);
    //Cout(() ? "Yes" : "No");
    //Cout(() ? "YES" : "NO");
}

Measured memory_bytes: 256
import java.util.*;
import java.util.Scanner;

public class Main {// Main
    public static void main(String[] args){
        Scanner reader = new Scanner(System.in);
        String input = reader.nextLine();
        String sample = "CODEFESTIVAL2016";

        int counter = 0;
        for(int i = 0; i < 16; i++){
          if(input.charAt(i) != sample.charAt(i)){
            counter++;
          }
        }

        System.out.println(""+counter);
    }
}

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

int main() {
  int r;
  cin >> r;
  if(r < 1200){
    cout << "ABC" << endl;
  }
  else if(1200 <= r && r < 2800){
      cout << "ARC" << endl;
    }
  else{
  cout << "AGC" << endl;
  }
}


Measured memory_bytes: 256
#include<cstdio>
#include<queue>
int n;
std::priority_queue<double> pq;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		double x;
		scanf("%lf",&x);
		pq.push(-x);
	}
	while (pq.size()>1)
	{
		double x=-pq.top();pq.pop();
	    double y=-pq.top();pq.pop();
	    pq.push(-(x+y)/2);
	}
	printf("%lf\n",-pq.top());
	return 0;
}

Measured memory_bytes: 3216
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int n;
char s[200001];
int a[200001],b[200001];
int main() {
	scanf("%d%s",&n,s);
	a[0]=(s[0]=='.'),b[0]=(s[0]=='#');
	fup(i,1,n-1,1)
	{
		a[i]=a[i-1]+(s[i]=='.');
		b[i]=i+1-a[i];
	}
	int ans=a[n-1];
	fup(i,0,n-1,1)
		ans=min(ans,b[i]+a[n-1]-a[i]);
	printf("%d",ans);
}

Measured memory_bytes: 2048
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

template <class T>
inline void read(T &x)
{
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return;
}

std::string s, t, u;
int a, b;

int main()  
{
    std::cin >> s >> t;
    read(a), read(b);
    std::cin >> u;
    if (u == s) --a;
    else    --b;
    std::cout << a << " " << b << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    if(c==1){
        cout<<"Open"<<endl;
    }
    else if(a==1&&b==1){
        cout<<"Open"<<endl;
    }
    else{
        cout<<"Close"<<endl;
    }
}



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

int N, K;
vector<int> A;

bool ok(ll i) {
  ll k = 0;

  priority_queue<ll> pq;
  rep(j,N) {
    k += A[j] % i;
    pq.push(A[j]%i);
  }

  while(k != 0) {
    ll p = pq.top();
    pq.pop();
    k -= i;
    pq.push(p-i);
  }

  ll s = 0;
  while(!pq.empty()) {
    auto p = pq.top();
    pq.pop();
    s += abs(p);
  }
  return s/2 <= K;
}

int main () {
  cin >> N >> K;
  A.resize(N);

  ll M = 0;
  rep(i,N) {
    cin >> A[i];
    M += A[i];
  }

  vector<ll> R;
  for(ll i = 1; i <= sqrt(M); i++) {
    if(M % i == 0) {
      R.push_back(i);
      R.push_back(M/i);
    }
  }
  sort(all(R));

  for(int i = R.size() - 1; i >= 0; i--) {
    if(ok(R[i])) {
      cout << R[i] << endl;
      return 0;
    }
  }

  return 0;
}


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

def dfs(s):
    stack = [(s, -1, 1)]
    while(len(stack)):
        v, p, c = stack[-1]
        stack.pop()
        color[v] = c
        for e in graph[v]:
            if e[0] == p: continue
            stack.append((e[0], v, abs(c - e[1] % 2)))


n = int(input())
color = [-1] * n
graph = [[] for _ in range(n)]

for _ in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    u, v = u-1, v-1
    graph[u].append((v, w))
    graph[v].append((u, w))

dfs(0)
for c in color: print(c)

Measured memory_bytes: 75940
import sys
from functools import lru_cache
sys.setrecursionlimit(20000)


class Dp:

    def __init__(self, size):
        self.size = size

    @lru_cache(maxsize=None)
    def calc(self, n):
        if n == 1:
            return 1
        return self.calc(n//2) * 2 + 1


def main():
    h = int(input())
    dp = Dp(h)
    result = dp.calc(h)
    print(result)


if __name__ == "__main__":
    main()


Measured memory_bytes: 38256
a, b, k = map(int, input().split())
count = 0
if(a > b):
    tmp = a
    a = b
    b = tmp
for i in range(b, 0, -1):
    if a % i == 0 and b % i == 0:
        count += 1
        if count == k:
            print(i)
            exit(0)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
template <class Q>
void clearQueue(Q & q) {
    q = Q();
}
void solve(){
	string s,t;
    cin>>s>>t;
    int m=s.length();
    int n=t.length();
    int dp[m+1][n+1];
    dp[0][0]=0;
    for(int i=1;i<=m;i++){
        dp[i][0]=0;
    }
    for(int j=1;j<=n;j++) dp[0][j]=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(s[i-1]==t[j-1]) 
            dp[i][j]=1+dp[i-1][j-1];
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int len=dp[m][n];
    int i=m;int j=n;string ans="";
    while(i>=1&&j>=1){
        if(s[i-1]==t[j-1]){
            ans=ans+s[i-1];
            i--;j--;
        }
        else if(dp[i-1][j]>dp[i][j-1]) i--;
        else j--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL); 
	int T=1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 74000
#include "bits/stdc++.h"

using namespace std;

#define int long long int
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define se second
#define fi first

typedef pair<int, int> pii;
typedef vector<int> vi;

const int inf = 1e18;
const int mod = 1e9 + 7;

inline int add(int x, int y) { x += y; if (x >= mod) x -= mod; return x;}
inline int sub(int x, int y) { x -= y; if (x < 0) x += mod; return x;}
inline int mul(int x, int y) { return ((x % mod) * (y % mod)) % mod;}
inline int power(int a, int b) {
    int x = 1;
    while (b) {
        if (b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline int inv(int a) { return power(a, mod - 2);}

const int N = 1e5 + 5;
int dp[N][2], n;
vi g[N];

void dfs(int u, int par) { // 1-black 0-white
    dp[u][0] = dp[u][1] = 1;
    for (int v : g[u]) {
        if (v == par) continue;
        dfs(v, u);
        dp[u][0] = mul(dp[u][0], add(dp[v][0], dp[v][1]));
        dp[u][1] = mul(dp[u][1], dp[v][0]);
    }
}

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

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs(1, 0);

    cout << (dp[1][0] + dp[1][1]) % mod << endl;

    return 0;
}

Measured memory_bytes: 14208
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}

	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑

int a, b, c, mon;
int main() {
	cin >> a >> b >> c;
	for (int i = min(a, b); i >= 1; --i) {
		if (a%i == 0 && b%i == 0) { ++mon; }
		if (mon == c) {
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256