akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let n: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let S: Vec<Vec<char>> = (0..n).map(|_| {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().chars().collect()
    }).collect();

    let mut dp = vec![vec![0; n]; 26];
    for i in 0..n {
        for &c in &S[i] {
            dp[c as usize - 'a' as usize][i] += 1;
        }
    }
    let x = (0..26).map(|i| *dp[i].iter().min().unwrap()).collect::<Vec<_>>();
    let mut ans = "".to_string();
    for i in 0..26 {
        for _ in 0..x[i] {
            ans += (('a' as u8 + i as u8) as char).to_string().as_str();
        }
    }

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

Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };



int S[20010];

int main() {
	int N;
	cin >> N;
	if (N == 3) {
		cout << 2 << " " << 5 << " " << 63 << endl;
		return 0;
	}
	if (N == 4) {
		cout << 2 << " " << 5 << " " << 20 << " " << 63 << endl;
		return 0;
	}
	else {
		S[0] = 2; S[1] = 3; S[2] = 9; S[3] = 6;
		int cnt =10;
		FOR(i, 4, N) {
			while (cnt % 2 != 0 && cnt % 3 != 0&&cnt%5!=0)cnt++;

			S[i] = cnt;
			cnt++;
		}
		ll sum = 0;
		REP(i, N)sum += S[i];
		FOR(i, 1, 30) {
			if (sum % 30 == i) {
				if (i % 2 == 1) {
					S[2] = 30000 - 60 - i + 9;
				}
				else {
					S[3] = 30000 - 60 - i + 6;
				}
			}
		}
		REP(i, N) {
			cout << S[i] << " ";
		}
	}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main(){
    int N, X;
    int ans = INF;
    cin >> N;
    vector<int> hito(N);
    rep(i, N) cin >> hito[i];
    for(int P=1; P<=100; ++P){
        int su = 0;
        for(int j=0; j<N; ++j){
            su += pow((hito[j]-P), 2);
        }
        ans = min(ans, su);
    }
    cout << ans << endl;
    return 0;
}


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

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)

typedef pair<int, int> Pair;
vector<vector<vector<Pair>>> succ;
vector<vector<int>> numPrev;


int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N; cin >> N;
  succ.resize(N+1, vector<vector<Pair>>(N+1));
  numPrev.resize(N+1, vector<int>(N+1));
  
  for (int i = 1; i <= N; i++) {
    int pr = -1;
    for (int j = 1; j <= N-1; j++) {
      int x; cin >> x;
      if (j > 1) {
	int p1, q1, p2, q2;
	if (i < pr) {
	  p1 = i; q1 = pr;
	}else {
	  p1 = pr; q1 = i;
	}
	if (i < x) {
	  p2 = i; q2 = x;
	}else {
	  p2 = x; q2 = i;
	}
	succ.at(p1).at(q1).emplace_back(p2, q2);
      }
      pr = x;
    }
  }

  for (int i = 1; i <= N; i++) {
    for (int j = i+1; j <= N; j++) {
      for (Pair p : succ.at(i).at(j)) {
	numPrev.at(p.first).at(p.second) += 1;
      }
    }
  }

  int days = 0;
  int done = 0;
  vector<Pair> top;
  for (int i = 1; i <= N; i++) {
    for (int j = i+1; j <= N; j++) {
      if (numPrev.at(i).at(j) == 0) top.emplace_back(i, j);
    }
  }

  while (top.size() > 0) {
    days += 1;
    done += top.size();
    vector<Pair> nextTop;
    for (Pair p : top) {
      for (Pair q : succ.at(p.first).at(p.second)) {
	numPrev.at(q.first).at(q.second) -= 1;
	if (numPrev.at(q.first).at(q.second) == 0) {
	  nextTop.emplace_back(q.first, q.second);
	}
      }
    }
    top = nextTop;
  }

  if (done < N * (N-1) / 2)  days = -1;
  
  cout << days << endl;

  return 0;
}



Measured memory_bytes: 43392
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxN=1e5+5;
int n;
char s[maxN];
void dfs(int x,int y){
    if(y==n)return ;
    if(s[y]=='1'){
        printf("%d %d\n",x,y+1);
        dfs(y+1,y+1);
    }
    else{
        printf("%d %d\n",x,y+1);
        dfs(x,y+1);
    }
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<n;i++){
        if(s[i]!=s[n-i]){
            cout<<"-1";
            return 0;
        }
    }
    if(s[1]!='1'||s[n]=='1'){
        cout<<"-1";
        return 0;
    }
    printf("1 2\n");
    dfs(1,2);
    return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>
int main(){
  int a[3],i,j;
  scanf("%d %d %d",&a[0],&a[1],&a[2]);
  for(i=0;i<2;i++){
    for(j=0;j<2-i;j++){
      if(a[j]>a[j+1]){
	int temp=a[j];
	a[j]=a[j+1];
	a[j+1]=temp;
      }
    }
  }
  printf("%d %d %d\n",a[0],a[1],a[2]);
  return 0;
}

Measured memory_bytes: 596
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int aa = (b - a);
        int bb = (c - b);
        if(aa == bb) System.out.println("YES");
        else System.out.println("NO");
    }
}


Measured memory_bytes: 35660
#include<iostream>
#include <malloc.h>
#include <vector>
#include<queue>
#include <algorithm>
#include<set>

using namespace std;


int main(){
  int n;
  cin >> n;
  set<int> s;
  int a;
  for(int i=0;i<n;i++) {
    cin >> a;
    s.insert(a);
  }
  cout << s.size() << endl;
  return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100010
#define INF 10000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000000;
const int MOD = 1000000007;
int main(){
    int n,l;
    cin>>n>>l;
    int ans=l*n+n*(n+1)/2-n;
    if(l<=0){
        ans-=min(0,l+n-1);
    }else{
        ans-=l;
    }
    OUT(ans);
	return 0;
}

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

vector < vector < int > > g;
vector < int > add, ans;

void dfs (int u, int p, int d) {
	ans[u] = d + add[u];
	for (int v: g[u]) {
		if (v != p)
			dfs(v, u, ans[u]);
	}
}

signed main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, q;
	cin >> n >> q;
	g.resize(n + 1);
	add.assign(n + 1, 0);
	ans.assign(n + 1, 0);
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 0; i < q; ++i) {
		int u, d;
		cin >> u >> d;
		add[u] += d;
	}
	dfs(1, -1, 0);
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << ' ';
	cout << '\n';
}


Measured memory_bytes: 24320
D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))

#得点の大きい順に並び替えておく
l = l[::-1]

ans = float("inf")
for i in range(2**D):
    total = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            total += 100*(D-j)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            #break

print(ans)

Measured memory_bytes: 43376
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include <sstream>
#include<iomanip>
#include <ctype.h>

//#include<bits/stdc++.h>





using namespace std;
int main() {


	int a, b;
	cin >> a >> b;
	if (a > b)swap(a, b);
	for (int i = a + 1; i <= b - 1; i++) {
		if (i - a == b - i) {
			cout << i << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;

	return 0;
}


Measured memory_bytes: 256
function main(arg) {
	var arg = arg.split("\n")
	var tmp = arg.shift()
	var N = Number(tmp.split(" ")[0])
	var M = Number(tmp.split(" ")[1])

	var A = []

	var result = new Array(M + 1).fill(0)

	for (var i = 0; i < arg.length; i++) {
		var tmp = arg[i].split(" ")
		tmp.shift()
		// A.push()
		var row = tmp.map(Number)
		for (var j = 0; j < row.length; j++) {
			var index = row[j]
			result[index]++
		}
	}

	var count = 0

	for (var i = 0; i < result.length; i++) {
		if (result[i] === N) {
			count++
		}
	}
	// console.log(result)
	console.log(count)

}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 21064
def bingo():    
    A=[]
    for i in range(3):
        A.extend(list(map(int, input().split())))
    N = int(input())
    n=[]
    while N>0:
        inp = int(input())
        if inp in A:
            n.append(inp)
        N-=1
    A = [A[:3],A[3:6],A[6:9], [A[0], A[4], A[8]], [A[2], A[4], A[6]], [A[0], A[3], A[6]], [A[1], A[4], A[7]], [A[2], A[5], A[8]]]
    for ele in A:
        if ele[0] in n and ele[1]in n and ele[2]in n:
            return 'Yes'
    return 'No'
print(bingo())

Measured memory_bytes: 3064
N=input()
if N[-1]=="2" or N[-1]=="4" or N[-1]=="5" or N[-1]=="7" or N[-1]=="9":
  print("hon")
elif N[-1]=="0" or N[-1]=="1" or N[-1]=="6" or N[-1]=="8":
  print("pon")
elif N[-1]=="3":
  print("bon")

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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;

template <typename T> T gcd(T a, T b) {
    if (b == 0)
        return a;

    return gcd(b, a % b);
}

template <typename T> T lcm(T a, T b) {
    return (a * b) / gcd(a, b);
}

void solve() {
    ll n, m, x;
    cin >> n >> m >> x;

    ll c[n], a[n][m];
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    ll sum_c, t[m], min_c = 1e9;
    bool possible;
    for (ll bit = 0; bit < (1<<n); bit++) {
        sum_c = 0;
        bzero(t, sizeof(t));
        possible = true;
        for (ll i = 0; i < n; i++) {
            if (bit & (1<<i)) {
                sum_c += c[i];
                for (ll j = 0; j < m; j++) {
                    t[j] += a[i][j];
                }
            }
        }

        for (ll i = 0; i < m; i++) {
            if (t[i] < x) {
                possible = false;
                break;
            }
        }

        if (possible) {
            min_c = min(min_c, sum_c);
        }
    }

    cout << (min_c < 1e9 ? min_c : -1) << endl;
}

int main() {
    solve();

    return 0;
}


Measured memory_bytes: 3640
#!/usr/bin/env python3


def solve(a, b, k):
    d1 = min(a, k)
    a -= d1
    k -= d1
    d2 = min(b, k)
    b -= d2
    k -= d2
    return a, b


def main():
    a, b, k = (int(z) for z in input().split())
    res = solve(a, b, k)
    print(*res)


if __name__ == "__main__":
    main()


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

int main() {
    int H, W;
    cin >> H >> W;
    vector <string> C(H);
    for (int i=0; i<H; i++) {
        cin >> C.at(i);
    }
    for (string c : C) {
        cout << c+"\n"+c+"\n";
    }
}

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

int a[100001],b[100001];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    long long ans=0,now=0;
    for (int i=1;i<=n;i++)
    {
        bool flag=0;
        for (int j=0;j<30;j++)
            if (!(k&(1<<j))&&a[i]&(1<<j))
            {
                flag=1;
                break;
            }
        if (!flag) now+=b[i];
    }
    ans=max(ans,now);
    for (int d=1;d<30;d++)
        if (k&(1<<d))
        {
            now=0;
            for (int i=1;i<=n;i++)
            {
                bool flag=0;
                for (int j=0;j<30;j++)
                    if (((j==d)||(j>d&&!(k&(1<<j))))&&a[i]&(1<<j))
                    {
                        flag=1;
                        break;
                    }
                if (!flag) now+=b[i];
            }
            ans=max(ans,now);
        }
    cout<<ans;
	return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll n;
  cin >> n;
  vec a(n);
  for(ll i=0;i<n;i++) cin >> a[i];
  sort(a.begin(),a.end());
  ll mx=a[n-1];
  vec cnt(mx+1);
  for(ll i=0;i<n;i++) {
    cnt[a[i]]++;
  }
  ll f=1;
  for(ll i=0;i<=mx;i++) {
    if(cnt[i]&&i<mx/2) f=0;
    if(mx%2&&i==(mx+1)/2&&cnt[i]!=2) f=0;
    if(mx%2==0&&i==mx/2&&cnt[i]!=1) f=0;
    if(i>mx/2&&!cnt[i]) f=0;
  }
  if(f) cout << "Possible" << endl;
  else cout << "Impossible" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>

#define pb push_back
#define mp make_pair

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef long long ll;

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

  int f[26] = {0};
  for (char c : s) {
    f[c-'a']++;
  }

  int res = -1;
  for (int i = 0; i < 26; ++i) {
    if (f[i] == 0) {
      res = i;
      break;
    }
  }

  if (res == -1) {
    cout << "None";
  } else {
    cout << (char)('a'+res) << endl;
  }

  cout << endl;
  return 0;
}


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

vector<bool> good;
vector<bool> seen;
vector<int> H;

void dfs(const vector<vector<int>> &G, int v){
    if (seen[v]) return;
    seen[v] = true;
    for (auto next_v : G[v]){
        if (H[v] <= H[next_v]){
            good[v] = false;
        }
        if (seen[next_v]) continue;
        dfs(G, next_v);
    }
}

int main(){
    int N, M;
    cin >> N >> M;
    for (int i=0; i<N; i++){
        int h;
        cin >> h;
        H.push_back(h);
    }

    vector<vector<int>> road(N);
    for (int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        road[a].push_back(b);
        road[b].push_back(a);
    }
    good.assign(N, true);
    seen.assign(N, false);
    for (int i=0; i<N; i++){
        dfs(road, i);
    }
    int ans = 0;
    for (int i=0; i<N; i++){
        if (good[i]){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
        #define eprintf(...) 42
#endif

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

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

  vi a(n);
  rep(i, n) cin >> a[i];

  vl s(n+1), se(n+1);
  rep(i, n){
    s[i+1] = s[i] + a[i];
    se[i+1] = se[i];
    if(i%2 == 0) se[i+1] += a[i];
  }

  while(q--){
    int x; cin >> x;
    int i = upper_bound(all(a), x) - a.begin(); 
    int l = i-1, r = n;

    // 全部交互にとる
    if(l >= n-1){
      if(n%2){
        cout << se[n] << endl;
      }else{
        cout << s[n]-se[n] << endl;
      }
      continue;
    }

    // (交互)(青木)(高橋)
    while(r-l > 1){
      int m = (l+r)/2;
      int d = a[m] - x;
      int j = lower_bound(all(a), x-d) - a.begin();
      int cnt = m - j + 1;
      if(n-cnt <= m) r = m;
      else l = m;
    }

    l += 1;
    int cnt = n-l;
    if(n%2){
      cout << (s[n]-s[l]) + se[max(l-cnt, 0)] << endl;
    }else{
      cout << (s[n]-s[l]) + (s[max(l-cnt, 0)]-se[max(l-cnt, 0)]) << endl;
    }
  }

/*
  rep(i, n+1){
    cout << s[i] << " ";
  }
  cout << endl;
  rep(i, n+1){
    cout << se[i] << " ";
  }
  cout << endl;
  */

  return 0;
}


Measured memory_bytes: 3712
n = int(input())
ans = 0

for i in range(1, n+1):
    ans += i * (n-i+1)
for _ in range(n-1):
    u, v = map(int, input().split())
    if u > v:
        u, v = v, u
    ans -= u*(n-v+1)
print(ans)

Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    int N;
    cin >> N;
    vector<int> dp(100010, INF);
    dp.at(0) = 0;
    for(int i = 0; i <= N; i++){
        for(int c6 = 1; i + c6 <= N; c6 *= 6){
            dp.at(i + c6) = min(dp.at(i + c6), dp.at(i) + 1);
        }
        for(int c9 = 1; i + c9 <= N; c9 *= 9){
            dp.at(i + c9) = min(dp.at(i + c9), dp.at(i) + 1);
        }
    }

    cout << dp.at(N) << endl;
}

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

using namespace std;

typedef vector<int> vi;

const int maxn = 2e5 + 2;
const int mod = 1e9 + 7;


int add(int a, int b)
{
  return a + b >= mod ? a + b - mod : a + b;
}

int f[maxn], a[maxn], n, g[maxn];

int main()
{
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i];

  n = unique(a, a + n + 1) - a;

  f[0] = 1;
  for (int i = 1; i < n; ++i)
    {
      f[i] = add(f[i - 1], g[a[i]]);
      g[a[i]] = add(g[a[i]], f[i - 1]);
     }

  cout << f[n - 1];
}







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

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

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

bitset<100010> A[62];
int v[62];

int gauss_elimination(int n, int m){
    int r = 0;
    REP(j,m){
        FOR(i,r,n-1){
            if (A[i][j]){
                swap(A[r], A[i]);
                swap(v[r], v[i]);
                break;
            }
        }
        if (A[r][j] == 0) continue;
        FOR(i,r+1,n-1){
            int k = A[i][j];
            if (k) A[i] ^= A[r];
            if (k) v[i] ^= v[r];
            // cout << "here" << endl;
            // REP(i,n){
            //     REP(j,m) cout << A[i][j] << " ";
            //     cout << endl;
            // }
        }
        r++;
        if (r == n) break;
    }
    return r;
}

int main() {
    int n;
    cin >> n;
    VL a(n);
    ll x = 0;
    REP(i,n){
        a[i] = lin();
        x ^= a[i];
    }
    int m = 62;
    ll y = 0;
    REP(bb,m){
        int b = m - bb - 1;
        bool f = true;
        int d = 0;
        FOR(c,b,m-1){
            if (c != b && ((y >> c) & 1) == 0) continue;
            int cnt = 0;
            REP(i,n){
                A[d][i] = ((a[i] >> c) & 1);
                cnt += A[d][i];
            }
            if (cnt % 2){
                f = false;
            }
            if (!f) break;
            v[d] = 1;
            d++;
        }
        if (!f) continue;
        // cout << endl;
        // REP(i,A.size()){
        //     for (int x : A[i]) cout << x;
        //     cout << endl;
        // }
        int r = gauss_elimination(d, n);
        int s = 0;
        REP(i,d) if (v[i]) s = i + 1;
        // cout << b << " " << r << " " << s << " " << f << endl;
        if (f && r >= s){
            y |= (1LL << b);
        }
    }
    cout << x + 2 * y << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

typedef pair<char, int> card;

bool ShowTwiceOrMore(vector<card>& v) {
    vector<int> counter = vector<int>(v.size() + 1, 0);
    for (int i = 0; i < v.size(); ++i) {
        if (++counter[v[i].second] >= 2) {
            return true;
        }
    }
    return false;
}

vector<string> GetMultString(vector<card>& v) {
    vector<string> result = vector<string>(10, "");
    for (int i = 0; i < v.size(); ++i) {
        result[v[i].second] += v[i].first;
    }

    return result;
}

bool isStable(vector<card>& origin, vector<card>& handled) {
//    if (!ShowTwiceOrMore(origin)) {return true;}
    if (GetMultString(origin) == GetMultString(handled)) {
        return true;
    } else {
        return false;
    }
}

void PrintCard(card& c) {
    cout << c.first << c.second;
}

void PrintVector(vector<card>& v) {
    for (int i = 0; i < v.size(); ++i) {
        PrintCard(v[i]);
        if (i + 1 != v.size()) {
            cout << " ";
        } else {
            cout << endl;
        }
    }
}

void Swap(int& a, int& b) {
    if (a != b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
}

void Swap(card& a, card& b) {
    card tmp = b;
    b = a;
    a = tmp;
}

vector<card> BubbleSort(vector<card> v) {
    for (int i = 0; i < v.size(); ++i) {
        for (int j = v.size() - 1; j > i; --j) {
            if (v[j].second < v[j - 1].second) {
                Swap(v[j], v[j - 1]);
            }
        }
    }

    return v;
}

vector<card> SelectionSort(vector<card> v) {
    int mini;
    for (int i = 0; i < v.size(); ++i) {
        mini = i;
        for (int j = i + 1; j < v.size(); ++j) {
            if (v[j].second < v[mini].second)
                mini = j;
        }
        Swap(v[mini], v[i]);
    }

    return v;
}

int main() {
//    freopen("E:/in.txt", "r", stdin);

    int N;
    int tmpI;
    char tmpC;
    card tmp;
    vector<card> v,v1,v2;

    cin >> N;

    for (int i = 0; i < N; ++i) {
        cin >> tmpC >> tmpI;
        tmp = make_pair(tmpC, tmpI);
        v.push_back(tmp);
    }

    v1 = BubbleSort(v);
    PrintVector(v1);
    if (isStable(v, v1)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }
    v2 = SelectionSort(v);
    PrintVector(v2);
    if (isStable(v, v2)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }
}



Measured memory_bytes: 3216
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;

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

    map<char,int> mp;
    for(char c = 'a'; c <= 'z';c++) mp[c]++;

    if(S.size() == 26){
        int i = 25;
        while(S[i] < S[i-1] && i > 0) i--;
        if(i == 0) S = "-1";
        else {
            char s = '~';
            for(int j=i;j<26;j++) if(S[i-1] < S[j]) s = min(s,S[j]);
            S[i-1] = s;
            S = S.substr(0,i);
        }
    }
    else {
        for(char c : S) mp.erase(c);
        auto itr = mp.begin();
        S += itr->first;
    }

    cout << S << endl;
}



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

// 1 つの証言を表す構造体
using pint = pair<int,int>; // 「人」と「0 or 1」

// 入力
int N;
vector<vector<pint>> v;

// 整数 bit に対応する「決め打ち」が整合しているかを判定
bool judge(int bit) {
    
    // i 人目の証言を検証する
    for (int i = 0; i < N; ++i) {
        
        // i 人目が「不親切」だったら、証言はすべて無意味
        if ( !(bit & (1 << i)) ) continue;

        // それぞれ確認
        for (pint xy : v[i]) {
            int x = xy.first; // x が
            int y = xy.second; // y = 1: 正直、y = 0: 不親切

            // y = 1 なのに「不親切」だったらダメ
            if (y == 1 && !(bit & (1 << x))) return false;

            // y = 0 なのに「正直者」だったらダメ
            if (y == 0 && (bit & (1 << x))) return false;
        }
    }
    return true;
}


int main() {
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i) {
        int A; cin >> A;
        v[i].resize(A);
        for (int j = 0; j < A; ++j) {
            cin >> v[i][j].first >> v[i][j].second;
            --v[i][j].first; // 0-indexed に
        }
    }

    int res = 0;
    for (int bit = 0; bit < (1 << N); ++bit) {
        
        // 矛盾 check
        if (judge(bit)) {
            
            // bit に含まれる人数を数える
            int count = 0;
            for (int i = 0; i < N; ++i) {
                if (bit & (1 << i)) ++count;
            }
            res = max(res, count);
        }
    }

    cout << res << endl;
}

Measured memory_bytes: 256
def solve():
    N = int(input())
    S = input()

    ans = 0
    for i in range(1000):
        num = str(i).zfill(3)
        idx = 0
        for digit in S:
            if digit == num[idx]:
                idx += 1
            if idx == 3:
                ans += 1
                break
    
    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 40796
import java.util.Scanner;

class Main
{
    public static void main(String[] args)
    {     
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = 3600;
        int c = 60;
        
        System.out.print( a / b );
        System.out.print( ":" );
        System.out.print( ( a % b ) / c );
        System.out.print( ":" );
        System.out.println( ( a % b ) % c );
        return;
}
}


Measured memory_bytes: 26332
import java.io.*;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        String s = fs.next();
        for( int i = 0 ; i < s.length() ; i++ ){
            System.out.print("x");
        }
    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte()) {
                return buffer[ptr++];
            } else {
                return -1;
            }
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
                ptr++;
            }
            return hasNextByte();
        }

        public String next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public long nextLong() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }

        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
                throw new NumberFormatException();
            }
            return (int) nl;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}


Measured memory_bytes: 22868
#include<iostream>
#include<algorithm>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
long long inf=100000000000000;
int main(){
  int n;
  long long a[100005];
  cin >> n;
  int i;
  for(i=0;i<n;i++){
    cin >> a[i];
  }
  long long dp[100005];
  for(i=0;i<n;i++){
    dp[i]=inf;
  }
  dp[0]=0;
  for(i=1;i<n;i++){
    chmin(dp[i],dp[i-1]+abs(a[i]-a[i-1])); // 一個飛ばしたとき //
    if(i>=2){ // iが1の時しないようにする //
    chmin(dp[i],dp[i-2]+abs(a[i]-a[i-2])); // 二個飛ばしたとき //
    }
  }
  cout << dp[n-1]; // n-1個目のdpが最小値 //
  return(0);
}

Measured memory_bytes: 1792
import java.util.*;
public class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int H = sc.nextInt();
      int W = sc.nextInt();
      int h = sc.nextInt();
      int w = sc.nextInt();
      System.out.println(H*W - W*h - H*w + h*w);
    }
}

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;

#define mp make_pair
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

void setIO(string name = ""){
    freopen((name+".in").c_str(), "r", stdin); 
    freopen((name+".out").c_str(), "w", stdout);
}

int main(){
 	ios_base::sync_with_stdio(0); cin.tie(0); 
	// setIO();
	ll n; cin >> n;
	if(n>=30) cout << "Yes" << "\n";
	else cout << "No" << "\n";
    
}





Measured memory_bytes: 3652
#include <iostream>
using namespace std;
int main(void){
    int n, a[10000]={};
    long int sum;
    
    while(true){
        sum=0;
        cin >> n;
        if(n == 0) break;
        for(int i=0; i<n; i++){
            cin >> a[i];
            sum += a[i];
        }
        double ave = sum/n;
        int count = 0;
        for(int i=0; i<n; i++){
            if(ave >= a[i]) count++;
        }
        cout << count << endl;
    }
    return 0;
}



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

int main() {
  int A,B,C;
  cin >> A >> B >> C;
  
  int A1 = A*C-B;
  cout << A1 << endl;
  int A2 = A*A1-B;
  cout << A2 << endl;
  int A3 = A*A2-B;
  cout << A3 << endl;
  int A4 = A*A3-B;
  cout << A4 << endl;
  int A5 = A*A4-B;
  cout << A5 << endl;
  int A6 = A*A5-B;
  cout << A6 << endl;
  int A7 = A*A6-B;
  cout << A7 << endl;
  int A8 = A*A7-B;
  cout << A8 << endl;
  int A9 = A*A8-B;
  cout << A9 << endl;
  int A10 = A*A9-B;
  cout << A10 << endl;
  
  
  
}

Measured memory_bytes: 256
N,M,C=map(int,input().split())

B=list(map(int,input().split()))
count=0
for i in range(0,N):
  total=C
  A=list(map(int,input().split()))
  for j in range(0,M):
    total+=A[j]*B[j]
  if total>0:
    count+=1
    
print(str(count))

Measured memory_bytes: 3064
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;


long long int N, M, K, H, W, L, R;

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

	cin >> N;
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < N - 1; i++) {
		int box[1000] = {};
		int bag = 0;
		for (int j = 0; j <= i; j++) {
			box[s[j]] = 1;
		}
		for (int j = i + 1; j < N; j++) {
			box[s[j]] += 2;
		}
		for (auto j : box) {
			if (j > 2 && j % 2) bag++;
		}
		ans = max(ans, bag);
	}
	cout << ans << endl;
	return 0;
}


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

int main() {
  int n, a;
  cin >> n >> a;
  int x = n - (n / 500) * 500;
  if (x < a || x == a){
    cout << "Yes" << endl;
  }
  if (x > a){
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()
int main(){
    int k;cin>>k;
    ll ans=0;
    if(k%2==0){
        ans=k/2*k/2;
    }else{
        ans=k/2*(k/2+1);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3644
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  string s;
  cin >> s;
  int N = s.size();

  int cnt = 0;
  for(int i=0;i<N-1;i++){
    if(s[i]!=s[i+1]) cnt++;
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
int main()
{
    // 文字列の入力
    int a;
	cin >> a;
	
	a = a + a * a + a * a* a;
	
	printf("%d\n", a);
	
    return 0;
}

Measured memory_bytes: 3692
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
char s[1005][1005];

int main() {
	int h, w, a, b;
	scanf("%d %d %d %d", &h, &w, &a, &b);
	for (int i = 1; i <= b; i++) {
		for (int j = 1; j <= a; j++)
			s[i][j] = '1';
		for (int j = a+1; j <= w; j++)
			s[i][j] = '0';
	}
	for (int i = b+1; i <= h; i++) {
		for (int j = 1; j <= a; j++)
			s[i][j] = '0';
		for (int j = a+1; j <= w; j++)
			s[i][j] = '1';
	}
	for (int i = 1; i <= h; i++)
		printf("%s\n", s[i]+1);
	return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back
#define sz(x) int(x.size())

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    else return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};

class Factrial{
public:
  vl Fac;
  Factrial(int MAX){
    Fac = vl(MAX+1);
    rep(i,MAX) {
      if(i == 0) Fac[i+1] = 1;
      else Fac[i+1] = ((i+1)*Fac[i])%MOD;
    }
  }
};

int main(){
  int n,r; cin >> n >> r;
  cout << r + 100*max(10-n,0) << endl;
}

Measured memory_bytes: 256
/* CM one day */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <algorithm>
#include <unordered_map>
#define int                long long
#define pb                 push_back
#define pi                 pair<int,int>
#define vi                 vector<int>
#define all(v)             v.begin(),v.end()
#define MOD                1000000007
#define F                  first
#define S                  second
#define FOR(i,r)           for(int i=0;i<r;i++)
#define REP(i,l,r)         for(int i=l;i<r;i++)
#define RER(i,l,r)         for(int i=l;i>=r;i--)
#define print(v)           for(auto i : v)cout << i << ' ';
#define FASTIO             ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mem(arr,k)         memset(arr,k,sizeof(arr));
#define pii                acos(-1.0)
#define PI                 3.1415926535897932385
#define Sin(a)             sin((pi*a)/180)
#define test()             int x;cin >> x;while(x--)
using namespace std;
const int inf = (int)1e17;
const int N = (int)1e5+5;
int32_t main(){

	FASTIO;
	int n;
	cin >> n;
	string str;
	cin >> str;
	vector<int>g[3];
	REP(i,0,n){
		if(str[i]=='R')
			g[0].pb(i);
		else if(str[i]=='G')
			g[1].pb(i);
		else
			g[2].pb(i);
	}
	int ans = 0;
	REP(i,0,n){
		REP(j,i+1,n){
			if(str[i]==str[j])
				continue;
			int op;
			set<char>tm;
			tm.insert('R');
			tm.insert('G');
			tm.insert('B');
			tm.erase(str[i]);
			tm.erase(str[j]);
			char ch = *tm.begin();
			if(ch == 'R')
				op = 0;
			else if(ch == 'G')
				op = 1;
			else
				op = 2;
			//if(i)
			auto itr = upper_bound(all(g[op]),j);
			if(itr == g[2].end())
				continue;
			int left = g[op].size()-(itr - g[op].begin());
			if(binary_search(all(g[op]),2*j-i)){
				left--;
			}
			ans += left;
		}
	}
	cout << ans << endl;
    return 0;

}

Measured memory_bytes: 3696
#include<iostream>
#define M 100000007
using namespace std;

int r,c;
int dp[2][10][3][100000]; //dp[r][c][左からn本][上からn本]
int g[20][20];
char z;
int po3[21];

int main(){
  cin >> r >> c;

  po3[0] = 1;
  for(int i=0;i<c;i++)po3[i+1] = po3[i]*3;

  for(int i=0;i<r;i++)
    for(int j=0;j<c;j++){
      cin >> z;
      if(z=='.')g[i][j] = 0;
      else g[i][j] = z-'0';
    }

  for(int i=0;i<c;i++)
    for(int j=0;j<3;j++)
      for(int k=0;k<po3[c];k++)dp[0][i][j][k] = 0;
  dp[0][0][0][0] = 1;

  for(int i=0;i<r;i++){
    int id = i&1, nxt = 1-id;

    for(int j=0;j<c;j++)
      for(int k=0;k<3;k++)
	for(int l=0;l<po3[c];l++)dp[nxt][j][k][l] = 0;

    for(int j=0;j<c-1;j++){
      if(!g[i][j]){
	for(int k=0;k<3;k++){
	  for(int l=0;l<po3[c];l++){
	    int m = (l/po3[j])%3;
	    if(m && k)continue;
	    dp[id][j+1][k][l] += dp[id][j][k][l];
	    dp[id][j+1][k][l] %= M;
	  }
	}
      }else{
	for(int k=0;k<3;k++){
	  for(int l=0;l<po3[c];l++){
	    int m = (l/po3[j])%3;
	    int n = g[i][j] - m - k;
	    
	    if(n<0 || n>4)continue;
	    for(int x=0;x<3;x++){
	      if(n-x<0 || n-x>2)continue;
	      int w = l - m*po3[j] + (n-x)*po3[j];
	      dp[id][j+1][x][w] += dp[id][j][k][l];
	      dp[id][j+1][x][w] %= M;
	    }
	  }
	}
      }
    }

    if(!g[i][c-1]){
      for(int l=0;l<po3[c];l++){
	dp[nxt][0][0][l] += dp[id][c-1][0][l];
	dp[nxt][0][0][l] %= M;
      }
    }else{
      for(int k=0;k<3;k++){
	for(int l=0;l<po3[c];l++){
	  int m = (l/po3[c-1])%3;
	  int n = g[i][c-1] - m - k;
	  if(n<0 || n>2)continue;
	  int w = l - m*po3[c-1] + n*po3[c-1];
	  dp[nxt][0][0][w] += dp[id][c-1][k][l];
	  dp[nxt][0][0][w] %= M;
	}
      }
    }
  }

  cout << dp[r&1][0][0][0] << endl;
}

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

N=int(input())
E=[tuple(map(int,input().split())) for i in range(N-1)]

ELIST=[[] for i in range(N+1)]
EDEG=[0]*(N+1)

for x,y in E:
    ELIST[x].append(y)
    ELIST[y].append(x)

    EDEG[x]+=1
    EDEG[y]+=1

from collections import deque
Q=deque()
Q.append(1)

H=[-1]*(N+1)
H[1]=0

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if H[to]==-1:
            H[to]=H[x]+1
            Q.append(to)

MAXH=max(H)

Q=deque()
xi=H.index(MAXH)
Q.append(xi)

H=[-1]*(N+1)
H[xi]=0

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if H[to]==-1:
            H[to]=H[x]+1
            Q.append(to)


MAXH=max(H)

Q=deque()
xi=H.index(MAXH)
Q.append(xi)

H2=[-1]*(N+1)
H2[xi]=0

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if H2[to]==-1:
            H2[to]=H2[x]+1
            Q.append(to)

ANS1=(max(H)+2)//2
print(ANS1)

#print(H)
#print(H2)

if MAXH%2==1:
    Q=deque()
    USE=[0]*(N+1)

    for i in range(N+1):
        if (H[i]==MAXH//2 and H2[i]==MAXH//2+1) or (H[i]==MAXH//2+1 and H2[i]==MAXH//2):
            Q.append(i)
            USE[i]=1

    ANS2=1

    #print(Q)

    while Q:
        NQ=deque()
        score=1
        while Q:
            x=Q.pop()
            USE[x]=1
            score=max(score,len(ELIST[x])-1)

            for to in ELIST[x]:
                if USE[to]==1:
                    continue
                NQ.append(to)

        ANS2*=score
        Q=NQ
            
    print(ANS2*2)

else:
    Q=deque()

    for i in range(N+1):
        if H[i]==MAXH//2 and H2[i]==MAXH//2:
            Q.append(i)
            MID=i

    ANS2=len(ELIST[MID])
    USE=[0]*(N+1)

    #print(Q)

    while Q:
        NQ=deque()
        score=1
        while Q:
            x=Q.pop()
            USE[x]=1
            if x!=MID:
                score=max(score,len(ELIST[x])-1)

            for to in ELIST[x]:
                if USE[to]==1:
                    continue
                NQ.append(to)

        ANS2*=score
        Q=NQ
            
    #print(ANS2)

    Q=deque()
    for j in ELIST[MID]:
        Q.append(j)
        Q.append(MID)
        USE=[0]*(N+1)
        USE[j]=1
        USE[MID]=1

        score2=1

        while Q:
            NQ=deque()
            score=1
            while Q:
                x=Q.pop()
                USE[x]=1
                #if x!=MID and x!=j:
                score=max(score,len(ELIST[x])-1)

                for to in ELIST[x]:
                    if USE[to]==1:
                        continue
                    NQ.append(to)

                #print("!",x,score)

            score2*=score
            Q=NQ

        #print(j,score2)

        ANS2=min(ANS2,score2*2)

    print(ANS2)


Measured memory_bytes: 3572
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<iomanip>

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

using namespace std;

#define debug(x) cout<<(#x)<<"="<<(x)<<", ";
#define debug1(x) debug(x) cout<<'\n';
#define debug2(x1, x2) debug(x1) debug(x2) cout<<'\n';
#define debug3(x1, x2, x3) debug(x1) debug(x2) debug(x3) cout<<'\n';
#define debug4(x1, x2, x3, x4) debug(x1) debug(x2) debug(x3) debug(x4) cout<<'\n';
#define debug5(x1, x2, x3, x4, x5) debug(x1) debug(x2) debug(x3) debug(x4) debug(x5) cout<<'\n';

#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sort(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb(x) emplace_back(x);

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<int, int, lli> tiil;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;

int main(){
fast_io
string s; cin>>s;
if(s[0]=='9' or s[1]=='9') cout<<"Yes";
else cout<<"No";
return 0;
}

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

typedef long long ll;
 
int main(){
  int a, b;
  cin >> a >> b;
  int c = a * b;
  string ans;
  if(c%2==0) ans = "Even";
  else ans = "Odd";
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int K,N;
int main(){
  cin>>K>>N;
  vector<int> A(N),B(N);
  for(int i=0;i<N;i++)cin>>A[i];
  for(int i=0;i<N-1;i++)B[i]=A[i+1]-A[i];
  B[N-1]=A[0]+K-A[N-1];
  sort(B.begin(),B.end());
  reverse(B.begin(),B.end());
  cout<<K-B[0]<<endl;
}

Measured memory_bytes: 1792
"""
~~ Author : Bhaskar
~~ Dated : 31~05~2020
"""

import sys
from bisect import *
from math import floor,sqrt,ceil,factorial as F,gcd,pi,trunc
from itertools import chain,combinations,permutations,accumulate
from collections import Counter,defaultdict,OrderedDict,deque
from array import array
from decimal import Decimal
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)-1
mod = 1000000007
lcm = lambda a,b : (a*b)//gcd(a,b)
setbit = lambda x : bin(x)[2:].count("1")

def solve():
    x = list(map(str,sys.stdin.readline().split()))
    a = Decimal(x[0])
    b = Decimal(x[1])
    print(floor(a*b))

if __name__ == "__main__":
    try:
        sys.stdin = open("input.txt","r")
    except :
        pass
    solve()


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

Measured memory_bytes: 256