akhauriyash/Code-Regression huggingface dataset:
def solve(N, P):
    prime_list = []
    for i in range(2, int(P ** (1 / 2)) + 1):
        cnt = 0
        while P % i == 0:
            cnt += 1
            P //= i
        if cnt:
            prime_list.append([i, cnt])
    if P != 1:
        prime_list.append([P, 1])

    ans = 1
    for prime, cnt in prime_list:
        if cnt >= N:
            ans *= prime ** (cnt // N)
    return ans

if __name__ == '__main__':
    n, p = map(int, input().split())
    print(solve(n, p))

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

int main(void){
    char A[100];
    char B[100];
    scanf("%s",&A);
    scanf("%s",&B);
    int fini=0;
    if(strlen(A)>strlen(B)){
        printf("GREATER");
      	fini=1;
    }else if(strlen(A)<strlen(B)){
        printf("LESS");
      	fini=1;
    }else{
        for(int i=0;i<strlen(A);i++){
            if((int)A[i]>(int)B[i]){
                printf("GREATER");
                fini=1;
                break;
            }else if((int)A[i]<(int)B[i]){
                printf("LESS");
                fini=1;
                break;
            }
        }
    }
    if(fini==0){
        printf("EQUAL");
    }
    
    return 0;
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  if(s.size()==1){
    cout << s[0]-'0' << endl;
  }
  else{
    bool flag=true;
    for(int i=1;i<s.size();i++){
      if(s[i]!='9'){
        flag=false;
      }
    }
    if(!flag){
      cout << s[0]-'0'-1+9*(s.size()-1) << endl;
    }
    else{
      cout << s[0]-'0'+9*(s.size()-1) << endl;
    }
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
//const long long mod = 1000000007;
//const long long mod = 998244353;
int main() {
	int N;
	scanf("%d", &N);
	long long*cnt = new long long[N];
	for (long long i = 0; i < N; i++)cnt[i] = 0;
	for (long long i = 0; i < N; i++) {
		int A;
		scanf("%d", &A);
		cnt[A - 1]++;
	}
	long long*num = new long long[N + 1];
	for (long long i = 0; i <= N; i++)num[i] = 0;
	for (long long i = 0; i < N; i++) {
		for (long long j = 0; j < cnt[i]; j++) {
			num[j]++;
		}
	}
	long long*rel = new long long[N + 1];
	for (long long i = 0; i <= N; i++)rel[i] = 0;
	for (long long i = 1; i <= N; i++) {
		rel[i] = rel[i - 1] + num[i - 1];
	}
	for (long long K = 1; K <= N; K++) {
		long long r = 0;
		for (int i = 20; i >= 0; i--) {
			long long c = r | (1 << i);
			if (c >= N + 1)continue;
			if (rel[c] >= c * K)r = c;
		}
		printf("%lld\n", r);
	}
	return 0;
}

Measured memory_bytes: 7936
def solve():
  n = input()

  if not n:
    return False

  b = map(int, raw_input().split())

  for i in range(n + 1):
    a = b[:i] + b[i + 1:]
    ok = True
    s = set()
    for j in range(n - 1):
      s.add(a[j + 1] - a[j])
    if len(s) == 1:
      print b[i]
      break

  return True

while solve():
  pass

Measured memory_bytes: 4248
def ctoi(c):  # a~zを0~25に変換する(各アルファベットを数字に変換する)
    return ord(c) - 97


N = int(input())
S = list(input())
bits = [[0]*(N+1) for _ in range(26)]  # Binary Indexed Treeを26種類の各アルファベットについてもつ(0初期化, 1-index)


def BIT_query(idx):  # 各文字について1からidx番目までの文字数を数える
    res = [0]*26
    for i in range(26):
        tmp = 0
        p = idx
        while p > 0:  # 1からidx番目までの要素の和を取る
            tmp += bits[i][p]
            p -= p&(-p)  # 区間の長さを引くことで次のindexを得ることができる
        res[i] = tmp
    return res


def BIT_update(idx, alphabet, x):  # alphabet番目のアルファベットについてidx番目の要素の値にxを加える
    while idx <= N:  # idx番目の要素を含む全ての要素についてxを加える
        bits[alphabet][idx] += x
        idx += idx&(-idx)


for i in range(N):  # 各BITを与えられた文字列で初期化する
    BIT_update(i+1, ctoi(S[i]), 1)  # Sのi番目(0-index)の文字に対応するBITのi+1番目の要素を1として更新する

Q = int(input())
for _ in range(Q):
    flag, a, b = map(str, input().split())
    flag = int(flag)
    a = int(a)
    if flag == 1:
        if S[a-1] == b:  # 同じ文字の場合, 変更しない
            continue
        else:
            BIT_update(a, ctoi(S[a-1]), -1)  # a番目の要素を別のものに変えるので、-1
            BIT_update(a, ctoi(b), 1)  # a番目の要素を文字bに変えるので+1
            S[a-1] = b  # 文字列のa番目の文字を変更する
    elif flag == 2:  # aとbは区間の左端と右端
        b = int(b)
        cnt1 = BIT_query(b)  # 1からbまでの各文字の文字数
        cnt2 = BIT_query(a-1)  # 1からa-aまでの各文字の文字数
        ans = 0
        for i in range(26):
            if cnt1[i]-cnt2[i] > 0:  # lからrまでのその文字の文字数が1以上であれば、その文字はlからrまでの部分文字列に現れるので種類数を1増やす
                ans += 1
        print(ans)


Measured memory_bytes: 165020
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(Q)]

A_lst = combinations_with_replacement(range(1, M+1), N)
A_lst = list(map(list, A_lst))
A_lst.sort()

dm = 0 #d_sum_max
for A in A_lst:
    ds = 0 #d_sum
    for a, b, c, d in lst:
        if A[b-1] - A[a-1] == c:
            ds += d
    if ds > dm:
        dm = ds
print(dm)

Measured memory_bytes: 22860
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

struct UnionFind{
    v: Vec<usize>
}

impl UnionFind{
    fn new(n: usize) -> UnionFind{
        let mut v: Vec<usize> = Vec::new();
        for i in 0..n{
         v.push(i);
        }
        UnionFind{v:v}
    }

    fn find(&mut self, i: usize) -> usize{
        if self.v[i] == i{
            i
        }else{
            let ni = self.v[i];
            self.v[i] = self.find(ni);
            self.v[i]
        }
    }

    fn union(&mut self, i: usize, j: usize){
        let root_i = self.find(i);
        let root_j = self.find(j);
        self.v[root_i] = root_j;
    }

}

struct CombMod{
    fac: Vec<u64>,
    inv: Vec<u64>,
    finv: Vec<u64>,
    mmod: u64,
}

impl CombMod{
    pub fn new(max: u64, m: u64) -> CombMod{
        let max: usize = max as usize;
        let mut fac: Vec<u64> = vec![0;max+1];
        let mut finv: Vec<u64> = vec![0;max+1];
        let mut inv: Vec<u64> = vec![0;max+1];

        fac[0] = 1;
        fac[1] = 1;
        finv[0] = 1;
        finv[1] = 1;
        inv[1] = 1;

        for i in 2..max+1{
            fac[i] = fac[i-1] * i as u64 % m;
            inv[i] = m - inv[m as usize %i] * (m/(i as u64)) % m;
            finv[i] = finv[i-1] * inv[i] % m;
        }

        CombMod{
            fac: fac,
            finv: finv,
            inv: inv,
            mmod: m,
        }
    }

    fn get(&self, n: u64, m: u64) -> u64{
        assert!(n >= m && n != 0 && m != 0);
        self.fac[n as usize] * self.finv[m as usize] % self.mmod
            * self.finv[(n-m) as usize] % self.mmod
    }
}

fn main(){
    let n: usize = read_as_vec()[0];
    let s = read_as_string();

    println!("{}", s.matches("ABC").count());
}


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

#define int long long
#define counter(m)     for(int i=0;i<m;i++)
#define gcd            __gcd
#define endl           "\n"
#define pb             emplace_back
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define deci(x, y)      fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PI             3.141592653589793238
using namespace std;
int grid[101][101];
int a[100001];
int32_t main() {
    nitin;
    int h,w;
    cin>>h>>w;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int idx=0;
    for(int i=0;i<h;i++)
    {
        if(i%2==0)
        {
            for(int j=0;j<w;j++)
            {
                grid[i][j]=idx+1;
                a[idx]--;
                if(a[idx]==0)
                    idx++;
            }
        }
        else{
            for(int j=w-1;j>=0;j--)
            {
                grid[i][j]=idx+1;
                a[idx]--;
                if(a[idx]==0)
                    idx++;
            }
        }
    }
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
            cout<<grid[i][j]<<((j==w-1)?"\n":" ");
    }
    return 0;
}

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

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	map<string, vector<int>>M;
	string s; int n;
	while (cin >> s >> n) {
		M[s].push_back(n);
	}
	each(it, M) {
		cout << it->first << endl;
		sort(it->second.begin(), it->second.end());
		int i(0);
		each(that, it->second) {
			if (i++)cout << " ";
			cout << *that;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3048
n,x,y = map(int,input().split())
ans = [0]*n
for i in range(n):
    for j in range(i,n):
        ans[min(j-i,(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])


Measured memory_bytes: 3444
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main(void){
	char s1[1001];
	char s2[] = " .\n";
	char w[11];
	char end[] = "END_OF_TEXT";
	int i;
	char *tok;
	char *tp;
	int cnt = 0;

	scanf("%s", w);

	for(i = 0;i< sizeof(w)/sizeof(w[0]);i++){
		w[i] = tolower(w[i]);
	}

	while(1){
		scanf("%s", s1);

		tok = strtok( s1, s2);

		while(tok != NULL){
			if(strcmp(end,tok) == 0){
				printf("%d\n", cnt);
				return 0;
			}

			tp = tok;

			while(*tok != '\0'){
				*tok = tolower(*tok);
				++tok;
			}

			tok = tp;

			if(strcmp(w,tok) == 0){
				cnt++;
			}
			tok = strtok(NULL,s2);
		}
	}
	return 0;
}



Measured memory_bytes: 2104
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using P = pair<int,int>;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;
int dist[2020][2020];
int main() {
    int n, x, y; cin >> n >> x >> y;
    --x; --y;
    rep(i,n)rep(j,n) {
        if (j<=i) continue;
        dist[i][j] = j-i;
    }
    dist[x][y] = 1;
    
    rep(i,n) {
        rep(j,n) {
            if (j<=i) continue;
            if (i==x && j==y) continue;
            
            if (i<=x && y<=j) dist[i][j] = min(dist[i][x]+dist[y][j]+1,dist[i][j]);
            else if (i>x && y<=j) dist[i][j] = min(dist[x][i]+dist[y][j]+1,dist[i][j]);
            else if (i<=x && y>j) dist[i][j] = min(dist[i][x]+dist[j][y]+1,dist[i][j]);
            else if (i>x && y>j) dist[i][j] = min(dist[x][i]+dist[j][y]+1,dist[i][j]);
            //if (i<=x && y<=j) dist[i][j] = min(dist[i][x]+dist[y][j]+1,dist[i][j-1]+1);
            //else if (i>x && y<=j) dist[i][j] = min(dist[x][i]+dist[y][j]+1,dist[i][j-1]+1);
            //else if (i<=x && y>j) dist[i][j] = min(dist[i][x]+dist[j][y]+1,dist[i][j-1]+1);
            //else if (i>x && y>j) dist[i][j] = min(dist[x][i]+dist[j][y]+1,dist[i][j-1]+1);
            
        }
    }
    map<int,int> mp;
    rep(i,n) {
        rep(j,n) {
            if (j<=i) continue;
            //cout << "i: " << i << " j: " << j << " dist: " << dist[i][j] << endl;
            mp[dist[i][j]]++;
        }   
    }
    for (int i=1;i<=n-1;++i) {
        cout << mp[i] << endl;
    }
    return 0;
}

























Measured memory_bytes: 15488
#include <iostream>
#define INF 1e+9
using namespace std;

int main(){
	int d,n;
	while(cin >> d >> n,d){
		int a[100],e[100],r[100],dp[101][101];
		for(int i = 0;i <= d;i++){
			for(int j = 0;j <= 100;j++) dp[i][j] = INF;
		}
		dp[d][0] = 0;
		for(int i = 0;i < n;i++) cin >> a[i] >> e[i] >> r[i];
		for(int i = d;i >= 1;i--){
			for(int j = 0;j <= 100;j++){
				for(int k = 0;k < n;k++){
					if(r[k] <= j){
						dp[max(0,i - a[k])][min(100,j + e[k])] = min(dp[max(0,i - a[k])][min(100,j + e[k])],dp[i][j] + 1);
					}
				}
			}
		}
		int mi = INF;
		for(int i = 0;i <= 100;i++) mi = min(mi,dp[0][i]);
		if(mi == INF) cout << "NA" << endl;
		else cout << mi << endl;
	}
	return 0;
}

Measured memory_bytes: 3116
/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
*/
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int arr[200200];
int segtree[600600];
int cnt[200200];
vector<int> vi[200200];
vector<int> va;
int sana[200200];
void update(int idx, int l, int r, int id, int val)
{
    if(id < l || id > r) return;
    if(l == r && l == id) {
        segtree[idx] = val;
        return;
    }
    int mid = (l+r) / 2;
    update(idx*2, l, mid, id, val);
    update(idx*2+1, mid+1, r, id, val);
    segtree[idx] = max(segtree[idx*2], segtree[idx*2+1]);
}
int query(int idx, int l, int r, int kiri, int kanan)
{
    if(l > kanan || r < kiri) return 0;
    if(l >= kiri && r <= kanan) return segtree[idx];
    int mid = (l+r) / 2;
    int curr = 0;
    curr = max(curr, query(idx*2, l, mid, kiri, kanan));
    curr = max(curr, query(idx*2+1, mid+1, r, kiri, kanan));
    return curr;
}
const int N = 2e5 + 5;
void dfs(int now, int prev)
{
    int last = query(1, 1, N, arr[now], arr[now]);
    int curr = query(1, 1, N, 1, arr[now] - 1);
    curr++;
    update(1, 1, N, arr[now], curr);
    sana[now] = query(1, 1, N, 1, N);
    for(auto x : vi[now])
    {
        if(x == prev) continue;
        dfs(x, now);
    }
    update(1, 1, N, arr[now], last);
}
int main()
{
	int n,i,j,k,x,y,ans,curr,temp,m;
	int tc;
	cin >> n;
	for(i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
        va.push_back(arr[i]);
    }
    sort(va.begin(), va.end());
    for(i=1;i<=n;i++)
    {
        arr[i] = lower_bound(va.begin(), va.end(), arr[i]) - va.begin();
        arr[i]++;
    }
    for(i=1;i<n;i++)
    {
        cin >> x >> y;
        vi[x].push_back(y);
        vi[y].push_back(x);
    }
    dfs(1, 0);
    for(i=1;i<=n;i++) cout << sana[i] << endl;
	return 0;
}


Measured memory_bytes: 32820
def main():
    n, m = list(map(int, input().split()))
    ret = {}
    for i in range(m):
        q, res = list(input().split())
        if q in ret:
            if ret[q][-1] == 'WA':
                ret[q].append(res)
        else:
            ret[q] = [res]
    ans = 0
    pena = 0
    for k in ret:
        if ret[k][-1] == 'AC':
            ans += 1
            pena += ret[k].count('WA')
    print(ans, pena)


if __name__ == '__main__':
    main()

Measured memory_bytes: 69336
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b){
    return b ? gcd(b, a%b) : a;
}

long long lcm(long long a, long long b){
    return a / gcd(a,b) * b;
}

long long f(long long x, int c, int d){
    long long  res = x;
    res -= x / c;
    res -= x / d;
    res += x / lcm(c,d);
    return res;
}

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

    long long ans = f(b,c,d) - f(a-1,c,d);
    printf("%ld\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int m, coin;
	while(1){
		
		scanf("%d", &m);
		if (m == 0){
			break;
		}
		m = 1000 - m;
		coin = 0;
	
		if (500 <= m){
			m -= 500;
			coin++;
		}
	
		while (m != 0){
			
			if (m >= 100){
				m -= 100;
				coin++;
			}
			else if (m >= 50){
				m -= 50;
				coin++;
			}
			else if (m >= 10){
				m -= 10;
				coin++;
			}
			else if (m >= 5){
				m -= 5;
				coin++;
			}
			else{
				m -= 1;
				coin++;
			}
		}
		printf("%d\n", coin);
	}
	return (0);
}

Measured memory_bytes: 600
using System;

class Program
{
    public static void Main()
    {
        // スペース区切りの整数の入力
        int n = int.Parse(Console.ReadLine());
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), i => int.Parse(i));
        int[] b = Array.ConvertAll(Console.ReadLine().Split(' '), i => int.Parse(i));

        long sum = 0;

        for (long i = 0; i < n; i++)
        {

            if (a[i] >= b[i])
            {
                sum += b[i];
            }
            else
            {
                sum += a[i];
                b[i] -= a[i];

                if (a[i + 1] >= b[i])
                {
                    sum += b[i];
                    a[i + 1] -= b[i];
                }
                else
                {
                    sum += a[i + 1];
                    a[i + 1] = 0;
                }

            }

        }

        Console.WriteLine(sum);

    }
}

Measured memory_bytes: 35020
#include<iostream>
#include<cmath>
#include<string>
#include<cstdlib>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<string.h>

#include<iomanip>
#define PI 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148
using namespace std;
#define A 0.33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333


int main()
{
	string str;
	int b[1000],sum=0;
	memset(b,0,1000*sizeof(int));
		
			while(getline(cin,str)){
				if(str=="0")
					break;
				sum++;//???1????§????????????±????§£
				for(unsigned int i=0;i<str.size();i++)
					b[sum]+=(str[i]-48);
			}
for(int i=1;i<=sum;i++)
	cout<<b[i]<<endl;


}
		
		

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

int main() {
  string s;
  cin >> s;
  int l = s.size();

  vector<int> number(26);
  for (int i = 0; i < l; i++) {
    number[s[i] - 'a']++;
  }
  
  for (int i = 0; i < 26; i++) {
    if (number.at(i) == 0) {
      cout << (char)(i + 'a') << endl;
      return 0;
    }
  }
  cout << "None" << endl;
}

Measured memory_bytes: 512
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;


namespace AtCoder
{
    class Program
    {
        static long[] Sarray() { return ReadLine().Trim().Split().Select(long.Parse).ToArray(); }
        static List<long> Slist() { return ReadLine().Trim().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            var N = Sarray();
            var Ai = Sarray();
            var Bi = Sarray();
            var Ci = Sarray();
            var ans = Bi.Sum();
            for (var i = 0; i < Ai.Length - 1; ++i)
            {
                if (Ai[i + 1] - Ai[i] == 1)
                    ans += Ci[Ai[i] - 1];
            }
            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
using System;
using System.Text.RegularExpressions;

namespace Atcoder2
{
    class Program
    {

        public static void Main(string[] args)
        {
            int point = int.Parse(Console.ReadLine());

            if (400 <= point && point <= 599)
            {
            Console.WriteLine(8);
            }
            else if (600 <= point && point <= 799)
            {
            Console.WriteLine(7);
            }
            else if (800 <= point && point <= 999)
            {
                Console.WriteLine(6);
            }
            else if (1000 <= point && point <= 1199)
            {
                Console.WriteLine(5);
            }
            else if (1200 <= point && point <= 1399)
            {
                Console.WriteLine(4);
            }
            else if (1400 <= point && point <= 1599)
            {
                Console.WriteLine(3);
            }
            else if (1600 <= point && point <= 1799)
            {
                Console.WriteLine(2);
            }
            else if (1800 <= point && point <= 1999)
            {
                Console.WriteLine(1);
            }
        }
    }
}


Measured memory_bytes: 27532
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0560

"""
import sys
from sys import stdin
input = stdin.readline


def solve(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    dp_I = [[0] * (N+1) for _ in range(M+1)]
    for y in range(M):
        t_J = [0] * (N+1)
        t_O = [0] * (N+1)
        t_I = [0] * (N+1)
        for x in range(N):
            land = field[y][x]
            if land == 'J':
                t_J[x+1] = t_J[x] + 1
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x]
            elif land == 'O':
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x] + 1
                t_I[x+1] = t_I[x]
            else:
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x]
                t_I[x+1] = t_I[x] + 1

        for x in range(1, N+1):
            dp_J[y+1][x] = dp_J[y][x] + t_J[x]
            dp_O[y+1][x] = dp_O[y][x] + t_O[x]
            dp_I[y+1][x] = dp_I[y][x] + t_I[x]

    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = dp_I[y2][x2] - dp_I[y1-1][x2] - dp_I[y2][x1-1] + dp_I[y1-1][x1-1]
        print(' '.join(map(str, result)))


def solve2(M, N, K, field):
    dp_J = [[0] * (N+1) for _ in range(M+1)]
    dp_O = [[0] * (N+1) for _ in range(M+1)]
    for y in range(M):
        t_J = [0] * (N+1)
        t_O = [0] * (N+1)
        for x in range(N):
            land = field[y][x]
            if land == 'J':
                t_J[x+1] = t_J[x] + 1
                t_O[x+1] = t_O[x]
            elif land == 'O':
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x] + 1
            else:
                t_J[x+1] = t_J[x]
                t_O[x+1] = t_O[x]

        for x in range(1, N+1):
            dp_J[y+1][x] = dp_J[y][x] + t_J[x]
            dp_O[y+1][x] = dp_O[y][x] + t_O[x]


    for _ in range(K):
        result = [0, 0, 0]
        y1, x1, y2, x2 = map(int, input().split())
        result[0] = dp_J[y2][x2] - dp_J[y1-1][x2] - dp_J[y2][x1-1] + dp_J[y1-1][x1-1]
        result[1] = dp_O[y2][x2] - dp_O[y1-1][x2] - dp_O[y2][x1-1] + dp_O[y1-1][x1-1]
        result[2] = (x2 - x1 + 1) * (y2 - y1 + 1) - result[0] - result[1]
        print(' '.join(map(str, result)))


def main(args):
    M, N = map(int, input().split())
    K = int(input())
    field = [input().strip() for _ in range(M)]
    solve2(M, N, K, field)


if __name__ == '__main__':
    main(sys.argv[1:])
    

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

typedef long long ll;
typedef pair<int, int> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << a + b + c << endl;
}

Measured memory_bytes: 3216
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
int ka[214514],inv[214514];
void setkaijo(int n){
	ka[0]=1;
	for(int i=1;i<=n;i++){
		ka[i] = ka[i-1] * i;
		ka[i] %= inf;
	}
}
int modpow(int x,int k){
	// x ^ k mod inf
	int res = 1;
	while(k>0){
		if(k%2)res = (res*x)%inf;
		x = (x*x)%inf;
		k >>=1;
	}
	return res;
}
void setinv(int n){
	for(int i=0;i<=n;i++){
		inv[i] = modpow(ka[i],(ll)inf-2);
	}
}
int comb(int n,int k){
	if( k<0 || n<0 || k>n)return 0;
	if(k==0 || k==n)return 1;
	int res = (ka[n] * inv[k]) % inf;
	res = (res*inv[n-k]) % inf;
	return res;
}
signed main(){
	int n,k;
	cin>>n>>k;
	setkaijo(4100);
	setinv(4100);
	for(int i=1;i<=k;i++){
		int ans = 1;
		ans *= comb( n - k + 1, i );
		ans *= comb( k - 1, k - i );
		ans %= inf;
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
"use strict"
function Main(input){
  input=input.trim();
  input=input.split(/\s+/);
  for(let i=0;i<input.length;i++)
    input[i]=input[i]-0;
  var A=input[0];
  var B=input[1];
  var K=input[2];
  var num=Math.min(A,B);
  var counter=0;
  while(counter<K){
    counter+=(A%num===0&&B%num===0)?1:0;
    num--;
  }
  console.log(num+1);
}

Main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 21064
n = int(input())
x = []
u = []

total = 0
for i in range(n):
    x_tmp, u_tmp = input().split()
    if u_tmp == 'JPY':
        total += int(x_tmp)
    elif u_tmp == 'BTC':
        total += float(x_tmp) * 380000

print(total)


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String day = sc.next();
		int remain = 0;

		if (day.equals("MON")) {
			remain = 6;
		} else if (day.equals("TUE")) {
			remain = 5;
		} else if (day.equals("WED")) {
			remain = 4;
		} else if (day.equals("THU")) {
			remain = 3;
		} else if (day.equals("FRI")) {
			remain = 2;
		} else if (day.equals("SAT")) {
			remain = 1;
		} else if (day.equals("SUN")) {
			remain = 7;
		}
		System.out.println(remain);
	}

}

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

int main(){
    int M, K;
    cin >> M >> K;
    if(M==0 && K==0){
        cout << "0 0" << endl;
    }else if(M==1 && K==0){
        cout << "0 1 1 0" << endl;
    }else if(M>=2 && K<(1<<M)){
        int N = (1<<M);
        vector<int> b;
        for(int i=0; i<N; i++){
            if(i != K)
                b.push_back(i);
        }
        for(int i=0; i<N-1; i++){
            cout << b[i] << " ";
        }cout << K << " ";
        for(int i=N-2; i>=0; i--){
            cout << b[i] << " ";
        }cout << K << endl;
    }else{
        cout << -1 << endl;
    }
}

Measured memory_bytes: 2424
# coding: utf-8
# Your code here!
N = int(input())
A = list(map(int,input().split()))
A.insert(0, 0)
#ユークリッド互除法の関数の定義
def gcd(a,b):
    if(a < b):
        a, b = b, a
    if b == 0 : return a
    return gcd(b, a % b)


L = [0] * (N + 10)
R = [0] * (N + 10)

L[0] = 0
L[1] = A[1]
for i in range(1, N):
    L[i + 1] = gcd(L[i], A[i + 1])

R[N + 1] = 0
R[N] = A[N]
for i in reversed(range(1, N)):
    R[i] = gcd(R[i + 1], A[i])

'''   
for i in range(1, N + 1):
    print(L[i])
'''

maxnum = 0
for i in range(1, N + 1):
    if i == 1:
        num = R[2]
    elif i == N:
        num = L[N - 1]
    else:
        num = gcd(L[i - 1], R[i + 1])
        
    maxnum = max([maxnum, num])
    
print(maxnum)

Measured memory_bytes: 64108
#include<stdio.h>
#include<string.h>
int main(){
    int m,n,i,j;
    char str[100][100];
    scanf("%d%d",&m,&n);
    for(i=0;i<m;i++){
        scanf("%s",str[i]);
    }
   for(i=0;i<n+2;i++){
     printf("#");
   }
   printf("\n");
   for(i=0;i<m;i++){
     printf("#");
     for(j=0;j<n;j++){
        printf("%c",str[i][j]);
     }
     printf("#\n");
   }
   for(i=0;i<n+2;i++){
      printf("#");
   }
   printf("\n");
   return 0;
}


Measured memory_bytes: 128
#!/usr/bin/env python3
import sys
from bisect import bisect_left

def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    A_index = []
    ## ACの場所を全部記録しときたい→Aの場所を全部記録
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            A_index.append(i)
    
    for j in range(Q):
        if r[j] <= 1:
            print(0)
            continue

        left_index = bisect_left(A_index,l[j]-1)
        right_index = bisect_left(A_index,r[j]-1)
        print(right_index-left_index)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()


Measured memory_bytes: 13948
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll n, d, x, y, ans = 0;

int main() {
	cin >> n >> d;
	rep(i, n) {
		cin >> x >> y;
		if (x * x + y * y <= d * d)ans++;
	}
	cout << ans << endl;
	return 0;
}

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

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define st first
#define nd second
#define endl '\n'
#define what_is(x) cerr << #x << " is " << x << endl;
#define what_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << e << ' '; cerr << '\n'; //vector, set
#define what_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << x[i] << ' '; cerr <<  '\n'; //n first element of array
#define cerr_pair(x) '{' << x.st << ", " << x.nd << '}'
#define pwhat_is(x) cerr << #x << " is " << cerr_pair(x) << endl;
#define pwhat_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << cerr_pair(e) << ' '; cerr << '\n'; //vector, set
#define pwhat_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << cerr_pair(x[i]) << ' '; cerr <<  '\n'; //n first element of array
// #define int long long
// #define pow mypow

typedef pair<int,int> pii;
const int N = 1e5+5;
const int INF = 1e9+5;
const int MOD = 1e9+7;

int32_t main()
{
	IOS
	// freopen("input.txt", "r", stdin);
	int temperature; cin >> temperature;
	cout << (temperature >= 30? "Yes": "No") << endl;
	return 0;
}


Measured memory_bytes: 3652
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map(String::toInt)
    val groupNumList = Array(n + 2, { 1 })
    val inputList = mutableListOf<Pair<Int,Int>>()
    for (i in 0 until m) {
        val (a, b) = readLine()!!.split(' ').map(String::toInt)
        inputList.add(Pair(a,b))
    }
    inputList.sortBy { it.first }
    for (i in 0 until m) {
        val (a, b) = inputList[i]
        if (groupNumList[a] == groupNumList[b]) {
            for (i in b..n) {
                groupNumList[i] = groupNumList[i] + 1
                if (groupNumList[i] == groupNumList[i + 1]) break
            }
        }
    }
    println(groupNumList[n] - 1)
}


Measured memory_bytes: 122452
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int count = 0;
      for(int i = 0;i < n;i++){
      	for(int j = 0;j < n;j++){
        	if(n == 4*i+7*j)count++;
        }
      }
      if(count > 0)System.out.println("Yes");
      else System.out.println("No");
    }
}

Measured memory_bytes: 23764
#include<iostream>
#include<cstring>

#define ZERO(a) memset(a,0,sizeof(a))
#define FIELD 9
using namespace std;
enum {S,E,N,W};
int top[FIELD][FIELD];
int z[FIELD][FIELD];

int side[6+1][4]={
	{},
	{3,5,4,2},
	{3,1,4,6},
	{1,2,6,5},
	{5,6,2,1},
	{6,4,1,3},
	{2,4,5,3}
};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int getIndex(int t,int n){
	for(int i=0;i<4;i++)
		if(side[t][i]==n)return i;
	return -1;
}
void roll(int *t,int *f,int n,int compass){
	if(compass==N)
		*f = 7-*t;
	else if(compass==S)
		*f = *t;
	*t = 7-n;
}
void fall(int y,int x,int t,int f){
	for(int i=6;3<i;i--){
		int index=getIndex(t,i);
		if(index!=-1){
			index = (index-getIndex(t,f)+4) %4;
			if(z[y+dy[index]][x+dx[index]] < z[y][x]){
				roll(&t,&f,i,index);
				fall(y+dy[index],x+dx[index],t,f);
				return;
			}
		}
	}
	z[y][x]++;
	top[y][x] = t;
}
int main(){
	int n,t,f,num[6+1];
	while(cin>>n,n){
		ZERO(num);
		ZERO(top);
		ZERO(z);
		while(n--){
			cin>>t>>f;
			fall(FIELD/2,FIELD/2,t,f);
		}
		for(int i=0;i<FIELD;i++)
			for(int j=0;j<FIELD;j++)
				num[top[i][j]]++;
		for(int i=1;i<6;i++)cout<<num[i]<<' ';
		cout<<num[6]<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long 
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef pair<P, P> PP;
 
const int MOD = 1e9 + 7;
const int dy[] = { 0, 0, 1, -1 };
const int dx[] = { 1, -1, 0, 0 };
 
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int fact[2000];

int elePow(int a, int b) {
    int num = 1;
    while(b != 0) {
        if(b & 1) num = num * a % MOD;
        b /= 2;
        a =  a * a % MOD;
    }
    return num;
}

int nCr(int n, int r) {
    if(r > n) return 0;
    if(r == 0) return 1;
    int a = fact[n], b = fact[r] * fact[n - r] % MOD;
    int res = a * elePow(b, MOD - 2) % MOD;
    return res;
}

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

    int N, K;
    cin >> N >> K;
    fact[0] = fact[1] = 1;
    for(int i = 1; i < N; ++i) {
        fact[i + 1] = (fact[i] * (i + 1)) % MOD;
    }
    for(int i = 1; i <= K; ++i) {
        int res = (nCr(N - K + 1, i) * nCr(K - 1, i - 1)) % MOD;
        cout << res << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.security.KeyStore.TrustedCertificateEntry
import java.util
import java.util.{ArrayList, Collections, Comparator, List => JList}
import scala.math._

import scala.collection.mutable
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
import scala.util.{Failure, Success, Try}

object Main{
  val LINE_SEPARATOR = "\n"
  def main(args: Array[String]): Unit = {
    if (sys.env.getOrElse("TEST", "")=="1"){
      println(test());
    }else{
      val input=io.Source.stdin.getLines().mkString(LINE_SEPARATOR);
      println(solve(input).trim());
    }
  }

  def init (nRows: Int, nCols: Int, default: Int) = Array.tabulate(nRows,nCols)( (x,y) =>  default)

  def sortIgnoreCase1(list: JList[String]): JList[String] = {
    val r = new ArrayList[String](list)
    Collections.sort(r, new Comparator[String] {
      override def compare(o1: String, o2: String): Int = o1.compareToIgnoreCase(o2)
    })
    r
  }

  def solve(input: String): String = {
    val n = input.toInt
    (1 to n).map(_.toString.toSeq.length).count(_ % 2 == 1).toString
  }

  def gcd(m: Long, n: Long): Long = n match {
    case 0 => m
    case _ => gcd(n, m % n)
  }
  def lcm(a: Long, b: Long): Long = a * b / gcd(a, b)

  val tests=List(
    """11""".stripMargin -> """9
                                   |""".stripMargin,
    """136""".stripMargin -> """46
                                    |
                                                   |
                              |""".stripMargin
  )

  def test():String= {
    return tests.map{case (i,o)=>(i.trim(),o.trim())}
      .zipWithIndex.map{
      case ((input,outputExpect),i)=>{
        val output=solve(input).trim();
        s"test${i+1}:"+(if(output==outputExpect){
          "Passed"
        }else{
          s"Failed\nexpect:\n${outputExpect}\noutput:\n${output}"
        })
      }}
      .mkString("\n");
  }
}

Measured memory_bytes: 39768
def chc(H,now):
    if(now == 0):
        return True
    else:
        for i in range(now):
            if(H[i]>H[now]):
                return False
        return True


N = int(input())
H = list(map(int,input().split()))

counter = 0
for i in range(N):
    if(chc(H,i)):
        counter += 1

print(counter)



Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define bgn begin()
#define sz size()
#define en end()
#define pb push_back
#define pp() pop_back()
#define V vector
#define P pair
#define yuko(a) setprecision(a)
#define uni(a) a.erase(unique(a.begin(),a.end()),a.end())
#define Q queue
#define pri priority_queue
#define Pri priority_queue<int,vector<int>,greater<int>>
#define PriP priority_queue<P<int,int>,vector<P<int,int>>,greater<P<int,int>>>
#define all(a)  (a).begin(),(a).end()
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int D = 60;
const int MAX_N = 200005;
int to[D][MAX_N];



signed main(){
  int n, k;
  cin >> n >> k;
  fo(i,n){
    cin >> to[0][i];
    to[0][i]--;
  }
  fo(i , D-1){
    fo(j , n){
      to[i+1][j] = to[i][to[i][j]];
    }
  }
  int v = 0;
  for(int i = D-1; i>=0; i--){
    int l = 1ll<<i;
    if(l <= k){
      v = to[i][v];
      k -= l;
    }
  }
  cout << v+1 << endl;
  return 0;
}

Measured memory_bytes: 97384
N = input()
T, A = map(int, input().split())
H = list(map(int, input().split()))

def main():
    ans = 0
    diff_max= 1000
    for i, x in enumerate(H, start=1):
        diff = abs(T-x*0.006 - A)
        if diff < diff_max:
            diff_max = diff
            ans = i
    return ans

if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3060
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


int main() {
  int h, n;
  cin >> h >> n;
  int sum = 0;
  rep(_, n){
    int a;
    cin >> a;
    sum += a;
  }
  if (sum >= h) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

int main()
{
	int N, M;
	cin >> N >> M;
	
	string A[55];
	string B[55];
	
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	for(int j = 0; j < M; j++){
		cin >> B[j];
	}
	
	bool judge = false;
	
	for(int i = 0; i < N - M + 1; i++){
		for(int j = 0; j < N - M + 1; j++){
			for(int k = 0; k < M; k++){
				if(B[k] != A[i + k].substr(j, M)){
					break;
				}
				if(k == M - 1){
					judge = true;
				}
			}
		}
	}
	if(judge){
		cout << "Yes";
	}
	else {
		cout << "No";
	}
}


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

using namespace std;
typedef long long ll;
typedef vector<ll> vel;
typedef vector<string> ves;
typedef vector<int> vei;
typedef vector<vector<ll>> vvel;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REP(a, b, m) for (ll a = (ll)(b); a < (ll)(m); a++)

int main() {
    ll n,k;cin>>n>>k;
    vel A(n);
    rep(i,n) {
        cin>>A[i];
    }
    rep(i,(n-k)) {
        if(A[i+k]>A[i]) {
            cout<<"Yes"<<endl;
        }
        else {
            cout<<"No"<<endl;
        }
    }
}

Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<vector<vector<int> > > building(4,vector<vector<int> >(3,vector<int>(10)));
    int b,f,r,v;
    for(int i = 0 ; i < n ; i++){
        cin >> b >> f >> r >> v;
        building[b - 1][f - 1][r - 1] += v;
    }

    for(int b = 0 ; b < 4 ; b++){
        for(int f = 0 ; f < 3 ; f++){
            for(int r = 0 ; r < 10 ; r++)
                cout << " " << building[b][f][r];

            cout << endl;
        }
        if(b < 3)
            cout << "####################" << endl;
    }
    
    
    return 0;
}


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

using namespace std;

typedef long long ll;

const int N = 100010;

int n , freq[N],a[N], all,rem = 0;

int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for (int i = 0; i < n; ++i){
		scanf("%d",&a[i]);
		freq[a[i]]++;
	}
	for (int i = 1 ; i < N; ++i){
		if(freq[i] == 0)
			continue;
		rem += (freq[i]-1);
	}

	while(rem > 0){
		rem -= 2;
		all += 2;
	}
	
	printf("%d\n",n-all );
	return 0;
}

Measured memory_bytes: 1024
import copy
n=input()
n=int(n)
s=input()
l=[]
indexs=[]
for i in range(n):
  l.append(s[i])
lr=copy.deepcopy(l)
lr.reverse()
se=set(l)
for k in se:
  if l.index(k)+lr.index(k)!=n-1:
    indexs.append([l.index(k),n-1-lr.index(k)])
count=[0]*n
for j in range(len(indexs)):
  for t in range(indexs[j][0],indexs[j][1]):
    count[t]+=1
print(max(count))

Measured memory_bytes: 3444
#include<stdio.h>
int n;
int x;
int l[105];
int ans = 1;
int sum;
int main(){
	scanf("%d %d", &n, &x);
	for(int i = 1; i <= n; i++)
		scanf("%d", &l[i]);
	for(int j = 1; j <= n; j++){
		sum += l[j];
		if(sum <= x) ans++;
	}
	printf("%d\n", ans);
}

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

void output(int diffx, int diffy, int addx, int addy) {
    if (addx) {
        if (diffx > 0) cout << "L";
        else cout << "R";
    }
    if (diffy > 0) rep(i,diffy+addy) cout << "U";
    else rep(i,-diffy+addy) cout << "D";
    if (diffx > 0) rep(i,diffx+addx) cout << "R";
    else rep(i,-diffx+addx) cout << "L";
    if (addy) {
        if (diffy > 0) cout << "D";
        else cout << "U";
    }
}

int main() {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    int diffx = tx - sx;
    int diffy = ty - sy;
    output(diffx, diffy, 0, 0);
    output(-diffx, -diffy, 0, 0);
    output(diffx, diffy, 1, 1);
    output(-diffx, -diffy, 1, 1);
}



Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int MOD = (int)1e9 + 7;
const double PI = 3.14159265358979323846;
template <class T, class U>
void chmin(T& t, const U& u) {
  if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
  if (t < u) t = u;
}

const int MX = 10000;
int main(void) {
  string s, t;
  cin >> s >> t;
  int res = MX;
  rep(i, s.size()) {
    if (i + t.size() > s.size()) break;
    int cnt = 0;
    rep(j, t.size()) {
      if (s[i + j] != t[j]) cnt++;
    }
    chmin(res, cnt);
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;
const double pi = acos(-1.0);

int main() {
    int q; cin >> q;
    rep(i, q) {
        string x, y; cin >> x >> y;
        int dp[1100][1100];
        rep(i, 1100) rep(j, 1100) dp[i][j] = 0;
        rep(i, x.size()) {
            rep(j, y.size()) {
                if(x[i] == y[j]) chmax(dp[i+1][j+1], dp[i][j] + 1);
                else chmax(dp[i+1][j+1], max(dp[i+1][j], dp[i][j+1]));
            }
        }
        cout << dp[x.size()][y.size()] << endl;
    }
}


Measured memory_bytes: 7928
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define mkp make_pair
#define pb push_back
#define ff first
#define ss second
#define debug1(a) cout<<a<<endl;
#define debug2(a,b) cout<<a<<' '<<b<<endl;
#define debug3(a,b,c) cout<<a<' '<<b<<' '<<c<<endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,a,b)for(int i=a;i<b;i++)
#define repre(i,a,b)for(int i=a;i<=b;i++)
#define clr1(arr) memset(arr,-1,sizeof(arr));
#define clr0(arr) memset(arr,0,sizeof(arr));
#define pi pair<int,int>
#define pii pair<int,pi>
#define aint(v) v.begin(),v.end()
#define pq priority_queue
#define mpq priority_queue<int,vector<int>,greater<int> >
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> orderedSet;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> orderedMSet;
//*p.find_by_order(index) return value at index
//p.order_of_key(key) return index
/*
2d pointer array
int **dp;
in main function
int row,col;
dp=new int*[n];
rep(i,n)dp[i]=new int[m]
*/
int power(int x,int y);
bool isPrime(int n);
int modInv(int a,int b);
int gcdExtended(int a,int b,int *x,int* y);
int mpower(int a,int b,int p);

int32_t main()
{
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  fastio
  int n,k;
  cin>>n>>k;
  int ans=0;
  rep(i,n)
  {
    int a;
    cin>>a;
    if(a>=k)ans++;
  }
  cout<<ans<<endl;

  return 0;
}

int modInv(int a, int m){
int x, y;
int g = gcdExtended(a, m, &x, &y);
int res = (x%m + m) % m;
return res;
}

int gcdExtended(int a, int b, int *x, int *y){
if (a == 0){
    *x = 0, *y = 1;
    return b;
}
int x1, y1;
int gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}

int mpower(int x, int y, int p){
int res = 1;
x = x % p;
while(y > 0){
    if(y & 1) res = (res*x) % p;
    y = y>>1;
    x = (x*x) % p;
}
return res;
}

int power(int x, int y){
int res = 1;
while (y > 0){
    if (y & 1) res = res*x;
    y = y>>1;
    x = x*x;
}
return res;
}

bool isPrime(int n){
if (n <= 1)  return false;
if (n <= 3)  return true;
if (n%2 == 0 || n%3 == 0) return false;
int p=sqrt(n);
for(int i=5;i<=p;i=i+6)
    if (n%i == 0 || n%(i+2) == 0)
        return false;
return true;
}


Measured memory_bytes: 256
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#ifdef _WIN32
#define __builtin_popcount __popcnt
#endif
// Time Complexity: O(3^K + P * H * M log N)
int N, M, H, K, S, T, P, a, b, c, h, r;
int main() {
	while (cin >> N >> M >> H >> K, N) {
		vector<vector<vector<int> > > G(N);
		for (int i = 0; i < M; i++) {
			cin >> a >> b >> c >> h >> r; a--, b--, r--;
			G[a].push_back({ b, c, h, r });
			G[b].push_back({ a, c, h, r });
		}
		vector<int> cost(1 << K, 999999999); cost[0] = 0;
		cin >> S >> T >> P; S--, T--;
		for (int i = 0; i < P; i++) {
			cin >> a >> b;
			int bit = 0;
			for (int j = 0; j < a; j++) cin >> c, c--, bit += 1 << c;
			cost[bit] = b;
		}
		vector<pair<int, int> > v;
		for (int i = 0; i < 1 << K; i++) v.push_back(make_pair(__builtin_popcount(i), i));
		sort(v.begin(), v.end());
		for (int i = 0; i < v.size(); i++) {
			for (int j = 0; j < i; j++) {
				cost[i | j] = min(cost[i | j], cost[i] + cost[j]);
			}
		}
		int ret = 999999999;
		for (int i = 0; i < 1 << K; i++) {
			if (cost[i] == 999999999) continue;
			vector<vector<int> > dist(N, vector<int>(H + 1, 999999999)); dist[S][0] = 0;
			priority_queue<vector<int> > que; que.push({ 0, S, 0 });
			while (!que.empty()) {
				vector<int> u = que.top(); que.pop();
				for (int j = 0; j < G[u[1]].size(); j++) {
					int f = G[u[1]][j][0], d = u[2] + G[u[1]][j][2], c = dist[u[1]][u[2]];
					if (!(i & (1 << G[u[1]][j][3]))) c += G[u[1]][j][1];
					if (d <= H && dist[f][d] > c) {
						dist[f][d] = c;
						que.push({ -dist[f][d], f, d });
					}
				}
			}
			int res = 999999999;
			for (int j = 0; j <= H; j++) res = min(res, dist[T][j]);
			ret = min(ret, res + cost[i]);
		}
		cout << (ret != 999999999 ? ret : -1) << endl;
	}
	return 0;
}

Measured memory_bytes: 3364