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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<ll> h(n);
    vector<bool> bad(n);
    for (ll i = 0; i < n; i++)
        bad[i] = false;
    for (ll i = 0; i < n; i++)
        cin >> h[i];
    for (ll i = 0; i < m; i++)
    {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        if (h[a] >= h[b])
        {
            bad[b] = true;
        }
        if (h[a] <= h[b])
        {
            bad[a] = true;
        }
    }
    ll cnt = 0;
    for (ll i = 0; i < n; i++)
    {
        if (!bad[i])
            cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3996
import qualified Control.Monad as C
import qualified Data.Array as A
import Data.Array ((!))
import qualified Data.Map.Strict as M

main :: IO ()
main = do
    [n, m] <- map read . words <$> getLine :: IO [Int]
    edges <- C.replicateM m (l2t . map read . words <$> getLine)
    let graph = A.array ((1,1), (n,n)) ([((i,j), False)|i<-[1..n],j<-[1..n]] 
                ++ concat [[((i,j), True), ((j,i), True)]|(i,j)<-edges])
    print . maximum . (0:) . snd . unzip . M.toList 
        $ dfs (M.fromList [(i, 0)|i<-[1..n]]) graph [] 1 n 
    

dfs :: M.Map Int Int 
    -> A.Array (Int, Int) Bool
    -> [Int]
    -> Int -- cur
    -> Int -- cnt
    -> M.Map Int Int
dfs memo graph already cur vertexesCnt = let
    memo'    = M.update (\n -> Just $ n+1) cur memo
    already' = cur:already
    nexts'   = filter (\n -> notElem n already && graph!(cur,n)) [1..vertexesCnt]
    in case (length already' == vertexesCnt, length nexts') of
        (True, _) -> memo'
        (_, 0)    -> M.empty
        (_, _)    -> foldr (M.unionWith (+)) M.empty
                     $ map (\next -> dfs memo' graph already' next vertexesCnt) nexts'

l2t (x:x':[]) = (x,x')
{-# INLINE l2t #-}

Measured memory_bytes: 1020
/*Anup Ghosh*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi acos(-1)
#define ull unsigned long long
#define nl printf("\n")
#define MAXN 1000005
#define gcd(a,b) __gcd(a,b)
#define pb push_back
#define fio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main()
{
	fio();
	int n;
 string s;
 char y;
 string ans;
 cin>>n>>s;
 int x,i;
 int len=s.size();
 for(i=0;i<len;i++){
 x=s[i]-'A';
 x=(x+n)%26;
 y='A'+x;
 ans=ans+y;
 }
 cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3800
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        return self.bit.bisect(self.bit.sum(x))

    def size(self):
        return self.bit.sum(self.N)


N, *A = map(int, open(0).read().split())

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

ms = Multiset(M)
for b in (memo[a] for a in A):
    i = ms.lower_bound(b - 1)
    if i != 0:
        ms.erase(i)
    ms.insert(b)

print(ms.size())


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


using namespace std;

#define all(v)              v.begin(),v.end()
#define allr(v)             v.rbegin(),v.rend()
#define sz(v)               (int)sizeof(v)
#define pb(x)               push_back(x)
#define mkpr(x,y)           make_pair(x,y)
#define oo                  INT_MAX
#define noo                 INT_MIN
#define forn(i, n)          for(ll i=0;i<n;i++)
#define fore(i,b,e)         for(ll i=b;i<=e;i++)
#define ford(i,n)           for(ll i=n-1;i>=0;i--)


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

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

void dance()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void file()
{
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}

ll gcd(ll a, ll b)
{
    return !b ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

template<typename t>
void printV(vector<t> v)
{
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << ' ';
    }
    cout << endl;
}

bool isPrime(int n)
{

    if (n == 2)
        return true;
    if (n < 2 || n % 2 == 0)
        return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}

/**
 *****code begins here*****
**/
ull ncr(ull n,ull r)
{
    r=max(r,n-r);
    ull u=1,d=1;
    for(ull i=r+1; i<=n; i++)
        u*=i;
    for(ull i=1; i<=n-r; i++)
        d*=i;
    return u/d;
}

int main()
{
    dance();
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    sort(all(v));
    int mn=oo;
    for(int i=k-1;i<n;i++)
    {
        mn=min(mn,v[i]-v[i-k+1]);
    }
    cout<<mn<<endl;
    return 0;
}


Measured memory_bytes: 640
S = input()
if S[0] != 'A':
  print('WA')
elif S[2:-1].count('C') != 1:
  print('WA')
else:
  cindex = S.index('C')
  for i in range(len(S[1:])):
    if i+1 == cindex:
      continue
    if S[i+1].isupper():
      print('WA')
      exit()
  print('AC')


Measured memory_bytes: 9048
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AGC024_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] strs = Console.ReadLine().Split(' ');

            long a = long.Parse(strs[0]);
            long b = long.Parse(strs[1]);
            long c = long.Parse(strs[2]);
            long k = long.Parse(strs[3]);

            Console.WriteLine("{0}", (k%2==0)? a-b : b-a);
        }
    }
}


Measured memory_bytes: 13140
#!/usr/bin/env python3
import sys


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uni = UnionFind(N)
    for xx,yy in zip(x,y):
        uni.Unite(xx-1,yy-1)  

    cnt = 0
    for i,pp in enumerate(p):
        if  i+1 == pp or uni.isSameGroup(i,pp-1):
            cnt += True

    print(cnt)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    M = int(next(tokens))  # type: int
    p = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]" 
    y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, p, x, y)

if __name__ == '__main__':
    main()


Measured memory_bytes: 18072
/*
    i have no idea
*/

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main(){
    IOS;
    int a, b, t;
    cin >> a >> b >> t;
    cout << (int)((t+0.5)/a )* b;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

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

    map<string,int> mp;

    for (int i = 0; i < N; i++){
        string s;
        cin >> s;
        mp[s]+=1;//mpは0で初期化されている？
    }

    int mx=0;

    for (auto p : mp){
        if(mx<p.second){
            mx=p.second;
        }
    }

    for(auto p : mp){
        if(mx==p.second){
            cout << p.first << "\n";
        }
    }
    return 0;
}


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

using namespace std;


using int64 = long long;
const int64 INF = 1LL << 60;

struct UnionFind {
  vector< int > data;

  UnionFind(int sz) {
    data.assign(sz, -1);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    //if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k) {
    return (-data[find(k)]);
  }
};


int main() {
  int N, M;
  int A[100000], B[100000];
  vector< int > g[100000];

  cin >> N >> M;
  vector< pair< int64, int > > ord(N);
  for(int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    ord[i] = {max(A[i] - B[i], 0), i};
  }
  sort(begin(ord), end(ord));
  for(int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  UnionFind uf(N);
  vector< int64 > dp(N, INF);
  vector< int64 > dp2(N);
  for(auto &p : ord) {
    int64 need;
    int to;
    tie(need, to) = p;
    int64 all = 0;
    vector< int64 > f;
    for(auto &from : g[to]) {
      from = uf.find(from);
      if(dp[from] == INF) {
        continue;
      }
      if(to != from) {
        f.emplace_back(from);
        all += dp2[from];
        dp2[to] += dp2[from];
        uf.unite(to, from);
      }
    }
    dp[to] = INF;
    if(f.empty()) {
      dp[to] = need + B[to];
    }
    for(auto &from : f) {
      dp[to] = min(dp[to], dp[from] + B[to] + max(0LL, need - dp[from]) + all - dp2[from]);
    }
    dp2[to] += B[to];
  }
  cout << *max_element(begin(dp), end(dp)) << endl;
}


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

int makeBigInt(char*, const char*);
int sumBigInt(char*, const char*, const char*);

int main(void){
	int i, n, err;
	char buf[1024], bg[2][81];
	
	scanf("%d", &n);
	
	while(n--){
		err = 0;
		
		scanf(" %s", buf);
		err += makeBigInt(bg[0], buf);
		
		scanf(" %s", buf);
		err += makeBigInt(bg[1], buf);
		
		err += sumBigInt(buf, bg[0], bg[1]);
		
		if(err < 0){
			printf("overflow\n");
			continue;
		}
		
		for(i = 0; i < 79; i++)
			if(buf[i] != '0') break;
		
		printf("%s\n", buf + i);
	}
	
	return 0;
}

int makeBigInt(char *bg, const char *stg){
	int l, i;
	
	l = 80 - strlen(stg);
	
	if(l < 0) return -1;
		
	for(i = 0; i < l; i++)
		bg[i] = '0';
	
	strcpy(bg + l, stg);
	
	return 0;
}

int sumBigInt(char *sum, const char *a, const char *b){
	int i, n;
	int m = 0;
	
	for(i = 79; i >= 0; i--){
		n = (a[i] - '0') + (b[i] - '0') + m;
		m = n / 10;
		sum[i] = (n % 10) + '0';
	}
	
	sum[80] = '\0';
	
	return (m ? -1 : 0);
}

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

int main() {

	long long int lmin = 0, lmax = 0;
	int sum = 0;
	long long int add = 0;
	long long int a = 0;

	cin >> lmin >> lmax;

	add = lmin;

	while (add<=lmax) {
		sum += 1;
		add = add * 2;
	}

	cout << sum << endl;


	return 0;
}

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

int main() {
    int n;
    cin >> n;
    cout << n << ":";
    for(int i=2; i*i<=n; i++){
        while(n%i == 0){
            cout << " " << i;
            n /= i;
        }
    }
    if(n != 1){
        cout << " " << n;
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3120
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    
    public class QuestionA
    {
        /// <summary>
        /// A - Registration
        /// https://atcoder.jp/contests/abc167/tasks/abc167_a
        /// </summary>
        /// <param name="args"></param>
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 文字列の入力
            string str_S = Console.ReadLine();

            string str_T = Console.ReadLine();

            int num_Length = str_S.Length;

            string kkk = str_T.Substring(0, num_Length);

            if (str_T.Substring(0, num_Length) == str_S) Console.WriteLine("Yes");
            else Console.WriteLine("No");

            Console.Out.Flush();

        }
    }
}


Measured memory_bytes: 25768
N, K = map(int, input().split())
S=input()
if S[K-1] == "A":
    ans = S[:K-1] + "a" + S[K:]
elif S[K-1] == "B":
    ans = S[:K-1] + "b" + S[K:]
else:
    ans = S[:K-1] + "c" + S[K:]
print(ans)

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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define mp make_pair
#define ll long long
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 100010
#define inf 1e9

int main()
{

    ll n, sum = 0;
    string ss;
    cin >> n >> ss;
    for(ll i = 0;i < ss.size(); i++)
    {

        if(ss[i]=='A' && ss[i+1]=='B'&&ss[i+2]=='C' && i<=n-2) sum++;
    }
    cout << sum;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int i,n,a=0,m; char s[300009];
	scanf("%d%s",&n,s);
	for(i=1;i<n;i++)if(s[i]=='E')a++;
	m=a;
	for(i=0;i<n-1;i++){
		if(s[i]=='W'&&s[i+1]=='W')a++;
		if(s[i]=='E'&&s[i+1]=='E')a--;
		m=(m>a?a:m);
	}
	printf("%d",m);
}

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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 10000000000000000;
double PI = 3.1415926535;

ll ceiling(ll a,ll b){
  if(a % b == 0){
    return a / b;
  }else{
    return (a / b) + 1;
  }
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

int main(){
  ll N,M;cin >> N >> M;
  vector<vector<int>> jobs(M+1);
  for(int i = 0;i < N;i++){
    int a,b;cin >> a >> b;
    if(a > M) continue;
    jobs[M-a].push_back(b);
  }
  priority_queue<int> Q;
  ll ans = 0;
  for(int i = M;i >= 0;i--){
    for(int j = 0;j < jobs[i].size();j++){
      Q.push(jobs[i][j]);
    }
    if(Q.size()){
      ans += Q.top();
      Q.pop();
    }
  }
  cout << ans << endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  int ans = 0;
  while(true){
    for(int i = 0; i < n; i++){
      if(a[i] % 2 == 1){
        cout << ans << endl;
        return 0;
      }
    }
    ans++;
    for(int i = 0; i < n; i++){
      a[i] /= 2;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)

int main(){
   int a,b;
   cin >> a >> b;
   cout << (a-1)*(b-1) << endl;
   
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

int main() {
   std::string ss, ts;
   std::cin >> ss >> ts;
   std::string us = ss + ts;
   Int t = std::stol(us);
   puts((Int)sqrt(t)*(Int)sqrt(t)==t?"Yes":"No");
}


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

using namespace std;

long long cnt = 0;

int insertionSort(int *arr,int n,int gap) {
	for (int i=gap; i<n; i++) {
		int key = arr[i];
		int j = i-gap;
		while (j >= 0 && arr[j] > key) {
			arr[j+gap] = arr[j];
			j-=gap;
			cnt++;
		}
		arr[j+gap] = key;
	}
}

void shellSort(int *arr,int n) {
	vector<int> gaps;
	for (int i = 1; i<=n; i=i*3 + 1) {
		gaps.push_back(i);
	}
	cout << gaps.size() << endl;

	for (int i=gaps.size()-1; i>=0; i--) {
		if (i!= gaps.size() -1) cout << " ";
		cout << gaps[i];
		insertionSort(arr,n,gaps[i]);
	}
	cout << endl;
	cout << cnt << endl;
	for (int i=0; i<n; i++) {
		cout << arr[i] << endl;
	}
}

int main() {
	int n;
	cin >> n;
	int *arr = new int[n];
	for (int i=0; i<n; i++) {
		cin >> arr[i];
	}
	shellSort(arr,n);
}


Measured memory_bytes: 7056
import java.util.*;
//import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		char[] s = sc.next().toCharArray();
		long k = parseLong(sc.next());
		sc.close();
		int ans = 0;
		for(i=0;i<k;i++) {
			ans = s[i]-'0';
			if(ans!=1) break;
		}
		out.println(ans);
	}
}

Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    vector<pair<ll, ll>> ab(n - 1);
    vector<vector<ll>> g(n);
    ll mv = -1, mi;
    rep(i, n - 1) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
        ab[i] = make_pair(a, b);
        if (sz(g[a]) > mv) {
            mv = sz(g[a]);
            mi = a;
        }
        if (sz(g[b]) > mv) {
            mv = sz(g[b]);
            mi = b;
        }
    }
    priority_queue<ll> pq;
    rep(i, n) {
        ll c;
        cin >> c;
        pq.push(c);
    }
    queue<ll> q;
    q.push(mi);
    vector<ll> ans(n, -1);
    ans[mi] = pq.top(); pq.pop();
    while(!q.empty()) {
        auto p = q.front(); q.pop();
        for(auto u : g[p]) {
            if (ans[u] != -1) continue;
            ans[u] = pq.top(); pq.pop();
            q.push(u);
        }
    }
    ll tot = 0;
    rep(i, n - 1) {
        tot += min(ans[ab[i].first], ans[ab[i].second]);
    }
    printf("%lld\n", tot);
    rep(i, n) printf("%lld%s", ans[i], (i == (n - 1)) ? "\n" : " ");
    return 0;
}


Measured memory_bytes: 1408
class Sieve(n: Int) {
    private val f = IntArray(n + 1)

    init {
        f[0] = -1
        f[1] = -1
        for (i in 2..n) {
            if (f[i] > 0) continue
            f[i] = i
            if (i.toLong() * i.toLong() > n) continue
            for (j in i * i..n step i) {
                if (f[j] == 0) f[j] = i
            }
        }
    }

    fun factor(x: Int): MutableMap<Int, Int> {
        val r = mutableMapOf<Int, Int>()
        var x1 = x
        while (x1 != 1) {
            r[f[x1]] = r.getOrElse(f[x1]) { 0 } + 1
            x1 /= f[x1]
        }
        return r
    }
}

fun main() {
    val sieve = Sieve(10000000)
    val n = readLine()!!.toInt()
    var ans = 0L
    for (i in 1..n) {
        var x = 1L
        for ((k, v) in sieve.factor(i)) {
            x *= (v + 1)
        }
        ans += i * x
    }
    println(ans)
}


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

using namespace std;
const int MAXN = 100010;
int _w;

int n;
char s[MAXN];

int main() {
	_w = scanf( "%s", s );
	n = (int)strlen(s);
	for( int i = 0; i < n-8; ++i )
		putchar( s[i] );
	puts("");
	return 0;
}


Measured memory_bytes: 256
def main():
    n,k=map(int,input().split())
    ans=0
    maxi=sum(range(n-k+1,n+1))
    mini=sum(range(0,k))
    for i in range(k,n+2):
        tmp=maxi-mini+1
        ans=(ans+tmp)%(1e+9+7)
        maxi+=n-i
        mini+=i
    print(int(ans))
    

if __name__ == '__main__':
    main()

Measured memory_bytes: 9152
#include <bits/stdc++.h>
#define range(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) range(i,0,n)
using namespace std;

typedef complex<double> P;
const double eps=1.0e-10;
P points[210];
P rel[210][210];

int main(void){
	int n;
	while(cin >> n,n){
		rep(i,n){
			double x,y; char tmp;
			cin >> x >> tmp >> y;
			points[i]={x,y};
		}
		rep(i,n)rep(j,n) rel[i][j]=(points[i]+points[j])/P(2.0,0.0);

		int ans=0;
		rep(i,n)rep(j,n){
			int cur=0;
			rep(k,n) if(abs(points[k]-rel[i][j])<1.0+eps) cur++;
			ans=max(ans,cur);
		}
		cout << ans << endl;
	}
	return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  ll N; cin >> N;
  vector<ll> X(N); REP(i, N) cin >> X[i];
  ll ans = pow(10, 17) + 9;
  for(int i = 0; i <= 101; ++i) {
    ll tmp = 0;
     REP(k, N) {
       tmp += pow(X[k] - i, 2);
     }
     if(ans > tmp) ans = tmp;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3584
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a
# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx # 根をbxに統一

N, M, K = lr()
AB = [lr() for _ in range(M)]
friends = [[] for _ in range(N+1)]
block = [set() for _ in range(N+1)]
for a, b in AB:
    friends[a].append(b)
    friends[b].append(a)

for _ in range(K):
    c, d = lr()
    block[c].add(d)
    block[d].add(c)

V = [i for i in range(N+1)] # 1-indexed
for a, b in AB:
    if find(V, a) != find(V, b):
        union(V, a, b)

for i in range(1, N+1):
    V[i] = find(V, i)

for i in range(1, N+1):
    rmv = set()
    for x in block[i]:
        if V[i] != V[x]:
            rmv.add(x)
    block[i] -= rmv

counter = Counter(V)

answer = [None] * (N+1)
for i in range(1, N+1):
    num = counter[V[i]]
    answer[i] = num - len(friends[i]) - len(block[i]) - 1

print(*answer[1:])


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

using namespace std;

int N, M, Q;
vector<int> a, b, c, d;
vector<int> pattern;
int ans = 0;

int score()
{
    int res = 0;
    for(int i = 0; i < Q; i++){
        if((pattern[b[i] - 1] - pattern[a[i] - 1]) == c[i]){
            res+=d[i];
        }
    }
    //cout << res;
    return res;
}

void changePattern(int index, int start)
{
    if(index == pattern.size()){
        // for(int i = 0; i < pattern.size(); i++){
        //     cout << pattern[i] << " ";
        // }
        ans = max(ans, score());
        // cout << endl;
        return;
    }
    for(int i = start; i <= M; i++){
        pattern[index] = i;
        changePattern(index+1, i);
    }
}

int main(void)
{
    cin >> N >> M >> Q;
    a.resize(Q);
    b.resize(Q);
    c.resize(Q);
    d.resize(Q);
    pattern.resize(N);
    for(int i = 0; i < Q; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    changePattern(0, 1);
    cout << ans << endl;
    return 0;
} 

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

int main(void) {
    const int merry[] = {1, 2, 1, 2, 1, 4, 1, 4};
    int p[8], i, j, k, d, dmin, check, min_check;

    while (scanf("%d", &p[0]) == 1) {
        for (i = 1; i < 8; i++) {
            scanf("%d", &p[i]);
        }
        for (i = 0, dmin = INT_MAX, k = 0, min_check = 9999;
             i < 8; i++) {
            for (j = 0, d = 0; j < 8; j++) {
                d += p[j] > merry[(i+j)%8]? p[j]-merry[(i+j)%8]: 0;
            }
            check = merry[i]*1000 + merry[(i+1)%8]*100 + merry[(i+2)%8]*10 + merry[(i+3)%8];
            if (d < dmin || (d == dmin && check < min_check)) {
                dmin = d;
                min_check = check;
                k = i;
            }
        }
        printf("%d", merry[k]);
        for (i = 1; i < 8; i++) {
            printf(" %d", merry[(k+i)%8]);
        }
        puts("");
    }
    return 0;
}

Measured memory_bytes: 612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		int[] food = new  int[M];
		for (int i = 0; i < N; i++) {
			int K = sc.nextInt();

			for (int j = 0; j < K; j++) {
				food[sc.nextInt() - 1]++;
			}
		}

		int cnt = 0;
		for (int i = 0; i < food.length; i++) {
			if (food[i] == N) {
				cnt++;
			}
		}

		System.out.println(cnt);
	}

}

Measured memory_bytes: 21844
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ab;
        int yakusu[] = new int[n];
        yakusu[0] = 0;
        for(int i = 1; i < n; i++){
            for(int j = 1; i * j < n; j++){
                yakusu[i * j] += 1;
            }
        }
        int cnt = 0;
        int yakusu_sum[] = new int[n];
        yakusu_sum[0] = 0;
        for(int i = 1; i < n; i++){
            cnt += yakusu[i];
            yakusu_sum[i] = cnt;
        }
        
        System.out.println(yakusu_sum[n - 1]);
    }
}


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

bool checker( int** a  ,int x , int y , int d)
{
    ll ans =0;
    for(int i=0;i<d;i++)
    {
        ans += abs( a[x][i] - a[y][i]  )* abs( a[x][i] - a[y][i]  );
    }
    ll temp = sqrt(ans);
    if( temp*temp == ans)
        return true;
     return false;
}
int main() {
    int n, d;
    cin >> n >> d;

    int **a = new int *[n];
    for (int i = 0; i < n; i++)
    {
        a[i] = new int[d];
        for(int j=0;j<d;j++)
        {
            cin>>a[i][j];
        }
    }
    int ans =0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if( checker(a,i,j,d))
                ans++;
        }
    }
    cout<<ans;
}

Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] A = new int[N][M];
		int[]   b = new int[M];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j< M; j++) {
				A[i][j] = sc.nextInt();
			}
		}
		for(int i = 0; i < M; i++) {
			b[i] = sc.nextInt();
		}
		int[] c = multiMV(A, b);
		for(int i = 0; i < c.length; i++) {
			System.out.println(c[i]);
		}
		sc.close();
	}

	// 行列とベクトルの掛け算
	public static int[] multiMV(int[][] A, int[] b) {
		int[] c = new int[A.length];
		for(int i = 0; i < A.length; i++) {
			int e = 0;
			for(int j = 0; j < A[i].length; j++) {
				e += A[i][j] * b[j];
			}
			c[i] = e;
		}
		return c;
	}
}


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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

w,h,x,y = LI()

flg = 0
if w % 2 == 0 and h % 2 == 0:
    if x == w//2 and y == h//2:
        flg = 1

ans = w*h/2
print(ans,flg)

Measured memory_bytes: 38512
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[])
{
    string x;
    cin >> x;
    if(x=="Sunny"){
        cout << "Cloudy" << endl;
    }
    else if(x=="Cloudy"){
        cout << "Rainy" << endl;
    }
    else{
        cout << "Sunny" << endl;
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.C
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var S = ReadText();
            var K = ReadLong();

            var s = 'x';
            for (int i = 0; i < S.Length; i++)
            {
                var item = S[i];
                if (i + 1 == K)
                {
                    s = item;
                    break;
                }
                if (item != '1')
                {
                    s = item;
                    break;
                }
            }

            return s;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 27500
import java.util.*;
import static java.lang.System.*;

public class Main {

	Scanner sc = new Scanner(in);
	
	void run() {
		int n = sc.nextInt();
		int ans = 0;
		while (n > 3) {
			ans++;
			n = (int)Math.ceil((double)n/3);
		}
		out.println(ans+1);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 17352
N=int(input())
a = list(map(int,input().split()))
prev = a[0]
line = 1
score=0
for i in range(1,N):
    if a[i]==prev:
        line+=1
    else:
        prev=a[i]
        score += line//2
        line=1
score+=line//2

print(score)

Measured memory_bytes: 3064
N, M, X = map(int, input().split())
C = []
A = []
A_min = []

master = [0 for i in range(M)]
bought = [False for i in range(N)]
cost = 0

def f(master, book):
    for i in range(M):
        master[i] += book[i]
    return master

for i in range(N):
    c, *a = list(map(int, input().split()))
    C.append(c)
    A.append(a)

m = 10**100
for i in range(2**N):
    cost = 0
    master = [0 for i in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            master = f(master, A[j])
    if min(master) >= X:
        m = min(m, cost)
    if i == 2**N-1 and min(master) < X:
        m = -1
        
print(m)
                

Measured memory_bytes: 68944
#!/usr/bin/env python3
# -*- coding: utf-8 -*-*-

from sys import stdin
import collections


def main():
    N, X, Y = list(map(int, stdin.readline().split()))
    X -= 1
    Y -= 1

    cost = collections.defaultdict(lambda: 0)
    for i in range(N):
        for j in range(i + 1, N):
            # 左/右/中で完結
            min1 = j - i
            # ショトカを跨ぐ/# 始まりが中
            min2 = abs(X - i) + 1 + abs(j - Y)
            # 終わりが中
            min3 = abs(Y - i) + 1 + abs(X - j)
            shortest = min(min1, min2, min3)
            cost[shortest] = cost[shortest] + 1
    for i in range(1, N):
        print(cost[i])


if __name__ == "__main__":
    main()


Measured memory_bytes: 3956
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using P = pair<ll,ll>;
using um = unordered_map<ll,ll>;
#define fl cout<<flush;
#define endl '\n'
template <typename T> inline void prt(T v){cout<<v<<'\n';}
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ld pi=3.14159265358979323846;
const ld eps=1e-10;

inline ld dist(ld x1,ld y1,ld x2,ld y2){
    return (ld)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> X(N,0);
    vector<ll> Y(N,0);
    for(ll i=0;i<N;++i)cin>>X[i]>>Y[i];
    vector<P> vec(N);
    for(ll i=0;i<N;++i)vec[i]=P(X[i],Y[i]);
    sort(vec.begin(), vec.end(),[&](P l,P r){return atan2(l.second,l.first)<atan2(r.second,r.first);});
    for(ll i=0;i<N;++i)vec.emplace_back(vec[i]);
    ld ans=0.0;
    for(ll i=0;i<N;++i){
        for(ll j=0;j<N;++j){
            ld x=0,y=0;
            for(ll k=i;k<=i+j;++k){
                x+=vec[k].first;
                y+=vec[k].second;
            }
            chmax(ans,dist(0.0,0.0,x,y));
        }
    }
    cout << fixed << setprecision(20);
    prt(ans);fl
    return 0;
}



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

typedef long long ll;
#define PI 2 * acos (0.0)

ll MOD = 1e9 + 7 ;

int main()
{
  ll cnt = 0 ;
  string s ;
  cin >> s ;

  for(int i = 0; i < s.size() / 2; i++) {
    if(s[i] != s[s.size() - i - 1]) cnt++ ;
  }
  cout << cnt << endl ;

}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int coin[6] = {500, 100, 50, 10, 5, 1};

int main() {
	int N;
	
	while (cin >> N, N) {
		int A = 1000 - N, ans = 0;
		
		for_(i,0,6) {
			while (A >= coin[i]) {
				A -= coin[i];
				++ans;
			}
		}
		
		cout << ans << endl;
	}
}

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

const int mod = 1e9 + 7;

void add(int &x,int y) {
	x += y; if (x >= mod) x -= mod;
}

int mul(int x,int y) {
	return (long long) x * y % mod;
}

struct Matrix {
	vector<vector<int>> a;
	Matrix(int n = 0,int m = 0) {
		a.assign(n, vector<int>(m, 0));
	}
	Matrix operator * (const Matrix& mt) const {
		int n = a.size(), m = a[0].size(), p = mt.a[0].size();
		Matrix res(n, p);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				for (int k = 0; k < p; ++k) {
					add(res.a[i][k], mul(a[i][j], mt.a[j][k]));
				}
			}
		} 
		return res;
	}
};

Matrix pw(Matrix a,long long k) {
	int n = a.a.size();
	Matrix res(n, n);
	for (int i = 0; i < n; ++i) {
		res.a[i][i] = 1;
	}
	while (k) {
		if (k & 1) {
			res = res * a;
		}
		a = a * a;
		k >>= 1;
	}
	return res;
}

int main() {
	int n; long long k;
	scanf("%d %lld", &n, &k);
	Matrix a(n, n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &a.a[i][j]);
		}
	}
	a = pw(a, k);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			add(ans, a.a[i][j]);
		} 
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

int can (char *s, i32 f, i32 t) {
  for (i32 i = f; i < t; ++i) {
    if (s[i] == '#' && s[i + 1] == '#') {
      return 0;
    }
  }
  return 1;
}

void run (void) {
  i32 n, a, b, c, d;
  scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32 "%" SCNi32 "%" SCNi32, &n, &a, &b, &c, &d);
  a--; b--; c--; d--;
  char *s = (char *) calloc (n + 3, sizeof (char)) + 1;
  scanf ("%s", s);
  s[-1] = s[n] = s[n + 1] = '#';
  if (!(can (s, a, c) && can (s, b, d))) {
    puts ("No");
    return;
  }
  if (c > d) {
    i32 ok = 0;
    for (i32 i = b; i <= d && !ok; ++i) {
      if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
	ok = 1;
      }
    }
    if (!ok) {
      puts ("No");
      return;
    }
  }
  puts ("Yes");
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 384
import queue

"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
N = int(input())
A = [int(i) for i in input().split()]
B = 0
for i in range(len(A)):
	for j in range(len(A)):
		if i< j:
			B += A[i]*A[j]
print(B)

Measured memory_bytes: 4208
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define repr(i,x,n) for(int i=x; i<(n); i++)
#define ALL(x) (x).begin(),(x).end()
#define INF 1e9
typedef long long ll;
using VI = vector<int>;
using VS = vector<string>;
using graph = vector<vector<int>>;
int main()
{
int n,k,x,y;
cin>>n>>k>>x>>y;
if (n>k)
{
    cout<<k*x+(n-k)*y;
}
else cout<<n*x<<endl;
    return 0;
}

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

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

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + ABC[i][j])

ans = 0

for i in range(3):
    ans = max(ans, dp[N][i])

print(ans)


Measured memory_bytes: 47320
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;

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

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int main(){
  int a, b; cin >> a >> b;
  int height = (b - a) * (b - a + 1) / 2;
  cout << height - b << endl;
}


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

#define rep(i,p) for(int i=1;i<=p;i++)
#define ll long long

using namespace std;

int main(){


 ll int H,N;
 cin >> H >> N;

 ll int A,wa;
 wa =0;
 rep(i,N){
	 cin >> A;
    wa += A;
    if(wa>=H){
	    cout << "Yes";
	    return 0;
    }
 }
 cout << "No";









	return 0;

}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    int d=a*100;
    int e=b*10;
    int A=d+e+c;
    
  if(A%4==0){
      cout<<"YES"<<endl;
  }
  
  else{
      cout<<"NO"<<endl;
  }
}


Measured memory_bytes: 3564
int main(void){
	int n;
	int i;
	int debt = 100000;
	
	scanf("%d",&n);
	
	for(i = 0;i < n;i++){
		debt *= 1.05;
		if(debt%1000 > 0){
			debt -= debt%1000;
			debt += 1000;
		}
	}
	
	printf("%d\n",debt);
        return 0;
}

Measured memory_bytes: 592
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define fi first
#define se second
#define pii pair<int,int>

const int maxn=2e5+5;
int h[maxn],n,f[maxn];

main()
{
 	cin>>n;
  forinc(i,1,n) cin>>h[i];
  memset(f,127,sizeof f);
  f[1]=0;f[2]=abs(h[2]-h[1]);
  forinc(i,3,n) f[i]=min(f[i-1]+abs(h[i]-h[i-1]),f[i-2]+abs(h[i]-h[i-2]));
  cout<<f[n];
  
}

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

void cxxio() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}

int main() {
    cxxio();
    ll n, m;
    cin>>n>>m;
    string a, b;
    cin>>a>>b;
    ll d=__gcd(n, m);
    forn(i, d)
        if (a[n/d*i]!=b[m/d*i])
            return cout<<"-1\n", 0;
    cout<<(n*m/d)<<'\n';
}


Measured memory_bytes: 640
unittest
{
	assert( [ "20 30 70 90", "3" ].parse.expand.solve == 150 );
	assert( [ "10000 1000 100 10", "1" ].parse.expand.solve == 100 );
	assert( [ "10 100 1000 10000", "1" ].parse.expand.solve == 40 );
	assert( [ "12345678 87654321 12345678 87654321", "123456789" ].parse.expand.solve == 1524157763907942 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto qhsd = input.front.split.to!( long[] );
	input.popFront;
	auto n = input.front.to!( long );
	return tuple( [ tuple( qhsd[ 0 ], 0.25 ), tuple( qhsd[ 1 ], 0.50 ), tuple( qhsd[ 2 ], 1.00 ), tuple( qhsd[ 3 ], 2.00 ) ], n );
}

auto solve( Tuple!( long, double )[] qhsd, long n )
{
	// n以下のサイズで一番コスパが良いものをできるだけ買う
	auto m = qhsd[ 0 ];
	foreach( x; qhsd[ 1 .. $ ].filter!( ( a ) => a[ 1 ] <= n ) )
	{
		if( x[ 0 ] / x[ 1 ] < m[ 0 ] / m[ 1 ] ) m = x;
	}
	auto k = cast( long )( n / m[ 1 ] ) * m[ 0 ];
	auto r = n % m[ 1 ];
	if( r == 0 ) return k;
	
	// 端数を他のもので補う
	auto ans = long.max;
	foreach( x; qhsd.filter!( ( a ) => a[ 1 ] <= r ) )
	{
		ans = min( ans, k + cast( long )( r / x[ 1 ] ) * x[ 0 ] );
	}
	return ans;
}


Measured memory_bytes: 256
def factiring2(N,P):
	if N==1:
		ans=P
	else:
		ans=1
		for i in range(2,int(P**0.5)+1):
			cnt=0
			while P%i==0:
				P//=i
				cnt+=1
			if cnt>=N:
				ans*=i**(cnt//N)
	return ans	

	
		

			
	


N, P = map(int, input().split())
ans=factiring2(N,P)
print(ans)



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

struct BipartiteMatching {
  int n;
  vector< vector<int> > graph;

  BipartiteMatching(int n): n(n), graph(n) {}
  void addEdge(int a, int b) {
    graph[a].emplace_back(b);
    graph[b].emplace_back(a);
  }

  vector<int> used;
  vector<int> match;

  // max flow
  int solve() {
    match = vector<int>(n, -1);
    int flow = 0;
    for(int i = 0; i < n; i++) {
      if(match[i] < 0) {
        used = vector<int>(n, 0);
        if(dfs(i)) flow++;
      }
    }
    return flow;
  }

  private:
  bool dfs(int v) {
    if(used[v]) return false; //
    used[v] = 1;
    for(int u : graph[v]) if(match[u] < 0 || dfs(match[u])) {
      match[v] = u;
      match[u] = v;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n; cin >> n;
  BipartiteMatching ecasdqina(n*2);

  vector<int> ax = vector<int>(n), ay, bx, by = bx = ay = ax;
  for(int i = 0; i < n; i++) cin >> ax[i] >> ay[i];
  for(int i = 0; i < n; i++) cin >> bx[i] >> by[i];
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
    if(ax[i] < bx[j] && ay[i] < by[j])
      ecasdqina.addEdge(i, n + j);
  cout << ecasdqina.solve() << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <map>

using namespace std;

int parent(int i) {
	return i / 2;
}

int left(int i) {
	return 2 * i;
}

int right(int i) {
	return 2 * i + 1;
}

int main() {
	int H;
	int A[251];
	int pk, lk, rk;
	cin >> H;
	for (int i = 1; i <= H; i++) {
		cin >> A[i];
	}
	for (int i = 1; i <= H; i++) {
		printf("node %d: ", i);
		printf("key = %d, ", A[i]);
		pk = parent(i);
		if (1 <= pk) {
			printf("parent key = %d, ", A[pk]);
		}
		lk = left(i);
		if (lk <= H) {
			printf("left key = %d, ", A[lk]);
		}
		rk = right(i);
		if (rk <= H) {
			printf("right key = %d, ", A[rk]);
		}
		printf("\n");
	}
}

Measured memory_bytes: 1148
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

typedef long long ll;

bool isprime[10000001];

void sieve(ll N){
  
  fill(isprime,isprime+10000001,true);
  isprime[0]=isprime[1]=false;
  
  for(ll i=2;i*i<=N;i++){
    if(isprime[i]){
      for(ll j=i*i;j<N;j+=i){
	isprime[j]=false;
      }
    }
  }
}

int main(void){

  sieve(10000000);

  int res[10001];
  fill(res,res+10001,0);
  res[1]=2;
  for(int i=2,j=0;j<10001;i++)
    if(isprime[i])res[j+1]=res[j++]+i;

  int a;
  while(cin >> a,a){
    cout << res[a] << endl;
  }

  return 0;
}

Measured memory_bytes: 10960
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include <algorithm> 
using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;


int main()
{
    string s;cin >> s;
    int k;cin >> k;
    vector<string> v;

    for(int i=0;i<s.size();i++){
        for(int j=1;i+j<=s.size() && j<=k;j++){
            v.push_back(s.substr(i,j));
        }
    }
    sort(v.begin(),v.end());
    unique(v.begin(),v.end());
    p(v[k-1])
} 

Measured memory_bytes: 1660
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <cstdio>
#include <math.h>
#include <utility>
#include <list>
#include <functional>
using namespace std;

#define ll long long
#define vecint vector<int>
#define Pii pair<int, int>

#define REP(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define print(a) cout << a << endl

#define MOD 1000000007
#define NIL -1

int main(){
  int N;
  int x,y;
  int ans=1;
  int t;
  int mode;
  cin>>N;
  cin>>x;
  cin>>y;
  if(y-x>0){
    mode=1;
  }else if(x-y>0){
    mode=2;
  }else{
    mode=0;
  }
  x=y;
  REP(i,2,N){
    cin>>y;
    switch(mode){
      case 1:
      if(y-x>0){
        break;
      }else if(x==y){
        break;
      }else{
        mode=0;
        ans++;
        break;
      }
      case 2:
      if(x-y>0){
        break;
      }else if(x==y){
        break;
      }else{
        mode=0;
        ans++;
        break;
      }
      case 0:
      if(x-y>0){
        mode=2;
        break;
      }else if(x==y){
        break;
      }else{
        mode=1;
        break;
      }
    }
    x=y;
  }
  print(ans);
}


Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let (N, M): (i64, i64) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap()
        )
    };

    let k = std::cmp::min(N, M / 2);
    let ans = k + (M - 2 * k) / 4;

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

Measured memory_bytes: 4352