akhauriyash/Code-Regression huggingface dataset:
use std::io::stdin;
use std::str::FromStr;

fn read_line<T>() -> Vec<T>
where
    T: FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect()
}

fn read_str_as_char_vec() -> Vec<char> {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().chars().collect()
}

fn read_str_as_T<T>() -> T
where
    T: FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().parse().unwrap()
}

fn main() {
    // $BM>89DjM}(B
    let in_vec: Vec<usize> = read_line();
    let a = in_vec[0];
    let b = in_vec[1];
    let h = in_vec[2];
    let m = in_vec[3];

    let mut a_theta = (h as f64 + (m as f64) / 60.) / 12.;
    // if a_theta > 1. {
    //     a_theta -= 1.;
    // }
    let mut b_theta = (m as f64) / 60.;
    if b_theta > a_theta {
        let temp = b_theta;
        b_theta = a_theta;
        a_theta = temp;
    }
    let mut diff = a_theta - b_theta;
    if diff > 0.5 {
        diff = 1. - diff;
    }

    let res_pow = f64::powi(a as f64, 2) + f64::powi(b as f64, 2) - 2. * (a as f64) * (b as f64) * (diff * 2.0 * std::f64::consts::PI).cos();
    let res = f64::powf(res_pow, 0.5);
    println!("{}", res);
}


Measured memory_bytes: 2964
//-----

var log = console.log;
if (typeof process != "undefined") {
	var input = "";
	process.stdin.resume();
	process.stdin.setEncoding('utf8');
	process.stdin.on('data', function (chunk) {
		input += chunk;
	});
	process.stdin.on('end', function () {
		var lines = input.split("\n");
		main(lines);
	});
}

//-----

function main(lines) {
	//???????????????????????¢?????????
	var input = lines.shift();
	//??\??????????????????
	var stream = input.split("");
	//??????????????£????????????????????¨??§?????°??????????????¢
	//?????????????????§??????????????§?????????????????????????????§???????????¨?????£????????§??????????????????
	var reader = getreader();
	//reader??¢??°???????´???????????????????????????¨??§??????
	//?????¨??¶??????reader??¢??°?????????????????????
	stream.forEach(reader);
	//?????????????????????
	var result = reader.getresult();
	//??????
	if (result[1] != 0) {
		log("" + result.shift() + "\n" + result.shift() + " " + result.shift().join(" "));
	} else {
		log(0);
		log(0);
	}
}

//??????????????£???????????????
function getreader(len) {

	//?????¢???
	var A = 0;
	//?°´?????????????????°
	//length??§????????????(?¨???????1)
	//let k = 0;
	//????°´??????????????¢???
	var L = [];

	//?????¨??????????????????
	var s = [];
	//?°´?????????????§???????????????????
	//??????????°´????????????????????????????????\?????????????????????
	var p = [];

	var reader = function reader(ele, idx) {
		switch (ele) {
			case "\\":
				s.push(idx);
				break;
			case "_":
				break;
			case "/":
				if (s.length != 0) {
					//???????????????????????????
					var c = s.pop();
					//??????????????????(?????¨?°´?????????????°´???)
					var l = idx - c;
					//?????¢???????¶?????????????????????????
					var lp = l;
					//?°´?????????????????±??????
					for (var j = p.length; j >= 0; j--) {
						//???????????????????????£???????§?????????????????????????????????????????????°?°´???????????????????????????
						if (p[j] > c) {
							l += L.pop();
							p.pop();
						}
					}

					//L?????????
					L.push(l);
					//A????????????
					A += lp;
					//????????§???p????¨????
					p.push(c);
				} else {
					//???????????????????????????
				}
				break;
		}
	};

	//???????????????????????¢??°
	reader.getresult = function () {
		return [A, L.length, L];
	};

	return reader;
}

Measured memory_bytes: 17216
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>

typedef long long ll;
ll N,M,a,b,ans=1,temp;
//bool flag[10000][10000];


int main(){
    scanf("%lld %lld",&N,&M);
    a=M/2;
    if(a>=N){
        ans=(N+a)/2;

    }else {
        ans=M/2;
    }

    printf("%lld",ans);
    return 0;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define fo(i, n) for(int i = 1; i <= n; ++i)
#define rep(i, a, b) for(int (i) = (a); (i) < (b); ++(i))

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 200200;
const int mod = 1e9 + 7;
const ll INF = 1e18;
int n,m,ok[20][20],a[20];
ll dp[1<<10][10];
int ans;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	fo(i,m)
	{
		int x,y;
		cin>>x>>y;
		ok[x][y]=1;
		ok[y][x]=1;
	}
	for(int i=0;i<(1<<n);++i)
		for(int j=0;j<n;++j)
			dp[i][j]=0;
	dp[1][0]=1;
	for(int i=0;i<(1<<n);++i)
		for(int j=0;j<n;++j)
			if(!((1<<j)&i))	
				for(int k=0;k<n;++k)
					if((1<<k)&i)
						if(ok[k+1][j+1])
							dp[i+(1<<j)][j]+=dp[i][k];
	for(int i=1;i<n;++i)	
		ans+=dp[(1<<n)-1][i];
	cout<<ans;
	return 0;	
}

Measured memory_bytes: 256
//Volume1-0160
import java.util.Scanner;

class Main {

	public static void main(String[] arg){

		            int    n,l,lr,w,wr,sum;
		      final int[]  srnk = { 60, 80, 100, 120, 140, 160},
		                   wrnk = {  2,  5,  10,  15,  20,  25},
		                   fee  = {600,800,1000,1200,1400,1600};

		Scanner sc = new Scanner(System.in);

		while((n = sc.nextInt()) != 0){
			sum = 0;
			while(n-- > 0){
				l = sc.nextInt()+sc.nextInt()+sc.nextInt();
				w = sc.nextInt();

				lr = -1;
				for(int i=0;i<6;i++)
					if(l <= srnk[i]){
						lr = i;
						break;
					}
				if(lr == -1){continue;}

				wr = -1;
				for(int i=0;i<6;i++)
					if(w <= wrnk[i]){
						wr = i;
						break;
					}
				if(wr == -1){continue;}

				if   (lr<wr){sum += fee[wr];}
				else        {sum += fee[lr];}
			}
			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 58380
#include "stdio.h"

int main(void){
  int x,y,z,min,n,i;
  long int sum = 0;
  long int max;
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%d ", &x);
    sum += x;
    if(i == 0){
      min = x;
      max = x;
    }else{
      if(min > x){
        min = x;
      }
      if(max < x){
        max = x;
      }
    }
  }
  printf("%d %ld %ld\n", min, max, sum);
}



Measured memory_bytes: 2108
#include <iostream>
using namespace std;
int main(void)
{
    int n;
    cin>>n;
    int dp[n+1];
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 3112
N = int(input())
a = list(map(int, input().split()))
decided = [0 for _ in range(N+1)]

a.insert(0,0)

for i in range(N,0,-1):
    count = 0
    check = 2*i
    while check <= N:
        count = (count+decided[check])%2
        check += i
    if a[i] == 1 and count == 1:
        continue
    elif a[i] == 0 and count ==0:
        continue
    else:
        decided[i] = 1

print(sum(decided))
answer = [i for i in range(N+1) if decided[i]==1]

print(" ".join(list(str(i) for i in answer)))

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int main(){
    int n;
    cin >> n;
    ll k;
    cin >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i]--;
    }

    vector<int> used;
    int index = 0;
    int loop_size;
    int loop_begin;
    vector<bool> checked(n, false);
    while(1){
        checked[index] = true;
        used.push_back(index);
        k--;
        index = a[index];
        if (k == 0){
            cout << index + 1 << endl;
            return 0;
        }

        if (checked[index]){
            auto itr = find(used.begin(), used.end(), index);
            loop_size = used.size() - (itr - used.begin());
            loop_begin = index;
            break;
        }
    }

    k %= (ll)loop_size;
    int res = loop_begin;
    for (int i = 0; i < k; ++i) {
        res = a[res];
    }
    cout << res + 1 << endl;
}


Measured memory_bytes: 5016
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int A,C,G,T;
  char b;
  cin >> b;
  if(b=='A'){
  cout << 'T' << endl; 
  }
  else if(b=='C'){
  cout << 'G' << endl;
  }
  else if(b=='G'){
  cout << 'C' << endl; 
  }
  else {
  cout << 'A' << endl; 
  }
  }
  

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

#define int long long


signed main(void) {
  int num; // num
  num = 0; // count, result
  // num = numeric_limits<int>::min(); // max
  // num = numeric_limits<int>::max(); // min
  int N;
  // int M;
  // array<int, 100000> A;;
  // string S;
  // string T;
  int T, A;
  array<double, 1000> H;

  cin >> N;
  cin >> T>>A;

  for (int i = 0; i < N; ++i) {
    int h;
    cin >> h;
    H[i] = abs(A - T + h * 0.006);
  }

  num = 0;
  for (int i = 1; i < N; ++i) {
    if (H[i] < H[num]) num = i;
    
  }

  cout << num + 1 << endl;

  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var cin = new Scanner2();
			string s = cin.Next();
			string t = cin.Next();
			Console.WriteLine(t + s);
		}
	}

	public class Scanner2
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private readonly string filePath_;
		private string[] buf_;
		private int index_;
		Func<string> reader_;

		public Scanner2(string file = "")
		{
			if (string.IsNullOrWhiteSpace(file)) {
				reader_ = Console.ReadLine;
			} else {
				filePath_ = file;
				var fs = new StreamReader(file);
				reader_ = fs.ReadLine;
			}
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = reader_();
			while (st == "") {
				st = reader_();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}

		public void Save(string text)
		{
			if (string.IsNullOrWhiteSpace(filePath_)) {
				return;
			}

			File.WriteAllText(filePath_ + "_output.txt", text);
		}
	}
}

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

using namespace std;

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

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

const int MX = 2e5+5;
int n;
ll a[MX], res = 0;
map<int, stack<int>> mp;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		mp[a[i]].push(i);
	}

	for (int j = 31; j >= 0; j--) {
		ll k = 1ll << j;

		for (int i = 0; i < n; i++)
			if (a[i] != -1 && a[i] < k)
				if (mp.count(k - a[i])) {
					bool f = 0;
					
					while (mp[k-a[i]].size() && (a[mp[k-a[i]].top()] == -1 || mp[k-a[i]].top() == i)) {
						if (mp[k-a[i]].top() == i) f = 1;
						mp[k-a[i]].pop();
					}

					if (mp[k-a[i]].size()) {
						res++;
						a[mp[k-a[i]].top()] = -1;
						mp[k-a[i]].pop();
						a[i] = -1;
					} else if (f) {
						mp[k-a[i]].push(i);
					}
				}
	}

	cout << res << endl;

	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repc(i, a, b) for (int i = a; i <= (int)(b); i++)
#define ll long long
#define vec vector
#define pb push_back
#define ft first
#define sd second
#define all(vec) vec.begin(), vec.end()

typedef pair<int, int> P;

const int MOD = 1e9 + 7;
const int INF = 1001001001;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};

//------------------------------------------------------//

const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}



int main(){
  int n, k;
  cin >> n >> k;
  vec<int> l(k), r(k);
  rep(i, k) cin >> l[i] >> r[i];

  vec<mint> dp(n+1);
  vec<mint> dpsum(n+1);
  dp[1] = 1;
  dpsum[1] = 1;

  repc(i, 2, n){
    rep(j, k){
      int li = i - r[j];
      int ri = i - l[j];
      if(ri < 0) continue;
      li = max(li, 1);
      dp[i] += dpsum[ri] - dpsum[li-1];
    }
    dpsum[i] = dpsum[i-1] + dp[i];
  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 6424
//#include "stdc++.h"
#include <bits/stdc++.h>
using namespace std;
#define RALL(c) rbegin(c),rend(c)
typedef long long llong;
using vi = vector<int>;

int s[3];

int main() {
	for (int i = 0; i < 3; i++) cin >> s[i];

	sort(RALL(s));

	cout << s[0] * 10 + s[1] + s[2] << endl;
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k,a;
    cin >> n;
    double kvalue = (1+sqrt(1+8*n))/2;
    string ans = "Yes";
    vector<int> cnt(n);

    if((int)kvalue==kvalue) k = (int)kvalue;
    else ans = "No";
    a = 2*n/k;
    int s[k][a];
    for(int j = 0;j < a;j ++){
      s[0][j] = j;
      cnt[j] ++;
    }

    for(int i = 1;i < k;i ++){
      int p = 0;
      for(int j = 0;j < i && p < a;j ++){
        for(int l = 0;l < a && p < a;l ++){
          if(cnt[s[j][l]] != 2){
            s[i][p] = s[j][l];
            cnt[s[i][p]] ++;
            p ++;
            break; 
          }
        }
      }
      for(int j = 1;p < a;j ++){
        s[i][p] = s[i-1][a-1]+j;
        cnt[s[i][p]] ++;
        p ++;
      }
    }
    if(ans == "Yes"){
      cout << ans << endl << k << endl;
      for(int i = 0;i < k;i ++){
        cout << a << " ";
        for(int j = 0;j < a;j ++){
          cout << s[i][j]+1 << " ";
        }
        cout << endl;
      }
    }else cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+7;

int a[MAXN];
int r[MAXN];

void placeAt(int x, int _x) {
    if (a[_x]==x) return;
    int y = a[_x];
    int _y = r[x];
    swap(a[_x], a[_y]);
    swap(r[x], r[y]);
}

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

    int n, x;
    cin >> n >> x;
    int z = n+n;

    if (x==1||x==z-1) {
        cout << "No" << "\n";
        return 0;
    }

    for (int i = 1; i < z; i++) {
        a[i] = i;
        r[i] = i;
    }

    placeAt(x, n);
    placeAt(x-1, n-1);
    placeAt(x+1, n+1);
    if (x+2 < z) placeAt(x+2, n-2);
    if (x-2 > 0) placeAt(x-2, n+2);

    cout << "Yes\n";
    for (int i = 1; i < z; i++) cout << a[i] << "\n";

    return 0;
}


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

int main() {
  
  int N;
  cin >> N;
  int d = 0;
  
  for (int i = 0;i < N;i++) {
    string x;
    cin >> x;
    if (x == "Y") {
      d = 1;
    }
  }
  
  if (d == 0) {
    cout << "Three" << endl;
  } else if (d == 1) {
    cout << "Four" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <set>

using namespace std;
int main()
{
    int n, m, tmp;
    set<int> a, b;
    cin >> n;
    for (int i=0; i<n; ++i){
        cin >> tmp;
        a.insert(tmp);
    }
    cin >> m;
    for (int i=0; i<m; ++i){
        cin >> tmp;
        b.insert(tmp);
    }
    for (auto itr=a.begin(); itr != a.end(); ++itr){
        b.insert(*itr);
    }
    for (auto itr=b.begin(); itr != b.end(); ++itr){
        cout << *itr << endl;
    }
}


Measured memory_bytes: 31220
import itertools
import numpy as np

h, w, k = map(int, input().split())
ans = 0
grid = [[m for m in input()] for _ in range(h)]

flg=[True, False]
for fh in itertools.product(flg, repeat=h):
    for fw in itertools.product(flg, repeat=w):
        cnt = 0
        cflg = True
        for i in range(h):
            if not fh[i]: continue
            if not cflg: break
            for j in range(w):
                if not fw[j]: continue
                if grid[i][j] == '#': cnt += 1
                if cnt > k:
                    cflg = False 
                    break
                    
        if cnt == k: ans += 1
print(ans)

Measured memory_bytes: 27000
#include <iostream>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;

int H, W;
vector<long> v;
int main(){

	while (true){
		cin >> H >> W;
		if (H + W == 0)break;

		for (int y = 0; y < H; ++y){
			for (int x = 0; x < W; ++x){
				if (y % 2 == 0){
					(x % 2 == 0) ? cout << "#" : cout << ".";
				}
				else{
					(x % 2 == 0) ? cout << "." : cout << "#";
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1152
n = int(input())
a = [int(i) for i in input().split()]
maxind = a.index(max(a))
maxnum = a[maxind]
tmp = 0
for i in range(len(a)):
    if i == maxind:
        continue
    tmp += a[i]
msg = 'No'
if maxnum < tmp:
    msg = 'Yes'
print(msg)

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

void dfs_comp(vector<vector<int>> const& adjlist, vector<int>& comp, vector<int>& oddity, int v, int color, int odd = 0)
{
    if (comp[v] == -1) {
        comp[v] = color;
        oddity[v] = odd;
        for (int nn : adjlist[v]) {
            dfs_comp(adjlist, comp, oddity, nn, color, 1 - odd);
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adjlist(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b; --a; --b;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }

    vector<vector<int>> inv_adjlist(n);
    for (int i = 0; i < n; ++i) {
        sort(adjlist[i].begin(), adjlist[i].end());
        for (int j = 0, k = 0; j < n; ++j) {
            if (k < (int) adjlist[i].size() && adjlist[i][k] == j) {
                ++k;
            } else if (i != j) {
                inv_adjlist[i].push_back(j);
            }
        }
    }

    vector<int> comp(n, -1);
    vector<int> oddity(n, -1);
    int ncomp = 0;
    for (int i = 0; i < n; ++i) {
        if (comp[i] == -1) {
            dfs_comp(inv_adjlist, comp, oddity, i, ncomp);
            ncomp += 1;
        }
    }

    // Проверить двудольность
    for (int i = 0; i < n; ++i) {
        for (int nn : inv_adjlist[i]) {
            if (oddity[nn] == oddity[i]) {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    vector<int> comp_size(ncomp);
    vector<int> comp_oddsize(ncomp);
    for (int i = 0; i < n; ++i) {
        comp_size[comp[i]] += 1;
        comp_oddsize[comp[i]] += oddity[i];
    }

    vector<int8_t> knapsack(n + 1), nknapsack(n + 1);
    knapsack[0] = 1;
    for (int icomp = 0; icomp < ncomp; ++icomp) {
        for (int i = 0; i <= n; ++i) {
            if (knapsack[i]) {
                nknapsack[i + comp_oddsize[icomp]] = 1;
                nknapsack[i + comp_size[icomp] - comp_oddsize[icomp]] = 1;
            }
        }
        knapsack.assign(n + 1, 0);
        knapsack.swap(nknapsack);
    }

    int v = 0;
    for (int i = n / 2; i >= 0; --i) {
        if (knapsack[i]) {
            v = i;
            break;
        }
    }

    cout << (v * (v - 1) / 2 + (n - v) * (n - v - 1) / 2) << endl;
}


Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		int x = scan.nextInt();

		int count = 0;
		for(int i=0; i<=a; ++i) {
			for(int j=0; j<=b; ++j) {
				for(int k=0; k<=c; ++k) {
					int sum = 500*i+100*j+50*k;
					if(sum == x) {
						count++;
					}
				}
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 23252
#include <iostream>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <cassert>
#include <vector>
#include <cmath>
using namespace std;

#define sqr(x) ((x) * (x))

int main() {
	int n;

	while(cin >> n, n) {
		vector<pair<double,double> > v;
		vector<pair<double,double> > a;
		pair<double,double> prev;

		for(int i = 0; i < n; i++) {
			pair<double,double> tmp;

			scanf("%lf,%lf", &tmp.first, &tmp.second);
			v.push_back(tmp);
		}

		sort(v.begin(), v.end());
		a.push_back(v[0]);
		prev.first = 0;
		prev.second = 1;

		do {
			double theta = 10;
			int next_v = -1;
			pair<double,double> next_prev;

			for(int i = 0; i < v.size(); i++) {
				pair<double,double> tmp;
				double tmp_cos;
				double tmp_theta;

				tmp.first = v[i].first - a[a.size() - 1].first;
				tmp.second = v[i].second - a[a.size() - 1].second;

				if(tmp.first == 0 && tmp.second == 0)
					continue;

				tmp_cos = (prev.first * tmp.first + prev.second * tmp.second) / (sqrt(sqr(prev.first) + sqr(prev.second)) * sqrt(sqr(tmp.first) + sqr(tmp.second)));
				tmp_theta = acos(tmp_cos);

				if(tmp_theta < theta) {
					theta = tmp_theta;
					next_v = i;
					next_prev = tmp;
				}
			}

			assert(next_v >= 0);
			a.push_back(v[next_v]);
			prev = next_prev;
		} while(a[0] != a[a.size() - 1]);

		cout << v.size() - a.size() + 1 << endl;
	}
	
	return 0;
}

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

#include <set>
#include <map>
#include <iomanip>

using namespace std;

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

using ll = long long;

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

	cout << r * 2 * 3.141592 << endl;

	return 0;
}


Measured memory_bytes: 3780
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

void solve()
{
 string a;
 cin>>a;
  int l=a.length();
  if(a[l-1]=='s'){cout<<a<<"es"<<endl;}
  else{cout<<a<<"s"<<endl;}
}

int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);cout.tie(0);

        solve();

    return 0;
}



Measured memory_bytes: 3616
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;

const int N=100005;

int n;
ll sum,d;
ll a[N];

int main(){
	int i;
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	a[n+1]=a[1];
	for (i=1;i<=n;i++) a[i]=a[i+1]-a[i];
	if (sum%(1ll*n*(n+1)/2)) printf("NO\n");
	else{
		d=sum/(1ll*n*(n+1)/2);
		for (i=1;i<=n;i++){
			a[i]-=d;
			if (a[i]%n!=0||a[i]>0){
				printf("NO\n");
				return 0;
			}
		}
		printf("YES\n");
	}
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
using namespace std;
 
int main(){
   int n,m,d;
   cin >> n >> m >> d;
 
   if( d !=0){
      printf("%.7f", 2.0 * (n-d) * (m-1) / n / n);
   }else{
      printf("%.7f", 1.0  * (m-1)  / n);
   }
}


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

int main() {
	ll		a,b,c,h,i,j,k,l,m,n,x,y;
	string	ans = "No";
	cin >> n >> m >> k;
	for(i=0;i<=n;i++) for(j=0;j<=m;j++) {
		x = i*(m-j) + j*(n-i);
		if (x==k) ans = "Yes";
	}

	cout << ans << endl;
	return 0;
}


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

int main() {
    int n,buf = 0,sum = 0;
    cin >> n;
    vector<int> d(n);
    for(int i = 0; i < n; i++){
        cin >> d.at(i);
    }
    sort(d.begin(),d.end());
    reverse(d.begin(),d.end());
    for(int i = 0; i < n; i++){
        if(buf != d.at(i)){
            sum++;
        }
        buf = d.at(i);
    }
    cout << sum << endl;
}


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

AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key = lambda x: x[0])

count = 1
B = 10 ** 9
for a, b in AB:
    if a < B:
        B = min(B, b)
    else:
        count += 1
        B = b

print (count)


Measured memory_bytes: 18232
#include <stdio.h>

int main(void)
{
	int doubt=100000,amari;
	int week;
	int i;
	
	scanf("%d",&week);
	
	for(i=0;i<week;i++)
	{
		doubt = doubt*1.05;
		
		amari = doubt%1000;
		if(amari!=0)
		{
			doubt += 1000-amari;
		}
	}
	
	printf("%d\n",doubt);
	
	return 0;
}


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

int N;
long long A[330];
bool exist = true;

int main(void){

    cin >> N;
    for (int i = 1; i <= N;i++) cin >> A[i];
    long long S = A[1] + A[2];
    long long X = 0;
    for (int i = 1;i <= N; i++) {
        X = X^A[i];
    }
    X = X ^ (A[1] ^ A[2]);

    long long D = (S - X) / 2;
    if (D < 0 || D > A[1]) exist = false;
    if ((D & X) != 0 || ((S + X) & 1) != 0) exist = false;

    if (exist){
        long long ans = D;
        for (int i = 40; 0 <= i; i--){
            if ((X >> i) & 1){
                if ((ans | (1LL << i)) <= A[1]) ans |= (1LL << i);
            }
        }
        if (A[1] - ans >= 0 && ans > 0) {
             cout << A[1] - ans << endl;
        }
        else {
            cout << -1 << endl;
        }
    } else {
        cout << -1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3608
from collections import Counter
def p(n):
    a=[]
    i=2
    while i*i<=n:
        while n%i==0:
            a.append(i)
            n//=i
        i+=1
    if n>1:
        a.append(n)
    return a
N=int(input())
c=Counter(p(N))
ans=0
for k,v in c.items():
    j=0
    for i in range(1,100000):
        j+=i
        if j>v:
            break
        ans+=1
print(ans)

Measured memory_bytes: 9380
from itertools import product
N = int(input())
lis = [0]*(N+1)
numlist = [i for i in range(1,100)]
for x,y,z in product(numlist, repeat=3):
    q = x**2 + y**2 + z**2 + x*y + y*z + z*x
    if q <= N:
        lis[q] += 1
for i in lis[1:]:
    print(i)

Measured memory_bytes: 68740
#coding: utf-8

def check(d,n):
    nums = []
    r = 100 ** d
    nums.append(r)
    # if r == 0: r = 1
    # for i in range(1,n+1):
    #     nums.append(r * i)

    count = r
    while True:
        if len(nums) >= n:
            break
        count = count + r
        r2 = (r*100)
        if count % r2 != 0:
            nums.append(count)
    return nums[-1]

if __name__ == "__main__":
    d,n = map(int, input().split(" "))
    result = []

    print(check(d,n))

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass : Scanner
{
    static void Main()
    {
        var N = RLong();
        
        long ans = 0;
        long max = N;
        for (long i = 1; i <= Sqrt(N)+1; i++)
        {
            if (N % i == 0&&N/i-1>i) ans += N / i-1;
        }
        WriteLine(ans);
    }
}

class Scanner
{
    public static int RInt() => int.Parse(Console.ReadLine());
    public static long RLong() => long.Parse(Console.ReadLine());
    public static string RString() => Console.ReadLine();
    public static double RDouble() => double.Parse(Console.ReadLine());

    public static int[] RInts() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    public static int[] RInts(Func<string, int> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static long[] RLongs() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
    public static long[] RLongs(Func<string, long> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static double[] RDoubles() => Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    public static double[] RDoubles(Func<string, double> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static string[] RStrings() => Console.ReadLine().Split();
    //public static string[] RStrings(Func<string, string> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static T1 ReadStream<T1>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        return r1;
    }
    public static (T1, T2) ReadStream<T1, T2>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        return (r1, r2);
    }
    public static (T1, T2, T3) ReadStream<T1, T2, T3>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        return (r1, r2, r3);
    }
    public static (T1, T2, T3, T4) ReadStream<T1, T2, T3, T4>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        var r4 = (T4)Convert.ChangeType(r[3], typeof(T4));
        return (r1, r2, r3, r4);
    }
}

Measured memory_bytes: 27380
#include<bits/stdc++.h>
using namespace std;
#define ll int64_t
#define f first
#define sec second
#define pb push_back
#define pf push_front
#define po pop_back
#define fast ios_base::sync_with_stdio(false)
#define vi vector<ll>
#define vii vector< pair<ll,ll> >
#define pi pair<ll,ll>
#define map map<ll,ll>
#define set set<ll>
#define tostr to_string
#define toint stoi
#define gcd __gcd

vi g[100002];
ll vis[100002];
ll d1[100002],d2[100002];

void dfs1(ll u,ll d)
{
        vis[u]=1;
        d1[u]=d;
        for(auto x:g[u])
        { if(vis[x]==0)
           dfs1(x,d+1);
        }
}

void dfs2(ll v,ll d)
{
      vis[v]=1;
        d2[v]=d;
        for(auto x:g[v])
        { if(vis[x]==0)
           dfs2(x,d+1);
        }
}

int main()
{
    fast;
    ll n,i,u,v,a,b;
    cin>>n>>u>>v;
    for(i=0;i<n-1;i++)
    {
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    for(i=1;i<=n;i++)
        vis[i]=0;
    dfs1(u,0);

    for(i=1;i<=n;i++)
        vis[i]=0;
    dfs2(v,0);

    ll ans=0;
    for(i=1;i<=n;i++)
     {if(d2[i]>d1[i])
       ans=max(ans,d2[i]);
     }

    cout<<ans-1<<endl;
}


Measured memory_bytes: 10752
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x;
  int s1, s2, s3;
  
  cin >> x;
  s1 = x / 100;
  s2 = (x - s1 * 100) / 10;
  s3 = x % 10;
  
  cout << (s1 + s2 + s3) << endl;
}

Measured memory_bytes: 3592
N = int(input())
Robot = []
for i in range(N):
    a, b = map(int, input().split())
    Robot.append((a - b, a + b))
now = -10000000000
Robot.sort(key=lambda x: x[1])
ans = 0

for i in range(N):
    if Robot[i][0] >= now:
        ans +=1
        now = Robot[i][1]

print(ans)

Measured memory_bytes: 57048
#!/usr/bin/env python3
import sys
INF=10**16

def solve(N: int, K: int, h: "List[int]"):

    dp = [INF]*N
    dp[0] = 0
    dp[1] = abs(h[1] - h[0])

    for i in range(2, N):
        for k in range(1, K + 1):
            dp[i] = min(dp[i - k] + abs(h[i] - h[i - k]), dp[i])
    
    print(dp[N - 1])

    return


# Generated by 1.1.6 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
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


Measured memory_bytes: 53284
open List
let rec($)l=function[]->l|[e]->e::l|((a,b),s)as x::((((c,d),t)::z)as y)->if a<c&&b>d then l$(((a,b),s+t)::z)else(x::l)$y
let a=[]$(fold_left(fun(i,q,w)x->match x with|'_'->i+1,q,w|'\\'->i+1,i::q,w|_->(match q with[]->i+1,q,w|j::o->i+1,o,((j,i),i-j)::w))(0,[],[])(let s=read_line()in let a=ref[]in for i=String.length s-1downto 0do a:=s.[i]::!a done;!a)|>fun(_,_,t)->t);;Printf.printf"%d
"(fold_left(fun z(_,n)->z+n)0 a);print_int(length a);iter(fun(_,n)->Printf.printf" %d"n)a;print_newline()

Measured memory_bytes: 5200
X, N = map(int, input().split())
if N == 0:
    print(X)
elif N == 100:
    if X <= 50:
        print(0)
    else:
        print(101)

else:
    p = list(map(int, input().split()))
    abs_list = []
    re_list = []
    min = 1000
    min_index = 0

    for i in range(250):
        abs_list.append(-100+i)
    for j in p:
        abs_list.remove(j)
    for i in range(len(abs_list)):

        re_list.append(abs(abs_list[i] - X))
    for i in range(len(re_list)):
        if min > re_list[i]:
            min = re_list[i]
            min_index = i
    if re_list[min_index] > X:
        print(0)
    else:
        print(abs_list[min_index])


Measured memory_bytes: 9224
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	a.erase(unique(all(a)), a.end());

	bool sp = false;
	for (int i : a)
	{
		print((sp ? " " : "") << i);
		sp = true;
	}
	println("");
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

bool iskaibun(string s) {
	for (int i = 0; i < s.size(); ++i) if (s[i] != s[s.size() - 1 - i]) return false;
	return true;
}

int main() {
	string S;
	cin >> S;
	
	bool ans = true;
	string a = S.substr(0, S.size() / 2);
	string b = S.substr((S.size() + 1) / 2);
	ans &= iskaibun(a);
	ans &= iskaibun(b);
	
	reverse(ALL(a));
	ans &= a == b;
	puts([&] {
		return ans;
	}() ? "Yes": "No");
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// chmax, chmin
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;
}

vector<vector<pair<int, int> > > A;

int main() {
    int N;
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            int x, y;
            cin >> x >> y;
            --x;
            A[i].push_back({x, y});
        }
    }

    int ans = 0;
    for (int i = 0; i < (1 << N); i++) {
        int bad = false;
        for (int j = 0; j < N; j++) {
            int ok = true;
            int p = i >> j & 1;
            for (auto t : A[j]) {
                if ((i >> t.first & 1) != t.second) {
                    ok = false;
                }
            }
            if(p && ok == false ){
                bad = true;
            }
        }
        if(!bad){
            ans = max(ans, __builtin_popcount(i));
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
/*   -- AUTHOR -- 
  ---- cervotrex ---- 
*/
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define eb emplace_back
#define mk make_pair
#define all(arr) arr.begin(),arr.end()
#define mod 1000000007
const ll INF = 1LL << 60;
const int MAX_N = 1000005;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ook order_of_key
#define fbo find_by_order
// ordered_set <int> s  ;
// auto x=s.find_by_order(k);
// s.order_of_key(val);

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a(n), b(MAX_N,0), dp(MAX_N,0);
    for(int i=0;i<n;i++){
      cin>>a[i];
      b[a[i]]++;
      dp[a[i]]++;
      if(b[a[i]]>1)
        dp[a[i]]=0;
    }

    if(b[1]){
      if(b[1]>1)
        return cout<<"0\n", 0;
      else
        return cout<<"1\n", 0 ;
    }

    for(int i=0;i<n;i++){
      for(int j=2;j*j<=a[i];j++)
        if(a[i]%j==0&&(b[j]||b[a[i]/j])){
          dp[a[i]]=0;
          break;
        }
    } 

    int ans=0;
    for(int i=0;i<n;i++)
      if(dp[a[i]]>0)
        ans++;

    cout<<ans<<"\n";
  }
  return 0;
}

Measured memory_bytes: 11852
#include <iostream>
#include <cmath>
using namespace std;
#define KMAX  30
#define VMAX  1000000

int main(){
  int k, v;
  int K[KMAX];
  char T[VMAX+1];
  bool prime[VMAX+1];
  for (int i=0;i<=VMAX;i++) prime[i] = false;
  for (int i=3;i<=VMAX;i+=2) prime[i] = true;
  prime[2] = true;
  int limit = (int)sqrt((double)VMAX) + 1;
  for (int i=3;i<=limit;i+=2){
    if (!prime[i]) continue;
    for (int j=i+i;j<=VMAX;j+=i) prime[j] = false;
  }

  while (cin >> k >> v && !(k ==0 && v ==0)){
    for (int i=0;i<k;i++) cin >> K[i];
    for (int j=0;j<=v;j++) T[j]=0;
    T[0]=1;
    for (int j=K[0];j<=v;j+=K[0]) T[j]=1;
    for (int i=1;i<k;i++){
      for (int j=K[i];j<=v;j++){
        T[j] = (T[j] | T[j-K[i]]);
      }
    }
    int ans = -1;
    for (int i=v;i>1;i--)
      if (prime[i] && T[i]){
        ans = i;
        break;
      }
    if (ans==-1)
      cout << "NA" << endl;
    else
      cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3112
N, *A = map(int, open(0).read().split())

C = [0]*(N+1)
for a in A:
    C[a] += 1

total = 0
for c in C:
    total += c*(c-1)//2

for a in A:
    n = C[a]
    if n >= 2:
        ans = total - n + 1
    else:
        ans = total
    print(ans)

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


def get_fact(N):
  ret = set([N])
  for i in range(2,int(N**0.5)+2):
    if N%i == 0:
      ret.add(i)
      ret.add(N//i)
  return ret


def main():
  ## input
  N,K = map(int, input().split())
  An = list(map(int, input().split()))

  ## Solve
  fset = get_fact(sum(An))
  ans = 1
  for f in fset:
    Amod = [a%f for a in An]
    Amod = sorted(Amod)
    if sum(Amod[:-sum(Amod)//f]) <= K:
      ans = max(ans,f)
  return ans


if __name__ == "__main__":
  ans = main()
  print(ans)


Measured memory_bytes: 44508
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define temT template<typename T>
using namespace std;
typedef long long ll;
const int N=int(1e5)+10;

int fp[N],x,m,i,l,r; ll n,res,cur;

ll SB(){
	FOR(i,0,N-10) if(fp[i]==1) x=i;
	FOR(i,1,(int)n) res+=x,x=1ll*x*x%m;
	return res;
}

int main(){
	cin>>n>>x>>m;
	for(i=1;!fp[x];x=1ll*x*x%m,i++) fp[x]=i;
	if(fp[x]>n) return cout<<SB(),0;
	FOR(j,1,N-10) if(fp[j] && fp[j]<fp[x]) res+=j;
	l=i-fp[x]; r=(n-fp[x]+1)%l;
	FOR(j,1,N-10) if(fp[j]>=fp[x]){
		if(fp[j]-fp[x]<r) res+=j;
		cur+=j;
	}
	res+=cur*((n-fp[x]+1)/l);
	return cout<<res,0;
}

Measured memory_bytes: 4012
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    string s;
    cin>>s;
    int ans=0,cnt=0;
    rep(i,s.size()){
        if(s[i]=='A'||s[i]=='T'||s[i]=='G'||s[i]=='C'){
            cnt++;
        }
        else{
            ans=max(ans,cnt);
            cnt=0;
        }
    }
    ans=max(ans,cnt);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define INF 1e9
typedef long long ll;
using namespace std;

int main() {
    int a,b; cin >> a >> b;
    if((a+b)%2==0){
        cout << (a+b)/2 << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

vector<bool> b;

void dfs(vector<vector<int>>&z,vector<int>&ans,int v){
    b[v] = true;
    int x = 0;
    for (auto next_v : z[v]) {
        if (b[next_v]) continue;
        dfs(z,ans,next_v);
        x = x ^ (ans.at(next_v) + 1);
    }
    ans.at(v) = x;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>>z(n);
    for (int i = 0; i < n-1; i++) {
        ll a, b;
        cin >> a >> b;
        z.at(a-1).push_back(b-1);
        z.at(b-1).push_back(a-1);
    }
    vector<int>ans(n);
    b.assign(n, false);
    dfs(z, ans, 0);
    if (ans.at(0) == 0)cout << "Bob" << endl;
    else cout << "Alice" << endl;
}

Measured memory_bytes: 13952
#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, w;
	while(true) {
		cin>>h>>w;
		if(h==0&&w==0) break;
		for(int j=0; j<w; j++) cout<<'#';
		cout<<'\n';
		for(int i=2; i<h; i++) {
			cout<<'#';
			for(int j=2; j<w; j++) {
				cout<<'.';
			}
			cout<<"#\n";
		}
		for(int j=0; j<w; j++) cout<<'#';
		cout<<"\n\n";
	}
	return 0;
}



Measured memory_bytes: 3156
n = int(input())
C = []
for i in range(n):
    x, y = map(int, input().split())
    C.append(complex(x, y))


def calc_kyori(O, C):
    res = 0
    for i in range(n):
        temp = abs(O - C[i])
        res = max(temp, res)
    return res


def sannbunn_first(x, my, MY):
    cnt = 100
    while cnt > 0:
        y1 = (2 * my + MY) / 3
        y2 = (my + 2 * MY) / 3
        v1 = calc_kyori(complex(x, y1), C)
        v2 = calc_kyori(complex(x, y2), C)
        if v2 < v1:
            my = y1
        else:
            MY = y2
        cnt -= 1
    return my


def sannbunn_second(mx, MX, my, MY):
    cnt = 100
    while cnt > 0:
        x1 = (2 * mx + MX) / 3
        x2 = (mx + 2 * MX) / 3
        yy1 = sannbunn_first(x1, my, MY)
        v1 = calc_kyori(complex(x1, yy1), C)
        yy2 = sannbunn_first(x2, my, MY)
        v2 = calc_kyori(complex(x2, yy2), C)
        if v2 < v1:
            mx = x1
        else:
            MX = x2
        cnt -= 1
    return mx, yy1, v1


if n == 2:
    ans = abs(C[0] - C[1]) / 2
else:
    rx, ry, ans = sannbunn_second(0, 1000, 0, 1000)
    # ans = calc_kyori(complex(rx, ry), C)
print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))

int main()
{
    std::ios::sync_with_stdio(false);
    ll h,w;
    while(cin>>h>>w)
    {
        ll ans=inf;
        for(int i=1;i<h;i++)
        {
            ll a=h-i;
            if(i!=h-1)
            {
                ans=min(ans,max(i*w,max(a/2*w,(a-a/2)*w))-min(i*w,min(a/2*w,(a-a/2)*w)));
            }
            ans=min(ans,max(i*w,max(a*(w/2),a*(w-w/2)))-min(i*w,min(a*(w/2),a*(w-w/2))));
         //   cout<<i<<" "<<max(i*w,max(a*(w/2),a*(w-w/2)))-min(i*w,min(a*(w/2),a*(w-w/2)))<<" "<<ans<<endl;
       //     cout<<a<<" "<<i<<" "<<w<<" "<<endl;
        }
    //    cout<<ans<<endl;
        for(int i=1;i<w;i++)
        {
            ll a=w-i;
            if(i!=w-1)
            {
                ans=min(ans,max(i*h,max(a/2*h,(a-a/2)*h))-min(i*h,min(a/2*h,(a-a/2)*h)));
            }
            ans=min(ans,max(i*h,max(a*(h/2),a*(h-h/2)))-min(i*h,min(a*(h/2),a*(h-h/2))));
        }
        cout<<ans<<endl;
    }
    return 0;
}


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

long long n,a,m,b,qq;
string ss;
int main() {
    cin>>n;
    int l[n],l1[n];
    l[n]=0;
    l1[n]=0;
    for (int i=0; i<=n; i++){
        l[i]=0;
        l1[i]=0;
    }
    for (int i=0; i<n; i++){
        cin>>l[i];
    }
    for (int i=1; i<n; i++){
        if (i==1){
            l1[i]=abs(l[i]-l[i-1]);
        }
        else{
            l1[i]=min(l1[i-1]+abs(l[i-1]-l[i]), l1[i-2]+abs(l[i-2]-l[i]));
        }
    }
    cout<<l1[n-1]<<endl;
}


Measured memory_bytes: 1024
while True:
    h,w = [int(x) for x in input().split( )]
    if h == w == 0:
        break
    else:
        for hh in range(h):
            for ww in range(w):
                if (hh+ww) % 2 == 0:
                    print('#',end = '')
                else:
                    print('.',end = '')
            print('')
        print('')



Measured memory_bytes: 7016