akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;


int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> correct(n + 1);
    vector<int> penalty(n + 1);
    int pi;
    string si;
    for (int i = 0; i < m; i++) {
        cin >> pi >> si;
        if (si == "AC")
            correct[pi] = 1;
        else
            if (correct[pi] == 0) penalty[pi]++;
    }
    int c = 0, p = 0;
    for (int i = 1; i <= n; i++) c += correct[i];
    for (int i = 1; i <= n; i++) {
        if (correct[i]) p += penalty[i];
    }
    cout << c << " " << p << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#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 pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
const long long MOD = 1000000007;

//最大最小の入れ替え
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;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (int i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (int i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}
//素因数分解
map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

//切り上げの割り算は(a + b - 1) / bでできる
//時間を意識しろ
//コードテストちゃんとして
//画面とにらめっこするな書け
//WA出すたびにABCは五億円払え
//わからない問題はとばせ
//躊躇なくぐぐれ

//ここから
int main(){
    string S;
    cin>>S;
    ll count=0;
    ll B=0;
    rep(i,S.size()){
        if(S.at(i)=='B'){
            B++;
        }else{
            count+=B;
        }
    }
    cout<<count<<endl;
}


Measured memory_bytes: 640
import fractions

if __name__ == '__main__':
  n = int(input())
  work_list = []
  for i in range(n):
    a, b = map(int, input().split(" "))
    work_list.append((a, b))
      
  work_sorted = sorted(work_list, key=lambda x:x[1])
  total_work = 0
  success = "Yes"
  for key, value in work_sorted:
    total_work = total_work + int(key)
    if total_work > value:
      success = "No"
      break

  print (success)


Measured memory_bytes: 35460
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}
ll N;
string s;
ll i, j, k;
set<string> product;
int main(){
    scanf("%lld",&N);
    REP(i, N){
        //scanf("%s", s);
        cin >> s;
        product.insert(s);
    }

    cout << product.size();
    printf("\n");
    return 0;
}

Measured memory_bytes: 19248
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long P = 1;
    for ( int i = 1; i <= N ; i++) {
       P = P * i;
       P = P % 1000000007; 
   }
    System.out.println(P);
  }
}

Measured memory_bytes: 25684
a = Array.new(4)
b = Array.new(4)
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
a_sum = a.inject(:+)
b_sum = b.inject(:+)
if a_sum >= b_sum
  puts a_sum
else
  puts b_sum
end

Measured memory_bytes: 6096
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = 0;
	int tmp;
	string s, t;
	vector<string> ss, tt;
	cin >> s >> t;
	REP(i, s.size()) ss.push_back(s.substr(i, 1));
	REP(i, t.size()) tt.push_back(t.substr(i, 1));
	sort(ss.begin(), ss.end());
	sort(tt.begin(), tt.end(), greater<string>() );
	string sss = "", ttt = "";
	REP(i, ss.size()) sss += ss[i];
	REP(i, tt.size()) ttt += tt[i];
	if (sss<ttt) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	//cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include <math.h>
int main(){
    long long int a,b,n;
    scanf("%lld %lld %lld",&a,&b,&n);
    long long int sum=0;

    if(b-1<n){
        sum=floor(a*(b-1)/b)-a*floor((b-1)/b);
    }
    else{
        sum=floor(a*n/b)-a*floor(n/b);
    }
    printf("%lld",sum);

}


Measured memory_bytes: 1704
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename T>
struct edge {
    int src,to;
    T cost;

    edge() = default;
    edge(int to, T cost) : src(-1), to(to), cost(cost) {}
    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
    bool operator<(const edge &e) const {
        return cost < e.cost;
    }
};

struct UnionFind {
    vector<int> node;

    UnionFind() = default;
    UnionFind(int x) {init(x);}

    void init(int x) {
        node.assign(x,-1);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (node[x] > node[y]) swap(x,y);
        node[x] += node[y];
        node[y] = x;
        return true; 
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int root(int x) {
        if (node[x] < 0) return x;
        return node[x] = root(node[x]);
    }

    int size(int x) {
        return -node[root(x)];
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    vector<ll> X(N+1);
    rep(i,N) cin >> X[i];
    vector<edge<ll>> E;
    rep(i,M) {
        int u,v,w; cin >> u >> v >> w;
        --u; --v;
        E.emplace_back(u,v,w);
    }

    sort(all(E));
    UnionFind uf(N);
    vector<int> cnt(N+1),ok(N+1);
    rep(i,M) {
        int p = uf.root(E[i].to);
        int q = uf.root(E[i].src);
        if (p == q) q = N;
        int c = cnt[p]+cnt[q];
        int o = ok[p]+ok[q];
        ll w = X[p]+X[q];
        cnt[p] = cnt[q] = ok[p] = ok[q] = X[p] = X[q] = 0;
        uf.merge(E[i].src,E[i].to);
        int v = uf.root(E[i].src);
        cnt[v] = c+1;
        X[v] = w;
        ok[v] = w >= E[i].cost ? cnt[v] : o;
    } 

    cout << M - accumulate(all(ok),0) << ln;
}


Measured memory_bytes: 3824
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
 
int main(){
	int n;
	cin >> n;
	pair<ll, ll> p[n];
	for(int i=0; i<n; i++){
		cin >> p[i].first >> p[i].second;
	}

	int ans=n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i==j) continue;
			ll x=p[i].first-p[j].first, y=p[i].second-p[j].second;
			int cnt=0;
			for(int k=0; k<n; k++){
				for(int l=0; l<n; l++){
					if(p[k].first-p[l].first==x && p[k].second-p[l].second==y){
						cnt++;
					}
				}
			}
			ans=min(ans, n-cnt);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b,c=0;
  cin>>n>>a>>b;
  for(int i=1;i<=n;i++){
    int d=i,e=0;
    while(d!=0){
      e+=d%10;
      d/=10;
    }
    if(e>=a&&e<=b)
      c+=i;
  }
  cout<<c;
}

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

int main(){
  int n, l;
  cin >> n >> l;
  vector<string> a(n);
  for(int i=0; i<n; i++){
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  for(int i=0; i<n; i++){
    cout << a[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main () {
  std::string str[4] = {"Sunny", "Cloudy", "Rainy", "Sunny"};
  std::string we;
  std::cin >> we;
  for(int i = 0; i < 3; ++i) {
    if(we == str[i]){
      std::cout << str[i + 1] << std::endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int a[1010];
int main() {
	int n, q;
	cin >> n;
	rep(i, n)cin >> a[i];
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		reverse(a + x, a + y);
	}
	rep(i, n)cout << a[i] << (i == n - 1 ? "\n" : " ");
	return 0;
}


Measured memory_bytes: 3072
n = int(input())
s = input()
ans = 0
for i in range(1,n):
    dum = []
    check = 0
    for j in s[0:i]:
        dum.append(j)
    dum = set(dum)
    #print(s[0:i])
    for k in dum:
        if s[i:n].count(k) >= 1:
            check += 1
    ans = max(check,ans)
print(ans)

Measured memory_bytes: 39024
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x,y,a,b;

double c,d,s;

	cin>>x>>y;
	a=x/y;
    b=x%y;
    c=x;
    d=y;
	s=c/d;

	cout<<a<<" "<<b<<" ";
	printf("%.5f\n",s);
}




Measured memory_bytes: 3220
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FS r = new FS();
		int n = r.nextInt();
		int k = r.nextInt();
		long ans = k;
		for(int i=1; i<n; i++ ) {
			ans *= (k-1);
		}
		System.out.println(ans);
	}

	// Read Class
	static class FS {
		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() { return hasNextByte() ? buffer[ptr++] : -1;}
		private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
		private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}

		public boolean hasNext() { skipUnprintable(); 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 int nextInt() {
			return (int)nextLong();
		}
		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();
			}
		}
	}
}


Measured memory_bytes: 7892
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define ss second
#define ff first
#define INF 300000000000001
#define ll_max 9000000000000000001
#define mod 998244353
#define PI 3.14159265358979323846L
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define db(args...) {string _ss = #args; replace(_ss.begin(), _ss.end(), ',' , ' '); stringstream ___s(_ss) ; debug(___s, args);}
using namespace std;
typedef vector<pair<ll,ll> > vll;
typedef vector<pair<int,int> > vii ;
typedef pair<ll,ll> pll;
const ll N = 500001;
const ll M = 21;
struct point {
    ll x, y;
    bool operator == (point b)
    {
        if(this -> x == b.x && this -> y == b.y) return 1;
        return 0;
    }
    bool operator != (point b)
    {
        return !(*this == b);
    }
};

void debug(stringstream &s){}
template <typename T, typename... Args>
void debug(stringstream &s, T a, Args... args)
{
    string word;
    s >> word;
    cout << word << " = " << a << endl;
    debug(s, args...);
}

ll fast_exp(ll x,ll n)
{
    if(n == 0) return 1;
    ll ans;
    if(n % 2 == 0)
    {
         ans = fast_exp(x, n / 2);
         ans = ans * ans % mod;
    }
    else ans = fast_exp(x, n - 1) * x % mod;
    return ans;
}

int main()
{
    fast;
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        ll n, m = 0, x = 0, y = 0, ans = 0, k, H1, H2, M1, M2;
        cin >> H1 >> M1 >> H2 >> M2 >> k;
        m = k % 60;
        n = k / 60;
        H2 -= n;
        M2 -= m;
        if(M2 < 0) M2 += 60, H2--;
        ans = abs(H2 - H1) * 60 + M2 - M1;
        cout << ans << "\n";
     }
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    long long wallet = 1000;
    long long lastPrice;
    cin >> lastPrice;
    N--;
    long long n;
    long long curPrice;
    while(N--) {
        cin >> curPrice;
        if(curPrice >= lastPrice) {
            n = wallet / lastPrice;
            wallet += n*(curPrice - lastPrice);
        } 
        lastPrice = curPrice;
    }
    cout << wallet;
    return 0;
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

int main() {
  vector<string> v = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
  in(string, s);
  rep(i, v.size()) if (v[i] == s) {
    out(7 - i);
    return 0;
  }
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define INF  numeric_limits<int>::max()
#define NINF numeric_limits<int>::min()

using namespace std;
using ll = long long;

int N, M;

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

    std::cin >> N >> M;

    int low  = 1;
    int high = N;
    REP(i, M) {
        int r, l;
        std::cin >> l >> r;

        if(low < l) {
            low = l;
        }
        if(r < high) {
            high = r;
        }
    }

    if(0 <= high - low + 1) {
        std::cout << high - low + 1 << std::endl;
    }
    else {
        std::cout << 0 << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int N;
    cin >> N;
    int ans = 1;
    
    for(int i = 1; i <= sqrt(N); i++){
        if(i * i <= N)      ans = i * i;
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val symbolToIndex = mapOf("S" to 0, "H" to 1, "C" to 2, "D" to 3)
    val indexToSymbol = symbolToIndex.map { (k, v) -> v to k }.toMap()
    var cards = Array(4) {Array(13) {true} }

    val elementNum = readLine()!!.toInt()
    for (i in (1..elementNum)) {
        val (symbol, suit) = readLine()!!.split(" ")
        cards[symbolToIndex.getValue(symbol)][suit.toInt() - 1] = false
    }

    cards.forEachIndexed {
        index, suits -> suits.forEachIndexed {
            suit, v -> if (v) {println("${indexToSymbol.getValue(index)} ${suit + 1}")}
        }
    }
}



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

x_before = 0
y_before = 0
t_before = 0
ans = 'Yes'

for i in range(N):
    t, x, y = map(int, input().split())
    
    #i番目とi+1番目までの距離
    distance = abs(x-x_before) + abs(y-y_before)
    
    #i番目とi+1番目までの時間
    time = t-t_before
    
    #i+1番目のtimeで行くことが可能か判定
    if time-distance<0:
        ans = 'No'
        break
    if time%2 != distance%2:
        ans = 'No'
        break
        
    #i+1番目のtimeで行くことが可能なら値を更新
    x_before = x
    y_before = y
    t_before = t
    
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s;
    cin>>s;
    if (s=="Sunny") {
        cout<<"Cloudy"<<endl;
    } else if (s=="Cloudy") {
        cout<<"Rainy"<<endl;
    } else {
        cout<<"Sunny"<<endl;
    }
}

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

for x, y, h in lst:
    if h > 0:
        base = (x, y, h)
        break

for cx in range(100 + 1):
    for cy in range(100 + 1):
        H = base[2] + abs(base[0] - cx) + abs(base[1] - cy)
        if all([max(H - abs(x - cx) - abs(y - cy), 0) == h for x, y, h in lst]):
            print(cx, cy, H)
            exit()


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;

int main(){
    string s,t;
    cin>>s>>t;
    int ans=0;
    for(int i=0;i<s.length();i++){
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans;
}


Measured memory_bytes: 3920
#include <iostream>

int main(){
    int a,b;
    int sum = 0;

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

    if(a == 3){
        sum += 100000;
    } else if(a == 2){
        sum += 200000;
    }else if(a == 1){
        sum += 300000;
    }

    if(b == 3){
        sum += 100000;
    } else if(b == 2){
        sum += 200000;
    }else if(b == 1){
        sum += 300000;
    }

    if(b == 1 && a==1){
        sum += 400000;
    }

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

Measured memory_bytes: 256
//設定値
var input = {};

//2次元長方形配列。 要素は-1(横棒の右側),0,1(横棒の左側)
var data = [];

//経路取得
var f = function(startLine, startStep){
	if(!startStep) startStep = 0;
	var now = startLine;
	var result = [now];
	for(var y=startStep; y<data.length; y++){
		now += data[y][now];
		result.push(now);
	}
	return result;
};
//ゴール指定時の経路取得 (経路はスタートから)
var rf = function(endLine){
	var now = endLine;
	var result = [now];
	for(var y=data.length-1; y>=0; y--){
		now += data[y][now];
		result.push(now);
	}
	return result.reverse();
};

var lines;
var loadInput = function(){
	//データ作成
	input = {steps:4};
	data = [];
	for(var j=0; j<4+input.steps; j++){
		var e = lines[j];

		def = ["lines", "start", "end", "steps"];
		if(j<def.length){
			input[def[j]] = parseInt(e);
			continue;
		}
	
		//i>4
		var line = [];
		for(var i=0; i<input.lines-1; i++){
			var c = parseInt(e.charAt(i));
			if(i>0 && c==0 && line[i-1]==1) c = -1;
			line.push(c);
		}
		line.push((line[line.length-1]==1) ? -1 : 0);
		data.push(line);
	}
	input.start -= 1;
	input.end -= 1;
	lines.splice(0, 4+input.steps);
	return true;
};

var calc = function(){
	var route = f(input.start);
	if(route[route.length-1] == input.end) {
		console.log("0");
		return;
	}
	var gRoute = rf(input.end);
	
	var result = "1";
	for(var y=0; y<input.steps; y++){
		if(Math.abs(route[y]-gRoute[y]) == 1 && data[y][route[y]]==0 && data[y][gRoute[y]]==0){ //隣り合っている
			result = (y+1) + " " + (Math.min(route[y], gRoute[y])+1);
			break;
		}
	}
	
	console.log(result);
};

var exec = function(){
	if(lines[0] == "0") return; 
	loadInput();
	calc();
	exec();
};

var lines = [];
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk)
{
    chunk.trim().split('\n').forEach(function(line) {
        lines.push(line);
    });
});
 
process.stdin.on('end', function(){
	exec();
});

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

void Stones(vector<int> &a, int maxHeapVal)
{
	int n = a.size();
	
	vector<int> playerList = {0, 1};

	vector<vector<int>> dp(maxHeapVal + 1, vector<int>(2, -1));
	
	/* dp[heap_val][first_player] denotes the winner when the game starts with 'heap_val' stones
	 * and the player numbered 'first_player' is the first to play
	 */
	
	// Nothing to pick. You lose.
	for(int first_player : playerList)
		dp[0][first_player] = not first_player;

	for(int heap_val = 1; heap_val <= maxHeapVal; heap_val++)
	{
		for(int first_player : playerList)
		{
			bool possible_to_win = false;
			for(auto choice : a)
				if(choice <= heap_val)
					if(dp[heap_val - choice][not first_player] == first_player)
						possible_to_win = true;
		
			if(possible_to_win)
				dp[heap_val][first_player] = first_player;
			else
				dp[heap_val][first_player] = not first_player;
		}
	}
	
	if(dp[maxHeapVal][0] == 0)
		cout << "First" << endl;
	else
		cout << "Second" << endl;
}

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

	vector<int> a(n);
	for(auto &ele : a)
		cin >> ele;

	Stones(a, maxHeapVal);
	return 0;
}



Measured memory_bytes: 5760
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

#define X real()
#define Y imag()

using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
using ll  = long long;

using point = complex<double>;


void err(istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << " = " << a << endl;err(++it, args...);}

const int N = 2e5 + 50;
const double EPS = 1e-8;
const long long mod = 1e9 + 7;

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



int  d;
string k;
long long dp[N][102][2]; // dp[indx][mod][isSmaller]

long long solve(int indx ,int m , bool isSmaller){
            if(indx == k.size())
                    return m == 0;
            long long &ret = dp[indx][m][isSmaller];
            if(~ret)
                    return ret;
            ret = 0;
            int lim;
            if(isSmaller)
                lim = 9;
            else
                lim = k[indx] - '0';
            for(int i = 0; i <= lim; ++i){
                //if(indx == 0 && i == 0) continue;
                int nMod = (m + i)%d;
                bool s = isSmaller;
                if(!s){
                    if(i < k[indx]-'0')
                        s = 1;
                }
                ret += solve(indx + 1, nMod, s);
                ret %= mod;
            }
            return ret % mod;

}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> k >> d;
    memset(dp,-1,sizeof dp);
    cout << (solve(0,0,0) - 1 + mod) % mod << '\n';


    return 0;
}

Measured memory_bytes: 319872
MOD = 10 ** 9 + 7

n = int(input())

if n == 1:
    print(0)
    exit()

if n == 2:
    print(2)
    exit()

print((pow(10, n, MOD) - 2 * pow(9, n, MOD) + pow(8, n, MOD)) % MOD)

# 10 ^ n | 数列全体
#  9 ^ n | 0 を含まない数列全体
#  9 ^ n | 9 を含まない数列全体
#  8 ^ n | 0, 9 を含まない数列全体

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

int main(){

	int a=0,b=0,i;
	char s[110];

	scanf("%s",s);
	
	for(i=0;i<3;i++){
		
		if(s[i]=='A')a=1;
		else if(s[i]=='B')b=1;
	}
	printf("%s\n", a*b==1? "Yes":"No");
	//printf("%ld %ld*(%ld - %ld)\n", cnt,edge,K,sa);
 return 0;
 }

Measured memory_bytes: 128
use std::io::Read;
use std::collections::BinaryHeap;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).ok();
    let mut it = buf.split_whitespace();
    let n = it.next().unwrap().parse::<usize>().unwrap();
    let x = it.next().unwrap().parse::<usize>().unwrap() - 1;
    let y = it.next().unwrap().parse::<usize>().unwrap() - 1;
    let mut res = vec![0; n];
    for s in 0..n {
        let mut d : Vec<i32> = vec![10000; n];
        d[s] = 0;
        let mut qu = BinaryHeap::new();
        qu.push((0i32, s));
        while !qu.is_empty() {
            let (_, pos) = qu.pop().unwrap();
            let mut update = |p : usize| {
                if d[p] > d[pos] + 1 {
                    d[p] = d[pos] + 1;
                    qu.push((-d[p], p));
                }
            };
            if pos > 0 { update(pos - 1) }
            if pos + 1 < n { update(pos + 1) }
            if pos == x { update(y) }
            if pos == y { update(x) }
        }
        for i in s+1..n { res[d[i] as usize] += 1 }
    }
    for i in 1..n { println!("{}", res[i]) }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define ll long long
#include <string>
#include <vector>
#include <math.h>
#include <utility>
#include<set>
#include<tuple>
#define f first
#define sec second
using namespace std;
/*
12
13
*/

ll min(ll a, ll b)
{
    if(a<b)
    return a;
    return b;
}
ll max(ll a, ll b)
{
    if(a>b)
    return a;
    return b;
}

ll DP(ll arr[], ll n, ll k)
{
   ll dp[n];
   memset(dp,0,sizeof(dp));
   dp[1]=abs(arr[1]-arr[0]);
   for(int i=2;i<n;i++)
   {
       ll mini=INT_MAX;
       for(int j=i-1;j>=max(0,i-k);j--)
       {
           mini=min(mini,dp[j]+abs(arr[i]-arr[j]));
       }
       dp[i]=mini;
       //dp[i]=min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i-1]-arr[i]));
   }

   return dp[n-1];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n=0,k=0;
    cin>>n>>k;
    ll arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }

    if(k>=n)
    {
        cout<<abs(arr[n-1]-arr[0]);
        return 0;
    }

    cout<<DP(arr,n,k);


}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ref(i,n) for(long long i=0;i<n;i++)
using namespace std;
int a[1000001];
vector<long long> v;
long long n,ans=0;
int main()
{
    cin>>n;
    long long nn=pow(n,0.5),p=0;
    long long i=2;
    while(n!=1){
            while(n%i==0){
                n/=i;
                a[i]++;
                if(v.size()==0||v[v.size()-1]!=i) v.push_back(i);
            }
            i++;
            if(i>nn) {p=1;break;}
    }

    ref(j,v.size()){
        ans+=(pow(a[v[j]]*8+1,0.5)-1)/2;
    }
    if(p==1) ans+=1;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 4104
//#define TEXT_FILES

#ifdef TEXT_FILES
#include<fstream>
#else
#include<iostream>
#endif
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

#ifdef TEXT_FILES
ifstream cin("A.in");
ofstream cout("A.out");
#endif

void solve()
{

}

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

	cout << (2 * 3.14159*r) << "\n";

	return 0;
}

Measured memory_bytes: 3264
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a,i;
  vector<int> adj[n+1];
  for(i=1;i<n;i++)
  {
    cin>>a;
    adj[a-1].push_back(i);
  }
  for(i=0;i<n;i++)
  cout<<adj[i].size()<<endl;
  return 0;
}

Measured memory_bytes: 14500
fun main(args: Array<String>) {
    abc088b()
}

fun abc088b() {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(" ").map { it.toInt() }
        .sortedDescending().mapIndexed { index, i -> Pair(index, i) }

    val (a, b) = aList.partition { it.first % 2 == 0 }

    val answer = a.map { it.second }.sum() - b.map { it.second }.sum()

    println(answer)
}


Measured memory_bytes: 37904
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=510;
int n,m,k,sum,ans,a[N],b[N];
bool work(int x){
	for(int i=1;i<=n;i++)
		b[i]=a[i]%x;
	sort(b+1,b+n+1);
	int l=1,r=n,d=0;
	while(l<r){
		if(b[l]<x-b[r]){
			d+=b[l];
			b[r]+=b[l];
			b[l++]=0;
		}
		else{
			d+=x-b[r];
			b[l]-=x-b[r];
			b[r--]=0;
			if(b[l]==0)
				l++;
		}
		if(d>k)
			return 0;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		sum+=a[i];
	}
	int m=sqrt(sum);
	for(int i=1;i<=m;i++)
		if(sum%i==0){
			if(work(sum/i)){
				printf("%d\n",sum/i);
				return 0;
			}
			if(work(i))
				ans=i;
		}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a , b , c , d;
  cin >> a >> b >> c >> d;
  if (a + b < c + d) {
    cout << "Right" << endl;
  }
  else if (a + b > c + d) {
    cout << "Left" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}

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

struct Card {
    char ch;
    int num;
    bool operator != (Card a) {
        return (this->ch != a.ch || this->num != a.num);
    }
};
Card *master;
int n;

void bubble(Card* d){
    int count = 0;
    bool replaced = true;
    while(replaced){
        replaced = false;
        for(int i = 0; i < n - count - 1; i++){
            if(d[i].num > d[i+1].num){
                Card buf = d[i];
                d[i] = d[i+1];
                d[i+1] = buf;
                replaced = true;
            }
        }
        count++;
    }
}

void selection(Card* d){
    int start = 0;
    for(int i = 0; i < n; i++){
        Card minCa = d[start];
        int min = d[start].num, pos = start;
        for(int k = start; k < n; k++){
            if(d[k].num < min){
                min = d[pos = k].num;
                minCa = d[k];
            }
        }
        d[pos] = d[start];
        d[start++] = minCa;
    }
}

int main() {
    cin >> n;
    master = new Card[n];
    for(int i = 0; i < n; i++){
        cin >> master[i].ch >> master[i].num;
    }
    
    Card d[n], e[n];
    for(int i = 0; i < n; i++){
        d[i] = e[i] = master[i];
    }
    
    bubble(d);
    
    for(int i = 0; i < n; i++){
        cout << (!i ? "" : " ") << d[i].ch << d[i].num;
    }
    cout << endl << "Stable" << endl;
    
    selection(e);
    
    bool isS = true;
    for(int i = 0; i < n; i++){
        if(isS && e[i] != d[i]) isS = false;
        cout << (!i ? "" : " ") << e[i].ch << e[i].num;
    }
    cout << endl << (isS ? "S" : "Not s") << "table" << endl;
    
    
    return 0;
}

Measured memory_bytes: 1192
#include<iostream>
#include<cstdio>
using namespace std;
int s[101],k[101],o[101];
int main()
{
	int i,j,n,m,p;
	cin>>n;
	cin>>m;
	for(i=1;i<=m;i++)cin>>k[i];
	for(i=1;i<=m;i++)
	{
		p=0;
		for(j=1;j<=n;j++)
		{
			cin>>o[j];
			if(o[j]==k[i])
			{
				s[j]++;
			}
			else p++;
		}
		s[k[i]]+=p;
	}
	for(i=1;i<=n;i++)cout<<s[i]<<endl;
	return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main(void){
    int n,k,c=1000000000;
    cin>>n>>k;
    int x[n];
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    
    for(int i=0;i<n-k+1;i++){
        int d = abs(x[i]) + x[i+k-1] - x[i];
        int e = abs(x[n-1-i]) +abs(x[n-1-i]-x[n-i-k]);
        d = min(d,e);
        if(c>d){
            c=d;
        }
    }
    
    cout<<c<<endl;
    
}


Measured memory_bytes: 640
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int P=998244353;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int inc(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
const int N=1e5+5;
int a[N],c[N],res,n,mx;
int main(){
	scanf("%d",&n);
	fp(i,1,n)scanf("%d",&a[i]),++c[a[i]],cmax(mx,a[i]);
	if(a[1]!=0||c[0]>1)return puts("0"),0;
	res=1;
	fp(i,1,mx)res=mul(res,ksm(c[i-1],c[i]));
	printf("%d\n",res);
	return 0;
}

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

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<double> point;
#define F first
#define S second



int main()
{
	#ifdef DGC
		//freopen("a.in", "r", stdin);
		//freopen("b.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	int h, a;
	cin >> h >> a;
	cout << (h+a-1) / a << "\n";

	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(long long i=(long long)(a);i<(long long)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	int a[3], b[3];

	int num[4]={};

	rep(i, 3){
		cin>>a[i]>>b[i];
		num[a[i]-1]++;
		num[b[i]-1]++;
	}

	bool flag=true;
	int odd=0;
	rep(i, 4){
		if(num[i]%2){
			flag=false;
			odd++;
		}
	}

	cout<<YN(flag||odd==2)<<endl;
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const int L=1e5+10;
LL A[L];
LL B[L];
LL D[L];
int main() {
	int N;
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> A[i];
	}
	vector<LL> pos;
	LL s=0;
	int c=0;
	for(int i=0;i<N;i++){
		cin >> B[i];
		if(A[i]>B[i]){
			pos.push_back(A[i]-B[i]);
		}
		else if(A[i]<B[i]){
			s+=B[i]-A[i];
			c++;
		}
	}
	sort(pos.rbegin(),pos.rend());
	if(s==0){
		cout << 0 << endl;
		return 0;
	}
	for(int i=0;i<pos.size();i++){
		s-=pos[i];
		if(s<=0){
			cout << c+i+1 << endl;
			return 0;
		}
	}
	cout << -1 << endl;

	return 0;
}



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

using namespace std;

struct Plant {
    string name;
    int C, P1, P2, S, M;
    Plant(string name, int C, int P1, int P2, int S, int M) :
        name(name), C(C), P1(P1), P2(P2), S(S), M(M){}
    Plant(){}
    
    bool operator < (const Plant &b) const {
        if ((S * M - C) * (b.P1 + b.M * b.P2)
                    != (b.S * b.M - b.C) * (P1 + M * P2)){
            return ((S * M - C) * (b.P1 + b.M * b.P2)
                        < (b.S * b.M - b.C) * (P1 + M * P2));
        }
        return (name > b.name);
    }
};

int main()
{
    int n;
    
    while (scanf("%d", &n) && n){
        vector<Plant> v(n);
        for (int i = 0; i < n; i++){
            char tmp[128];
            int P, A, B, C, D, E, F, S, M;
            scanf("%s %d %d %d %d %d %d %d %d %d", tmp, &P, &A, &B, &C, &D, &E, &F, &S, &M);
            v[i] = Plant((string)tmp, P, A + B + C, D + E, F * S, M);
        }
        
        sort(v.rbegin(), v.rend());
        
        for (int i = 0; i < n; i++){
            printf("%s\n", v[i].name.c_str());
        }
        puts("#");
    }
    
    return (0);
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 510000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  lli A,B,C,D,E,F,N,M,K,L,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> A >> B >> M;
  Vec(P,lli,A,0);
  Vec(Q,lli,B,0);
  rep(i,0,A)cin >> P[i];
  rep(i,0,B)cin >> Q[i];
  Vec(wa,pint,M,pint(0,0));
  Vec(ata,lli,M,0);
  rep(i,0,M)cin >> wa[i].first >> wa[i].second >> ata[i];
  sum=INF;
  rep(i,0,M)chmin(sum,P[wa[i].first-1]+Q[wa[i].second-1]-ata[i]);
  Sort(P);Sort(Q);
  chmin(sum,P[0]+Q[0]);
  Out(sum);
}


Measured memory_bytes: 4224
#include <iostream>
#include <stdio.h>
#include <cctype>
#include <cmath>
#include <math.h>
using namespace std;

void printa(int a[], int n) {
  for (int i=0;i<n;i++) {
    if (i!=(n-1)) {
      cout << a[i] << " ";
    } else {
      cout << a[i] <<endl;
    }
  }
}

int cnt = 0;
void inssort(int a[], int n, int g){
  int save,ind;
  for (int i=g;i<n;i++) {
    save = a[i];
    ind = i;
    for (int j=i-g;(j>=0)&&(save<a[j]);j-=g) {
      a[j+g] = a[j];
      ind = j;
      cnt ++;
    }
    a[ind] = save;
  }
}

int main(){
  int n,g,m=0;
  int a[1000000], b[100];
  cin >> n;
  for (int i=0;i<n;i++) {
    cin >> a[i];
  }
  g = n;
  if (g!=1) {
    while(g>1) {
      ((g/2)!=0) ? (g /= 2) : (g = 1);
      //cout << g << endl;
      b[m++] = g;
      inssort(a,n,g);
    }
  } else {
    m=1;
    b[0]=1;
    inssort(a,n,1);
  }
  cout << m << endl;
  printa(b,m);
  cout << cnt << endl;
  for (int i=0;i<n;i++) {
    cout << a[i] << endl;
  }
}



Measured memory_bytes: 6996
#include <cstdio>
#include <algorithm>

typedef long long LL;

static const int maxm = 3e3 + 10;
static const int INF = 1 << 30;
static const int MOD = 1e9 + 7;

LL f[maxm][maxm][2];
LL ans,n,m;

int main(){
	
	scanf("%lld%lld",&n,&m);
	
	f[0][0][1] = 1;
	for(int i = 1;i <= n;i++) f[0][i][0] = 1;

	if(n == 1){
		LL ans = 2;
		for(int i = 1;i <= m;i++) ans = ans * 2 % MOD;
		return printf("%lld\n",ans),0;
	}
	
	for(int i = 1;i <= m;i++){
		f[i][0][1] = (f[i - 1][0][1] + f[i - 1][1][0] + f[i - 1][1][1]) % MOD;
		f[i][1][0] = (f[i - 1][1][0] + f[i - 1][2][0]) % MOD;
		f[i][1][1] = (f[i - 1][0][1] + f[i - 1][1][0] +
					  2LL * f[i - 1][1][1] + f[i - 1][2][1]) % MOD;
		f[i][n][0] = (f[i - 1][n - 1][0] + f[i - 1][n][0]) % MOD;
		f[i][n][1] = (f[i - 1][n - 1][1] + f[i - 1][n][1]) % MOD;
		for(int j = 2;j < n;j++){
			f[i][j][0] = (f[i - 1][j - 1][0] + 2LL * f[i - 1][j][0] +
						  f[i - 1][j + 1][0]) % MOD;
			f[i][j][1] = (f[i - 1][j - 1][1] + 2LL * f[i - 1][j][1] +
						  f[i - 1][j + 1][1]) % MOD;
		}
	}
	
	for(int i = 0;i <= n;i++) ans = (ans + f[m][i][1]) % MOD;
	
	printf("%lld\n",ans);
	
	return 0;
}


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

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

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

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

long long stoi(string str) {
	long long ret;
	stringstream ss; ss << str;
	ss >> ret;
	return ret;
}

ull gcd(ull a, ull b) {
	if (b > a)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a%b);
}
void solve() {
	int n;
	cin >> n;
	ull ans = 1;
	rep(i, n) {
		ll a;
		cin >> a;
		ans = a/gcd(a, ans)*ans;
	}
	P(ans);
}

int main() {
	solve();
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
int A,B,C,k = 0,i,m = 0;
cin>>A>>B>>C;
while(1){
k = m/7;
i = A * m + B * k;
if(i >= C)
break;
m++;
}
cout<<m<<endl;
return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll modinv(ll a){
  ll b = mod,u = 1,v = 0,t;
  while(b){
    t = a/b;
    a -= t*b;swap(a,b);
    u -= t*v;swap(u,v);
  }
  u %= mod;
  if(u < 0) u += mod;
  return u;
}
int main(){
  ll S,i,ans = 0;scanf("%lld",&S);
  S -= 3;
  ll P[2001];P[0] = P[1] = 1;
  for(i=2;i<=2000;i++) P[i] = P[i-1]*i%mod;
  for(i=1;S>=0;i++,S-=3){
    ans = (ans+P[S+i-1]*modinv(P[S])%mod*modinv(P[i-1]))%mod;
  }
  printf("%lld\n",ans);
}

Measured memory_bytes: 3836
N = int(input())
T, A = 1, 1

for _ in range(N):
    t, a = map(int, input().split())
    if T <= t and A <= a:
        T, A = t, a
        continue
    z = max(-(-T//t), -(-A//a))
    T, A = t*z, a*z

print(T+A)

Measured memory_bytes: 3060
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func checkString(char rune) bool {
	return strings.Contains("ATCG", string(char))
}

func main() {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	input := stdin.Text()
	var size = 0
	var maxSize = 0
	for i := range input {
		if checkString(rune(input[i])) {
			size += 1
			if size > maxSize {
				maxSize = size
			}
		} else {
			size = 0
		}
	}
	fmt.Println(maxSize)
}


Measured memory_bytes: 640
import sys

def check_alloc(weights, cnt, cpct):	
	num = 1
	cur = 0
	for i in range(len(weights)):
		w = weights[i]
		if cur + w > cpct:
			cur = w
			num += 1
			if num > cnt or cur > cpct:
				return False
		else:
			cur += w
	return True

n, k = map(int, input().split())
weights = [0] * n
sum = 0
maxi = 0
for i in range(n):
	weight = int(input())
	weights[i] = weight
	sum += weight
	maxi = max(maxi, weight)

if k == 1:
	print(sum)
	sys.exit()

start = maxi
end = sum
mid = 0
while start <= end:
	mid = int(start + (end - start) / 2)
	can_alloc = check_alloc(weights, k, mid)
	if can_alloc == False:
		start = mid + 1
	else:
		if start == end: break
		end = mid

print(mid)



Measured memory_bytes: 9420
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define bp __builtin_popcount
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it : t)cout<<it<<" ";}
inline int powerexp(int a, int b, int m = MOD){ int res = 1;while(b){if(b&1)res = res * a % m;a = a * a % m,b >>= 1;}return res % m;}
inline int modinv(int a){ return powerexp(a,MOD-2,MOD);}
inline int lcm(int a, int b){ int g = __gcd(a,b);return a/g*b;}
inline int add(int x, int y){ x += y; if (x >= MOD) x -=  MOD; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % MOD;}
inline int sub(int x, int y){ x -= y; if (x<0) x += MOD; return x ;}

//-------------------< start here >-------------------------// 

void print_vector(vector<int> v){
  for(int i = 0; i < (int)v.size(); i++){
	  if (i == (int)v.size() - 1) cout << v[i];
	  else cout << v[i] << " ";  
	}
  cout << endl;	
}

void solve(){
  	int n, m;
  	vector<int> a, b;
  	cin >> n;
  	for(int i = 0; i < n; i++){
	  int x;
	  cin >> x;
	  a.push_back(x);	
	}
	cin >> m;
	for(int i = 0; i < m; i++){
	  int x;
	  cin >> x;
	  b.push_back(x);	
	}
   bool ok = true;
   for(int i = 0; i < m; i++){
	   if (!binary_search(all(a), b[i])){ok = false; break;}
	   else continue; 
	  }
  if (ok) cout << 1 << endl;
  else cout << 0 << endl;
}

//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr << "time elapsed " << (double)clock()/CLOCKS_PER_SEC << endl;
   #endif
}



Measured memory_bytes: 7380
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	int a, b;
	cin >> a >> b;
	if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) cout << "Possible\n";
	else cout << "Impossible\n";
}

Measured memory_bytes: 256
import sys
N,M=map(int,input().split())
if M==0:
  if N==1:
    ans=0
  else:
    ans=10**(N-1)
  print(ans)
  sys.exit()
listSC=[]  
for k in range(M):
  s,c=map(int,input().split())
  listSC+=[[s,c]]  
MAX=0  
if N==1:
  for s,c in listSC:
    MAX=max(MAX,c)
  if MAX==0:
    print(0)
    sys.exit()    
for i in range(10**(N-1),10**N):
  A=list(str(i))
  for k in range(M):
    if A[listSC[k][0]-1]!=str(listSC[k][1]):
      break
    if k==M-1:
      ans=i
      print(ans)
      sys.exit()
  if i==10**N-1:
    print(-1)

Measured memory_bytes: 3064