akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;

int main(){
    int a[6];
    for(int i=0;i<6;i++){
        cin >> a[i];
    }
    
    int n[4];
    for(int i=0;i<4;i++){
        n[i]=0;
        for(int j=0;j<6;j++){
            if(i+1==a[j])n[i]++;
        }
        //cout << n[i];
    }
    

    int n1,n2;
    n1 =n2 =0;
    for(int i=0;i<4;i++){
        if(n[i]==1)n1++;
        else if(n[i]==2)n2++;
    }
    if(n1==2 && n2==2)cout << "YES" << endl;
    else cout << "NO" <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
signed main(){
  int n , m , ket[3] , s , c;
  bool f=true;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    ket[i]=-1;
  }
  for(int i=0;i<m;i++){
    cin>>s>>c;
    if(ket[s-1] != c && ket[s-1] != -1){
      f=false;
    } else { 
      ket[s-1] = c;
    }
  }
  
  if(ket[0] == 0 && n > 1){
    f=false;
  }
  if(f){
    if(n == 1){
      cout<<max(ket[0],0);
    }
    else{
      cout<<max(ket[0],1);
    }
    for(int i=1;i<n;i++){
      cout<<max(ket[i],0);
    }
  } else {
    cout<<"-1";
  }
  cout<<endl;
  return(0);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define gcd(a,b)     __gcd(a,b)
#define lcm(a,b)     (a*b)/gcd
#define rep(i,n)     for(int i=0;i<n;i++)
#define Rep(i,n)     for(int i=1;i<=n;i++)
#define REP(i,j,n)   for(int i=j;i<=n;i++)
#define FOR(i,n)   for(int i=n;i>=0;i--)
#define n_digit(n)   floor(log10(n))+1





int main()
{


    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
   char  s;
   cin>>s;
   if(s>='A'&&s<='Z') cout<<"A"<<endl;
   else cout<<"a"<<endl;
   return 0;
    
}

Measured memory_bytes: 3648
// 最長共通部分裂問題

#include <bits/stdc++.h>

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define INTMAX 1000000000

using namespace std;
typedef long long ll;
typedef pair<ll ,ll> P;
const ll mod = 1e9+7;
const long double EPS = 0.0000000001;


int n;
int main(){
	cin >> n;
	for(int a = 0; a < n; a++){
		string x,y;
		cin >> x;
		cin >> y;

		// dp start
		int W = x.size(); int H = y.size();
		int dp[H+1][W+1] = {0};
		for(int i = 0; i < H+1; i++){
			dp[i][0] = 0;
		}
		for(int i = 0; i < W+1; i++){
			dp[0][i] = 0;
		}
		for(int i = 1; i < H+1; i++){
			for(int j = 1; j < W+1; j++){
				if(x[j-1] == y[i-1]){
					dp[i][j] = max(max(dp[i-1][j-1] + 1, dp[i-1][j]), dp[i][j-1]);
				}else{
					dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		// cout << endl;
		// for(int i = 0; i < H+1; i++){
		// 	for(int j = 0; j < W+1; j++){
		// 		cout << dp[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }

		cout << dp[H][W] << endl;
	}
}


Measured memory_bytes: 7128
#include <stdio.h>

int n, A[2000];

int solve(int i, int m){
  int res;
  if(m == 0) return 1;
  if(i >= n) return 0;
  res = solve(i + 1, m) || solve(i + 1, m - A[i]);
  return res;
}

int main(){
  int m,q,i,tmp[2000],j;

  scanf("%d",&n);

  for(i = 0; i < n; i++){
    scanf("%d",&A[i]);
  }

  scanf("%d",&q);

  for(i = 0; i < q; i++){
    scanf("%d",&m);
    if( solve(0,m)) printf("yes\n");
    else printf("no\n");
  }
  
  return 0;
}





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

int main(){
    int n;
    cin >> n;
    if(n==3){
        cout << 2 << ' ' << 5 << ' ' << 63 << endl;
        return 0;
    }
    else if(n==4){
        cout << 2 << ' ' << 5 << ' ' << 20 << ' ' << 63 << endl;
        return 0;
    }
    vector<long long> ans;
    for(int i=0; i<n/8; i++){
        ans.push_back(2+i*12);
        ans.push_back(3+i*12);
        ans.push_back(4+i*12);
        ans.push_back(6+i*12);
        ans.push_back(8+i*12);
        ans.push_back(9+i*12);
        ans.push_back(10+i*12);
        ans.push_back(12+i*12);
    }
    int m = n%8;
    int k = n/8;
    if(m!=0){
        ans.push_back(6+k*12);
        if(m%2==0) ans.push_back(12+k*12);
        m = (m-1)/2;
        if(m > 0) {
            ans.push_back(2+k*12);
            ans.push_back(4+k*12);
            m--;
        }
        if(m > 0) {
            ans.push_back(3+k*12);
            ans.push_back(9+k*12);
            m--;
        }
        if(m > 0) {
            ans.push_back(8+k*12);
            ans.push_back(10+k*12);
            m--;
        }
    }
    for(int i=0; i<n; i++){
        cout << ans[i] << ' ';
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;


public class Main{

	public static void main(String args[]){

		Scanner sc = new Scanner(System.in);

		int n=sc.nextInt();
		int k=sc.nextInt();

		String s=sc.next();

		char c[]=s.toCharArray();

		if(c[k-1]=='A')c[k-1]='a';
		else if(c[k-1]=='B')c[k-1]='b';
		else c[k-1]='c';

		for(int i=0;i<n;++i){
			System.out.print(c[i]);
		}
		System.out.println();

	}
}

Measured memory_bytes: 21844
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    cin >> n;
    int r_A = 0,l_B = 0,both = 0,count = 0;
    for(int i = 0;i < n;i++)
    {
        string s;
        cin >> s;
        for(int i = 0;i + 1 < s.size();i++)
        {
            if(s[i] == 'A' && s[i + 1] == 'B')
            {
                count++;
                s[i] = 'X';
                s[i + 1] = 'X';
            }
        }
        if(s[0] == 'B' && s[s.size() - 1] == 'A')
        {
            both++;
        }
        else if(s[0] == 'B')
        {
            l_B++;
        }
        else if(s[s.size() - 1] == 'A')
        {
            r_A++;
        }
    }
    if(both == 0)
    {
        cout << count + min(r_A,l_B) << "\n";
    }
    else if(r_A + l_B > 0)
    {
        cout << count + both + min(r_A,l_B) << "\n";
    }
    else
    {
        cout << count + both - 1 << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

int main() {
    string S;
    cin >> S;
    cout << S.substr(0, S.size() - 8) << endl;
}

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

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    for(int i=0;i<100;i++)
    {if((c-b)<=0)
    {cout<<"Yes";
    break;
    }
    else
    {c=c-b;
    }
    if((a-d)<=0)
    {cout<<"No";
    break;
    }
    else
    {a=a-d;
    }
    }

    return 0;
}

Measured memory_bytes: 3592
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<iomanip>
#include<map>
#include<utility>
#include<string>
#include<unordered_map>
#include <queue>

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

using namespace std;

#define min_3(a, b, c) min(a, min(b, c))
#define max_3(a, b, c) max(a, max(b, c))
typedef long long ll;

int main(){
    int h, w;
    cin >> h >> w;
    char s[h][w];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> s[i][j];
        }
    }

    int vx[4] = {1, 0, -1, 0};
    int vy[4] = {0, 1, 0, -1};
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(s[i][j] == '.') continue;
            bool brack_exist = false;
            for(int k = 0; k < 4; k++){
                int y = vy[k];
                int x = vx[k];
                if(i+y<=-1 || i+y>=h || j+x<=-1 || j+x>=w) continue;
                if(s[i][j] == s[i+y][j+x]){
                    brack_exist = true;
                    break;
                }
            }
            if(brack_exist == false){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
n=int(input())
c=[0]*(n-1)
s=[0]*(n-1)
f=[0]*(n-1)
for i in range(n-1):
    c[i],s[i],f[i]=map(int,input().split())

for i in range(n):
    t=0
    for j in range(i,n-1):
        if t<s[j]:
            t=s[j]
        elif t%f[j]!=0:
            t=t+f[j]-t%f[j]
        t+=c[j]
    print(t)

Measured memory_bytes: 3064
import sys
input = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7

N = int(input())

#A=0, G=1, C=2, T=3と考える

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]

#Tは制約に入らないので、スタートをTTT+Sみたいな感じに考える。ここで0とか1とか2を使うといらないところでcontinueしてしまう。
dp[0][3][3][3] = 1

for l in range(N):
    #左から3番目
    for last3 in range(4):
        #左から2番目
        for last2 in range(4):
            #左から1番目
            for last1 in range(4):
                #条件に当てはまるものないときはcontinue
                if dp[l][last3][last2][last1] == 0: 
                    continue
                #追加する文字
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1: continue
                    if last2 == 0 and last1 == 1 and now == 2: continue
                    if last2 == 2 and last1 == 0 and now == 1: continue
                    if last3 == 0 and last1 == 2 and now == 1: continue
                    if last3 == 0 and last2 == 2 and now == 1: continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD

#長さNの全部の答えを回収する
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= MOD
print(ans)

Measured memory_bytes: 48752
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	cin>>a;
	int b[a];
	for(int i=0;i<a;i++)
	{
		cin>>b[i];
	}
	if(a==0&&b[0]==1)
	{
		cout<<0;
		return 0;
	}
	int c=1;
	bool f=false;
	for(int i=0;i<a;i++)
	{
		if(b[i]==c)
		{
			c++;
			f=true;
		}
	}
	if(f==false)
	{
		cout<<"-1";
		return 0;
	}
	cout<<a-c+1;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

int n, m;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

    cin >> n >> m;
    vector<int> d(n, -1);

    for (int i = 0; i < m; ++i) {
        int s, c;
        cin >> s >> c;
        if ((d[s-1] != -1 && d[s-1] != c) || (n != 1 && s == 1 && c == 0)) {
            cout << -1 << endl;
            return 0;
        }
        d[s-1] = c;
    }
	
    if (d[0] == -1)
        d[0] = (n == 1 ? 0 : 1);

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = ans * 10 + (d[i] == -1 ? 0 : d[i]);
    }
    
    cout << ans << endl;
	return 0;
}

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

int main(){
    int n,k;
    cin >> n >> k;
    char str[64];
    cin >> str;

    if(str[k-1] > 90){
        str[k-1] -= 32;
    }else{
        str[k-1] += 32;
    }

    cout << str << endl;
    return 0;
    

}

Measured memory_bytes: 3624
function Main(input) {
  input = input.split('\n');
  //文字列から10進数に変換するときはparseIntを使います
  var a = parseInt(input[0], 10);
  var b = parseInt(input[1], 10);
  var c = parseInt(input[2], 10);
  var x = parseInt(input[3], 10);

  var ans = 0;
  for (var i = 0; i <= a; i++) {
    for (var j = 0; j <= b; j++) {
      for (var k = 0; k <= c; k++) {
        if (i * 500 + j * 100 + k * 50 === x) ans++;
      }
    }
  }

  //出力
  console.log('%d', ans);
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
#include<iostream>
using namespace std;
int t,a;
string s;
main()
{
cin>>t;
  t=0;
  cin>>s;
  for(int i=0;i<s.size();i++)
  {
if(s[i]=='I')t++;else t--;
    if(a<t)a=t;
  }
  cout<<a<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  VV<> g(3 * n);
  auto _ = [&](int v, int i) -> int { return 3 * v + i % 3; };
  while (m--) {
    int u, v; cin >> u >> v, --u, --v;
    for (int i = 0; i < 3; ++i) {
      g[_(u, i)].push_back(_(v, i + 1));
    }
  }
  int s, t; cin >> s >> t, --s, --t;
  queue<int> que;
  V<> d(3 * n, -1);
  d[_(s, 0)] = 0;
  que.push(_(s, 0));
  while (!que.empty()) {
    int v = que.front(); que.pop();
    for (int w : g[v]) if (d[w] == -1) {
      d[w] = d[v] + 1;
      que.push(w);
    }
  }
  cout << (d[_(t, 0)] != -1 ? d[_(t, 0)] / 3 : -1) << '\n';
}

Measured memory_bytes: 17792
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**19
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,K = LI()
    px = [LI() for _ in range(N)]
    px.sort()

    ans = INF
    for k in range(K,N+1):
        for i in range(N-k+1):
            w = px[i+k-1][0] - px[i][0]
            py = []
            for _,y in px[i:i+k]:
                py.append(y)
            py.sort()
            min_y = INF
            for j in range(k-K+1):
                min_y = min(min_y,py[K+j-1]-py[j])
            ans = min(ans,w * min_y)
    print(ans)

if __name__ == '__main__':
    main()

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

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

  string s;
  int q;
  cin >> s >> q;

  bool rev = false;
  string head, tail;

  while (q --> 0) {
    int t;
    cin >> t;

    if (t == 2) {
      int f;
      char c;
      cin >> f >> c;

      if (rev) {
        if (f == 1) tail += c;
        else head = c + head;
      } else {
        if (f == 1) head = c + head;
        else tail += c;
      }
    } else rev ^= 1;
  }

  if (rev) {
    reverse(head.begin(), head.end());
    reverse(tail.begin(), tail.end());
    reverse(s.begin(), s.end());

    cout << tail << s << head << '\n';
  } else cout << head << s <<  tail << '\n';

  return (0);
}


Measured memory_bytes: 4032
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int N = 2e5+10;
int a[N];
int main(){
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=k;++i){
        cin >> a[i];
    }
    int ans = n;
    for(int i=2;i<=k;++i){
        ans = min(ans, n-a[i]+a[i-1]);
    }
    ans = min(ans,a[k]-a[1]);
    cout << ans <<'\n';
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

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

using namespace std;

int main() {
	int n,k;
	cin >> n>>k;
	vector<int>p(n);
	rep(i,n){
		cin >> p[i];
	}

	sort(p.begin(),p.end());

	int ans =0;
	rep(i,k){
		ans += p[i];
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 3640
import math
X = int(input())
a = 0
while(a==0):
    if X == 2:
        print(2)
        break
    for x in range(2,math.floor(math.sqrt(X))+1):
        if X % x == 0:
            break
        if x == math.floor(math.sqrt(X)):
            print(X)
            a = 1
    X += 1


Measured memory_bytes: 3060
#include<stdio.h>
#include<limits.h>

#define MAX 101

void MatrixChain();

int n,p[MAX],M[MAX][MAX];

int main(){

  int i,r[MAX],c[MAX];

  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d%d",&p[i-1],&p[i]);
  }

  MatrixChain();
  
  printf("%d\n",M[1][n]);

  return 0;
}

void MatrixChain(){
  int i,j,k,l,q;

  for(i=1;i<n;i++) M[i][i]=0;

  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      M[i][j] = INT_MAX;
      for(k=i;k<j;k++){
	q=M[i][k]+M[k+1][j]+p[i-1]*p[k]*p[j];
	if(q<M[i][j]) M[i][j]=q;
      }
    }
  }
}

Measured memory_bytes: 636
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] edge = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				edge[i][j] = sc.nextInt();
			}
		}
		sc.close();

		long ans = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				ans += Math.min(edge[i][j], edge[j][i]);
			}
		}
		System.out.println(ans);

	}
}

Measured memory_bytes: 31344
#include <stdio.h>

int sosuu_num;
int sosuu_sum[10000];

void make_sosuu_list(void) {
	char is_sosuu[10001];
	int i,j;
	for(i=0;i<=10000;i++)is_sosuu[i]=1;
	is_sosuu[0]=is_sosuu[1]=0;
	for(i=2;i<=10000;i++) {
		if(is_sosuu[i]) {
			for(j=i+i;j<=10000;j+=i)is_sosuu[j]=0;
		}
	}
	sosuu_num=1;
	sosuu_sum[0]=0;
	for(i=0;i<=10000;i++) {
		if(is_sosuu[i]) {
			sosuu_sum[sosuu_num]=sosuu_sum[sosuu_num-1]+i;
			sosuu_num++;
		}
	}
}

int nibun_tansaku(int start,int end,int searchfor) {
	int left,right,mid;
	left=start;right=end-1;
	while(left<=right) {
		mid=(left+right)/2;
		if(sosuu_sum[mid]==searchfor)return mid;
		else if(sosuu_sum[mid]<searchfor)left=mid+1;
		else right=mid-1;
	}
	return -1;
}

int main(void) {
	int query;
	int i,result;
	make_sosuu_list();
	while(1) {
		scanf("%d",&query);
		if(query==0)break;
		result=0;
		for(i=0;i<sosuu_num;i++) {
			if(nibun_tansaku(i+1,sosuu_num,query+sosuu_sum[i])>=0) {
				result++;
			}
		}
		printf("%d\n",result);
	}
	return 0;
}

Measured memory_bytes: 0
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int INF=1e10;
int MOD=1e9+7;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
}
int kurai(int a,int b){
  int m=pow(10,b),n=pow(10,b-1);
  return (a%m)/n;
}
int ketawa(int a){
  int k=0;
  rep(i,keta(a)){
  k+=kurai(a,i+1);
  }
  return k;
}
int gcd(int a,int b){
  if(a%b==0)
    return b;
  return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int mid(int a,int b,int c){
  vector<int> k(3);
  k[0]=a;k[1]=b;k[2]=c;
  sort(all(k));
  return k[1];
}
bool sosuu(int a){
  bool b=1;
  if(a<=1)
    return 0;
  else{
  rep1(i,sqrt(a)-1){
  if(a%(i+1)==0)
  b=0;
  }
  return b;
  }
}
int modpow(int a,int b,int m=MOD){
 if(!b)return 1; if(b&1)return modpow(a,b-1,m)*a%m;
 int memo = modpow(a,b>>1,m);
 return memo*memo%m;
}
int fact_mod(int n) {
    int f=1; 
for(int i=2;i<n+1;i++) f=f*(i%MOD)% MOD;
    return f;
}
int mod_pow(int x,int n) {
    int res=1;
    while(n>0){
        if(n&1) res=(res*x)%MOD; 
        x=(x*x)%MOD;        
n>>=1; 
    }
    return res;
}
int c_mod(int n, int r) {
    if(r>n-r) r=n-r;
    if(r==0) return 1;
    int a=1;
    rep(i,r) 
a=a*((n-i)%MOD)%MOD;
    int b=mod_pow(fact_mod(r), MOD-2);
    return (a%MOD)*(b%MOD)%MOD;
}
signed main(){
  int a;
  cin>>a;
  vector<int> b(100000,0);
  rep1(i,100)rep1(j,100)rep1(k,100){
  b[i*i+j*j+k*k+i*j+j*k+k*i-1]++;
  }
  rep(i,a){
  out(b[i]);
  }
}


Measured memory_bytes: 4036
S = input()

cnt = 0
for i in range(3):
    n = 0
    for j in range(i + 1, 4):
        if S[i] == S[j]:
            n += 1
    if n == 1:
        cnt += 1

if cnt == 2:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
main () {
  int a, b, i, j;
  while(~scanf("%d %d", &a, &b)) {
    if (!a && !b) return 0;
    for (i = 0; i < a; i++) {
      for (j = 0; j < b; j++) putchar('#');
      putchar('\n');
    }
    putchar('\n');
  }
}


Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
int N;
string henkan(string s){
    //今まで出てきた文字数を確認する
    map<char, int> chars;
    map<char, char> char2char;
    string res = "";
    rep(i,s.size()){
        if(chars[s[i]] == 0){
            char bck = char('a' + chars.size()-1);
            res.push_back(bck);
            chars[s[i]]++;
            char2char[s[i]] = bck;
        }
        else{
            res.push_back(char2char[s[i]]);
        }
    }
    return res;
}
map<string, int> maps;
set<string> ans;
void dfs(string s){
    string x = henkan(s);
    if(maps[x])return;
    maps[x]++;
    if((int)x.size() == N){
        ans.insert(x);
        return;
    }
    for(int i = 0; i < N;i++){
        string nx = x;
        nx.push_back(char(i + 'a'));
        dfs(nx);
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    cin >> N;
    dfs("");
    for(auto y:ans){
        cout << y << endl;
    }
}

Measured memory_bytes: 24704
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int a = sc.nextInt();
        int b = sc.nextInt();

        if (a == b) {
            System.out.println("Draw");
            return;
        }

        if (a == 1) {
            System.out.println("Alice");
            return;
        }

        if (b == 1) {
            System.out.println("Bob");
            return;
        }

        System.out.println(a > b ? "Alice" : "Bob");
    }
}

Measured memory_bytes: 21844
import java.util.*;
import java.io.*;
public class Main {
	static long[] mmax=new long[812345];
	static long[] lazy=new long[812345];
	static void pushup(int x) {
		mmax[x]=Math.max(mmax[x<<1],mmax[x<<1|1]);
	}
	static void pushdown(int x) {
		mmax[x<<1]+=lazy[x];
		lazy[x<<1]+=lazy[x];
		mmax[x<<1|1]+=lazy[x];
		lazy[x<<1|1]+=lazy[x];
		lazy[x]=0;
	}
	static void update(int x,int L,int R,int l,int r,long v) {
		if (l<=L&&r>=R) {
			mmax[x]+=v;
			lazy[x]+=v;
			return;
		}
		pushdown(x);
		int m=(L+R)>>1;
		if (l<=m) update(x<<1,L,m,l,r,v);
		if (m<r) update(x<<1|1,m+1,R,l,r,v);
		pushup(x);
	}
	static long query(int x,int L,int R,int l,int r) {
		if (l<=L&&r>=R) return mmax[x];
		pushdown(x);
		int m=(L+R)>>1;
		long ret=0;
		if (l<=m) ret=Math.max(ret,query(x<<1,L,m,l,r));
		if (m<r) ret=Math.max(ret,query(x<<1|1,m+1,R,l,r));
		pushup(x);
		return ret;
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int n=(int)in.nval;
		in.nextToken();
		int m=(int)in.nval;
		ArrayList<Long>[] eve=new ArrayList[n+1];
		for (int i=1;i<=n;++i)
			eve[i]=new ArrayList();
		for (int i=0;i<m;++i) {
			in.nextToken();
			int l=(int)in.nval;
			in.nextToken();
			int r=(int)in.nval;
			in.nextToken();
			long a=(long)in.nval;
			if (a>0) eve[r].add(2000000000L*l+a);
			else eve[r].add(-2000000000L*l+a);
		}
		for (int i=1;i<=n;++i) {
			long tmp=Math.max(0L,query(1,0,n,0,i-1));
			update(1,0,n,i,i,tmp);
			for (int j=0;j<eve[i].size();++j) {
				int l=(int)(Math.abs(eve[i].get(j))/2000000000);
				long w=eve[i].get(j)%2000000000;
				if (w>1000000000) w-=2000000000;
				update(1,0,n,l,i,w);
			}
		}
		out.println(Math.max(0L,mmax[1]));
		out.flush();
	}
}

Measured memory_bytes: 83444
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
  public static void main(String[] args) {
    try {
      BufferedReader stdReader =
        new BufferedReader(new InputStreamReader(System.in));
      String line;
      while ((line = stdReader.readLine()) != null) { 
    	  int x = Integer.parseInt(line);
        System.out.println(x*x*x);
      }
      stdReader.close();
    } catch (Exception e) {
      e.getStackTrace();
      /*返却値は0固定*/
      System.exit(0); 
    }
  }
}

Measured memory_bytes: 17024
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <ctime>
#define ri register
#define inf 0x7fffffff
#define E (1)
#define mk make_pair
#define int long long
using namespace std; const int N=400010, Mod=998244353;
inline int read()
{
	int s=0, w=1; ri char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar(); return s*w;
}
void print(int x) {if(x<0) x=-x, putchar('-'); if(x>9) print(x/10); putchar(x%10+'0'); }
int n,a[N],b[N];
signed main()
{
	n=read();
	for(ri int i=1;i<=n;i++) a[i]=read(), b[i]=read();
	sort(a+1,a+1+n), sort(b+1,b+1+n);
	int p,q; p=q=0;
	if(n&1ll) p=a[(n+1)/2], q=b[(n+1)/2];
	else p=a[n/2]+a[n/2+1], q=b[n/2]+b[n/2+1];
	printf("%lld\n",q-p+1);
	return 0;
}

Measured memory_bytes: 6832
#include <bits/stdc++.h>
#define ff { ios_base::sync_with_stdio(false);cin.tie(NULL);}
using namespace std;

typedef long long ll;
 ll  pp=1e9+7; 
double pi=3.141592653589793238;
  
 int main() {
        ff;
        char c;
        cin>>c;
        if(isupper(c))cout<<"A"<<endl;
        else cout<<"a"<<endl;
		
    return 0;
}

            
		
        
           
  

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define IN freopen("hard1.txt","r",stdin)
#define OUT freopen("hard1.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG pf("Hi\n")
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 1000005

using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<i64, i64> pii;

#define INF 1000000000000000000LL
#define alpha 26
#define mod 998244353LL
#define maxn 500005
#define LOG 18

char s[1005][1005] ;

int main()
{
    int n , m , a , b ;

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

    int N = n , M = m ;

    for(int i=0 ; i<n ; i++)
    {
        for(int j=0 ; j<m ; j++) s[i][j] =  '.' ;
        s[i][m] = '\0' ;
    }

    if( n%2==1 )
    {
        for(int i=m-1 ; i-1>=0 ; i-=2)
        {
            if( a==0 ) continue ;
            a-- ;
            s[n-1][i] = '>' ;
            s[n-1][i-1] = '<' ;
        }
        n-- ;
    }
    if( m%2==1 )
    {
        for(int i=0 ; i+1<n ; i+=2)
        {
            if(b==0) continue ;
            b-- ;
            s[i][m-1] = '^' ;
            s[i+1][m-1] = 'v' ;
        }
        m-- ;
    }

//    printf("--- %d %d\n",a,b) ;

    if( n+1 == N && m+1==M && n>=2 && m>=2 && a%2==1 && b%2==1 )
    {
        s[n][0] = 'v' ; s[n-1][0] = '^' ;
        b-- ;
        s[n-2][0] = '<' ; s[n-2][1] = '>' ;
        a-- ;

        for(int j=m-1 ; j>1; j--)
        {
            if(b==0) break ;
            s[n-2][j] = '^' ;  s[n-1][j] = 'v' ;
            b-- ;
        }
        for(int j=2 ; j+1<m ; j+=2)
        {
            if(a==0) break ;
            if( s[n-2][j+1]!='.' || s[n-2][j] !='.' ) break ;
            s[n-2][j] = '<' ; s[n-2][j+1] = '>' ;
            a-- ;
        }
        for(int j=1 ; j+1<m ; j+=2)
        {
            if(a==0) break ;
            if( s[n-1][j]!='.' || s[n-1][j+1]!='.' ) break ;
            s[n-1][j] = '<' ; s[n-1][j+1] = '>' ;
            a-- ;
        }
        n -= 2 ;
    }

  /*  printf("------------ %d %d\n",a,b) ;

    for(int i=0 ; i<N ; i++)
    {
        printf("%s",s[i]) ;
        printf("\n") ;
    }
*/
    for(int j=0 ; j+1<m ; j+=2)
    {
        for(int i=0 ; i<n ; i++)
        {
            if(a==0) continue ;
            s[i][j] = '<' ; s[i][j+1] = '>' ;
            a-- ;
        }
    }

//    printf("-- %d %d\n",a,b) ;

    for(int j=0 ; j<m ; j++)
    {
        for(int i=0 ; i+1<n ; i++)
        {
            if( s[i][j]!='.' ) continue ;
            if(b==0) continue ;
            s[i][j] = '^' ;
            s[i+1][j] = 'v' ;
            b-- ;
            i++ ;
        }
    }

    if(a==0 && b==0)
    {
        printf("YES\n") ;
        for(int i=0 ; i<N ; i++) printf("%s\n",s[i]) ;
        return 0 ;
    }
    else printf("NO\n") ;

    return 0 ;
}


Measured memory_bytes: 2176
#include <iostream>

int main()
{
    uint32_t mon_hp;
    uint32_t arai_waza;
    uint32_t buf;
    uint32_t dmg_sum = 0;

    std::cin >> mon_hp >> arai_waza;
    for(int i = 0; i < arai_waza; i++){
        std::cin >> buf;
        dmg_sum += buf;
    }

    if(dmg_sum >= mon_hp){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#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=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    int n;
    cin >> n;
    int c = 0;
    int next = 1;
    REP(i, n) {
        int tmp;
        cin >> tmp;
        if (tmp == next) {
            c++;
            next++;
        }
    }
    if (c == 0) {
        cout << -1 << endl;
    } else {
        cout << n - c << endl;
    }
    return 0;
}

Measured memory_bytes: 384
X, N = list(map(int, input().split()))
if N == 0:
    P = [None]
else:
    P = list(map(int, input().split()))

P.sort()

if X not in P:
    ans = X
else:
    for i in range(101):
        a = X - i
        b = X + i
        if a not in P:
            ans = a
            break
        elif b not in P:
            ans = b
            break
print(ans)

Measured memory_bytes: 9196
#include<iostream>
using namespace std;
 
int main( ){
    int a, b;
    char op;
    
    while(1){
        cin >> a >> op >> b;
        if (op == '?' ) break;
        
        if ( op == '+') cout << a + b << endl;
        else if ( op == '-' ) cout << a - b << endl;
        else if ( op == '*' ) cout << a * b << endl;
        else if ( op == '/' ) cout << a / b << endl;
            }              
        
    return 0;
}   

Measured memory_bytes: 1160
def solve(N, Hs):
    def split(s, e):
        d = []
        for i in range(s, e):
            if Hs[i] != 0 and len(d) % 2 == 0:
                d.append(i)
            elif Hs[i] == 0 and len(d) % 2 == 1:
                d.append(i)
        if len(d) % 2 == 1:
            d.append(e)

        return [(d[2 * i], d[2 * i + 1]) for i in range(len(d) // 2)]

    def f(s, e):

        ans = 0
        if s >= len(Hs) or s > e:
            return 0
        if s == e:
            return Hs[s]
        m = min(Hs[s:e])
        c = Hs[s:e].count(0)
        if len(Hs[s:e]) == c:
            return 0
        if m == 0:
            l = split(s, e)
            for ss, ee in l:
                ans += f(ss, ee)
        else:
            ans += m
            for i in range(s, e):
                Hs[i] -= m
            ans += f(s, e)
        return ans

    return f(0, N)

if __name__ == "__main__":
    N = int(input())
    Hs = list(map(int, input().split(" ")))
    print(solve(N, Hs))


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

int main()
{
    int N;
    cin>>N;
    vector<int>A(N),B(N);
    for(int i=1;i<N;i++){
        cin>>A.at(i);
    }
    for(int i=1;i<N;i++){
        B.at(A.at(i)-1)+=1;
    }
    for(int i=0;i<N;i++){
        cout<<B.at(i)<<endl;
    }
}

Measured memory_bytes: 4788
#!/usr/bin/env python3
import sys
import math
import collections
import itertools
INF = float("inf")


def trial_division_sqrt(n):
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


def solve(N: int):
    primes = eratosthenes_sieve(N)

    pc = collections.Counter()
    for n in range(1, N+1):
        pc += trial_division_sqrt(n)
    ans = 0

    for p in itertools.combinations(primes, 3):
        # 2 4 4
        if pc[p[0]] >= 2 and pc[p[1]] >= 4 and pc[p[2]] >= 4:
            ans += 1
        # 4 2 4
        if pc[p[0]] >= 4 and pc[p[1]] >= 2 and pc[p[2]] >= 4:
            ans += 1
        # 4 4 2
        if pc[p[0]] >= 4 and pc[p[1]] >= 4 and pc[p[2]] >= 2:
            ans += 1

    for p in itertools.combinations(primes, 2):
        # 2 24
        if pc[p[0]] >= 2 and pc[p[1]] >= 24:
            ans += 1
        # 24 2
        if pc[p[0]] >= 24 and pc[p[1]] >= 2:
            ans += 1

        if pc[p[0]] >= 4 and pc[p[1]] >= 14:
            ans += 1
        if pc[p[0]] >= 14 and pc[p[1]] >= 4:
            ans += 1

    for p in primes:
        if pc[p] >= 74:
            ans += 1

    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


int main() {
	int n;
	cin >> n;
	if (n % 2 == 0) {
		cout << n / 2 << endl;
	}
	else cout << n / 2 + 1 << endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public static void main(String[] args){
		String		str;
		int a,b,multiple = 0,divisor = 0;
		ArrayList<String>	list	= new ArrayList<String>();
		ArrayList<Integer>	intList	= new ArrayList<Integer>();
		try {
			BufferedReader br	=	new BufferedReader(new InputStreamReader(System.in));
			while((str=br.readLine())!=null){
				list.add(str);						//行単位でArrayListに追加
			}
			br.close();
		} catch (IOException e) {
			e.printStackTrace();
		}

		for(int i=0; i<list.size(); i++){			//一行文のデータ毎に処理する
			String[] s = list.get(i).split(" ");	//listの要素を空白で区切って配列を作成
			for(int j=0; j<s.length; j++){			//int型に変換してArrayListに追加
				intList.add(Integer.parseInt(s[j]));
			}
			Collections.sort(intList);				//小さい順に並べる

			a = intList.get(0);						//a,bを決める。a<bとなっている。
			b = intList.get(1);
			
			//最大公約数を求める
			divisor = getDivisor(a,b);

			//最小公倍数を求める
			multiple = getMultiple(a,b);
			
			//結果の表示
			System.out.println(divisor + " " + multiple);
			
			intList.clear();						//リストのクリア
		}
	}
	
	//最大公約数を求めるメソッド
	static int getDivisor(int x, int y){
		if(x%y==0){
			return y;
		}else{
			int m = 1;
			while(m!=0){
				m = y%x;
				y = x;
				x = m;
			}
			return y;
		}
	}
	//最小公倍数を求めるメソッド
	static int getMultiple(int x, int y){
		for(int i=1; i<=x; i++){
			if(y*i%x==0){
				return y*i;
			}
		}
		return 0;
	}
}

Measured memory_bytes: 9652
def LIS(A):
    dp = [-next(A)]
    for a in A:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_right(dp, -a)] = -a
    return len(dp)

##################################################################################################################

import sys
input = sys.stdin.readline
from bisect import bisect_right

A = (int(input()) for _ in range(int(input())))

print(LIS(A))

Measured memory_bytes: 77852
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e9;

ll N,H;
ll a[100010],b[100010];

int main(){
    cin >> N >> H;
    for(ll i=0;i<N;i++)cin >> a[i] >> b[i];
    sort(a,a+N,greater<ll>());
    sort(b,b+N,greater<ll>());
    ll ma=a[0];

    ll res=0;
    for(auto it: b){
        if(H <= 0)break;
        if(it > ma){
            res++;
            H -= it;
        }else break;
    }

    if(H > 0)res += (H+ma-1)/ma;

    cout << res << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(1e6 + 5);
const int LOG = (int)(20);

lli n, X;

lli f(lli x, lli y) {
	if(y == 0)
		return 0;
	if(x < y)
		swap(x, y);
	if(x % y == 0)
		return 2 * (x / y) * y - y;

	return 2 * (x / y) * y + f(y, x % y);
}

int main() {
	fast_io();
	// freopen("inp.in", "r", stdin);

	cin >> n >> X;

	cout << f(n - X, X) + n;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
L=2**n
cost=[0]+[10**8 for i in range(L-1)]

for i in range(m):
    a,b=map(int,input().split())
    c=sum([2**(int(i)-1) for i in input().split()])
    for j in range(L):
        q=j|c
        x=cost[j]+a
        if cost[q]>x:
            cost[q]=x
print(cost[L-1] if cost[L-1]<10**8 else -1)

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16

ll n,m,l;
ll a[2002],b[200002];
ll sum[200002];
ll dp[2002][2002];

ll f(int i,int j){
  if(a[i]>a[j])swap(i,j);
  return (sum[a[j]+1]-sum[a[i]])/l;
}

int main(){
	cin.sync_with_stdio(false);
  cin>>n>>m>>l;
  rep(i,n){
    cin>>a[i];
    a[i]--;
  }
  sort(a,a+n);
  rep(i,m){
    cin>>b[i];
  }
  rep(i,m){
    sum[i+1]=sum[i]+b[i];
  }
  rep(i,2002)rep(j,2002)dp[i][j]=INF;
  dp[0][0]=f(0,n-1)*2;
  rep(i,n-2){
    rep(j,i+1){
      if(dp[i][j]==INF)continue;
      minch(dp[i+1][j],dp[i][j]-f(i,n-1)+f(i,i+1)+f(i+1,n-1));
      minch(dp[i+1][i],dp[i][j]-f(j,n-1)+f(j,i+1)+f(i+1,n-1));
    }
  }
  ll res=INF;
  rep(i,n){
    minch(res,min(dp[n-2][i],dp[i][n-2]));
  }
  cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 35992
#include <iostream>
using namespace std;
#define ll long long int
ll knapSack(ll W, int w[], int v[], int n) {
   ll i, wt;
   ll K[n + 1][W + 1];
   for (i = 0; i <= n; i++) {
      for (wt = 0; wt <= W; wt++) {
         if (i == 0 || wt == 0)
         K[i][wt] = 0;
         else if (w[i - 1] <= wt)
            K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
         else
        K[i][wt] = K[i - 1][wt];
      }
   }
   return K[n][W];
}
int main() {
  
   long long int n, W;
   cin >> n>>W;
   int v[n], w[n];
   for (int i = 0; i < n; i++) {
      cin >> w[i];
	  cin >> v[i];
      
   }
   cout << knapSack(W, w, v, n);
   return 0;
}

Measured memory_bytes: 82532
#include <bits/stdc++.h>
typedef long long ll;
#define MOD 1000000007
#define INF -99999999 
using namespace std;
 
int main()
{
    string S;
    cin >> S;
    int N = S.size();
    for (int i = 1; i < N/2; i++)
    {
        for (int j = 0; j < (N-2*i)/2; j++)
        {
            if(S[j] != S[(N-2*i)/2+j]) break;
            if(j == (N-2*i)/2 - 1){
                cout << N-2*i << endl;
                return 0;
            }
        }
        
    }
    return -1;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H, W;
	cin >> H >> W;
	REP(i, W + 2)cout << '#';
	cout << endl;
	REP(i, H) {
		string s;
		cin >> s;
		cout << "#" << s << "#" << endl;
	}
	REP(i, W + 2)cout << '#';
	cout << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 504
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
#define REP(i,n)for(int i = 0;i<(n);i++)
const int INF = 1e9;
 
int H,W;
string s[50];
string order;
int ct;
 
vector<char> ORDER{'~','N','E','S','W','C','T'};
vector<char> MOVE{'^','v','<','>'};
map<char,int> mp;
int dy[4] = {-1,0,1,0},dx[4] = {0,1,0,-1};
 
int stepped[1000][50][50][4];
bool goaled;
int y,x,dir;
 
bool regionCheck(int y,int x){
  return 0<=x&&x<W&&0<=y&&y<H&&s[y][x]!='#';
}
 
bool goalCheck(int y,int x){
  return s[y][x]=='g';
}

int search(int order_i){
  int start_i = order_i;
  while(order_i < order.size()){//end check
    int canOrder = 1;
 
    //stepped?
    if(stepped[order_i][y][x][dir]==2){goaled = false;
      return INF;
    }else stepped[order_i][y][x][dir]++;
 
    //is order?
    for(auto o:ORDER){
      if(order[order_i]==o){canOrder=-1;break;}
    }
 
    //condition check
    if(canOrder ==-1){
      bool reverse = false;
      if(order[order_i]=='~'){reverse=true;order_i++;}
 
      if(order[order_i] == 'C'){
				if(s[y + dy[dir]][x + dx[dir]] == '#')canOrder = 1;
				else canOrder = 0;
      }else if(order[order_i] == 'T')canOrder = 1;
      else if(mp[order[order_i]]==dir)canOrder = 1;
      else canOrder = 0;
       
      if(reverse)	{
				if(canOrder)canOrder = 0;
				else  canOrder= 1;//reverse
}
      order_i++;
    }
     
    if(canOrder==1){
      while(true){
				//is move order?
				bool canMove = false;
				for(auto m:MOVE)if(order[order_i]==m){canMove=true;break;}
				if(!canMove)break;
 
				//move
				ct++;
				if(order[order_i] == '^'){
					if(regionCheck(y+dy[dir],x+dx[dir])){
						y += dy[dir];x+=dx[dir];
					}
					if(goalCheck(y,x)){goaled = true;return INF;}
				}else if(order[order_i] == 'v'){
					if(regionCheck(y-dy[dir],x-dx[dir])){
						y -= dy[dir];x-=dx[dir];
					}
					if(goalCheck(y,x)){goaled = true;return INF;}
				}else if(order[order_i] == '<'){
					dir = (dir-1 + 4)%4;
				}else{
					dir = (dir+1 + 4)%4;
				}
 
				order_i++;
      }
    }else{
			//proceed index
			int bracket = 0,brace = 0;
			do{
				if(order[order_i] == '['){bracket++;
				}else	if(order[order_i] == ']'){bracket--;
				}else if(order[order_i] == '}'){brace--;
				}else if(order[order_i] == '{'){brace++;
				}
				if(bracket < 0 || brace < 0)break;
			}while(++order_i);
		}
    if(order[order_i] == '['||order[order_i]=='{'){
      order_i += search(order_i + 1);
		}
    else if(order[order_i] == '}'&&canOrder==1){
      order_i = start_i;
    }
    else if(order[order_i] == ']' || order[order_i] == '}'){
      return order_i - start_i + 2;
    }
  }
}
int main(){
  cin>>H>>W;
  REP(i,H)cin>>s[i];
  cin>>order;
  mp['N'] = 0;
  mp['E'] = 1;
  mp['S'] = 2;
  mp['W'] = 3;
  int sx,sy;
  REP(i,H){
    REP(j,W){
      if(s[i][j]== 's'){
				sy = i;sx = j;
				s[i][j] = '.';
				break;
      }
    }
  }
	int i =0;
	while(order[i] == '{'||order[i]=='[')i++;
	y = sy,x = sx,dir = 0;
  search(0);
  if(goaled) cout << ct << endl;
  else cout << -1 << endl;
}

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

int gcd(int a, int b){
    if(a < b) 
        return gcd(b, a);
    int r;
    while((r=a%b)){
        a = b;
        b = r;
    }
    return b;
}

int main(){
    long long  a, b;
    cin >> a >> b;

    long long  ans;
    ans = (long long)(a)*(long long)(b) / gcd(a,b);
    cout << ans << endl;
}

Measured memory_bytes: 256