akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rrep(i, n) for(int i=((int)(n));i>0;i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)	
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define REVSORT(c) SORT(c);REVERSE(c)
#define ALL(x) (x).begin(),(x).end()
#define INF 1e9
const long long MOD = 1000000007;
typedef long long ll;

int main(){
	ll N, M;
	cin >> N >> M;
	vector<ll> dp(N + 1, 0);
	vector<bool> ch(N + 1, true);
	rep(i, M){
		ll a;
		cin >> a;
		ch[a] = false;
	}
	dp[0] = 1;
	if(ch[1])dp[1] = dp[0];
	if(ch[2])dp[2] = dp[0] + dp[1];
	for(ll i = 3; i <= N; i++){
		if(ch[i])dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
	}
	cout << dp[N] << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

const long long int INF=99999999999999,inf=199999;
const long long int mod=1000000007;



long long int n,k,a[2000],sum=0,up=0,down=0,res=0;
int main() {
    long long int count=0;
    string str,str2;
    map<long long int,long long int>mp;
	cout << fixed << setprecision(10);
    cin>>n>>k;
	cout<<max(n-k,max(n+k,n*k));
	
} 


Measured memory_bytes: 256
import math

values = input().split("\n")
n = int(values[0].split(" ")[0])
d = int(values[0].split(" ")[1])
coordinates = []
for i in range(n):
  coordinates.append([int(number) for number in input().split(" ")])

print(len([coordinate for coordinate in coordinates if math.sqrt(coordinate[0]**2+coordinate[1]**2) <= d]))

Measured memory_bytes: 43528
s = gets.chomp
t = gets.chomp
ans_flag = false
ans = []
(0..s.size - t.size).each do|i|
  a = s.slice(i,t.size)
  (0..t.size-1).each do |k|
    if a[k] == t[k] || a[k] == "?"
      ans_flag = true
    else
      ans_flag = false
      break
    end
  end

  if ans_flag
    if i < 1
      ans_string = t + s.slice(i + t.size..-1)
    elsif i + t.size > s.size - 1
      ans_string = s.slice(0..i-1) + t
    else
      ans_string = s.slice(0..i-1) + t + s.slice(i + t.size..-1)
    end
    ans << ans_string.gsub(/\?/,"a")
  end
end
ans.sort!
puts ans.empty? ? "UNRESTORABLE" : ans[0]


Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
using lint  = long long;

signed main(){
 lint N; cin >> N;
 string s; cin >> s;
 lint need_left = 0, need_right = 0;
 lint c = 0;
 for(lint i = 0; i < N; i++){
   if(s[i] == '(') c++;
   else{
     if(c == 0) need_left++;
     else c--;
   }
 }
 lint x = count(s.begin(), s.end(), ')');
 need_right = N + need_left - 2*x;
 for(lint i = 0; i < need_left; i++) cout << '(';
 cout << s;
 for(lint i = 0; i < need_right; i++) cout << ')';
 cout << endl;
}

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.close();
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i < 40000; i++) {
			list.add(i * i);
		}
		if (list.contains(N)) {
			System.out.println(N);
		} else {
			for (int i = 0; i < list.size(); i++) {
				if (list.get(i) > N) {
					System.out.println(list.get(i - 1));
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 23892
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i,n) for(int i = 0;  i < n ; ++i)
#define REP(i,a,b) for(int i = a ; i <= b ; ++i)
#define s(n) scanf("%d",&n)
#define rev(i,n) for(int i = n ; i >= 0 ; --i)
#define REV(i,a,b) for(int i = a ; i >= b ; --i)
#define miN(a,b) (((a)<(b))?(a):(b))
#define sc(n) scanf("%c",&n)
#define tr(c,i) for(typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define INF 1000000000
#define pii pair<long long int,long long int>
#define pb(a) push_back(a)
typedef long long ll;
using namespace std;
void pre(){}
void solve(){
    ll n,m,u,v;cin>>n>>m;
    vector<int>arr[n+1];
    ll val[n+1];
    for(int i=0;i<n;i++) cin>>val[i+1];
    for(int i=0;i<m;i++){
        cin>>u>>v;
        arr[v].pb(u);
        arr[u].pb(v);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        bool flag = 1;
        for(auto j:arr[i]){
            if(val[j]>=val[i]){
                flag= 0;
                break;
            }
        }
        if(flag){
            ans++;
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    //cin>>num;
    for(long long int i=0;i<num;i++){
      //  cout<<"Case #"<<i+1<<" :";
       	solve();
    }   
}




Measured memory_bytes: 9536
M=10**9+7
N,A,B,C=map(int,input().split())
f=[1]
for i in range(1,2*N):
	f.append(f[-1]*i%M)
t=pow(A+B,M-2,M)
A*=t
B*=t
a=pow(A,N,M)
b=pow(B,N,M)
z=0
for i in range(N):
	z+=100*t*f[N+i]*pow(f[N-1]*f[i],M-2,M)*(a+b)
	z%=M
	a=a*B%M
	b=b*A%M
print(z)


Measured memory_bytes: 11052
#include<bits/stdc++.h>
#include <utility>
using namespace std;
string findSum(string str1, string str2)
{
    if (str1.length() > str2.length())
        swap(str1, str2);
    string str = "";
    int n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());

    int carry = 0;
    for (int i=0; i<n1; i++)
    {
        int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
        carry = sum/10;
    }
    for (int i=n1; i<n2; i++)
    {
        int sum = ((str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
        carry = sum/10;
    }
    if (carry)
        str.push_back(carry+'0');
    reverse(str.begin(), str.end());

    return str;
}
int main()
{
    unsigned long long s,i=0;
    cin>>s;
    string sum ="0";
    while(++i<=s){
      if(!(i%3==0 || i%5==0))sum=findSum(to_string(i),sum);
    }
    cout<<sum<<endl;
    return 0;
}


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

#define INF (INT32_MAX)
#define MOD (1000000000+7)
#define MAX 50

int N, A;
int x[MAX];

long long dp[MAX + 1][MAX + 1][MAX*MAX + 1];

int main() {
	cin >> N >> A;
	for( int i = 0; i < N; i++ ) {
		cin >> x[i];
	}

	sort( x, x + N );
	int X = max( x[N - 1], A );
	dp[0][0][0] = 1;
	for( int j = 1; j <= N; j++ ) {
		for( int k = 0; k <= N; k++ ) {
			for( int s = 0; s <= N*X; s++ ) {
				if( s < x[j - 1] ) {
					dp[j][k][s] = dp[j - 1][k][s];
				}
				else if( k > 0 && s >= x[j - 1] ) {
					dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][ s - x[j - 1] ];
				}
				else {
					dp[j][k][s] = 0;
				}
			}
		}
	}

	long long ans = 0;
	for( int k = 1; k <= N; k++ ) {
		ans += dp[N][k][A * k];
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 50048
class Main
{
	public static void main(String[] args) {
		java.io.BufferedReader reader = null;
		try {
			reader = new java.io.BufferedReader(
				new java.io.InputStreamReader(System.in)
				);
			String[] inputs = reader.readLine().split(" ");
			int a = Integer.parseInt(inputs[0]);
			int b = Integer.parseInt(inputs[1]);
			int c = Integer.parseInt(inputs[2]);
			int t;
			if (a > b) {
				t = a;
				a = b;
				b = t;
			}
			if (a > c) {
				t = a;
				a = c;
				c = t;
			}
			if (b > c) {
				t = b;
				b = c;
				c = t;
			}
			System.out.printf("%d %d %d\n", a, b, c);
		} catch (java.io.IOException e ) {
			e.printStackTrace();
		} finally {
			if (reader != null) {
				try {
					reader.close();
				} catch (java.io.IOException e) {
					e.printStackTrace();
				}
			}
		}
	}
}

Measured memory_bytes: 16908
#include <bits/stdc++.h>
#define ALL(a) (a).begin(),(a).end()
#define N_MAX 1000
using namespace std;

int main() {
	long long int A, B, K;
	cin >> A >> B >> K;

	if (A >= K) {
		cout << A - K << ' ' << B << endl;
	}
	else if(A < K && K <= A+ B) {
		cout << 0 << ' ' << B - K + A << endl;
	}
	else {
		cout << 0 << ' ' << 0 << endl;
	}
}

Measured memory_bytes: 256
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int n, c;

int a[404], b[404];
LL mod = 1e9 + 7;
LL dp[404][404];

LL mpow[404][404];
LL ruimpow[404][404]; 

int main(){
    cin >> n >> c;
    REP(i, n)cin >> a[i];
    REP(i, n)cin >> b[i];

    mpow[0][0] = 1;
    for(int i = 1;i <= 400;i++){
        mpow[i][0] = 1;
        REP(j, 401)mpow[i][j + 1] = mpow[i][j] * i % mod;
    }
    REP(i, 401)REP(j, 401){
        (ruimpow[i + 1][j] = ruimpow[i][j] + mpow[i][j]) %= mod;
    }

    dp[0][0] = 1;
    REP(i, n){
        for(int j = 0;j <= c;j++){
            for(int k = 0;j + k <= c;k++){
                LL num = (ruimpow[b[i] + 1][k] - ruimpow[a[i]][k] + mod) % mod;
                (dp[i + 1][j + k] += dp[i][j] * num) %= mod;
            }
        }
    }
    cout << dp[n][c] << endl;
}

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

using namespace std;

int main()
{
    int n,m,i,j,k,x;
    cin>>n>>m;

    //int i;
    vector<unordered_set<int>>V(m);
    for(i=0;i!=m;i++)
    {
        //int j,k;
        cin>>k;

        for(j=0;j!=k;j++)
        {
            //int x;
            cin>>x;
            V[i].insert(x-1);
        }
    }

    vector<int>P(m);
    for(i=0;i!=m;i++)
        cin>>P[i];

    // for(j=0;j!=m;j++)
    // {
    //     for(auto it=V[j].begin();it!=V[j].end();it++)
    //         cout<<*it<<' ';
    //     cout<<'\n';
    // }

    int num = 0;
    for(i=0;i!=(int)pow(2,n);i++)
    {
        vector<int>numSwitch(m,0);
        for(j=1,x=0;j<=i;j=j<<1,x++)
        {
            //cout<<(j&i)<<' ';

            if((j&i)!=0)
            {
                //int k;
                for(k=0;k!=m;k++)
                    if(V[k].find(x)!=V[k].end())     // fill it up
                        numSwitch[k]++;
            }
        }

        //cout<<'\n';
        // for(j=0;j!=m;j++)
        //     cout<<numSwitch[j]<<' ';
        // cout<<'\n';


        int c = 0;
        for(j=0;j!=m;j++)
        {
            if((numSwitch[j]-P[j])%2 == 0)
                c++;
            else
                break;
        }

        if(c == m)
            num++;
    }

    cout<<num;

    return 0;
}

Measured memory_bytes: 4104
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define alpha_size 26



int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);    
  
    int k, a, b;
    cin >> k >> a >> b;
    for (int i = a; i <= b; i++){
      if (i % k == 0){
        cout << "OK" << endl;
        return 0;
      }
    }
    cout << "NG" << endl;
}

Measured memory_bytes: 3688
class Main{
    public static void main(String[] a){
        System.out.println("1x1=1");
        System.out.println("1x2=2");
        System.out.println("1x3=3");
        System.out.println("1x4=4");
        System.out.println("1x5=5");
        System.out.println("1x6=6");
        System.out.println("1x7=7");
        System.out.println("1x8=8");
        System.out.println("1x9=9");
        System.out.println("2x1=2");
        System.out.println("2x2=4");
        System.out.println("2x3=6");
        System.out.println("2x4=8");
        System.out.println("2x5=10");
        System.out.println("2x6=12");
        System.out.println("2x7=14");
        System.out.println("2x8=16");
        System.out.println("2x9=18");
        System.out.println("3x1=3");
        System.out.println("3x2=6");
        System.out.println("3x3=9");
        System.out.println("3x4=12");
        System.out.println("3x5=15");
        System.out.println("3x6=18");
        System.out.println("3x7=21");
        System.out.println("3x8=24");
        System.out.println("3x9=27");
        System.out.println("4x1=4");
        System.out.println("4x2=8");
        System.out.println("4x3=12");
        System.out.println("4x4=16");
        System.out.println("4x5=20");
        System.out.println("4x6=24");
        System.out.println("4x7=28");
        System.out.println("4x8=32");
        System.out.println("4x9=36");
        System.out.println("5x1=5");
        System.out.println("5x2=10");
        System.out.println("5x3=15");
        System.out.println("5x4=20");
        System.out.println("5x5=25");
        System.out.println("5x6=30");
        System.out.println("5x7=35");
        System.out.println("5x8=40");
        System.out.println("5x9=45");
        System.out.println("6x1=6");
        System.out.println("6x2=12");
        System.out.println("6x3=18");
        System.out.println("6x4=24");
        System.out.println("6x5=30");
        System.out.println("6x6=36");
        System.out.println("6x7=42");
        System.out.println("6x8=48");
        System.out.println("6x9=54");
        System.out.println("7x1=7");
        System.out.println("7x2=14");
        System.out.println("7x3=21");
        System.out.println("7x4=28");
        System.out.println("7x5=35");
        System.out.println("7x6=42");
        System.out.println("7x7=49");
        System.out.println("7x8=56");
        System.out.println("7x9=63");
        System.out.println("8x1=8");
        System.out.println("8x2=16");
        System.out.println("8x3=24");
        System.out.println("8x4=32");
        System.out.println("8x5=40");
        System.out.println("8x6=48");
        System.out.println("8x7=56");
        System.out.println("8x8=64");
        System.out.println("8x9=72");
        System.out.println("9x1=9");
        System.out.println("9x2=18");
        System.out.println("9x3=27");
        System.out.println("9x4=36");
        System.out.println("9x5=45");
        System.out.println("9x6=54");
        System.out.println("9x7=63");
        System.out.println("9x8=72");
        System.out.println("9x9=81");

    }
}

Measured memory_bytes: 16892
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

const int maxn = 1e5 + 5;
ll res[maxn];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	res[n - 1] += a[n - 1];
	for(int i = 0; i <= n - 2; i++){
		if(i % 2 == 0) res[n - 1] -= a[i];
		else res[n - 1] += a[i];
	}
	for(int i = 0; i < n - 1; i++){
		res[i] = 2 * a[i == 0 ? n - 1 : i - 1] - res[i == 0 ? n - 1 : i - 1];
	}
	for(int i = 0; i < n; i++) cout << res[i] << " ";
}

Measured memory_bytes: 2944
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll h,n;cin>>h>>n;
    vector<ll>a(n+1),b(n+1);
    ll amax=0;
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        chmax(amax,a[i]);
    }
    ll dp1[100001];ll ans=INF;
    
    //初期化 求最小值就这样 最大值反着来即可 不要多逼逼
    for(ll i=0;i<=10000+amax;i++)dp1[i]=INF;
    dp1[0]=0;
    
    //dp[i] 为了消灭i体力所需要的最小魔法值
    for(ll i=1;i<=n;i++){
        for(ll j=a[i];j<=h+amax;j++){//j可以直接从a[j]开始
            chmin(dp1[j],dp1[j-a[i]]+b[i]);
            /*ll ncnt=j/a[i];
            for(int k=0;k<=ncnt;k++)
            chmin(dp1[j],dp1[j-k*a[i]]+b[i]*k);*///因为是从小到大遍历过来的所以不需要这个步骤
        }
    }
    
    //打h到h+amax之间的最小ans 可以理解吧
    for(ll i=h;i<=h+amax;i++)
        chmin(ans,dp1[i]);
    cout<<ans<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------









Measured memory_bytes: 384
#include <bits/stdc++.h>
 size_t strlen(const char *s);
#define rep(i,n) for(long long int i=0;i<n;i++)
#define sz(x) ((int)(x).size())

using namespace std;
std::vector<int> graph[10050];//graph頂点数のsize
const int N=200010;
//const ll P=1000000007;
const long long P=998244353;
using ll = long long;
vector<ll> prime;

//絶対値
int ze(int a, int b){
	if(a>b){
		return a-b;
	}else{
		return b-a;
	}
}
//小さい方
long long int min(long long int a,long long int b){
	if(a>b){
		return b;
	}else{
		return a;
	}
}
//大きい方
long long int max(long long int a,long long int b){
	if(a>b){
		return a;
	}else{
		return b;
	}
}
// a^n mod 
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod 
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

//mod掛け算
long long mt(long long a, long long b, long long mod){
	return (a*b)%mod;
}

//メモ

/*
	memset(b, '\0', sizeof(b));
初期化*/


/*
	string s;
	s.size()
*/

/*
	char s[N];
	strlen(s)
*/
/*
	if(  <  )puts("Yes");
	else puts("No");
*/

/*文字列比較
if(strcmp(name[i],s)==0)
*/

/*
	graph[a].push_back(b);//graph[a][i番目に入れた]==b
	graph[j].size()	//forで回すときとか

*/


int main(){
  ll number=1001000;
  vector<long long> primes(number);
  vector<long long> prime(0);
  rep(i, pow(number,0.5)+10){
    if(i<2) continue;
    if(primes.at(i)==0){
//      cout<<i<<",";
      ll k=i;
      while(i*k<number){
        primes.at(i*k)++;
        k++;
      }
    }
  }
  rep(i, number){
    if(i<2) continue;
    if(primes.at(i)==0){
      prime.push_back(i);
//      cout<<i<<",";
    }
  }
  ll m;
  cin>>m;
  ll ans=0;
  bool y=false;
  rep(i, sz(prime)){
    if(m==1){
      y=true;
      break;
    }else{
        ll kari=m;
          bool finish=false;
        for(ll j=1;!finish;j++){
          ans++;
          rep(k,j){
            if(kari%prime.at(i)==0){
              kari=kari/prime.at(i);
            }else{
              finish=true;
              break;
            }
          }
        }
        ans--;
      while(m%prime.at(i)==0){
        m=m/prime.at(i);
      }
                     
    }
  }
  if(!y){
    ans++;
  }
  cout<<ans<<endl;
          
          
    
  
}


Measured memory_bytes: 12184
N = int(input())
L = list(map(int,input().split()))
b2 = 0
b4 = 0

for i in range(N):
    if L[i] % 4 == 0:
        b4 += 1
    elif L[i] % 2 == 0:
        b2 += 1
other = N-b4-b2
if b2 != 0:
    other += 1
print('Yes' if other<= b4+1 else 'No')



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

const int mN = 20;
const int oo = 2e9;
int c[mN], a[mN][mN];
int s[mN];

int main()
{
    int n,m,x;
    cin >> n >> m >> x;
    for (int i=0; i<n; i++) {
        cin >> c[i];
        for (int j=1; j<=m; j++) cin >> a[i][j];
    }
    int ans = oo;
    for (int mask=0; mask<(1<<n); mask++) {
        int cost = 0;
        fill(s,s+1+m,0);
        for (int b=0; b<n; b++) if ((mask>>b)&1) {
            cost += c[b];
            for (int j=1; j<=m; j++) s[j] += a[b][j];
        }
        bool check = true;
        for (int j=1; j<=m; j++) check &= (s[j] >= x);
        if (check) ans = min(ans, cost);
    }
    if (ans == oo) ans = -1;
    cout << ans;
}


Measured memory_bytes: 3632
#include <iostream> // includes cin to read from stdin and cout to write to stdout
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std; // since cin and cout are both in namespace std, this saves some text

#define REP(i, n) for (int (i) = 0; i < (n); ++i)

int main()
{
    string str;
    int K;
    cin >> str;
    cin >> K;
    
    vector<string> dict;
    unordered_map<string, int> checker;
    REP(i, str.size()) {
        for (int j = 1; j <= str.size(); ++j) {
//            if (i + j > str.size()) break;
            string sub = str.substr(i, j);
            if (dict.size() > K && dict[K-1] < sub) {
                break;
            }
            if (checker[sub] > 0) {
                continue;
            }
            dict.push_back(sub);
            ++checker[sub];
            sort(dict.begin(), dict.end());
        }
//        if (dict.size() >= K) break;
    }

//    REP(i, vec.size()) cout << vec[i] << endl;
    cout << dict[K-1] << endl;
    
    return 0;
}



Measured memory_bytes: 256
c=[list(map(int,input().split())) for i in range(3)]
a=[0]*3
b=[0]*3
a[0]=min(c[0])
b[0]=c[0][0]-a[0]
b[1]=c[0][1]-a[0]
b[2]=c[0][2]-a[0]
a[1]=c[1][1]-b[1]
a[2]=c[2][2]-b[2]
for i in range(3):
    for j in range(3):
        if a[i]+b[j]!=c[i][j]:
            print("No")
            break
    else:continue
    break
else:print("Yes")

Measured memory_bytes: 3192
N, M = map(int, input().split())
a_list = [int(input()) for _ in range(M)]

mod = 10 ** 9 + 7

dp = [0] * (N + 1)
dp[0] = 1
not_use = [False] * (N + 1)
for a in a_list:
    not_use[a] = True

for i in range(N+1):
    not_u = not_use[i]
    if not_u:
        continue
    else:
        if i < N:
            dp[i + 1] += dp[i]
            dp[i + 1] %= mod
        if i < N - 1:
            dp[i + 2] += dp[i]
            dp[i + 2] %= mod

print(dp[N] % mod)


Measured memory_bytes: 9640
home = True
s = raw_input().strip()
if 'N' in s and 'S' not in s:
    home = False
if 'S' in s and 'N' not in s:
    home = False
if 'W' in s and 'E' not in s:
    home = False
if 'E' in s and 'W' not in s:
    home = False
print('Yes' if home else 'No')

Measured memory_bytes: 8816
import java.util.Scanner;

public class Main{

	public static void main(String[] args){

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();

	    int oddcnt = N-N/2;

	    double prob = (double)oddcnt/(double)N;

	    System.out.println(prob);

	}
}



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

 
int main(){

 
    long double A,B,H,M;
    cin >> A >> B >> H >> M;
    long double pi = 3.1415926535;
 
    long double funkaku,jikaku;
    funkaku = M / 60;
    jikaku = H / 12 + M / 720;
 
    long double theta = abs(0.5*(60*H-11*M)*pi/180);
    // cout << theta;
    long double result;
 
    if(theta == 0){
        result = abs(A-B);
    }
    else{
        result = sqrt(pow(A,2) + pow(B,2) - 2 * A * B * cosl(theta));
    }
    
    cout << fixed << setprecision(15) << result;
}

Measured memory_bytes: 4176
s=list(input())
c=list(reversed(s))
n=len(s)
t=list(s[:int((n-1)/2)])
a=list(reversed(t))
u=list(s[int((n+3)/2)-1:])
b=list(reversed(u))
#print(b)
if t==a and u==b and s==c:
    print("Yes")   
else:
    print("No")
    

Measured memory_bytes: 3060
def heapify(V, H, i):
  l, r = i*2+1, i*2+2
  iv = V[i]
  lv = V[l] if l < H else -1e10
  rv = V[r] if r < H else -1e10
  if lv > iv and lv >= rv:
    V[i] = lv
    V[l] = iv
    heapify(V, H, l)
  elif rv > iv:
    V[i] = rv
    V[r] = iv
    heapify(V, H, r)

H = int(input())
V = list(map(int, input().split()))

for i in range(H-1, -1, -1):
  heapify(V, H, i)
print(''.join([' '+str(v) for v in V]))


Measured memory_bytes: 64004
#include<iostream>
int R,C,s[10000][10],f[10],N,i,j,n,m;void rec(int k){if(k<R){f[k]=0;rec(k+1);f[k]=1;rec(k+1);}else for(n=i=0;i<C;i++,n+=m>R-m?m:R-m,N=N>n?N:n)for(m=j=0;j<R;j++)m+=s[i][j]^f[j];}main(){for(;std::cin>>R>>C,R|C;rec(0),printf("%d\n",N))for(j=R;j-->0;)for(i=C;i-->0;)scanf("%d",s[i]+j);}

Measured memory_bytes: 1304
#  --*-coding:utf-8-*--

import math

A,B = map(int, input().split())

x = max(math.ceil(A*100/8), math.ceil(B*10))

if math.floor(x*0.08) != A or math.floor(x*0.1) != B:
    print(-1)
else:
    print(x)



Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::string O,E;
    std::cin>>O>>E;
    std::string pass;

    int count1=0,count2=0;

    for(int i=0;i<O.length()+E.length();i++){
        if(i%2==0){
            pass.push_back(O[count1++]);
        }else{
            pass.push_back(E[count2++]);
        }
    }

    std::cout<<pass<<std::endl;
    return 0;
}

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

using namespace std;
#define ll long long

#define rep(i, a) for (int (i) = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int (i) = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int (i) = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int (i) = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__ "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}

#ifdef LOCAL
	#define lcout(a) cout << a;
	#define lcoutln(a) cout << a << endl;
	#define lcerr(a) cerr << a;
	#define lcerrln(a) cerr << a << endl;
#else
	#define lcout(a) 
	#define lcoutln(a) 
	#define lcerr(a) 
	#define lcerrln(a) 
#endif

int N, P;
int tyo[50];
int pos;
int wan;

signed main()
{
	cin >> N >> P;
	while (N) {
		wan = P;
		pos = 0;
		rep(i, N) tyo[i] = 0;
		while (true) {
			if (wan) {
				wan--;
				tyo[pos]++;
			} else {
				wan = tyo[pos];
				tyo[pos] = 0;
			}
			if (tyo[pos] == P) break;
			pos = (pos+1) % N;
		}
		cout << pos << endl;
		cin >> N >> P;
	}	
}



Measured memory_bytes: 2972
import math
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())

    res = []
    def isP(i):
        if i == 1:
            return False
        for j in res:
            if i % j == 0:
                return False
        return True

    def calc(p):
        mx = math.floor(math.log(N,p))
        # print("mx",mx)
        e_v = pow(p,mx)
        e = 0
        ng = False
        for i in reversed(range(mx)):
            if not ng and N % e_v == 0:
                ng = True
                e = i+1

            if not ng:
                e_v //= p
                e = i+1

        # print("e",e)
        base = -1+math.sqrt(1+8*e)
        return math.floor(base/2)

    tail = []
    ans = 0
    for p in range(1, int(N**0.5)+1):
        tail.append(N//p)
        if N % p == 0 and isP(p):
            res.append(p)
            # print("p",p)

            ans += calc(p)
    for p in tail:
        if N % p == 0 and isP(p):
            res.append(p)
            # print("p",p)

            ans += calc(p)


    print(ans)

if __name__ == "__main__":
  main()

Measured memory_bytes: 140564
#include<stdio.h>


int main(void)
 {
     int S, s, m, h;
     scanf("%d", &S);
     h = S / 3600;
     m = (S % 3600) / 60;
     s = (S - 3600 * h - 60 * m);
     printf("%d:%d:%d\n", h, m, s);
     return 0;
     }

Measured memory_bytes: 592
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
	int n;
	cin >> n;
	int i;
	long long int sum = 0;
	for (i = 1; i <= n; i++)
	{
		if (i % 3 != 0 && i % 5 != 0)
			sum += i;
	}
	cout << sum << endl;
} 

Measured memory_bytes: 3588
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int s, d, m;
int main() {
	while (~scanf("%d%d%d", &s, &d, &m)) {
		vector<vector<pair<int, int> > > v(s);
		for (int i = 0; i < s; i++) {
			int z; scanf("%d", &z); v[i].resize(z);
			for (int j = 0; j < z; j++) scanf("%d%d", &v[i][j].first, &v[i][j].second);
		}
		vector<pair<int, int> > x;
		for (int i = 0; i < d; i++) {
			int f; scanf("%d", &f);
			x.insert(x.end(), v[f].begin(), v[f].end());
		}
		int n = x.size();
		vector<vector<int> > dp(n + 1, vector<int>(m + 1, -99999999));
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= x[i - 1].second) dp[i][j] = max(dp[i][j], dp[i - 1][j - x[i - 1].second] + x[i - 1].first);
			}
		}
		int ret1 = 0, ret2 = 0;
		for (int i = 0; i <= m; i++) {
			if (dp[n][i] > ret1) ret1 = dp[n][i], ret2 = i;
		}
		printf("%d %d\n", ret1, ret2);
	}
	return 0;
}

Measured memory_bytes: 6032
#include<stdio.h>
int main(void)
{
	int a, b, c;

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

	if (a < b && b < c) {
		printf("Yes\n",a ,b ,c);
	}
	else {
		printf("No\n", a, b, c);
	}

	return(0);
}


Measured memory_bytes: 2124
n = int(input())

honest = []
for i in range(n):
    a = int(input())
    honest.append({})
    for j in range(a):
        x,y = map(int, input().split())
        honest[i][x-1] = y
ans = 0
for i in range(1<<n):
    tmp = 0
    hon = 0
    for j in range(n):
        if 1<<j & i == 0:
            continue
        for k,v in honest[j].items():
            if (1<<k & i) != v<<k:
                break
        else:
            tmp += 1
            hon |= 1<<j
    if hon == i and tmp > ans:
        # print(bin(i), bin(tmp), 1<<1 & i, )
        ans = tmp
print(ans)


Measured memory_bytes: 3064
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, x: i64, d: i64,
    }
    if d == 0 {
        puts!("{}\n", if x == 0 { 1 } else { n + 1 });
        return;
    }
    let (x, d) = if d < 0 {
        (-x, -d)
    } else {
        (x, d)
    };
    let mut hm = HashMap::new();
    let xd = (x % d + d) % d;
    for i in 0..n + 1 {
        let r = xd * i as i64 % d;
        let v = hm.entry(r).or_insert(vec![]);
        let q = (x * i as i64 - r) / d;
        let k = i as i64;
        let lo = k * (k - 1) / 2;
        let hi = (2 * n as i64 - 1 - k) * k / 2;
        v.push((q + lo, q + hi));
    }
    let mut tot: i64 = 0;
    for (_key, mut v) in hm {
        v.sort();
        let mut cur = -1 << 60;
        for (l, r) in v {
            if r >= cur {
                tot += r - max(l, cur) + 1;
                cur = r + 1;
            }
        }
    }
    puts!("{}\n", tot);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

int main(void){
	int a, b, d, r;
	double f;

	cin >> a >> b;

	d = a / b;
	r = a%b;
	f = static_cast<double>(a) / b;

	cout << d << " " << r << " " << fixed << setprecision(8) << f << "\n";

	return 0;
}

Measured memory_bytes: 1248
#include <stdio.h>

int main(void) {
	int n, m;
	
	while (scanf("%d%d", &n, &m), n) {
		int i, j, max = 0;
		int l[100000], r[100000];
		
		long long s = 0;
		long long ss = 0;
		
		l[0] = 0;
		r[0] = 0;

		for (i = 1; i < m; ++i) {
			l[i] = 30001; // ??????????????????
			r[i] = -1;    // ??????????????????
		}
		
		for (i = 1; i <= n; ++i) {
			unsigned int t;
			scanf("%u", &t);
			s = (s + t) % m;
			ss += t;
			
			l[s] = i < l[s] ? i : l[s]; // ??????
			r[s] = i > r[s] ? i : r[s]; // ??????
			
			max = max < s ? s : max;
		}
		
		if (ss < m) {
			printf("%d\n", (int)ss);
			continue;
		}
		
		// ????????????????????°???
		for (i = 1; i < m; ++i) {
			if (r[i] <= 0) {
				continue;
			}
			
			// ??????????????????????????´(i+1)????????°???
			for (j = 1; j < m - max; ++j) {
				// ?????´????????¢???????????°???????????´??°
				if (l[i + j] < r[i]) {
					max = m - j;
					break;
				}
			}
		}

		printf("%d\n", max);
	}
	
	return 0;
}

Measured memory_bytes: 1388
#include<bits/stdc++.h>
#define fatafat ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define MOD ((long long)(1e9)+7)
#define excl(i,a,b) for(int i=a;i<b;i++)
#define incl(i,a,b) for(int i=a;i<=b;i++)
#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define PII pair<int,int>

using namespace std;

int binexp(int a,int b)
{
    if(b)
    {
        if(b%2)
            return a*binexp(a*a,b/2);
        return binexp(a*a,b/2);
    }
    return 1;
}

int modexp(int a,int b,int m)
{
    if(b)
    {
        if(b%2)
            return (a*modexp((a*a)%m,b/2,m))%m;
        return modexp((a*a)%m,b/2,m);
    }
    return 1;
}

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

int euclidgcd,euclidx,euclidy;

void exteuclid(int a,int b)
{
    if(b==0)
    {
        euclidgcd=a;
        euclidx=1;
        euclidy=0;
    }
    else
    {
        exteuclid(b,a%b);
        int temp=euclidx;
        euclidx=euclidy;
        euclidy=temp-euclidy*(a/b);
    }
}

int modinv(int a,int m)
{
    exteuclid(a,m);
    return (euclidx%m + m)%m;
}

int pmodinv(int a,int m)
{
    return modexp(a,m-2,m);
}

bool checkprime(int a)
{
    for(int i=2;i*i<=a;i++)
        if(a%i==0)
            return false;
    return true;
}

vector<bool> seive(int n)
{
    vector<bool> ret(n+1,true);
    ret[0]=ret[1]=false;
    for(int i=2;i*i<=n;i++)
        if(ret[i])
            for(int j=i*i;j<=n;j+=i)
                ret[j]=false;
    return ret;
}

vector<bool> seivelims(int l,int r)
{
    vector<bool> ret(r-l+1,true);
    for(int i=2;i*i<=r;i++)
    {
        for(int j=max(i*i,((l+i-1)/i)*i);j<=r;j+=i)
        {
            ret[j-l]=false;
        }
    }
    return ret;
}

vector<int> rootnfact(int n)
{
    vector<int> ret;
    for(long i=2;i*i<=n;i++)
        while(n%i==0)
        {
            ret.push_back(i);
            n/=i;
        }
    if(n!=1)
        ret.push_back(n);
    return ret;
}

vector<int> prelognfact(int n)
{
    vector<int> minprime(n+1,0);
    minprime[0]=minprime[1]=0;
    for(int i=2;i*i<=n;i++)
    {
        if(minprime[i]==0)
        {
            for(int j=i*i;j<=n;j+=i)
            {
                if(minprime[j]==0)
                    minprime[j]=i;
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(minprime[i]==0)
            minprime[i]=i;
    return minprime;
}

vector<int> lognfact(int n,vector<int> minprime)
{
    vector<int> ret;
    while(n!=1)
    {
        ret.push_back(minprime[n]);
        n/=minprime[n];
    }
    return ret;
}

signed main()
{
    fatafat;
    int a,b,t;
    cin>>a>>b>>t;
    cout<<(t/a)*b;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num::clamp;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout()]
fn main() {
    input! {
        h: i64, w: i64, n: usize,
        sr: i64, sc: i64,
        s: Chars,
        t: Chars,
    }

    let (u, d, l, r) = (0, 1, 2, 3);
    let mut scum = vec![vec![0; n+1]; 4];
    let mut tcum = vec![vec![0; n+1]; 4];
    for i in 0..n {
        match s[i] {
            'U' => scum[u][i+1] += 1,
            'D' => scum[d][i+1] += 1,
            'L' => scum[l][i+1] += 1,
            'R' => scum[r][i+1] += 1,
            _ => unreachable!()
        }
        match t[i] {
            'U' => tcum[u][i+1] += 1,
            'D' => tcum[d][i+1] += 1,
            'L' => tcum[l][i+1] += 1,
            'R' => tcum[r][i+1] += 1,
            _ => unreachable!()
        }
    }
    
    let mut ans = "YES";
    for i in 1..n+1 {
        for dir in 0..4 {
            scum[dir][i] += scum[dir][i-1];
            tcum[dir][i] += tcum[dir][i-1];
        }

        if tcum[l][i] - scum[r][i] >= sc {
            tcum[l][i] -= 1;
        }
        if tcum[r][i] - scum[l][i] > w - sc {
            tcum[r][i] -= 1;
        }
        if tcum[u][i] - scum[d][i] >= sr {
            tcum[u][i] -= 1;
        }
        if tcum[d][i] - scum[u][i] > h - sr {
            tcum[d][i] -= 1;
        }

        if scum[l][i] - tcum[r][i-1] >= sc {
            ans = "NO";
            break;
        }
        if scum[r][i] - tcum[l][i-1] > w - sc {
            ans = "NO";
            break;
        }
        if scum[u][i] - tcum[d][i-1] >= sr {
            ans = "NO";
            break;
        }
        if scum[d][i] - tcum[u][i-1] > h - sr {
            ans = "NO";
            break;
        }

    }
    println!("{}", ans);
}


Measured memory_bytes: 16440
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node{
  int key;
  Node *next,*prev;
};

Node *nil;

Node* listSearch(int key){
  Node *cur=nil->next;
  while(cur!=nil&&cur->key!=key){
    cur=cur->next;
  }
  return cur;
}

void init(){
  nil=(Node *)malloc(sizeof(Node));
  nil->next=nil;
  nil->prev=nil;
}

void printlist(){
  Node *cur=nil->next;
  int isf=0;
  while(1){
    if(cur==nil) break;
    if(isf++>0) printf(" ");
    printf("%d",cur->key);
    cur=cur->next;
  }
  printf("\n");
}

void deleteNode(Node *t){
  if(t==nil) return;
  t->prev->next=t->next;
  t->next->prev=t->prev;
  free(t);
}

void deleteFirst(){
  deleteNode(nil->next);
}

void deleteLast(){
  deleteNode(nil->prev);
}

void deleteKey(int key){
  deleteNode(listSearch(key));
}

void insert(int key){
  Node *x=(Node *)malloc(sizeof(Node));
  x->key=key;
  x->next=nil->next;
  nil->next->prev=x;
  nil->next=x;
  x->prev=nil;
}

int main(){
  int key,n,i;
  int size=0;
  char com[20];
  int np=0,nd=0;
  scanf("%d",&n);
  init();
  for(i=0;i<n;i++){
    scanf("%s%d",com,&key);
    if(com[0]=='i'){insert(key); np++; size++;}
    else if(com[0]=='d'){
      if(strlen(com)>6){
	if(com[6]=='F') deleteFirst();
	else if(com[6]=='L') deleteLast();
      }else{
	deleteKey(key); nd++;
      }
      size--;
      }
    }
  printlist();

  return 0;
}

Measured memory_bytes: 33840
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        win=2**n-1
        know=[2**x for x in range(n)]
        date=[[] for x in range(31)]
        for i in range(n):
            indata=[int(x) for x in raw_input().split()]
            for j in indata[1:]:
                date[j].append(i)
        #print know,date
        for dd in range(1,31):
            m=0
            d=date[dd]
            for pd in d:
                m|=know[pd]
            if m==win:
                print dd
                break
            else:
                for pd in d:
                    know[pd]=m
        else:
            print -1
        #print win, know

Measured memory_bytes: 4244
/*
ye mera template hai
apna khud likho bc :P
*/

/*
Author : Sarvagya Agarwal
*/

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

//defines
#define openin freopen("input.txt","r",stdin)
#define openout freopen("output.txt","w",stdout)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define int long long
#define mod 1000000007
#define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
#define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair

/* Print pair */
template <typename T,typename S>
ostream & operator << (ostream &os , const pair<T,S> &v) {
    os << "(" ;
    os << v.first << "," << v.second << ")" ;
    return os ;
}
/* Print vector */
template <typename T>
ostream & operator << (ostream &os , const vector<T> &v) {
    os << "[" ;
    int sz = v.size() ;
    for(int i = 0 ; i < sz ; ++i) {
        os << v[i] ;
        if(i!=sz-1)os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print set */
template <typename T>
ostream & operator << (ostream &os , const set<T> &v) {
    T last = *v.rbegin() ;
    os << "[" ;
    for(auto it : v) {
        os << it  ;
        if(it != last) os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print Map */
template <typename T,typename S>
ostream & operator << (ostream &os , const map<T,S> &v) {
    for(auto it : v) {
        os << it.first << " : " << it.second << "\n" ;
    }
    return os ;
}
int power(int a , int b)
{
    int res = 1 ;
    while(b)
    {
        if(b%2) {
            res = (res * a) % mod ;
        }
        b/=2 ;
        a = (a*a) % mod ;
    }
    return res ;
}

//debug
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
		cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
		const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
int cnt[100005] ;
int32_t main()
{
    fast;
    int n ;
    cin >> n ;
    rep(i,1,n) {
        int x ;
        cin >> x ;
        cnt[x] += 1 ;
    }
    priority_queue<pair<int,int> > Q ;
    rep(i,1,100000) {
        if(cnt[i] > 2) {
            Q.push({cnt[i],i}) ;
        }
    }
    int ans = 0 ;
    while(!Q.empty()) {
        auto c = Q.top() ; Q.pop() ;
        if(c.ff < 3) break ;
        int diff = c.ff - 3 ;
        if(diff & 1) {
            cnt[c.ss] = 2 ;
        } else {
            cnt[c.ss] = 1 ;
        }
        ans += diff/2 + 1 ;
    }
    // all are 1 and 2 now
    int two = 0 , one = 0 ;
    rep(i,1,100000) {
        if(cnt[i] == 2)two++;
        else if(cnt[i]==1)one++ ;
    }
    trace(one,two) ;
    if(two%2==0) {
        ans += two/2 ; one += two ;
        cout << one ;
    }
    else {
        ans += two/2 ;
        one += (two/2)*2 ;
        cout << one ;
    }
    return 0;

}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    string n;
    cin >>  n;
    reverse(all(n));
    vector<vector<ll>> dp(n.size()+1, vector<ll>(2, inf));//min(dp[i][0], dp[i][1]) := 後ろからi桁まで考えるとき、使う紙幣の数
    dp[0][0] = 0;
    REP(i, n.size()){
        int x = n[i-1] - '0';
        dp[i][0] = min(dp[i-1][0], dp[i-1][1]+1)+x;
        dp[i][1] = min(dp[i-1][0]+10-x, dp[i-1][1]+10-(x+1));
    }
    cout << min(dp[n.size()][0],dp[n.size()][1]+1) << endl;
}

Measured memory_bytes: 55940
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#define Endl endl
#define mp make_pair
#define ll long long 
#define ull unsinged long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define quickcin ios_base::sync_with_stdio(false);
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
#define int ll
const int inf=1039074182;
const ll llinf=1LL*inf*inf;
using namespace std;
int n;
int c[200005];
vector <int> vec[200005];
int a[200005];
int res[200005];
int delta;

ll calc(int x)
{
	return 1LL*x*(x+1)/2;
}

void dfs(int x,int p)
{
	int actvx=a[c[x]]+delta;
	delta++;
	for(auto u:vec[x])
	{
		a[c[x]]=-delta;
		if(u==p) continue;
		dfs(u,x);
		int nowvx=a[c[x]]+delta;
		res[c[x]]+=calc(nowvx);
	}
	a[c[x]]=actvx-delta;
}

signed main()
{
//	freopen("input.txt","r",stdin);
	quickcin;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>c[i];
		c[i]--;
	}
	int x,y;
	for(int i=0;i<n-1;i++)
	{
		cin>>x>>y;
		x--;
		y--;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dfs(0,-1);
	for(int i=0;i<n;i++)
	{
		res[i]+=calc(a[i]+delta);
	}
	for(int i=0;i<n;i++)
	{
		res[i]=calc(n)-res[i];
	}
	for(int i=0;i<n;i++)
	{
		cout<<res[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 34776