akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

class Problem0005
{
    static void Main(string[] args)
    {
        var inputPairs =
            GetInputLines()
            .Select(line => line.Split().Select(word => int.Parse(word)).ToArray());
        foreach (int[] pair in inputPairs)
        {
            int n1 = pair[0];
            int n2 = pair[1];
            int gcd = GetGCD(n1, n2);
            long lcm = (long)n1 * (long)n2 / gcd;
            Console.WriteLine(gcd.ToString() + " " + lcm.ToString());
        }
    }

    static int GetGCD(int n1, int n2)
    {
        int leastCommonFactor =
            Enumerable.Range(2, Math.Min(n1, n2) - 1)
            .FirstOrDefault(n => n1 % n == 0 && n2 % n == 0);
        if (leastCommonFactor != 0)
        {
            return leastCommonFactor * GetGCD(n1 / leastCommonFactor, n2 / leastCommonFactor);
        }
        else
        {
            return 1;
        }
    }

    static IEnumerable<string> GetInputLines()
    {
        string line;
        while (!string.IsNullOrEmpty(line = System.Console.ReadLine()))
        {
            yield return line;
        }
    }
}

Measured memory_bytes: 9592
def solve(c1_list, c2_list, c3_list):

    a1 = 0
    ans = "No"
    while a1 <= 100:
        b_list = [c - a1 for c in c1_list]

        a2 = len(set([c - b for c, b in zip(c2_list, b_list)]))
        a3 = len(set([c - b for c, b in zip(c3_list, b_list)]))

        if a2 == 1 and a3 == 1:
            ans = "Yes"
            break
        else:
            a1 += 1

    return ans

if __name__ == "__main__":
    c1_list = [int(i) for i in input().split()]
    c2_list = [int(i) for i in input().split()]
    c3_list = [int(i) for i in input().split()]
    print(solve(c1_list, c2_list, c3_list))


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

using namespace std;

void solve()
{
	int n, k;
	string s;
	cin >> n >> k >> s;
	n = s.size();
	int r = 0, cnt = k, flag = 1;
	while (r < n)
	{
		if (s[r] == '0')
		{
			if (flag == 1) cnt--;
			if (cnt == -1) break;
			flag = 0;
		}
		else
		{
			flag = 1;
		}
		r++;
	}
	while(r < n && s[r] == '1')
	{
		r++;
	}
	int ans = r, l = 0;
	//while(l < n && s[l] == '0') l++;
	//cout << l << ' ' << ans << endl;
	for (; l < n; l++)
	{
		if (l < r) ans = max(ans, r - l);
		while(l < n && s[l] == '1') l++;
		while(l < n && s[l] == '0') l++;
		while(r < n && s[r] == '0') r++;
		while(r < n && s[r] == '1') r++;
		if (l == r) r++;
		//cout << l << ' ' << r << endl;
	}
	if (l < r) ans = max(ans, r - l);

	reverse(s.begin(), s.end());

	r = 0, cnt = k, flag = 1;
	while (r < n)
	{
		if (s[r] == '0')
		{
			if (flag == 1) cnt--;
			if (cnt == -1) break;
			flag = 0;
		}
		else
		{
			flag = 1;
		}
		r++;
	}
	while(r < n && s[r] == '1')
	{
		r++;
	}
	ans = max(ans, r);
	l = 0;
	//while(l < n && s[l] == '0') l++;
	//cout << l << ' ' << ans << endl;
	for (; l < n; l++)
	{
		while(l < n && s[l] == '1') l++;
		while(l < n && s[l] == '0') l++;
		while(r < n && s[r] == '0') r++;
		while(r < n && s[r] == '1') r++;
		if (l < r) ans = max(ans, r - l);
		if (l == r) r++;
		//cout << l << ' ' << r << endl;
	}
	if (l < r) ans = max(ans, r - l);

	cout << ans << endl;
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
int a[100100];
int c[100100];
bool check(int x,int i)
{
    if(c[x]<a[i])
    {
        return 1;
    }
    else
    {
        return 0;
    }
    
}
int bs(int l, int r,int i)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid,i)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    int cnt=1;
    c[1] = a[1];
    for(int i=2;i<=n;i++)
    {
        int pos = bs(1,cnt,i);
        if(c[pos]<a[i])
        {
            c[pos] = a[i];
        }
        else
        {
            cnt++;
            c[cnt] = a[i];
        }
        
    }
    cout << cnt << endl;
    return 0;
}

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

int main()
{
	ll m,i,j,k,s=0,x=0,y=0,z,a,n,b,c,g,minn=INT_MIN;
cin>>n>>m;
if(n==m) cout<<"Yes";
else cout<<"No";
	
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




string S;
//---------------------------------------------------------------------------------------------------
int solve() {
    int N = S.length();
    int ans = 0;
    rep(i, 2, N - 1) if (i % 2 == 0) {
        string A = S.substr(0, i / 2);
        string B = S.substr(i / 2, i / 2);
        if (A == B) ans = max(ans, i);
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    cout << solve() << endl;
}

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

int n,k,m;
string s;

int main() {
  cin >> n;
  int a[n*3];
  rep(i,n*3) cin >> a[i];
  sort(a,a+n*3,greater<int>());
  ll ans=0;
  rep(i,n) ans+=a[2*i+1];
  cout << ans << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; ++i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)

const int MAX = 22;
const ll MOD = 1e9+7;
int N;
ll dp[1<<MAX];
ll A[MAX][MAX];

ll solve(int idx, int rest) {
  if (idx == N) return 1;
  if (dp[rest] >= 0) return dp[rest];

  ll ret = 0;
  REP (i, N) if (A[idx][i] && (rest>>i)&1)
    (ret += solve(idx+1, rest-(1<<i))) %= MOD;
  return dp[rest] = ret;
}

int main () {
  cin >> N;
  REP (i, N) REP (j, N) cin >> A[i][j];
  REP (i, 1<<MAX) dp[i] = -1;

  cout << solve(0, (1<<N)-1) << endl;
}

Measured memory_bytes: 33024
using System;
using System.Collections.Generic;
using System.Linq;

class F
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var h = read();
		int n = h[0], u = h[1], v = h[2];
		var rs = new int[n - 1].Select(_ => read()).ToArray();
		var map = rs.Concat(rs.Select(r => new[] { r[1], r[0] })).ToLookup(r => r[0], r => r[1]);

		var d = new int[n + 1];
		var branch = new bool[n + 1];
		var parents = new int[n + 1].Select(_ => new List<int>()).ToArray();
		var stack = new List<int>();
		Dfs(v, map, d, branch, parents, stack);

		var escape = 0;
		foreach (var x in Enumerable.Range(1, n).Where(i => !branch[i]).OrderBy(i => -d[i]))
		{
			if (x == u) { escape = x; break; }
			if (d[x] <= d[u]) continue;

			var t = x;
			while (d[t] > d[u])
				t = parents[t][(int)Math.Log(d[t] - d[u], 2)];
			if (t == u) { escape = x; break; }

			var ut = u;
			while (t != ut)
			{
				var k = 0;
				while (k < parents[t].Count && parents[t][k] != parents[ut][k]) k++;
				if (k > 0) k--;
				t = parents[t][k];
				ut = parents[ut][k];
			}
			if (d[u] - d[t] < d[t] - d[v]) { escape = x; break; }
		}
		Console.WriteLine(d[escape] - 1);
	}

	static int[] p2 = Enumerable.Range(0, 20).Select(i => (int)Math.Pow(2, i)).ToArray();

	static void Dfs(int p, ILookup<int, int> map, int[] d, bool[] branch, List<int>[] parents, List<int> stack)
	{
		d[p] = stack.Count;
		for (int i = 0; p2[i] <= stack.Count; i++)
			parents[p].Add(stack[stack.Count - p2[i]]);

		stack.Add(p);
		foreach (var np in map[p])
		{
			if (stack.Count >= 2 && np == stack[stack.Count - 2]) continue;
			branch[p] = true;
			Dfs(np, map, d, branch, parents, stack);
		}
		stack.RemoveAt(stack.Count - 1);
	}
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    string s;
    cin >> s;
    if(s == "ARC"){
        cout << "ABC" << endl;
    }else{
        cout << "ARC" << endl;
    }

    return 0;
}

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

int main(){
    char s[1000000];
    int n,m;
    while(cin>>n,n){
        cin>>m>>s;
        int ans = 0;
        for(int i=0;i<m-n*2;++i){
            int count=0;
            if(s[i]=='I'){
                for(int j=0;;++j){
                    if(s[i+2*j+1]!='O'||s[i+2*j+2]!='I') break;
                    ++count;
                }
                ans +=max(0,count-n+1);
                i += count*2;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 4068
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;

// 素集合データ構造
struct UnionFind {
  vector<int> par, sizes; // par:あるデータの親, sizes:あるデータが属する木のサイズ

  // コンストラクタ
  // データ一つ一つを木とし、親は自分自身に初期化する
  UnionFind(int n) : par(n), sizes(n, 1) {
    for (int i = 0; i < n; i++) par[i] = i;
  }

  // データxが属する木の根ノードを取得
  // 再帰的に根を調べる際に、調べた辺を根に直接繋ぎ直すことで効率化している（経路圧縮）
  int find(int x) {
    return (x == par[x] ? x : par[x] = find(par[x]));
  }

  // 2つのデータx, yが属する木をマージする
  void unite(int x, int y) {
    // それぞれのデータの根ノードを取得
    x = find(x);
    y = find(y);

    // x, yが同じ木に属するならマージしない
    if (x == y) return;

    // xの木がyの木より大きくなるようにする
    if (sizes[x] < sizes[y]) swap(x, y);

    // xがyの親になるようにマージする
    par[y] = x;
    sizes[x] += sizes[y];
  }

  // 2つのデータx, yが同じ木に属するかどうか
  bool same(int x, int y) {
    return (find(x) == find(y));
  }

  // データxの属する木のサイズを返す
  int size(int x) {
    return sizes[find(x)];
  }
};

// 頂点a, bを繋ぐコストcostの無向辺
struct Edge {
  int a, b, cost;

  // Edgeの比較はcostで行うことを定義している？
  bool operator<(const Edge &o) const {
    return cost < o.cost;
  }
};

// 頂点数と辺集合の組として定義したグラフ
struct Graph {
  int n; // 頂点数
  vector<Edge> es; // 辺集合
};

// クラスカル法で無向最小全域木を求め、コストの和を返す
int kruskal(Graph g) {
  // costの小さい辺から繫いでいくので、昇順にソートしておく
  sort(g.es.begin(), g.es.end());

  UnionFind uf(g.n);
  int min_cost = 0;
  for (int i = 0; i < g.es.size(); i++) {
    Edge e = g.es[i];
    // 辺を追加しても閉路ができないなら、辺を繋ぐ
    if (!uf.same(e.a, e.b)) {
      min_cost += e.cost;
      uf.unite(e.a, e.b);
    }
  }

  return min_cost;
}

int main() {
  int N;
  cin >> N;
  P x[N], y[N];
  for (int i = 0; i < N; i++) {
    scanf("%d %d", &x[i].first, &y[i].first);
    x[i].second = y[i].second = i;
  }

  // 最小全域木を求めるのに辺が多すぎるので、ソートして隣り合う頂点の辺のみを残す
  sort(x, x + N);
  sort(y, y + N);
  Graph g;
  g.n = N;
  Edge e;
  for (int i = 0; i < N - 1; i++) {
    e.a = x[i].second; e.b = x[i+1].second; e.cost = x[i+1].first - x[i].first;
    g.es.push_back(e);
    e.a = y[i].second; e.b = y[i+1].second; e.cost = y[i+1].first - y[i].first;
    g.es.push_back(e);
  }

  // クラスカル法
  cout << kruskal(g) << endl;
  return 0;
}


Measured memory_bytes: 7920
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int answer = 0;
    int[] array = new int[N + 1];
    for(int i = 1; i <= N; i++){
      array[i] = sc.nextInt();
    }
    for(int i = 1; i <= N; i++){
      if(i %2 == 1 && array[i] % 2 == 1){
        answer++;
      }
    }
    System.out.println(answer);
  }
}

Measured memory_bytes: 35776
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define scanl(x) scanf("%ld", &x)
#define scans(x) scanf("%s", x)

#define INF 100000000000
#define M 1000000007

#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

int main() {
	long N;
	long T[100001];
	long A[100001];
	int i;
	long m;
	long x[100001];
	long ans = 1;
	
	scanl(N);
	for(i=0;i<N;i++) {
		scanl(T[i]);
	}
	for(i=0;i<N;i++) {
		scanl(A[i]);
	}
	
	m = T[0];
	x[0] = T[0];
	for(i=1;i<N;i++) {
		if(m != T[i]) {
			x[i] = T[i];
			m = T[i];
			if(T[i] > A[i]) ans = 0;
		} else {
			x[i] = INF;
		}
	}
	m = A[N-1];
	x[N-1] = A[N-1];
	for(i=N-2;i>=0;i--) {
		if(m != A[i]) {
			x[i] = min(x[i], A[i]);
			m = A[i];
			if(A[i] > T[i]) ans = 0;
		}
	}
	
	for(i=0;i<N;i++) {
		if(x[i] == INF) {
			ans *= min(T[i], A[i]);
			ans %= M;
		}
	}
	
	if(T[N-1] != A[0]) ans = 0;
	printf("%ld\n", ans);
	
	return 0;
}

Measured memory_bytes: 2560
#include<iostream>
using namespace std;
int main()
{
	int S;
	cin >> S;
	int h = S / 3600;
	int x = S % 3600;
	int m = x / 60;
	int s = x % 60;
	cout << h << ":" << m << ":" << s << endl;


	return 0;

}

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

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const ll INF = 1LL << 60;

//Write From this Line

int main()
{
	ll h , w ;
	cin >>  h >> w ;
	//1行目は切り上げがいける
	if( h == 1 || w == 1 ){
		cout << 1 << endl;
		return 0 ;

	}
	ll gyo1 = (w + 2 - 1) / 2;
	ll gyo2 = (w ) / 2;
	ll re1 = (h + 2 - 1) / 2;
	ll re2 = (h) / 2;
	ll ans = gyo1 * re1 + gyo2 * re2 ;
	cout << ans << endl;
}


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

const int MOD = 1e+9 + 7;

int main() {
  int N, M, a;
  cin >> N >> M;
  vector<bool> broken(N + 1, false);
  rep(i, M) {
    cin >> a;
    broken[a] = true;
  }

  vector<int> dp(N + 1, 0);
  dp[0] = 1;
  dp[1] = broken[1] ? 0 : 1;
  for (int i = 2; i <= N; i++) {
    if (broken[i]) continue;
    dp[i] = dp[i - 1] + dp[i - 2];
    dp[i] %= MOD;
  }
  cout << dp[N] << endl;

  return 0;
}

Measured memory_bytes: 3796
#include<bits/stdc++.h>
    using namespace std;
    int main(){

    long long h,w; cin >> h >> w;

    if (h==1||w==1)
    {
      cout << 1;
    }
    else{
    cout << (h*w+1)/2<<"\n";
  }
    return 0;
  }


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

int main()
{
  int a,b,c,x = 0;
  cin >>a>>b>>c;
  int y = a;
  while(y <= c){
    x += b;
    y += a;
  }
  cout << x << endl;
  return 0;
}


Measured memory_bytes: 3612
#include<stdio.h>
int main()
{
    int N, M, DayOfWork = 0;

    scanf("%d %d", &N, &M);
    int A[M];
    
    for(int i = 0; i < M; i++)
    {
        scanf(" %d", &A[i]);
        DayOfWork += A[i];
    }
    printf("%d", (DayOfWork <= N)? (N - DayOfWork) : -1);
    
    return 0;
}

Measured memory_bytes: 1760
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.next());  
    int[] A = new int[N];
    for(int i = 0; i<N; i++){
        int index = Integer.parseInt(sc.next()) - 1;
        A[index] = i + 1;
    } 
    for(int i = 0; i<N; i++){
        System.out.print(A[i] + " ");
    }

  }
}



Measured memory_bytes: 48340
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

int main()
{
    long long N,K;
    long long cnt;
    bool update = true;

    cin >> N >> K;

    long long minimum;

    N = N % K;

    while(update){
        update = false;
        minimum = N;
        N = min(N,abs(N-K));
        if(minimum > N){
            update = true;
        }
    }

    cout << N;

  
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    ll a[n + 1];
    for (int i = 0; i < n; i++) cin >> a[i];
    a[n] = a[0];
    vector<ll> ans(n + 1, 0);
    ll f = 0;
    for (int i = 0; i < n; i++) f = a[i] - f;
    ans[0] = f / 2;
    for (int i = 0; i < n; i++) {
        ans[i + 1] = a[i] - ans[i];
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] * 2 << " \n"[i == n - 1];
    }
    return 0;
}

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


signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
 
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll ans=0;
    bool end=false;
    while(!end){
        end=true;
        ll cnt=0;
        for(int i=0;i<n;i++){
            cnt += a[i]/n;
        }
        for(int i=0;i<n;i++){
            ll t=a[i]/n;
            a[i] -= t*n - cnt + a[i]/n;
            if(a[i]>=n) end=false;
        }
        ans += cnt;
    }
    cout<<ans<<endl;
    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

i64 solve_knapsack_small_weight(const vi &ws, const vi &vs, int MAX_WEIGHT) {
    int n = ws.size();
    vi value(MAX_WEIGHT + 1);
    for (int i = 0; i < n; i++) {
        for (int j = MAX_WEIGHT; j >= 0; j--) {
            if (j - ws[i] >= 0) {
                value[j] = max(value[j], value[j - ws[i]] + vs[i]);
            }
        }
    }
    i64 nax = 0;
    for (int i = 0; i <= MAX_WEIGHT; i++) {
        nax = max(nax, value[i]);
    }
    return nax;
}

int main() {
    int n, w;
    cin >> n >> w;
    vi ws(n), vs(n);
    for (int i = 0; i < n; i++) {
        cin >> ws[i] >> vs[i];
    }
    cout << solve_knapsack_small_weight(ws, vs, w) << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
	using namespace std;
	int main()
	{
		 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	long int n,q,i,j,b,c,l;
	cin>>n;
	long long int s=0,ans;
	long int a[n],dp[100002]={0};
		for(i=0;i<n;i++)
		{
		cin>>a[i];
		dp[a[i]]++;
		s+=a[i];
		}
	
		cin>>q;
		l=q;
ans=s;
		while(q--)
		{
				
			cin>>b>>c;
		if(dp[b])
		{
			ans+=c*dp[b]-b*dp[b]; 
			dp[c]+=dp[b];
			dp[b]=0;
		}
		cout<<ans<<endl;
		}
		
		
	}

Measured memory_bytes: 5224
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <tuple>
#include <math.h>
#include <set>
#include <map>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
using vb = vector<bool> ;
using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end() 
const ll INF = 1e18 ;
const ll mod = 1e9+7 ;
const double pie = acos(-1); 
vll dx4 = {-1,0,1,0} ;
vll dy4 = {0,-1,0,1} ;
vll dx8 = {-1,0,1,1,1,0,-1,-1} ;
vll dy8 = {-1,-1,-1,0,1,1,1,0} ; 

void fix_cout(){cout << fixed << setprecision(20) ; }
ll gcd(ll a,ll b){if(b==0) return a ; return gcd(b,a%b) ; }
ll lcm(ll a,ll b){return a/gcd(a,b)*b ; }
void chmax(ll &a,ll b){if(a<b) a = b ; }
void chmin(ll &a,ll b){if(a>b) a = b ; }

int main(){
	ll n ; cin >> n ;
	vvll g(n,vll(0)) ;
	for(int i=0;i<n-1;i++){
		ll a,b ;
		cin >> a >> b ;
		a-- ; b-- ;
		g.at(a).push_back(b) ;
		g.at(b).push_back(a) ;
	}
	vll ans(n,-1) ;
	vll c(n) ;
	for(auto &i:c) cin >> i ;
	sort(all(c)) ;
	reverse(all(c)) ;
	queue<ll> q ;
	ans.at(0) = c.at(0) ;
	q.push(0) ;
	ll pos = 0 ;
	while(!q.empty()){
		ll p = q.front() ;
		q.pop() ;
		ans.at(p) = c.at(pos) ;
		pos++ ;
		for(int i=0;i<g.at(p).size();i++){
			if(ans.at(g.at(p).at(i))==-1) q.push(g.at(p).at(i)) ;
		}
	}
	ll sum = 0 ;
	for(int i=1;i<n;i++) sum += c.at(i) ;
	cout << sum << endl ;
	for(int i=0;i<n;i++) cout << ans.at(i) << (i==n-1?"\n":" ") ;
}

Measured memory_bytes: 4220
#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))

int
main(int argc, char *argv[])
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  int m = max(a, max(b, c));
  printf("%d", a + b + c - m);
  return 0;
}

Measured memory_bytes: 128
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    
u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])
    
ans = 1
for i in range(1, N+1):
    ans = max(ans, u.size(i))
print(ans)

Measured memory_bytes: 26264
n=int(input())
g=[[] for i in range(n+1)]
for i in range(n-1):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
def dfs(x,p):
	s=sum([dfs(u,x) for u in g[x] if u!=p])
	return s^1 if s<2 else 2
print("First" if dfs(1,1) else "Second")

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

int main() {
  int N, A, B, C;
  cin >> N >> A >> B >> C;
  vector<string> s(N), t(N);
  for (int i = 0; i < N; i++) cin >> s[i];

  for (int i = 0; i < N; i++) {
    if (s[i] == "AB") {
      if (A == 0 && B == 0) {
        cout << "No" << endl;
        return 0;
      }

      if (A == 0) {
        A++, B--;
        t[i] = "A";
      } else if (B == 0) {
        A--, B++;
        t[i] = "B";
      } else if (A == 1 && B == 1 && C == 0 && i < N - 1) {
        if (s[i + 1] == "AC") {
          A++, B--;
          t[i] = "A";
        } else {
          A--, B++;
          t[i] = "B";
        }
      } else {
        if (A >= B) {
          A--, B++;
          t[i] = "B";
        } else {
          A++, B--;
          t[i] = "A";
        }
      }

    } else if (s[i] == "BC") {
      if (B == 0 && C == 0) {
        cout << "No" << endl;
        return 0;
      }

      if (B == 0) {
        B++, C--;
        t[i] = "B";
      } else if (C == 0) {
        B--, C++;
        t[i] = "C";
      } else if (B == 1 && C == 1 && A == 0 && i < N - 1) {
        if (s[i + 1] == "AB") {
          B++, C--;
          t[i] = "B";
        } else {
          B--, C++;
          t[i] = "C";
        }
      } else {
        if (B >= C) {
          B--, C++;
          t[i] = "C";
        } else {
          B++, C--;
          t[i] = "B";
        }
      }
    }

    if (s[i] == "AC") {
      if (A == 0 && C == 0) {
        cout << "No" << endl;
        return 0;
      }

      if (A == 0) {
        A++, C--;
        t[i] = "A";
      } else if (C == 0) {
        A--, C++;
        t[i] = "C";
      } else if (A == 1 && B == 0 && C == 1 && i < N - 1) {
        if (s[i + 1] == "AB") {
          A++, C--;
          t[i] = "A";
        } else {
          A--, C++;
          t[i] = "C";
        }
      } else {
        if (A >= C) {
          A--, C++;
          t[i] = "C";
        } else {
          A++, C--;
          t[i] = "A";
        }
      }
    }
  }
  cout << "Yes" << endl;
  for (int i = 0; i < N; i++) cout << t[i] << endl;
}

Measured memory_bytes: 9604
mod = 10 ** 9 + 7

n = int(input())
s = input()
t = [(ind % 2) ^ (ss == 'W') for ind, ss in enumerate(s)]
# print(t)

ans = 1
zeros = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans = ans * zeros % mod
        zeros -= 1

if zeros > 0:
    print(0)
    exit()

for i in range(1, n + 1):
    ans = ans * i % mod

print(ans)


Measured memory_bytes: 5096
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

int main() {
  int N, c0 = 0, c1 = 0, c2 = 0, c3 = 0;
  cin >> N;
  vector<string> S(N);
  REP(i, N) {
    cin >> S[i];
  }
  REP(i, N) {
    if (S[i] == "AC") {
      c0++;
    } else if (S[i] == "WA") {
      c1++;
    } else if (S[i] == "TLE") {
      c2++;
    } else {
      c3++;
    }
  }
  cout << "AC x " << c0 << endl;
  cout << "WA x " << c1 << endl;
  cout << "TLE x " << c2 << endl;
  cout << "RE x " << c3 << endl;
  return 0;
}


Measured memory_bytes: 6424
from math import ceil
D, G = map(int, input().split(" "))
pc = [[int(i) for i in input().split(" ")] for _ in range(D)]

s = 100 * 11
for i in range(2 ** D):
    ans = 0
    num = 0
    zero = 0
    for j in range(D):
        if (i >> j) & 1:
            ans += 100*(j+1)*pc[j][0] + pc[j][1]
            num += pc[j][0]
        else:
            zero = j
    if G > ans:
        cand = ceil((G-ans)/(100 * (zero+1)))
        if cand > pc[zero][0]:
            continue
        else:
            num += cand
    if num < s:
        s = num
print(s)

Measured memory_bytes: 3064
#include <stdio.h>
int main (int argc, char * argv[])
{
    int x,i=1;
    while(1){
        scanf("%d",&x);

        if(x==0){
            break;
        }
        printf("Case %d: %d\n",i,x);
        i++;
    }
    return 0;
}



Measured memory_bytes: 2032
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int w;
    while(scanf("%d",&w)!=EOF)
    {

        int i;
        long long area = 0;
        for(i=w;i<600;i+=w)
        {
            area += w*i*i;
        }
        printf("%lld\n",area);
    }

}

Measured memory_bytes: 1188
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
#define vsort(v) sort(v.begin(), v.end());
#define vunique(v) unique(v.begin(), v.end());
#define mp make_pair
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int r, g, b;
	cin >> r >> g >> b;
	int tmp = r * 100 + g * 10 + b;
	if(tmp % 4 == 0) cout << "YES" << endl;
	else cout << "NO" << endl;

}


Measured memory_bytes: 256
using System;
using System.Numerics; 

namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    string[] str=Console.ReadLine().Split(' ');
      int i=0;
    while(i<5){
    
      if(int.Parse(str[i])==0){
        break;
      }
        i++;
      
    }Console.WriteLine(i+1);
  }
  }
}


Measured memory_bytes: 27476
#include <bits/stdc++.h>
using namespace std;
#define sortv(x) sort(x.begin(), x.end())
#define revv(x) sort(x.begin(), x.end(), greater<int>())
#define accumlate(x) rep(i, 1, x.size()) x[i] += x[i - 1]
#define mod 1000000007
typedef long long ll;
int main(){
 int N,K;
 cin>>N>>K;
 K--;
 vector<ll> h(N);
 for (int i=0; i<N; i++)
 cin>>h[i];
 sortv(h);
 ll ans=h[K]-h[0];
 for(int i=0;i+K<N;i++)
   ans=min(ans,h[i+K]-h[i]);
  cout<<ans<<endl;
 return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
#define vecout(V) for(int i=0;i<V.size();i++) {cout<<V[i]<<endl;}
typedef long long ll;

int main(void){
    int k;
    cin>>k;
    vector<int> ans={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout<<ans[k-1]<<endl;
    return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define vi vector<ll>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define el printf("\n")
#define pb push_back
#define f first
#define s second
#define arrondi(a) (long long)floor(a+0.5);
#define NIL -1
ll N=500005;
ll MAX=9223372036854775807;
ll MOD=1000000007;
long double PI =4*atan(1);

int main()
{
	IOS;
    cout.precision(30);
    int k,x; cin >> k >> x;
    for (int i=max(-1000000,x-k+1);i<=x;i++)
        cout << i << " ";
    for (int i=x+1;i<min(x+k,1000000);i++)
    cout << i << " ";
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) cout << fixed << setprecision(x)
#define endl '\n'
const ll inf = LLONG_MAX;
const long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  ll n;
  cin >> n;
  vector<vll> trv(n + 1, vll(3, 0));
  for (ll i = 0; i < n; i++) cin >> trv[i + 1][0] >> trv[i + 1][1] >> trv[i + 1][2];
  for (ll i = 1; i <= n; i++) {
    ll dt = trv[i][0] - trv[i - 1][0], dx = abs(trv[i][1] - trv[i - 1][1]), dy = abs(trv[i][2] - trv[i - 1][2]);
    if (dt % 2 != (dx + dy) % 2 || dt < dx + dy) {
      No();
      return 0;
    }
  }
  Yes();
}

Measured memory_bytes: 5760
from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e]+=count[v]
        q.append(e)
print(*count)

Measured memory_bytes: 56056
#include <cstdio>
typedef long long int64;
static const int MAXN = 42;
static const int MAXS = 5 + 7 + 5;
static const int MODULUS = 1e9 + 7;
#define _  %  MODULUS
#define __ %= MODULUS

int n, x, y, z;
int64 f[MAXN][2][1 << MAXS] = {{{ 0 }}};

int main()
{
    scanf("%d%d%d%d", &n, &x, &y, &z);

    int s = x + y + z;
    f[0][0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= 1; ++j)
            for (int k = 0; k < (1 << s); ++k) if (f[i][j][k])
                for (int d = 1; d <= 10; ++d) {
                    int t = ((k << d) | (1 << (d - 1))) & ((1 << s) - 1);
                    if ((t & (1 << (x + y + z - 1))) && (t & (1 << (y + z - 1))) && (t & (1 << (z - 1))))
                        (f[i + 1][1][t] += f[i][j][k])__;
                    else (f[i + 1][j][t] += f[i][j][k])__;
                }

    int64 ans = 0;
    for (int i = 0; i < (1 << s); ++i) ans += f[n][1][i];
    printf("%lld\n", ans _);

    return 0;
}


Measured memory_bytes: 84096
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut a: Vec<u64> = (0..3*n).map(|_| read()).collect();
    let mut sum = 0;

    a.sort();

    for i in 0..n {
        sum += a[3*n - (i*2 + 2)];
    }
    println!("{}", sum);

}


Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, A, B, C;
  cin >> N >> A >> B >> C;
  vector<string> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
  }
  bool flag = true;
  vector<char> ans(N);
  for(int i=0; i<N; i++){
    if(vec[i] == "AB"){
      if(A == 0 && B == 0){
        flag = false;
      }
      else if(A == 0){
        A++;
        B--;
        ans[i] = 'A';
      }
      else if(B == 0){
        A--;
        B++;
        ans[i] = 'B';
      }
      else{
        if(i == N-1){
          A++;
          B--;
          ans[i] = 'A';
          break;
        }
        if(vec[i+1] == "AB"){
         if(A < B){
            A++;
            B--;
            ans[i] = 'A';
          }
          else{
            A--;
            B++;
            ans[i] = 'B';
          }
        }
        if(vec[i+1] == "AC"){
          A++;
          B--;
          ans[i] = 'A';
        }
        if(vec[i+1] == "BC"){
          B++;
          A--;
          ans[i] = 'B';
        }
      }
    }
    
    if(vec[i] == "AC"){
      if(A == 0 && C == 0){
        flag = false;
      }
      else if(A == 0){
        A++;
        C--;
        ans[i] = 'A';
      }
      else if(C == 0){
        A--;
        C++;
        ans[i] = 'C';
      }
      else{
        if(i == N-1){
          A++;
          C--;
          ans[i] = 'A';
          break;
        }
        if(vec[i+1] == "AC"){
          if(A < C){
            A++;
            C--;
            ans[i] = 'A';
          }
          else{
            A--;
            C++;
            ans[i] = 'C';
          }
        }
        if(vec[i+1] == "AB"){
          A++;
          C--;
          ans[i] = 'A';
        }
        if(vec[i+1] == "BC"){
          C++;
          A--;
          ans[i] = 'C';
        }
      }
    }
    
    if(vec[i] == "BC"){
      if(B == 0 && C == 0){
        flag = false;
      }
      else if(B == 0){
        B++;
        C--;
        ans[i] = 'B';
      }
      else if(C == 0){
        B--;
        C++;
        ans[i] = 'C';
      }
      else{
        if(i == N-1){
          B++;
          C--;
          ans[i] = 'B';
          break;
        }
        if(vec[i+1] == "BC"){
          if(B < C){
            B++;
            C--;
            ans[i] = 'B';
          }
          else{
            B--;
            C++;
            ans[i] = 'C';
          }
        }
        if(vec[i+1] == "AB"){
          B++;
          C--;
          ans[i] = 'B';
        }
        if(vec[i+1] == "AC"){
          C++;
          B--;
          ans[i] = 'C';
        }
      }
    }
  }
  if(!flag){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
    for(int i=0; i<N; i++){
      cout << ans[i] << endl;
    }
  }
}



Measured memory_bytes: 6392
#include<bits/stdc++.h>
using namespace std;
int res;
string s;
int main()
{
    cin>>s;
    if(s=="RRR")
        return cout<<3, 0;
    if(s=="RRS"||s=="SRR")
        return cout<<2, 0;
    if(s=="SSS")
        return cout<<0, 0;
    else
        cout<<1;
}


Measured memory_bytes: 3636
#!/usr/bin/env python3
import math

D, G = map(int, input().split())
data = []
for i in range(D):
    p, c = map(int, input().split())
    data.append([100 * (i + 1), p, c])
data = sorted(data)[::-1]

ans = float("inf")

for i in range(2 ** D):
    total = 0
    num = 0
    idx = []
    for k in range(D):
        if i >> k & 1 == 1:
            idx.append(k)
    
    for j in idx:
        d = data[j]
        total += d[0] * d[1] + d[2]
        num += d[1]
    
    if total >= G:
        ans = min(ans, num)
    else:
        for j in set(range(D)) - set(idx):
            d = data[j]
            if total + d[0] * (d[1] - 1) >= G:
                num += math.ceil((G - total) / d[0])
                ans = min(ans, num)
                continue
            else:
                total += + d[0] * (d[1] - 1)
                num += d[1] - 1
print(ans)

Measured memory_bytes: 3064
<?php

//標準入力
class Scanner {
  private $arr = [];
  private $count = 0;
  private $pointer = 0;
  public function next() {
      if($this->pointer >= $this->count) {
          $str = trim(fgets(STDIN));
          $this->arr = explode(' ', $str);
          $this->count = count($this->arr);
          $this->pointer = 0;
      }
      $result = $this->arr[$this->pointer];
      $this->pointer++;
      return $result;
  }
  public function hasNext() {
      return $this->pointer < $this->count;
  }
  public function nextInt() {
      return (int)$this->next();
  }
  public function nextDouble() {
      return (double)$this->next();
  }
}

//標準出力
class out {
    public static function println($str = "") {
        echo $str . PHP_EOL;
    }
}



$sc = new Scanner();
$N = $sc->nextInt();
$W = array();
$S = array();


for($i = 1;$i <= $N; $i++){
    $W[] = $sc->nextInt();
}

for($j = 1; $j < $N; $j++){
    $S1 = array_sum(array_slice($W, 0    , $j));
    $S2 = array_sum(array_slice($W, $j, $N - $j + 1));

    $S [] = abs($S1 - $S2);
}

echo min($S).PHP_EOL;




Measured memory_bytes: 4732
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,d,h,i,j,k,l,m,n,v,w,x,y,z;
	ll		ans = 0;
	string	s;
	cin >> s;

	if (s[s.size()-1]=='s') s = s + "es";
	else s = s + "s";


	//vector<ll>	aa(n);
	//for(i=0;i<n;i++) cin >> aa[i];
	//vector<ll>	dp(n+1,INFL);
	//vector<vector<ll>>	dp2(x , vector<ll>(y,INFL));

	cout << s << endl;
	return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define fio freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define vll vector<long long int>
#define vpii vector<pair<int,int>>
#define dsc [](int a,int b)->bool {return a>b;}
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define MAX 100000000000000
#define test int t; cin>>t;
#define MOD 1000000007

using namespace std;

int main()
{
    #ifndef ONLINE_JUDGE
        fio
    #endif
    IOS

    ll n,d;
    cin>>n>>d;
    ll ans = 0;
    d = d*d;
    while(n--){
        ll x,y;
        cin>>x>>y;
        if(x*x+y*y<=d) ans++;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3640
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from bisect import bisect , bisect_left

def primes(max_number):
    """
    指定値未満の素数を取得するジェネレータ
    https://qiita.com/Mokkeee/items/93b6b7d59fa256aa1677 よりコピペ
    :param max_number: 最大値
    :return: 素数ジェネレータ
    """
    if max_number <= 2:
        raise StopIteration
    yield 2
    is_prime = [1] * max_number
    square_root_of_max = max_number ** 0.5
    for number in range(3, max_number, 2):
        if is_prime[number] is 0:
            continue
        yield number
        if number <= square_root_of_max:
            for multiple in range(number * 2, max_number, number):
                is_prime[multiple] = 0

P = list(primes(10**5 +1))
P = [p for p in P[1:] if (p+1)//2 == P[bisect_left(P, (p+1)//2)]]

Q = int(input())

for _ in range(Q):
    l, r = inpl()
    print(bisect(P, r) - bisect_left(P, l))

Measured memory_bytes: 4204
#include <bits/stdc++.h>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()




using namespace std;

struct Node{
  //ll num = 0;
  ll dist = 2000000000;

  ll path = -1;

  bool locked = false;

  vector <ll> near;
};

queue <ll> q;
vector <Node> gragh(100010); // 1 indexed
ll nd = 0;

void dfs(ll now);

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

ll N,M; 
cin>>N>>M;

REP(i,M){
  ll a,b; cin>>a>>b;
  gragh[a].near.push_back(b);
  gragh[b].near.push_back(a);
}

gragh[0].near.push_back(1);
gragh[1].near.push_back(0);
gragh[0].dist = 0;
gragh[1].path = 1;


//dfs(0);

q.push(0);

while(1){
  if(q.size() == 0) break;
  int q1 = q.front(); q.pop();
  //if(gragh[q1].locked = true) continue;
  dfs(q1); 
  
}


cout<<"Yes"<<endl;
for(int i=2;i<=N;i++){
 // cout<<"Yes"<<endl;
  cout<<gragh[i].path<<endl;
}


  


  return 0;
}

void dfs(ll now){
  
 // cout<<now<<endl;
  vector <ll> next = gragh[now].near;
  ll D = gragh[now].dist;
  //cout<<now<<" "<<D<<endl;

  for(int i=0;i<int(next.size());i++){
    ll ne =next[i];
    if(ne == gragh[now].path) continue;
    if(gragh[ne].dist  > D + 1){
      gragh[ne].path = now;
      gragh[ne].dist = D+1;
      //dfs(ne);
     // gragh[ne].locked = true;
      q.push(ne);
      //cout<<ne<<" "<<gragh[ne].dist<<endl;
    } 
  }
 
}

Measured memory_bytes: 15072
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H & b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H & b) const { return x == b.x && y == b.y; }
	bool operator!=(const H & b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T & a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T & a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n;
int a[400000];
bool solve(int t) {
	vector<H>v;
	v.push_back(H{ 1,0 });
	for (int i = 0; i < n; i++) {
		if (v[v.size() - 1].x < a[i]) {
			v.push_back(H{ a[i],1 });
		}
		else {
			while (!v.empty() && v[v.size() - 1].x > a[i]) v.pop_back();
			if (v[v.size() - 1].x == a[i]) v[v.size() - 1].y++;
			else v.push_back(H{ a[i],2 });
		}
		while (v.size() >= 2 && v[v.size() - 1].y == t + 1) {
			int k = v.size();
			if (v[k - 2].x == v[k - 1].x - 1) {
				v[k - 2].y++;
				v.pop_back();
			}
			else {
				k = v[k - 1].x - 1;
				v.pop_back();
				v.push_back(H{ k,1 });
			}
		}
		if (i == 0) v[0].y = 1;
	}
	if (v[0].y > t) return 0;
	return 1;

}
signed main() {
	cin >> n;
	bool b = 1;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (i > 0 && a[i - 1] >= a[i]) b = 0;
	}
	if (b) {
		cout << 1 << endl;
		return 0;
	}
	int l = 2, r = (1 << 30), t, ma = 1 << 30;
	for (int i = 0; i < 40; i++) {
		t = (r + l) / 2;
		if (solve(t)) {
			r = t;
			ma = min(ma, t);
		}
		else l = t;
	}
	cout << ma << endl;
}

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

long long n,m,ans=0;
vector<long long> divs;

long long gcd(long long x, long long y){
	//cout<<x<<" "<<y<<endl;
	if(y!=0){
		long long tmp=y;
		y=x%y;
		x=tmp;
		return gcd(x,y);
	}else{
		return x;
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i*i<=m;i++){
		if(m%i==0){
			divs.push_back(i);
			divs.push_back(m/i);
		}
	}
	for(long long i:divs){
		if(m-i*(n-1)>0){
			ans=max(ans,gcd(i,m-i*(n-1)));
		}
	}
	if(m%n==0){
		cout<<m/n<<endl;
	}else{
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final String VACANT = "Vacant";

    public static void main(final String[] args) {
        final FastScanner scanner = new FastScanner(System.in);
        final int n = scanner.nextInt();
        printAndFlush(0);
        final String initial = scanner.next();
        if (initial.equals(VACANT)) {
            return;
        }

        String previous = initial;
        int left = 0;
        int right = n - 1;
        for (int i = 0; i < 19; i++) {
            if (right - left == 1) {
                printAndFlush(right);
                return;
            }
            final int mid = (left + right) / 2;
            printAndFlush(mid);
            final String current = scanner.next();
            if (current.equals(VACANT)) {
                return;
            }

            if ((mid - left) % 2 == 0) {
                if (previous.equals(current)) {
                    left = mid;
            previous = current;
                } else {
                    right = mid - 1;
                }
            } else {
                if (previous.equals(current)) {
                    right = mid - 1;
                } else {
                    left = mid;
            previous = current;
                }
            }
        }
    }

    private static void printAndFlush(Object obj) {
        System.out.println(obj);
        System.out.flush();
    }

    private static class FastScanner {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(final InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (final IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}


Measured memory_bytes: 32800
def cmb(n):
    return (n * (n - 1)) / 2

k = int(input())
if (k % 2 == 0):
    print(int(cmb(k) - 2 * cmb(k / 2)))
else:   
    print(int(cmb(k) - ((cmb(k // 2) + cmb(k // 2 + 1)))))

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1000005;
const int MOD=998244353;
int n,m;
int a[N];
long long c[N];
long long f[N];
int mu[N];
int prime[N],tot;
bool isprime[N];
void init(int n=1000000)
{
	for(int i=1;i<=n;i++)
		isprime[i]=true;
	isprime[1]=false;
	mu[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i]) prime[++tot]=i,mu[i]=-1;
		for(int j=1;j<=tot&&i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=n;i++)
		c[a[i]]=(c[a[i]]+a[i])%MOD;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j+=i)
			f[i]=(f[i]+c[j])%MOD;
	return;
}
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	init();
	m=1000000;
	long long ans=0;
	for(int d=1;d<=m;d++)
		for(int t=1;t<=m/d;t++)
			ans=(ans+(ksm(d,MOD-2)*mu[t]+MOD)*f[t*d]%MOD*f[t*d]%MOD)%MOD;
	for(int i=1;i<=n;i++)
		ans=(ans-a[i]+MOD)%MOD;
	ans=ans*ksm(2,MOD-2)%MOD;
	printf("%lld",ans);
	return 0;
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  cout << fixed << setprecision(12);
  string s; cin>>s;
  for (char c: s) {
  if (c=='1') {
  cout<<9;
  } else if (c=='9') {
  cout<<1;
  } else {
  cout<<c;
  }
  }
  

  return 0;
}


Measured memory_bytes: 256