akhauriyash/Code-Regression huggingface dataset:
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
//過半数：N/2.0で判定
//優先度付きキュー
//priority_queue<
//ll,
//vector<ll>
//> q;
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
#define PI 3.14159265358979323846264338327950L
using namespace std;


//割るやつ
const ll MOD = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1));
}

//Nのd桁目の数
ll dignum(ll N, ll d) {
	ll x = pow(10, d);
	N %= x;
	ll y = pow(10, d - 1);
	N /= y;
	return N;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

ll RS(ll N, ll P, ll M) {
	if (P == 0) return 1;
	if (P % 2 == 0) {
		ll t = RS(N, P / 2, M);
		return t * t % M;
	}
	return N * RS(N, P - 1, M);
}

int main() {
	int N;cin >> N;
	vector<int> a(N);
	rep(i,N)cin >> a[i];

	int cnt = 0;
	for(int i = 1; i <= N;i++){
		if(i%2 == 1 && a[i-1]%2 == 1)cnt++;
	}

	cout << cnt << endl;
}	

Measured memory_bytes: 11004
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <map>

using namespace std;

map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}


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

    auto p = prime_factor(N);
    int64_t ans = 0;
    for(auto [key,val]: p) {
        // cerr << key << ' ' << val << endl;
        int64_t ok = 0;
        int64_t ng = 1'000'000'000;
        while(ok + 1 < ng) {
            int64_t mid = (ok + ng) / 2;
            if(mid*(mid+1)/2 <= val) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ans += ok;
    }

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


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

#define int long long

signed main() {
  int R0, W0, C, R;
  while ( cin >> R0 >> W0 >> C >> R, R0 ) {
    if ( W0*C <= R0 ) cout << 0 << endl;
    else cout << (W0*C-R0-1)/R+1 << endl;
  }
	 
  return 0;
}



Measured memory_bytes: 3084
#include<iostream>
#include<string>
using namespace std;
int main () {
    string x;
    cin>>x;
    for(int i=0;i<2;i++){
        if(x[i]=='9'){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n;
int par[N];
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i; }
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) { par[find(x)] = find(y); }
vector<int>G[N];
ll dp[N], ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[max(u, v)].push_back(min(u, v));
	}
	init(n);
	ans = dp[1] = 1ll;
	for (int i = 2; i <= n; i++) {
		int mx = 0;
		for (int v : G[i])mx = max(mx, v);
		dp[i] = i - mx + dp[i - 1];
		sort(G[i].begin(), G[i].end(), greater<int>());
		for (int j = 1; j < (int)G[i].size(); j++) {
			int v = G[i][j];
			dp[i] -= v;

		}
		ans += dp[i];
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 35756
#include<bits/stdc++.h>
const unsigned long long int M= 1000000007;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()	
#define fr(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define int   long long 
#define endl "\n"
using namespace std;
int power(int x,int y){int res=1;while(y>0){if(y&1)res=x*res; y=y>>1;x=x*x;}return res;}
int power(int x,int y,int mod){int res=1;while(y>0){if(y&1)res=x*res%mod; y=y>>1;x=x*x%mod;}return res;}

void nik()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
}
     

 	#define F first 
	#define S second 


int vis[50]={0};
std::vector<int> v[50],ans[50];

void dfs(int i,int p)
{
	if(v[i].size()==0)return ;
	if(!vis[i])
	{
		vis[i]=1;
		ans[p].pb(i);
		for(int it:v[i])
		{
			if(!vis[it])dfs(it,p);
		}

	}
}

signed main()
{	//nik();

int test=1;
//cin>>test;
while(test--)
{

int n;
cin>>n;
int cnt=0,ok=0;
fr(i,n)
{
	int a,b;
	cin>>a>>b;
	if(a==b)cnt++;
	else cnt=0;

	if(cnt==3)ok=1;
}

if(ok)cout<<"Yes";
else cout<<"No";

}
return 0;
}



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

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

    if(++i > n) break;
  }
  cout<<endl;
  
  return 0;
}



Measured memory_bytes: 3096
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			int[][] map = new int[8][8];
			String t = "";
			for(int i=0;i<8;i++){
				t = sc.next();
				for(int j=0;j<8;j++){
					if(t.codePointAt(j)==49)map[i][j]=1;
				}
			}

			
			for(int i=0;i<8;i++){
				for(int j=0;j<8;j++){
					if(map[i][j]==1){
						if(i==7){
							System.out.println("C");
						}else{
							if(i<6 && map[i+2][j]==1){
								System.out.println("B");
							}else if(j<6 && map[i][j+2]==1){
								System.out.println("C");
							}else if(i<6 && j!=0 && map[i+2][j-1]==1){
								System.out.println("D");
							}else if(i<6 && j!=7 && map[i+2][j+1]==1){
								System.out.println("F");
							}else if(map[i+1][j]==1 && map[i+1][j+1]==1){
								System.out.println("A");
							}else if(map[i+1][j]==1 && map[i+1][j+1]==0){
								System.out.println("G");
							}else{
								System.out.println("E");
							}
						}
						i=8;
						j=8;
		
					}					
				}
			}

		}
	}	
}

Measured memory_bytes: 20056
#include <bits/stdc++.h>
using namespace std;
#pragma region
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << (#x) << "] = [", _print(x)
#else
#define debug(x...)
#endif
#pragma endregion
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define sz(v) int((v).size())
#define int ll
#pragma region
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#pragma endregion

int MOD = 1e9+7;
int power(int a, int n)
{
    int ret = 1;
    int now = a;
    while(n)
    {
        if (n&1) ret = (ret * now)%MOD;
        now = (now * now)%MOD;
        n>>=1;
    }
    return ret;
}
int n, k;


int memo[111'111];
void solve()
{
    cin>>n>>k;
    for(int i = k;i>=1;--i)
    {
        memo[i] = power(k/i, n);
        for (int j = 2*i; j<=k;j+=i) memo[i] -= memo[j];
    }
    int ans = 0;
    for (int i=1;i<=k;++i)
    {
        ans = (ans + i*memo[i]%MOD)%MOD;
    }
    cout << ans << '\n';
}

signed main()
{
    int T = 1;
    ios_base::sync_with_stdio(0); cin.tie(0);
    //cin >> T;
    for(int i=1;i<=T;++i)
    {
        //cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}


Measured memory_bytes: 4348
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 110000
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	int N, T;
	cin >> N >> T;
	vi A(N);
	vi B(N);
	rep(i, N) {
		cin >> A[i] >> B[i];
	}
	vector<vector<vi>> ansmax(N + 1);
	rep(i, N + 1) {
		ansmax[i].resize(T + 1);
		rep(j, T + 1) {
			ansmax[i][j].resize(2);
			rep(b, 2) {
				ansmax[i][j][b] = 0;
			}
		}
	}
	rep(i, N) {
		int Atmp = A[i];
		int Btmp = B[i];
		ansmax[i + 1] = ansmax[i];
		rep(j, T + 1) {
			rep(b, 2) {
				int jnew = j + Atmp;
				int Bnew = ansmax[i][j][b] + Btmp;
				if (b == 0) {
					if (Bnew > ansmax[i + 1][j][1]) {
						ansmax[i + 1][j][1] = Bnew;
					}
				}
				if (jnew >= T)
					continue;
				if (Bnew > ansmax[i + 1][jnew][b]) {
					ansmax[i + 1][jnew][b] = Bnew;
				}
			}
		}
	}
	int ans = 0;
	rep(j, T + 1) {
		rep(b, 2) {
			int eval = ansmax[N][j][b];
			ans = max(ans, eval);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 494592
n=int(input())
h=[int(x) for x in input().split()]

h_state=[0]*n

def water(n,h,h_state):
    for i in range(n):
        if h_state[i]<h[i]:
            l=i
            break
        elif i==n-1 and h_state[i]<h[i]:
            l=i
        else:
            l=i+1
    
    for j in range(l,n):
        if h_state[j]==h[j]:
            r=j-1
            break
        else:
            r=j
    
    for k in range(l,r+1):
        h_state[k]+=1

cnt=0
while h_state != h:
    for i in range(n):
        if h_state[i]<h[i]:
            cnt+=1
            water(n,h,h_state)
            break
print(cnt)
        

Measured memory_bytes: 9220
#include <bits/stdc++.h>
using namespace std;
int main(){
  string a;
  cin>>a;
  int d=0;
  for(int i=0;i<a.size();i++){
    d=d+(a.at(i)-'0');
  }
  if(d%9==0)
  cout<<"Yes";
  else
    cout<<"No";
}


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

void solve(std::istream &ist, std::ostream &ost)
{
    /* ------- 宣言と入力 ------- */

    int N, K;

    ist >> N >> K;

    /* ------- 計算 ------- */

    //累積和
    long long int sum[N + 1] = {0};
    long long now_sum = 0;
    for (int i = 0; i < N + 1; i++)
    {
        now_sum += i;
        sum[i] = now_sum;
    }

    long long int mod = 1000000007;
    long long ans = 1;

    for (int i = K; i < N + 1; i++)
    {
        ans += (sum[N] - sum[N - i] + 1) - sum[i - 1];
        if (ans >= mod)
        {
            ans %= mod;
        }
    }

    ost << ans << endl;
}

#ifndef WOMAIN
int main()
{
    solve(std::cin, std::cout);
    return 0;
}
#endif


Measured memory_bytes: 5176
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long N  = sc.nextLong();
        int limit = (int)Math.sqrt(N);
        long min = N;
        for(int i = 1; i <= limit; i++){
            if(N % i == 0) {
            long j = N/i;
            min = Math.min(min, i + j -2);
            }
        }
        System.out.println(min);
    }
}

Measured memory_bytes: 23892
n = int(input())
h = list(map(int, input().split()))

INF = float("inf")
dp = [INF] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, n):
    a = abs(h[i] - h[i - 2])
    b = abs(h[i] - h[i - 1])
    dp[i] = min(dp[i - 2] + a, dp[i - 1] + b)
print(dp[n - 1])


Measured memory_bytes: 13928
#include <bits/stdc++.h>
using namespace std;
const long int MOD = 1e9+7;
int main() {
	int h,w;
	cin>>h>>w;

	char grid[h][w];
	long int dp[h][w];

	//dp[i][j] no . of ways to reach cell (i,j)

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>grid[i][j];
		}
	}

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(i==0 && j==0)
				dp[i][j]=1;
			else if(grid[i][j] == '#')
				dp[i][j]=0;
			else if(i==0)
				dp[i][j] = dp[i][j-1];
			else if(j==0)
				dp[i][j] = dp[i-1][j];
			else
				dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % MOD;

			//cout<<dp[i][j]<<" ";
		}
		//cout<<'\n';
	}
	cout<<dp[h-1][w-1]<<'\n';
	return 0;
}


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

typedef long long ll;
typedef vector <bool> v_bool;
typedef vector <ll> v_ll;
typedef vector <vector <ll> > vv_ll;
typedef vector < pair <ll,ll> > vp_ll;
typedef pair <ll,ll> p_ll;

bool TEST=false;
ll MOD = 1000000007;

void show(){if (TEST){cout << endl;}}
void show(string x){if (TEST){cout << x;}}
void show(string x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(ll x){if (TEST){cout << x;}}
void show(ll x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(p_ll p){
  if (TEST){cout << "{ ";show(p.first);cout << " ";show(p.second);cout << " }";}
}
void show(v_ll v){
  if (TEST){
    cout << "<begin> ";
    for (ll i=0;i<v.size();i++){show(v[i]); cout << " ";}cout <<"<end>"<< endl;
}}
void show(vv_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}
void show(vp_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}

ll mod(ll x){
  ll n=MOD;
  ll ret=x%n;
  if (ret<0)ret+=n;
  return ret;
}
void mod_self(ll &x){
  x=mod(x);
}
ll mod_inv(ll x){
  ll n=MOD;
  ll y = x,z = n-2, ret=1;
  y=mod(y);
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  return ret;
}
ll mod_pow(ll x,ll a){
  ll y = x,z = a,ret=1;
  y=mod(y);
  if (z<0)z=-z;
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  if (a<0) ret=mod_inv(ret);
  return ret;
}
v_ll mod_nck(ll n){
  v_ll nck(n+1,0);
  nck[0]=1;
  for (ll i=1;i<=n;i++){
    nck[i]=mod(nck[i-1]*(n+1-i));
    nck[i]=mod(nck[i]*mod_inv(i));
  }
  return nck;
}
v_ll mod_factorial(ll n){
  v_ll fct(n+1,0);
  fct[0]=1;
  for (ll i=1;i<=n;i++){
    fct[i]=mod(fct[i-1]*i);
  }
  return fct;
}

ll N,s,e,ans;
string S;
v_ll A;
int main(){
  cin >> N>> S;

  A.assign(2*N+10,0);
  if (S[0]!='B'){
    cout << 0 << endl;
    return 0;
  }
  ll t=0;
  for (ll i=0;i<2*N;i++){
    if ((S[i]=='B') && (t%2==0)){A[i]=0;t++;}
    else if ((S[i]!='B') && (t%2==1)){A[i]=0;t++;}
    else {A[i]=1;t--;}
  }
  //TEST=true;
  //show(A);
  ll x=0;
  for (ll i=0;i<2*N;i++){
    if (A[i]==0)x++;
  }
  if (x!=N){
    cout << 0 << endl;
    return 0;
  }
  s=0;e=0;
  ans=1;
  for (ll i=0;i<2*N;i++){
    if (A[i]==0)s++;
    else {
      if (s<=0){
        cout << 0 << endl;
        return 0;
      }
      ans*=s;ans%=MOD;s--;}
  }
  for (ll i=1;i<=N;i++){
    ans*=i;ans%=MOD;
  }
  cout << ans  << endl;
}


Measured memory_bytes: 2172
import java.util.*

fun int() = readLine()!!.toInt()

fun ints() = readLine()!!.split(" ").map {it.toInt()}.toIntArray()

fun triangle(n:Int) = n*(n+1)/2

fun main() {
	abc000X()
}

fun abc000X() {
	val end = System.currentTimeMillis()+1500

	val day = int()
	val days = 0 until day
	val types = 0..25

	val penalty = ints()
	val advantage = Array(day) {ints()}

	val last = Array(26) {
		val v = TreeSet<Int>()
		v.add(-1)
		v
	}

	var r = 0L
	val t = IntArray(day) {0}

	fun calcPenalty(d:Int,type:Int) = penalty[type]*(d-(last[type].floor(d)!!))
	fun calcPenaltySum(d:Int,type:Int) = penalty[type]*triangle(d-(last[type].floor(d)!!))

	for(d in days) {
		val ct = types.maxBy {advantage[d][it]+calcPenaltySum(d,it)}!!
		t[d] = ct
		last[ct].add(d)
		r += advantage[d][ct]-calcPenaltySum(d-1,ct)
	}

	for(t in types)
		r -= calcPenaltySum(364,t)

	while(end>System.currentTimeMillis()) {
		val d = days.random()
		val pt=t[d]
		r -= advantage[d][pt]-calcPenaltySum(d-1,pt)
		last[pt].remove(d)
		r -= calcPenaltySum((last[pt].ceiling(d) ?: 365)-1,pt)

		val ct = types.maxBy {advantage[d][it]+calcPenaltySum((last[pt].ceiling(d) ?: 365)-1,it)}!!
		t[d] = ct

		r += calcPenaltySum((last[ct].ceiling(d) ?: 365)-1,ct)
		last[ct].add(d)
		r += advantage[d][ct]-calcPenaltySum(d,ct)-calcPenaltySum((last[ct].ceiling(d) ?: 365)-1,ct)
	}

	System.err.println(r)
	t.forEach {println(it+1)}
}


Measured memory_bytes: 77340
#include <stdio.h>
#include <string.h>
 
char code[50][55];
int max;
 
char ntoc(char name[],int nb){
    int i = 1,j = 1;
    code[nb][0] = name[0];
    while(name[i]!='\n'){
        if(name[i-1]=='a'||name[i-1]=='i'||name[i-1]=='u'||name[i-1]=='e'||name[i-1]=='o'){
            code[nb][j] = name[i];
            j++;
        }
        i++;
    }
    if(j>max)max = j;
    code[nb][j]='\0'; 
}
 
int main(){
    int n,i,k,l,m;
    char name[55];
    scanf("%d",&n);
    getchar();
    while(n){
        max = 0;
        for(i=0;i<n;i++){
            fgets(name,55,stdin);
            ntoc(name,i);
        }
        for(k=1;k<=max;k++){
            for(l=0;l<n;l++)for(m=l+1;m<n;m++)if(!strncmp(code[l],code[m],k))goto NEXT;
            printf("%d\n",k);
            break;
NEXT:       printf("");
        }
        if(k==max+1)printf("-1\n");
        scanf("%d",&n);
        getchar();
    }
     
}

Measured memory_bytes: 1064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI 3.14159265358979
#define EPS 1e-8
#define mod 1000000007
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
	 
const ll INF=(ll)2e18;	
const int N=1e5+5;
 

 
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll modinverse(ll a,ll m)
{
	return binpow(a,m-2,m);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(0);
	
	string s,t;
	cin>>s>>t;
	
	ll ans=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]!=t[i])
		{
			ans++;
		}
	}
	cout<<ans;
}


Measured memory_bytes: 3740
#include <iostream>
#include <unordered_set>
#include <cstdint>
#include <vector>
#include <sstream>
#include <string>
#include <climits>
#include <set>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <numeric>
using namespace std;

int main()
{
	int k, x;
	cin >> k >> x;

	for (int i = 0; i < k * 2 - 1; i++)
	{
		cout << x - k + 1 << " ";
		x++;
	}
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
//typedef vector<vector<ll>> Graph;

const ll mod = 1e9 + 7;
//const ll mod = 998244353;

#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define spa << " " <<
#define fi first
#define se second

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<endl;};

bool ok = false;

void dfs(ll a, ll b, ll c, ll r){
    //cout << a spa b spa c << endl;
    if(b>a and c>b) ok = true;
    if(r==0) return;
    dfs(2*a, b, c, r-1);
    dfs(a, 2*b, c, r-1);
    dfs(a, b, 2*c, r-1);
    return;
}

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

    ll A, B, C, K;
    cin >> A >> B >> C >> K;

    dfs(A, B, C, K);

    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 3616
/* A - Takoyaki */

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N, X, T, ans;
  cin >> N >> X >> T;
  if(N % X == 0){
    ans = T * (N / X);
  }else{
    ans = T * (N / X + 1);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
using ll = long long;

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

    string n = to_string(N);

    int ans = 0;

    if(n[0]!='9'){
        if(n.size()==1){
            ans = n[0]-'0';
        }
        else if(all_of(n.begin()+1,n.end(),[](char c){return c=='9';})){
            ans += n[0]-'0';
            ans += (n.size()-1)*9;
        }
        else{
            ans += n[0]-'0'-1;
            ans += (n.size()-1)*9;
        }
    }
    else{
        auto p = find_if(n.begin(),n.end(),[](char c){return c!='9';});
        if(p!=n.end()){
            ans = (n.size()*9)-1;
        }
        else{
            ans = (n.size()*9);
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		String T = sc.next();
		long A = sc.nextLong();
		long B = sc.nextLong();
		String U = sc.next();
		if (U.equals(S)) {
			A--;
		} else {
			B--;
		}
		System.out.println(A + " " + B);
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define FILES                    \
	ifstream cin( "input.txt" ); \
	ofstream cout( "input.txt" );
#define FAST                             \
	std::ios_base::sync_with_stdio( 0 ); \
	std::cin.tie( 0 );                   \
	std::cout.tie( 0 );
#define FIXED cout << fixed << setprecision( 20 )
#define pb push_back
#define eps 1e-9
#define mod 1000000007
#define int long long
using graph = std::vector<std::vector<int>>;
using pll = std::pair<int, int>;
using ll = long long;
namespace my {
	int max( int x ) {
		return x;
	}
	template<typename... Args>
	int max( int x, Args... args ) {
		int y = max( args... );
		return ( x < y ) ? y : x;
	}
	int min( int x ) {
		return x;
	}
	template<typename... Args>
	int min( int x, Args... args ) {
		int y = min( args... );
		return ( x < y ) ? x : y;
	}
	int max( std::vector<int>& t ) {
		int mx = -1e18;
		for( int i = 0; i < t.size(); i++ ) {
			mx = std::max( mx, t[i] );
		}
		return mx;
	}
	int min( std::vector<int>& t ) {
		int mn = 1e18;
		for( int i = 0; i < t.size(); i++ ) {
			mn = std::min( mn, t[i] );
		}
		return mn;
	}
}	// namespace my

void z_f( std::vector<int>& z, std::string& s ) {
	int l = 0, r = 0;
	for( int i = 1; i < s.size(); i++ ) {
		if( r >= i ) {
			z[i] = std::min( r - i + 1, z[i - l] );
		}
		int& x = z[i];
		while( i + x < s.size() && ( s[i + x] == s[x] ) ) {
			++x;
		}
		if( i + x - 1 > r ) {
			l = i;
			r = i + x - 1;
		}
	}
}
void solve() {
	int n;
	std::cin >> n;
	std::vector<int> a( n, 0 );
	for( int i = 0; i < n; i++ ) {
		std::cin >> a[i];
	}
	std::sort( a.begin(), a.end() );
	int ans = 0;
	for( int i = 0; i < n; i++ ) {
		for( int j = i + 1; j < n; j++ ) {
			for( int k = j + 1; k < n; k++ ) {
				if( a[i] + a[j] > a[k] && a[i] != a[j] && a[j] != a[k] && a[k] != a[i] ) {
					//std::cout << i + 1 << ' ' << j + 1 << ' ' << k + 1 << '\n';
					ans++;
				}
			}
		}
	}
	std::cout << ans;
}
main() {
	int t = 1;
	FAST;
	// std::cin >> t;
	while( t-- ) {
		solve();
	}
}

Measured memory_bytes: 3656
import math

a,b,x,y = map(int,input().split())

s = 6*y
t = 30*x+y/2

_th = abs(s-t)
__th = min(_th,360-_th)
p = math.pi
th = __th*p/180
co = math.cos(th)

c2 = a**2+b**2-2*b*a*co
print(c2**(1/2))

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

int main(int argc, char** argv){
	int n,ret;
	unsigned char card_t[101],card_h[101];
	short point_t,point_h;

	// SetUp
	point_t = point_h = 0;
	// Input Number
	scanf("%d",&n);
	// Input Card & Check
	while(n-- > 0 ){
		scanf("%100s%100s",card_t,card_h);
		ret = strcmp(card_t,card_h);
		if( ret > 0 ){
			point_t += 3;
		} else if( ret < 0 ){
			point_h += 3;
		} else {
			point_t += 1;
			point_h += 1;
		}
	}
	// Output
	printf("%d %d\n",point_t,point_h);

	return 0;
}

Measured memory_bytes: 604
n = int(input())
a = sorted([int(i) for i in input().split()],reverse=True)
x = n+1

for i in range(len(a)):
  if i%2 ==0:
    x-=2
  if a[i] != x:
    print(0)
    break
else:
  print((2**(n//2))%(10**9 +7))

Measured memory_bytes: 13812
a, b = map(int, input().split())

def f(x):
  amari = x % 4
  if amari == 0:
    return x
  elif amari == 1:
    return 1
  elif amari == 2:
    return x ^ 1
  elif amari == 3:
    return 0


print(f(a-1)^f(b))

Measured memory_bytes: 3060
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String T = sc.next();
    
    int num = 0;
    for (int i = 0; i < S.length() ; i++){
      if( !S.substring(i,i+1).equals(T.substring(i,i+1)) )
        num++;
    }
    System.out.println(num);
  }
}

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

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int a,b;
cin>>a>>b;
int total=1;
int cnt=0;
while (true){
    if(total>=b){
        break;
    }
    total+=a-1;
    cnt++;
}
cout<<cnt<<endl;

//system("pause");
return 0;
}

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

int main()
 {
 	int a,b,c,d,f=0;
 	cin>>a>>b>>c>>d;
 	while (a>0&&c>0)
 	{
 		c=c-b;
 		if(a>0&&c>0)
 			a=a-d;
	 }
	 if(a<=0)
	 	cout<<"No"<<endl;
	else 
		cout<<"Yes"<<endl;
 	return 0;
 }

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int s1,s2,s3;
  int n;
  
  cin >> n;
  
  s1 = n/100;
  s2 = (n-s1*100)/10;
  s3 = (n-s1*100-s2*10);
  
  cout << s1 + s2 + s3 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0;i < (int)(n);i++)
#define RREP(i,n) for(int i = (int)n-1;i >= 0;i--)
#define FOR(i,s,n) for(int i = s;i < (int)n;i++)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;i--)
#define ALL(a) a.begin(),a.end()
//#define IN(a, x, b) (a<=x && x<b)
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a = b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a = b;return true;}return false;}
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void IN(T&t){cin>>t;}
template<class T,class... Ts>inline void IN(T&t,Ts&...ts){cin>>t;IN(ts...);}
template<class T>inline void OUT(T t){cout<<t<<"\n";}
template<class T,class... Ts>inline void OUT(T&t,Ts&... ts){cout<<t<<" ";OUT(ts...);}
template<typename T=int>vector<T>mv(size_t a){return vector<T>(a);}
template<typename T=int,typename... Ts>auto mv(size_t a,Ts... ts){return vector<decltype(mv<T>(ts...))>(a,mv<T>(ts...));}
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type FILL(T&t,const V&v){t=v;}
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type FILL(T&t,const V&v){for(auto &e:t)FILL(e,v);}
constexpr long long INF = 1e18;

signed main(){
	int n;
	IN(n);
	auto a = mv(n);
	IN(a);
	int mi = INF,ans = -1;
	REP(i,n){
		if(CHMIN(mi,a[i]))ans=i;
	}
	OUT(ans+1);
}


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

int main() {
  ll n;
  cin >> n;
  vector<vector<int>> f(n, vector<int>(10)), p(n, vector<int>(11));
  rep(i, n) rep(j, 10) cin >> f[i][j];
  rep(i, n) rep(j, 11) cin >> p[i][j];

  ll ans = -1e9;
  for (int si = 1; si < (1 << 10); si++) {
    vector<int> d(10);
    rep(i, 10) d[i] = (si >> i & 1);

    ll profit = 0;
    rep(i, n) {
      ll c = 0;
      rep(j, 10) if (d[j] == 1 && f[i][j] == 1) c++;
      profit += p[i][c];
    }
    ans = max(ans, profit);
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ASC(x) sort(ALL((x)))
#define DESC(x) sort(ALL((x)),greater<ll>())
#define pb push_back


vec fac(210000), finv(210000), inv(210000);

ll modpow(ll a, ll n, ll m)
{
    if(n == 0) return 1;
    ll t = modpow(a, n >> 1, m);
    t = t * t % m;
    if(n & 1) t = t * a % m;
    return t; 
}

void combinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    REP(i,2,210000) {
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
 
ll combmod(ll n, ll r)
{
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    ll c = 1;
    REP(i,0,r) c = c * (n-i) % MOD;
    c = c * finv[r] % MOD;
    return c;
}

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;

//    vec inv(200010, 0);
//    inv[1] = 1;
//    REP(i,2,200010) inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;

    combinit();

    ll nCa = n, nCb = n, c, f = 1;
    REP(i,2,a+1) nCa = ((nCa * (n-i+1) % MOD) * inv[i]) % MOD;
    REP(i,2,b+1) nCb = ((nCb * (n-i+1) % MOD) * inv[i]) % MOD;
    c = (modpow(2, n, MOD) - 1- nCa - nCb) % MOD;
    c = (c < 0) ? c + MOD : c;
    PR(c); 

    return 0;
}

/*

nC1 + ... + nCn - nCa - nCb
= 2^n - 1 - nCa - nCb

*/

Measured memory_bytes: 5120
//
// Created by moono on 2018/10/27.
//

#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;



int main() {
    //
    int N;
    string S;

    //
    cin >> N;
    cin >> S;

    //
    int x = 0, max_x = 0;
    for (int i = 0; i < N; ++i) {
        if(S[i] == 'I'){
            x++;
        }else if(S[i] == 'D'){
            x--;
        }

        if(x > max_x) max_x = x;
    }

    cout << max_x << endl;
    return 0;
}

Measured memory_bytes: 256
# B - Card Game for Two
N = int(input())
a = list(map(int, input().split()))

a.sort(reverse = True)
alice, bob = 0, 0

for i in range(N):
	if i % 2 == 0:
		alice += a[i]
	else:
		bob += a[i]

print(alice - bob)

Measured memory_bytes: 3060
import math
import sys

count = 0
m = 0
G = []

def insertion_sort(A, N, g):
    global count
    for i in range(g, N):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            count += 1
        A[j + g] = v

# h_(i+1) = 3h_i + 1 が最良の間隔 (らしい)
def shell_sort(A, N):
    global m, G
    m = math.floor(math.log(2*N+1, 3))
    G = [int((pow(3, i)-1)/2) for i in range(m, 0, -1)]

    for i in range(m):
        insertion_sort(A, N, G[i])


n = int(input())
A = list(map(int, sys.stdin.readlines()))
shell_sort(A, n)

print(m)
print(' '.join([str(h) for h in G]))
print(count)
for x in A:
    print(x)


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

using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i < (n); --i)
#define all(x) (x).begin(), (x).end()
#define gsort(x, n) sort((x), (x + n) greater<int>())
#define rv(s) reverse((s).begin(), (s).end())
#define setout(n, x) setw(n) << setfill(x)
#define Fixed(n) fixed << setprecision(n)
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).flont_back(a)
#define eb(x, a) (x).emplaes_back(a)
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1e9 + 7;

signed main()
{
   cin.tie(nullptr);
   ios_base::sync_with_stdio(false);

   int n,k;
   cin>>n>>k;

   if(n == 0){
      cout<<0<<'\n';
      return 0;
   }

   int cnt = n%k;
   if(cnt > abs(cnt-k)){
      cnt = abs(cnt-k);
   }
   cout<<cnt<<'\n';
   return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define debug(var) cout << #var << ": " << var << endl;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
using ll = long long;
using ull = unsigned long long;
using vvint = vector<vector<int>>;
constexpr ll mod = 1e9 + 7;

int main() {

  string S, T; cin >> S >> T;
  rep(i, S.size()) {
	char tmp = S[S.size() - 1];
	S.pop_back();
	S.insert(S.begin(), tmp);
	if (S == T) {
	  cout << "Yes";
	  return 0;
	}
  }

  cout << "No";

  return 0;
}

Measured memory_bytes: 256
x = list(map(int, input().split()))
y = list(map(int, input().split()))
z = [[0, 1, 2, 3], [0, 2, 1, 1], [1, 0, 2, 1], [2, 0, 1, 0], [1, 2, 0, 0], [2, 1, 0, 1]]
succeed = False
for i in range(6):
    match = True
    order = [0, 0, 0]
    for j in range(3):
        if {x[j], x[-j-1]} != {y[z[i][j]], y[-z[i][j]-1]}:
            match = False
            break
        else:
            if x[j] == y[z[i][j]]:
                order[j] = 1
                if x[j] == x[-j-1]:
                    order[j] = 2
    if match:
        if 2 in order:
            succeed = True
            break
        if (z[i][3] == 0 or z[i][3] == 3) and sum(order) % 2:
            succeed = True
            break
        if z[i][3] == 1 and not sum(order) % 2:
            succeed = True
            break
if succeed:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 7752
str = gets.split("")

if str[0] == str[1] && str[1] != str[2] && str[2] == str[3] && str[3] != str[0]
print("Yes")
elsif  str[0] == str[2] && str[1] == str[3] && str[0] != str[1] && str[2] != str[3]
print("Yes")
elsif str[0] == str[3] && str[1] == str[2] && str[0] != str[1]
print("Yes")
else
print("No")
end

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

#define FOR(i, j, n) for (int i(j); i < n; ++i)
#define FORR(v, c) for (auto &v : c)
#define F first
#define S second
#define SQ(x) (x)*(x)
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define dbg(x) cerr<<#x<<" = " << (x) << endl
#define pnl(x) cout << x << '\n'
#define pns(x) cout << x << ' '
#define read(x) cin >> x
#define read2(x,y) cin >> x >> y
#define read3(x, y, z) cin >> x >> y >> z
#define read4(a, b, c, d) cin >> a >> b >> c >> d
#define readv(v) FORR(c,v) read(c)

struct Arrete { int v, c;};
struct Point {int x, y; double distance(Point other) const {return sqrt(SQ(x-other.x)+SQ(y-other.y));}};

typedef	vector<int>	vi;
typedef pair<int,int>	ii;
typedef vector<string>	vs;
typedef vector<ii>	vii;
typedef vector<Arrete>	vg;
typedef vector<long long>	vl;
typedef	long long ll;

const int	NB_D = 4;
const int	DY[] = {-1, 1, 0, 0};
const int	DX[] = {0, 0, -1, 1};

const int MAXN = 1e5;

ll dp[MAXN];

int		main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int N, K;
	read2(N, K);
	
	vl h(N);
	readv(h);

	for (int i(1); i < N; ++i)
	{
		dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
		for (int k(2); k <= K and i-k >= 0; ++k)
			dp[i] = min(dp[i], dp[i-k] + abs(h[i-k] - h[i]));
	}


	pnl(dp[N-1]);
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long int
#define FF first
#define pb push_back
#define SS second
#define double long double

typedef long long ll;

using namespace std;

int dp[505][500005];
int wt[5001];
int val[5001];
signed main()
{
 // freopen("input.txt" , "r" , stdin);
  //freopen("output.txt" , "w" , stdout);

  int n,w;
  cin>>n>>w;
  for(int i=0;i<n;i++)
  {
    cin>>wt[i]>>val[i];
  }

  for(int i=0;i<=105;i++)
  {
    for(int j=1;j<=100004;j++)
    {
      dp[i][j]=10000000000;
    }
  }
  dp[0][val[0]]=wt[0];
  for(int i=1;i<n;i++)
  {
    for(int j=0;j<100005;j++)
    {
      if(val[i]<=j)
      {
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-val[i]]+wt[i]);
      }
      else
        dp[i][j]=dp[i-1][j];
    }
  }
  int ans=0;
  //cout<<w<<endl;

  for(int i=0;i<100005;i++)
  {
//  cout<<dp[n-1][i]<<" ";
    if(dp[n-1][i]<=w)
    {
      ans=max(ans,i);
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 297984
N = int(input())


def head_tail(num):
    if len(str(num)) == 1:
        return (num, num)
    top = int(str(num)[0])
    tail = int(str(num)[-1])
    return (top, tail)


pairs = {}
for i in range(1, N+1):
    p = head_tail(i)
    if p not in pairs:
        pairs[p] = 1
    else:
        pairs[p] += 1

ans = 0
for i in range(1, N+1):
    pair = head_tail(i)
    re = (pair[1], pair[0])
    ans += pairs.get(re, 0)
print(ans)

Measured memory_bytes: 3188
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String str = br.readLine();
			int x = 0;
			int l = str.length();
			for(int i = l-2; i >=0;i=i-2) {
				String s1 = str.substring(0, i/2);
				String s2 = str.substring(i/2,i);
				if(s1.equals(s2)) {
					System.out.println(i);
					break;
				}
			}

		}catch (Exception e) {
			System.exit(0);
		}
	}
}


Measured memory_bytes: 23252
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        int i=1;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        do {
            int x = i;
            if(x % 3 == 0) {
                System.out.print(" " + i);
            }
            else {
                do {
                    if(x % 10 == 3){
                        System.out.print(" " + i);
                        break;
                    }
                    x /= 10;
                    if (x != 0) {

                    }
                }while(x != 0);
            }
        }while(++i <= n);
        System.out.println();

    }
}


Measured memory_bytes: 28740
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int ok=0,c=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(a[i]<a[j])
			{
				ok=1;
				break;
			}
		}
		if(ok==0)
		{
			c++;
		}
		else
		{
			ok=0;
		}
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define N 100020
#define ll long long
using namespace std;
inline int read(){
  int x=0,f=1;char ch=getchar();
  while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
  while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return f?x:-x;
}
int cnt[N], a[N];
int main(int argc, char const *argv[]) {
  int n = read();
  int r = 1 << 30, d = 0;
  for (int i = 1; i <= n; ++ i){
    a[i] = read();
    cnt[a[i]] ++;
    r = min(a[i], r);
    d = max(a[i], d);
  }
  if (r != (d + 1) / 2 || cnt[r] > 1 + (d & 1)) {
    return puts("Impossible"), 0;
  }
  for (int i = r + 1; i <= d; ++ i) {
    if (cnt[i] < 2) {
      return puts("Impossible"), 0;
    }
  }
  puts("Possible");
  return 0;
}
/*
显然 max{a[i]} 即为树的直径。

显然 [直径/2,直径] 必须都存在。

除半径外所有值都应该>=2

半径分情况讨论

*/

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int main(){
    long long N;
    int r=0;
    cin >> N;
    for(int i=2;i<(sqrt(N)+1);i++){
        if(N%i==0){
           r=i;
        }
    }
    if(r==0){
         cout << N-1;
    }else{
        cout << r+N/r-2;
    }
    return 0;
}

Measured memory_bytes: 256
char r[99],g[99],d[99];main(){
	int c,i,j,k,l;
	for(;scanf("%s%s%s",r,g,d)>2;puts("")){
		for(i=j=k=l=0,c=g[j++];k+l<strlen(r)+strlen(g);){
		//if(c==r[i]){
			if(c==d[k]){//push_down
				k++;
				c=r[i++];
			}else{ //push_right
				putchar(c),l++;
				c=g[j++];
			}
		}
	}
exit(0);}

Measured memory_bytes: 524
using System;
using System.Linq;
using System.Collections.Generic;
    
    
class Program
{
    static void Main(string[] args)
    {
        string[] NM = Console.ReadLine().Split(' ');
        int N = int.Parse(NM[0]);
        int M = int.Parse(NM[1]);

        string[] Hstr = Console.ReadLine().Split(' ');
        int[] H = new int[N];
        for(int i=0; i<N; i++) {
            H[i] = int.Parse(Hstr[i]);
        }

        int[] A = new int[M];
        int[] B = new int[M];
        for(int i=0; i<M; i++) {
            string[] AB = Console.ReadLine().Split(' ');
            A[i] = int.Parse(AB[0]);
            B[i] = int.Parse(AB[1]);
        }

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

        for(int i=0; i<M; i++) {
            if(H[A[i] - 1] == H[B[i] - 1]) {
                goodH[A[i] - 1] = 0;
                goodH[B[i] - 1] = 0;
            }else if(H[A[i] - 1] > H[B[i] - 1]) {
                goodH[B[i] - 1] = 0;
            }else{
                goodH[A[i] - 1] = 0;
            }
        }

        int answer = 0;
        for(int i=0; i<N; i++) {
            answer += goodH[i];
        }

        Console.WriteLine(answer);
    }
}

Measured memory_bytes: 48572
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val s = sc.nextInt()

    var set = Set.empty[Int]
    set = set + s
    var bef = s

    for (i <- 1 to 1000000) {
      val j = f(bef)
      if (set.contains(j)) {
        println(i+1)
        sys.exit(0)
      } else {
        set = set + j
        bef = j
      }
    }
  }

  def f(n: Int): Int = {
    if (n % 2 == 0) n / 2
    else 3 * n + 1
  }
}


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

using ll=long long;



void solve(){
    int a,b;
    cin>>a>>b;
    if(a*b%2==0){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
}

signed main(){
    //while(1)
    solve();
}

Measured memory_bytes: 256
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

from collections import deque
todo = deque([1])
seen = deque([])
parent = [0] * (N+1)

# 親と子の関係を作る
while todo:
    x = todo.popleft()
    seen.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        todo.append(y)
        
# 根以外の頂点は、唯一の親を持つことから、
# vの親がpであるとき → color[v] に辺 pvの色を持たせると定めて色を管理
color = [-1] * (N+1)
for x in seen:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

ans = []
for a,b in ab:
    ans.append(color[b])

print(max(ans))
for i in ans:
    print(i)


Measured memory_bytes: 39388
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int n,m;
    cin >> n >> m;
    cout << n*(n-1)/2 + m*(m-1)/2 << endl;
}

Measured memory_bytes: 256
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
l = [0]
r = [0]
ans = 0
for i in range(n-1):
    l.append(gcd(l[i],a[i]))
for i in range(n-1):
    r.append(gcd(r[i],a[n-1-i]))
for i in range(n):
    ans = max(ans,gcd(l[i],r[-i-1]))
print(ans)

Measured memory_bytes: 16136
main = do
  [h,w] <- map read . words <$> getLine 
  s <- lines <$> getContents 
  (putStrLn . unlines) (solve (h,w) s)

type Pos = (Int,Int)

count :: Pos -> Pos -> [String] -> Char
count (h,w) (n,m) s = 
  if s !! n !! m == '#' then '#' else
  head $ show $ length $ filter (=='#') [s !! p !! q | i <- [-1,0,1],j <- [-1,0,1],not (i == 0 && j == 0),let p = n+i,let q = m+j,0 <= p,p<h,0<=q,q<w]

solve ::Pos -> [String] -> [String]
solve (h,w) s = [[count (h,w) (i,j) s |j <-[0..w -1] ] | i <- [0..h-1]]

Measured memory_bytes: 1020
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

type Scanner struct {
	sc  *bufio.Scanner
	buf []byte
}

func NewScanner(r io.Reader) *Scanner {
	s := &Scanner{
		sc: bufio.NewScanner(r),
	}
	s.sc.Split(bufio.ScanWords)
	s.sc.Buffer(s.buf, bufio.MaxScanTokenSize)
	return s
}

func (s *Scanner) nextInt() int {
	if s.sc.Scan() {
		i, err := strconv.Atoi(s.sc.Text())
		if err != nil {
			panic(err)
		}
		return i
	}
	panic("failed to scan")
}

func (s *Scanner) nextString() string {
	if s.sc.Scan() {
		return s.sc.Text()
	}
	panic("failed to scan")
}

func max(a ...int) int {
	m, s := a[0], a[1:]
	for _, v := range s {
		if m < v {
			m = v
		}
	}
	return m
}

func solve(r io.Reader) {

	sc := NewScanner(r)
	N := sc.nextInt()
	W := sc.nextInt()

	prev := make([]int, W+1)
	now := make([]int, W+1)

	for i := 0; i < N; i++ {
		w := sc.nextInt()
		v := sc.nextInt()

		copy(now, prev)
		for j := w; j <= W; j++ {
			now[j] = max(prev[j], prev[j-w]+v)
		}
		copy(prev, now)
	}
	fmt.Println(prev[W])
}

func main() {
	solve(os.Stdin)
}


Measured memory_bytes: 2304
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<functional>
#include<algorithm>
#include<bitset>
#include<utility>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
int main()
{
    long long l,r;
    cin>>l>>r;
    long long ans=400000000000;
    for (long long i=l;i<=min(r,l+2020);i++)
        for(long long int j=i+1;j<=min(r,l+2020);j++)
			ans=min(ans,(i*j)%2019);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
// C++ program to construct array from 
// XOR of elements of given array 
#include <bits/stdc++.h> 
using namespace std; 

void constructXOR(int A[], int n) 
{ 
	int XOR = 0; 
	for (int i = 0; i < n; i++) 
		XOR ^= A[i]; 

	for (int i = 0; i < n; i++) 
		A[i] = XOR ^ A[i]; 
} 
 
int main() 
{
	int n;
	cin >> n;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
	} 
	constructXOR(a, n); 

	for (int i = 0; i < n; i++) 
		cout << a[i] << " "; 
	
} 


Measured memory_bytes: 4276