akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

#define MAX 100

double dp[MAX+1][MAX];
double table[MAX][MAX];

int main(int argc, char *argv[]){
  
  for(;;){
    int n, m;
    int i, j, k;

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

    if(n == 0 && m == 0){
      break;
    }
    
    for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
	scanf("%lf", &table[i][j]);
      }
    }

    for(i = 0; i <= m; i++){
      for(j = 0; j < n; j++){
	dp[i][j] = i <= 1 ? 1.0 : 0.0;
      }
    }

    for(i = 2; i <= m; i++){
      for(j = 0; j < n; j++){
	for(k = 0; k < n; k++){
	  if(dp[i][j] < dp[i-1][k] * table[k][j]){
	    dp[i][j] = dp[i-1][k] * table[k][j];
	  }
	}
	//printf("dp[%d][%d] = %.2lf\n", i, j, dp[i][j]);
      }
    }

    {
      double max = 0;
      for(i = 0; i < n; i++){
	if(max < dp[m][i]){
	  max = dp[m][i];
	}
      }

      printf("%.2lf\n",max);
    }
    
    
    
  }
  
  return 0;    
}

Measured memory_bytes: 820
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define INF 10000000000
#define mod 1000000007
typedef long long int ll;
ll u(const void *a, const void *b){return *(ll*)a-*(ll*)b;}
ll d(const void *a, const void *b){return *(ll*)b-*(ll*)a;}
ll min(ll a,ll b){
  if(a>b)return b;
  return a;
}
ll max(ll a,ll b){
  if(a>b)return a;
  return b;
}
ll gcd(ll a,ll b){
  if(!b)return a;
  return gcd(b,a%b);
}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int kt(ll a){
  int sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
int ks(ll a){
  int sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
int main(void){
  int n,ans=1;
  scanf("%d",&n);
  char s[n+1];
  scanf("%s",s);
  FOR(n-1)if(s[i]!=s[i+1])ans++;
  PRN(ans);
  return 0;
}


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

int main()
{
    int N, M, C, ans = 0;
    int A[20][20];
    int B[20];
    int len[20];
    cin >> N;
    cin >> M;
    cin >> C;
    for (int i = 0; i < M; i++)
    {
        cin >> B[i];
        len[i] = 0;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> A[i][j];
        }
        for (int j = 0; j < M; j++)
        {
            len[i] += A[i][j] * B[j];
            //cout << len[j] << endl;
            if (j == M - 1 && len[i] + C > 0)
            {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int n;
    constexpr i64 mod = 1000000007;
    std::cin >> n;
    std::vector<int> s(n + 1), prev(n + 1), z(n + 1);
    std::map<int, int> pos;
    for (int i = 1; i <= n; i++) {
        int in;
        std::cin >> in;
        s[i] = s[i - 1] ^ in;
        z[i] = z[i - 1] + !s[i];
        prev[i] = pos[s[i]];
        pos[s[i]] = i;
    }
    i64 ret = 0;
    
    if (s[n] == 0) {
        ret = 1;
        for (int i = 1; i < z[n]; i++) ret = ret * 2ll % mod;
    }

    // std::cerr << ret << std::endl;
    // for (int i = 1; i <= n; i++) std::cerr << s[i] << " ";
    // std::cerr << std::endl;

    std::map<int, i64> t, p;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 0) {
            if (s[n] > 0) ret = (ret + p[s[n]]) % mod;
            continue;
        }

        if (t[s[i]]) t[s[i]] = (t[s[i]] + p[s[i]] * (z[i] - z[prev[i]]) % mod) % mod;
        else t[s[i]] = 1;

        if (s[n] == 0) ret = (ret + t[s[i]]) % mod;
        p[s[i]] = (p[s[i]] + t[s[i]]) % mod;
    }
    std::cout << (ret + (s[n] > 0)) << std::endl;

    return 0;
}


Measured memory_bytes: 55424
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N,M; cin>>N>>M;
  cout<<N*(N-1)/2+M*(M-1)/2<<endl;
  }


Measured memory_bytes: 256
import java.util.*

const val P = 998244353L

fun solveBruteForce(s: String): Int {
  val q = ArrayDeque<String>()
  q.offerLast(s)
  val set = mutableSetOf<String>()
  set.add(s)
  while (q.isNotEmpty()) {
    val state = q.pollFirst()
    for (i in 0 until (state.length - 1)) {
      if (state[i] != state[i + 1]) {
        val c1 = state[i]
        val c2 = state[i + 1]
        ('a'..'c').forEach {
          if (c1 != it && c2 != it) {
            val nextBuilder = StringBuilder(state)
            nextBuilder[i] = it
            nextBuilder[i + 1] = it
            val next = nextBuilder.toString()
            if (!set.contains(next)) {
              q.offerLast(next)
              set.add(next)
            }
          }
        }
      }
    }
  }
  return set.size
}

fun cToI(c: Char) = c - 'a'

fun main(args: Array<String>) {
  val s = readLine()!!

  if (s.all { it == s[0] }) {
    println(1)
    return
  }

  if (s.length <= 3) {
    println(solveBruteForce(s))
    return
  }

  val n = s.length
  // [element index][mod][last]
  val dp1 = Array(n, { Array(3, { LongArray(3, { 0L }) }) })
  val dp2 = Array(n, { Array(3, { LongArray(3, { 0L }) }) })
  for (x in 0..2) {
    dp1[0][x][x] = 1L
    dp2[0][x][x] = 1L
  }
  for (k in 0 until n - 1) {
    for (m in 0..2) {
      for (x in 0..2) {
        for (y in 0..2) {
          dp1[k + 1][(m + y) % 3][y] += dp1[k][m][x]
          dp1[k + 1][(m + y) % 3][y] %= P
          if (x != y) {
            dp2[k + 1][(m + y) % 3][y] += dp2[k][m][x]
            dp2[k + 1][(m + y) % 3][y] %= P
          }
        }
      }
    }
  }
  val sMod = s.map(::cToI).sum() % 3
  val t1 = dp1[n - 1][sMod].sum() % P
  val t2 = dp2[n - 1][sMod].sum() % P
  val sCount = !(0 until n - 1).any { s[it] == s[it + 1] }
  val ans = (t1 + P - t2 + if (sCount) 1 else 0) % P
  println(ans)
}


Measured memory_bytes: 113560
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 2e5 + 5; 
using namespace std;

int n, R, C, stk[N], top, cnt; 
struct node
{
	int id, v;
	node(int a = 0, int b = 0) { id = a, v = b; }
} p[N]; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

bool check(int x, int y)
{
	if(x > 0 && x < R && y > 0 && y < C) return 0;
	return 1; 
}

int val(int x, int y)
{
	if(!x) return y;
	if(y == C) return C + x;
	if(x == R) return 2 * C - y + R;
	return 2 * C + 2 * R - x; 
}

bool cmp(node a, node b) { return a.v < b.v; }

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin); 
#endif
	R = read <int> (), C = read <int> (), n = read <int> ();
	for(int x1, y1, x2, y2, i = 1; i <= n; i++)
	{
		x1 = read <int> (), y1 = read <int> (), x2 = read <int> (), y2 = read <int> ();
		if(!check(x1, y1) || !check(x2, y2)) continue;
		p[++cnt] = node(i, val(x1, y1));
		p[++cnt] = node(i, val(x2, y2)); 
	}
	sort(p + 1, p + cnt + 1, cmp);
	for(int i = 1; i <= cnt; i++)
		if(!top || p[i].id != p[stk[top]].id) stk[++top] = i;
		else top--;
	puts(top ? "NO" : "YES"); 
	return 0; 
}


Measured memory_bytes: 4812
#python3
def f(x):
    f = False
    for i in range(1, 10):
        if x%i == 0:
            k = x//i
            if 1<=k & k<=9:
               f = True 
    return f

def main():
    n = int(input())
    if f(n):
        print('Yes')
    else:
        print('No')

main()


Measured memory_bytes: 3064
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function main()
	n = readline() |> parseInt
	a = String[]
	for i in 1:n
		push!(a,readline() |> chomp)
	end
	println(length(Set(a)))
end

main()

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

int main(){
    int A, B, C, N, M ,K;
    int count = 0;
    string a, b, c;
    cin >> N >> a >> b >> c;

    for(int i = 0; i < N; i++){
        if(a.at(i)==b.at(i) && b.at(i)==c.at(i)) continue;
        else if(a.at(i)==b.at(i) && b.at(i)!=c.at(i)) count++;
        else if(b.at(i)==c.at(i) && c.at(i)!=a.at(i)) count++;
        else if(c.at(i)==a.at(i) && a.at(i)!=b.at(i)) count++;
        else count += 2;
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define hell 1000000007
#define hell1 1000000006
#define pb push_back
#define x first
#define y second
#define MAXL 100005
#define pll pair<ll,ll>
using namespace std;
//vector<ll>prime(15000002,0);
ll mM(ll a,ll b,ll mod){ll res = 0;a %= mod;while(b){if (b & 1)res = (res + a) % mod;a = (2 * a) % mod;b >>= 1;}return res;}
ll fpow(ll x,ll y,ll p){x=x%p;ll res=1;while(y){if(y&1)res=(res*x)%p;res%=p;if(res<0)res=(res+p)%p;y=y>>1;x=(x*x)%p;if(x<0)x=(x+p)%p;x%=p;}return res;}
ll inv(ll n,ll p){return fpow(n,p-2,p);}
ll modmul(ll x,ll y){return (x*y)%hell;}
ll modadd(ll x,ll y){if(x>=hell)x-=hell;if(y>=hell)y-=hell;ll temp=x+y;if(temp>=hell)temp-=hell;if(temp<0)temp = temp+hell;return temp;}
/*void sieve(){
	prime[1] = 1;
	for(ll i=2;i<=15000000;i++)
		if(!prime[i])
			for(ll j=i;j<=15000000;j+=i)
				if(!prime[j])
					prime[j] = i;
}*/
void lcs(string s,string t)
{
	ll dp[s.size()+1][t.size()+1];
	for(int i=0;i<=s.size();i++)
		for(int j=0;j<=t.size();j++)
			if(!i || !j)
				dp[i][j] = 0;
			else if(s[i-1]==t[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
	ll i = s.size(),j = t.size();
	string p = "";
	while(i && j)
	{
		if(s[i-1]==t[j-1])
		{
			p+=s[i-1];
			i--;
			j--;
		}
		else if(dp[i-1][j]>dp[i][j-1])
			i--;
		else
			j--;
	}
	reverse(p.begin(),p.end());
	cout << p << "\n";
}
int main(){
	ios
	ll t = 1;
	//cin >> t;
	//sieve();
	while(t--)
	{
		string s,p;
		cin >> s >> p;
		lcs(s,p);
	}
}


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

using ll=long long;
const ll MOD=1000000007;

int main() {
  int n,k,r,s,p;
  string a;
  cin >> n >> k >> r >> s >> p >> a;
  int ans=0;
  for(int i=0;i<n;i++){
    if(a[i]=='r')
      ans +=p;
    else if(a[i]=='s')
      ans +=r;
    else
      ans +=s;
  }
  //cout << ans << endl;
  for(int i=0;i<n-k;i++){
    if(a[i]==a[i+k]&&a[i]=='r'){
      ans -=p;
      a[i+k]='x';
    }
    else if(a[i]==a[i+k]&&a[i]=='s'){
      ans -=r;
      a[i+k]='x';
    }
    else if(a[i]==a[i+k]&&a[i]=='p'){
      ans -=s;
      a[i+k]='x';
    }
    //cout << ans << endl;
  }
    cout << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ac = 0, wa = 0, tle = 0, re = 0;
    while(n--){
		string s;
		cin >> s;
		if(s == "AC"){
			ac++;
			} else if (s == "WA"){
				wa++;
				} else if(s == "TLE"){
					tle++;
					} else if (s == "RE"){
						re++;
						}
		}
	cout << "AC x " << ac << endl << "WA x " << wa << endl << "TLE x " << tle << endl << "RE x " << re << endl;
	

}


Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

typedef long long ll;
using namespace std;

int main(void){
    
    string s,tmp;
    int m,h,l;
    int i;
    
    while(1){
        cin>>s;
        if(s=="-") break;
        cin>>m;
        for(i=0;i<m;i++){
            cin>>h;
            tmp=s.substr(0,h);
            s.erase(0,h);
            s+=tmp;
        }
        cout<<s<<endl;
    }
    

	return 0;
}


Measured memory_bytes: 3176
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t n;
    string s;
    cin >> n >> s;
    // すべての区切るパターンで数え上げる
    // i未満とi以上でリストを持って、それぞれで確認するのか
    int64_t allRes = 0;
    for(int i=0; i<n; i++){
        int64_t res = 0;
        set<char> left, right;
        for(int j=0; j<i; j++){
            // 左側
            left.insert(s.at(j));
        }
        for(int j=i; j<n; j++){
            // 右側
            right.insert(s.at(j));
        }
        for(char c:left){
            if(right.find(c)!=right.end()){
                res++;
            }
        }
        allRes = max(allRes, res);
    }
    cout << allRes << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MIN (-1) * (1 << 30)

using namespace std;

int main(void) {
	int H, W, i = 0, j, l, sum, ans = 0;
	cin >> H >> W;
	vector<vector<int>> x(H, vector<int>(W, 0));
	vector<string> s(H);
	for (; i < H; i++)
		cin >> s[i];
	for (i = 0; i < H; i++) {
		l = 0;
		for (j = 0; j < W; j++) {
			while (j < W && s[i][j] == '.')
				j++;
			sum = j - l;
			for (; l < j; l++)
				x[i][l] = sum;
			if (j < W)
				x[i][j] = MIN;
			l = j + 1;
		}
	}
	for (j = 0; j < W; j++) {
		l = 0;
		for (i = 0; i < H; i++) {
			while (i < H && s[i][j] == '.')
				i++;
			sum = i - l;
			for (; l < i; l++)
				x[l][j] += sum;
			l = i + 1;
		}
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			ans = max(ans, x[i][j]);
		}
	}
	cout << ans - 1 << "\n";
	return 0;
}

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

using namespace std;

int main(){
  int N;
  cin >> N;
  
  if(N == 1) cout << 1 << endl << 1 << endl;
  else if(N == 2) cout << 2 << endl << 0 << endl << 11 << endl;
  else{
    cout << N - 1 << endl;
    for(int i = 1; i < N; i++){
      cout << 1;
      for(int j = 1; j < i; j++){
        cout << 0;
      }
      cout << 1;
      cout << endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n, m; cin >> n >> m;
    if(2*n >= m) cout << m/2 << endl;
    else cout << n+(m-(2*n))/4 << endl;
}

Measured memory_bytes: 256
var bubbleSort = function(arr, n) {
  var isSwapped = 1;
  var numSwapped = 0;
  while (isSwapped) {
    isSwapped = 0;
    for (var i = n - 1; i >= 1; i -= 1) {
      if (arr[i] < arr[i - 1]) {
        var temp = arr[i];
        arr[i] = arr[i - 1];
        arr[i - 1] = temp;
        numSwapped += 1;
        isSwapped = 1;
      }
    }
  }
  return numSwapped;
};

var n = 0;
var arr = [];
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
input.split('\n').forEach(function(line, i) {
  if (line !== '') {
    if (i % 2 === 0) {
      n = parseInt(line, 10);
    } else {
      arr = line.trim().split(' ').map(Number);
      var num = bubbleSort(arr, n);
      console.log(arr.join(' '));
      console.log(num);
    }
  }
});

Measured memory_bytes: 15816
N,M = (int(i) for i in input().split())
mx,mn = 0,float('inf')
for l,r in [[int(i) for i in input().split()] for i in range(M)]:
    mx = max(l,mx)
    mn = min(r,mn)
if mn-mx < 0:
    print(0)
else:
    print(mn-mx+1)


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

int main() {
    int n[4];
    int i;
    bool flg=true;
    // std::cout << "Hello, World!" << std::endl;
    cin>>n[0]>>n[1]>>n[2]>>n[3];
    for(i=0;i<4;i++){
        if(n[i]==1){
            break;
        }
        if(i==3){
            flg=false;
        }
    }
    for(i=0;i<4;i++){
        if(n[i]==9){
            break;
        }
        if(i==3){
            flg=false;
        }
    }
    for(i=0;i<4;i++){
        if(n[i]==7){
            break;
        }
        if(i==3){
            flg=false;
        }
    }
    for(i=0;i<4;i++){
        if(n[i]==4){
            break;
        }
        if(i==3){
            flg=false;
        }
    }

    if(flg){
        cout << "YES"<<endl;
    }else{
        cout << "NO" << endl;
    }

    return 0;
}

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

std::vector <int> l(8);

int main() {
	int n, sum = 0;
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		std::cin >> l[i];
		sum += l[i];
	}
	sum -= *std::max_element(l.begin(), l.end());
	if (*std::max_element(l.begin(), l.end()) < sum) {
		std::cout << "Yes" << std::endl;
	}
	else { std::cout << "No" << std::endl; }
	return 0;
}

Measured memory_bytes: 256
#include<map>
#include<list>
#include<queue>
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<vector>
#include<cmath>
#include<algorithm>

#define ull unsigned long long
#define ll long long
#define mp make_pair
#define imei(...)   "[ "<< #__VA_ARGS__ <<" = "<< __VA_ARGS__ <<" ] "

using namespace std;

vector<ll> val;

int main(int argc, char *argv[])
{
    int n;
    ll all = 0;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        all ^= v;
        val.push_back(v);
    }

    for (int i = 0; i < n; i++) {
        all ^= val[i];
        cout << all <<" ";
        all ^= val[i];
    }

    return 0;
}


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

#define N 1000000007

int main()
{
    ll n, a = 1, b = 1, c = 1;
    cin >> n;
    rep(i, n)
    {
        a *= 10;
        b *= 9;
        c *= 8;
        a %= N;
        b %= N;
        c %= N;
    }
    ll ans = (a - 2 * b + c) % N;
    if (ans < 0)
        ans += N;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>

using namespace std;

int main()
{
	int W, H;
	int i, j;

	while (1)
	{
		cin >> H >> W;

		if (W == 0 && H == 0)
			break;

		for (j = 0; j < H; j++)
		{

			for (i = 0; i < W; i++)
			{
				cout << '#';
			}
			cout << endl;
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1152
import sys
import math
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


# 素因数分解（複数回）
class Factorize(object):

    def __init__(self, maxnum):
        self.primes = self.__smallest_prime_factors(maxnum)

    # 素因数分解 O(logN)
    def factorize(self, n):
        fct = defaultdict(lambda: 0)
        while n != 1:
            fct[self.primes[n]] += 1
            n //= self.primes[n]
        return fct

    # n以下の最小の素因数を列挙する O(NlogN)
    def __smallest_prime_factors(self, n):

        prime = list(range(n + 1))

        for i in range(2, int(n**0.5) + 1):
            if prime[i] != i:
                continue
            for j in range(i * 2, n + 1, i):
                prime[j] = min(prime[j], i)
        return prime


def main():

    N = in_n()
    A = sorted(in_nl())

    M = 10**6 + 1
    ok = [True] * M

    fct = Factorize(M)

    pf = True
    for i in range(N):
        prime = fct.factorize(A[i])
        for p in prime.keys():
            if not ok[p]:
                pf = False
                break
            else:
                ok[p] = False

    g = A[0]
    for i in range(1, N):
        g = math.gcd(g, A[i])

    if pf:
        ans = "pairwise coprime"
    else:
        if g == 1:
            ans = "setwise coprime"
        else:
            ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 192944
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>

#define int long long
using namespace std;

int N, M, a[100010], b[100010], x[100010][20], c[10], t[100010], COUNT, m;

signed main()
{
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> a[i] >> b[i];
    }

    for (int i = 1; i <= M; i++) {
        x[a[i]][0]++;
        x[b[i]][0]++;
        x[a[i]][x[a[i]][0]] = b[i];
        x[b[i]][x[b[i]][0]] = a[i];
    }

    for (int i = 1; i <= N; i++) {
        if (x[i][0] == 0) {
            cout << "No" << endl;
            return 0;
        } else if (x[i][0] == 4) {
            COUNT++;
            c[0]++;
            c[c[0]] = i;
        } else if (x[i][0] == 6) {
            COUNT += 2;
            c[6] = i;
        } else if (x[i][0] % 2) {
            cout << "No" << endl;
            return 0;
        }
    }
    if (COUNT < 2) {
        cout << "No" << endl;
        return 0;
    } else if (COUNT >= 3) {
        cout << "Yes" << endl;
        return 0;
    }
    if (c[6]) {
        cout << "Yes" << endl;
        return 0;
    } else {
        if (COUNT == 2) {
            auto FIND = [&](auto i) {
                int bef, aft = 0;
                bef = c[1];
                aft = x[c[1]][i];
                while (aft != c[1] && aft != c[2]) {
                    if (x[aft][1] != bef) {
                        bef = aft;
                        aft = x[aft][1];
                    } else {
                        bef = aft;
                        aft = x[aft][2];
                    }
                }
                if (aft == c[2]) {
                    return 1;
                } else {
                    return 0;
                }
            };
            if (FIND(1) + FIND(2) + FIND(3) + FIND(4) == 4) {
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
        return 0;
    }


    return 0;
}


Measured memory_bytes: 17408
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
ans_kouho = sum(A[:K])
now_kouho = sum(A[:K])
for i in range(K, N):
    # print(ans_kouho)
    now_kouho = now_kouho-A[i-K]+A[i]
    ans_kouho = max(ans_kouho, now_kouho)
    # print(ans_kouho)
ans = (ans_kouho+K)/2
print(ans)


Measured memory_bytes: 25188
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 2e5 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const long long LINF = 1e18 + 3141;
 
void solve(){
    ll n;
    cin >> n;
    ll sp = (n + 1000 - 1) / 1000;
    cout << sp*1000 - n << '\n';
}
 
int main(){
    speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}

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

int n, a[3][105];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            a[i][j] += max(a[i - 1][j], a[i][j - 1]);
        }
    printf("%d\n", a[2][n]);
    return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using static System.Math;

class P
{
    static void Main()
    {
        int[] xy = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(xy[0] + xy[1] - gcd(xy[0], xy[1]) + 1);
    }

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


Measured memory_bytes: 8288
#include <iostream>
#include <string>
#include <vector>
//#include <math.h>
using namespace std;
typedef long long LL;

int main()
{
	int H, W, D;
	cin >> H >> W >> D;

	int HW = H * W;
	auto gridH = vector<int>(HW + 1);
	auto gridW = vector<int>(HW + 1);

	for (int h = 1; h <= H; h++) {
		int val;
		for (int w = 1; w <= W; w++) {
			cin >> val;
			gridH[val] = h;
			gridW[val] = w;
		}
	}

	auto Grid = vector<int>(HW + 1);
	for (int i = D +1; i <= HW; i++) {
		Grid[i] = Grid[i - D] + abs(gridH[i] - gridH[i - D]) + abs(gridW[i] - gridW[i - D]);
	}

	int Q, L, R, pos;
	cin >> Q;

	for (int i = 0; i < Q; i++) {
		cin >> L >> R;
		LL cnt = 0;

		cout << Grid[R] - Grid[L] << endl;
	}

	return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
typedef pair<string,string> Ps;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	int x,y,sx,sy,cost;
};
int main() {

	ll h;
	cin>>h;
	ll t=1,ans=1;
	h/=2;
	while(h>0){
		h/=2;
		t*=2;
		ans+=t;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
using namespace std;

int main(void){
    double W, H, x, y;
    cin >> W >> H >> x >> y;
    double area1 = 0.0, area2 = 0.0;
    area1 = W * ((double)(H)/2);
    if(x == ((double)(W)/2) && y == ((double)(H))/2){
        cout << area1 << " " << 1 << endl;
    } else {
        cout << area1 << " " << 0 << endl;
    }
}

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

int pow(int x, int n) {
  if (n == 0) return 1;
  int y = pow(x, n/2);
  int z = y*y;
  if (n & 1) z *= x;
  return z;
}

int main() {
  unsigned long k, l;
  cin >> k;
  
  if (k % 2 == 0 || k % 5 == 0) {
    cout << -1;
    return 0;
  }
  
  unsigned long mod = 0, count = 0;
  do {
    mod = 10*mod + 7;
    mod %= k;
    count++;
  } while (mod);
  
  cout << count;
  
  return 0;
}

Measured memory_bytes: 3616
#include <stdio.h>

int main(void) {

  int n;
  int a[100];

  int step;

  int temp;
  int i,j;

  while(1) {

    scanf("%d",&n);

    if(n==0) break;

    step=0;

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

      scanf("%d",&a[i]);

    }

    for(i=0;i<n-1;i++) {

      for(j=0;j<n-i-1;j++) {

	if(a[j]>a[j+1]) {

	  temp=a[j];
	  a[j]=a[j+1];
	  a[j+1]=temp;

	  step++;

	}

      }

    }

    printf("%d\n",step);

  }

  return 0;

}

Measured memory_bytes: 0
import math

n = input()

dis_1 = 0.0
dis_2 = 0.0
dis_3 = 0.0
dis_inf = 0.0

x = map(float, raw_input().split())
y = map(float, raw_input().split())

for i in xrange(n):
    dis_1 += abs(x[i] - y[i])
print "%.6f" % dis_1

for i in xrange(n):
    dis_2 += (x[i] - y[i])**2
print "%.6f" % math.sqrt(dis_2)

for i in xrange(n):
    dis_3 += abs(x[i] - y[i])**3
print "%.6f" % math.pow(dis_3, (1.0/3.0))

max_num = 0
for i in xrange(n):
    max_num = max(max_num, abs(x[i] - y[i]))
dis_inf = max_num
print "%.6f" % dis_inf

Measured memory_bytes: 6716
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)



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

	string X;
	cin >> X;
	int N = X.size();


	int ans = N;
	int cntS = 0;
	for (int i = 0; i < N; i++) {
		if (X[i] == 'S')cntS++;
		else {
			if (cntS == 0)continue;
			else {
				cntS--;
				ans -= 2;
			}
		}
	}
	puts(ans);

	return 0;
}

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

int main(void){
    double a,b;
    int h,m;
    scanf("%lf %lf %d %d",&a,&b,&h,&m);
    
    double ax,ay,bx,by;
    double PI=3.14159265358979323846;

    ax=cos(PI*h/6+PI*m/360);
    ay=sin(PI*h/6+PI*m/360);
    bx=cos(PI*m/30);
    by=sin(PI*m/30);
    
    double ans = (a*ax-b*bx)*(a*ax-b*bx)+(a*ay-b*by)*(a*ay-b*by);
    printf("%.20lf",sqrt(ans));
   
    return 0;
}

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

int main(){
    int N;
    scanf("%d", &N);
    char a[N];
    char b[N];
    char c[N];
    scanf("%s", a);
    scanf("%s", b);
    scanf("%s", c);
    int min = 0;
    for(int i = N-1; i>=0; i--){
        int tmp1 = 0;
        int tmp2 = 0;
        int tmp3 = 0;
        if(strcmp(&a[i], &b[i]) != 0)tmp1 = 1;
        if(strcmp(&a[i], &c[i]) != 0)tmp2 = 1;
        if(strcmp(&b[i], &c[i]) != 0)tmp3 = 1;
        if(tmp1+tmp2+tmp3 == 2)min += 1;
        if(tmp1+tmp2+tmp3 == 3)min += 2;
        b[i] = a[i];c[i] = a[i];
    }
    printf("%d\n", min);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,d,e;
  string s,ss,sss;
  cin>>a>>b;
  ll ans=0;
  ll now=1;
  while(now<b){
    now+=a-1;
    ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
x = list(map(int, input().split()))
if n >= m:
  print(0)

else:
  del x[m:]
  x.sort()
  d = []

  for i in range(len(x) - 1):
    d.append(x[i+1] - x[i])

  d.sort()

  print(sum(d[:(m-n)]))




Measured memory_bytes: 56744
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll n,k,cnt=0;
  cin >> n >> k;
  ll h[n];
  for(int i=0;i<n;i++){
    cin >> h[i];
    if(h[i]>=k)cnt ++;
  }
  cout << cnt << endl;
}


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

typedef long long ll;

using namespace std;

int main()
{
    ll w, h;

    while (cin >> h >> w)
    {
        if (w == 0 && h == 0)
            break;

        for (ll j=0; j<h; j++)
        {
            for (ll i=0; i<w; i++)
            {
                cout << '#';
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}



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

using namespace std;

typedef long long int ll;

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

  ll n, m, x;
  cin >> n >> m >> x;
  vector < ll > cst(n, 0);
  vector < vector < ll > > adj(n, vector < ll > (m));

  for(int i = 0; i < n; i++){
    cin >> cst[i];
    for(int j = 0; j < m; j++) cin >> adj[i][j];
  }

  ll mi = LLONG_MAX;
  for(int i = 0; i < ((ll)(1 << n)); i++){
    vector < ll > lvl(m, 0);
    ll tmp_cst = 0;
    for(int j = 0; j < n; j++){
      if((i >> j) & 1){
        tmp_cst += cst[j];
        for(int k = 0; k < m; k++){
          lvl[k] += adj[j][k];
        }
      }
    }

    bool ok = true;
    for(int i = 0; i < m; i++){
      if(lvl[i] < x) ok = false;
    }

    if(ok){
      mi = min(mi, tmp_cst);
    }
  }

  if(mi == LLONG_MAX) cout << -1 << endl;
  else cout << mi << endl;
}


Measured memory_bytes: 3664
//C 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10; 
int cnt[maxn];
int main(){
	int n;
	cin >> n;
	for(int i = 1;i < n;i++){
		int x;
		cin >> x;
		cnt[x]++;
	}
	for(int i = 1;i <= n;i++)cout << cnt[i] << endl;
	return 0;
}


Measured memory_bytes: 4416
K,N = map(int,input().split())
li = list(map(int,input().split()))
kyori = 0
for i in range(1,len(li)):
    if li[i] - li[i-1] > kyori:
        kyori = li[i] - li[i-1]
syokiti = li[0]+K-li[N-1]         
if syokiti < kyori:
    print(K - kyori)
else:
    print(K-syokiti)        


Measured memory_bytes: 25452
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define gcd __gcd
#define lcm(n, m) n * m / gcd(n, m)
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define ea(i, n) for(auto&& i: n)
#define so(n) sort(n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// rtsq ルート, int 2*10^9, __gcd

int main() {
  int A, B, C;
  ci(A, B, C);
  co(min(B / A, C));
}

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

using namespace std;

typedef long long ll;

int main(){
  int n, y; cin >> n >> y;
  int yy = y/1000;
  int a=-1, b=-1, c=-1;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n-i;j++){
      if(10*i + 5*j + (n-i-j) == yy){
        a=i, b=j, c=n-i-j;
        break;
      }
    }
  }
  cout << a << " " << b << " " << c << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define P pair<ll, ll>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 

////////////////////////////////////////////////////////


int main() {
    ll n; cin >> n;
    Vl a(n+1), ans(n+1, 0);
    Rep(i, 1, n) cin >> a[i];
    for(int i = n; i >= 1; i--){
        if(i > n/2) ans[i] = a[i];
        else{
            ll t = 2*i;
            ll cnt = 0;
            while(t <= n){
                if(ans[t]) cnt++;
                cnt %= 2;
                t += i;
            }
            ans[i] = (cnt+a[i])%2;
        }
    }
    ll nu = 0;
    Rep(i, 1, n){
        if(ans[i]) nu++;
    }
    co(nu);
    Rep(i, 1, n){
        if(ans[i]) cout << i << " ";
    }
    if(!nu) coel;
    

    return 0;
}


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

int main(void)
{
    string A, B;
    cin >> A >> B;

    if(A.size()>B.size())
        cout << "GREATER" << endl;
    else if(A.size()<B.size())
        cout << "LESS" << endl;
    else{
        for(int i{0}; i<A.size(); ++i){
            if(A[i]>B[i]){
                cout << "GREATER" << endl;
                return(0);
            }
            else if(A[i]<B[i]){
                cout << "LESS" << endl;
                return(0);
            }
        }
        cout << "EQUAL" << endl;
    }
}


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

const unsigned long long base = 111111;

unsigned long long rec(int v, const vector< vector<int> > &t,
		       unordered_map<unsigned long long, int> &num){
  unsigned long long res = 1;
  for(int u : t[v]){
    res += rec(u,t,num) * base;
  }
  
  num[res]++;
  return res;
}

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

  unordered_map<unsigned long long, int> num;
  rec(0,tree,num);

  long long ans = 0;
  for(auto x : num){
    ans += (long long)x.second * (x.second-1) / 2;
  }
  cout << ans << endl;
}

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

#define ll long long
ll mod =1000000007;
ll solve(vector<ll> &v,ll n,ll k){
    ll dp[n+2][k+2];
    for(ll j=0;j<=k;j++){
        dp[1][j]=(j>v[1])? 0 : 1;
    }

    for(ll i=2;i<=n;i++){
        for(ll j=0;j<=k;j++){
            if(j==0)
            dp[i][j]=dp[i-1][j];

            else
            dp[i][j]=(mod+dp[i-1][j]+dp[i][j-1]-((j-v[i]-1>=0)? dp[i-1][j-v[i]-1] : 0))%mod;
        }
    }
return dp[n][k];



}
int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> v(n+1);
    for(ll i=1;i<=n;i++){
        cin>>v[i];
    }
    cout<<solve(v,n,k)<<endl;

    return 0;
}

Measured memory_bytes: 81620
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>

using namespace std;

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

int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

static const double EPS = 1e-8;


string kang[] = {"a", "b", "c","d", "e", "f", "g", "h", "i","j", "k", "l","m","n", "o","p","q","r", "s","t", "u", "v", "w", "x", "y","z",
	"ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw","ts"};

int main(){
	string str;
	map<string,vector<string> > dubStr;
	dubStr["m"].push_back("mb");
	dubStr["m"].push_back("mp");

	dubStr["l"].push_back("ld");

	dubStr["n"].push_back("nc");
	dubStr["n"].push_back("nd");
	dubStr["n"].push_back("ng");
	dubStr["n"].push_back("nt");
	dubStr["n"].push_back("nw");

	dubStr["p"].push_back("ps");

	dubStr["q"].push_back("qu");

	dubStr["c"].push_back("cw");

	dubStr["t"].push_back("ts");

	int n;
	while(getline(cin,str)){

		n = atoi(str.c_str());

		map<P,int> kangPair;
		for(int line=0;line<n;line++){
			getline(cin,str);
			stringstream ss(str);
			while(ss >> str){
				map<string,int> freq;

				string prev = "";
				for(int s = 0; s<str.size();){

					string key = str.substr(s,1);
					string key2="";
					if(s<str.size()-1) key2 = str.substr(s,2);


					if(dubStr.find(key) != dubStr.end()){
						for(int i=0;i<dubStr[key].size();i++){
							if(key2 == dubStr[key][i]){

								if(prev != ""){
									kangPair[P(prev,key2)]++;
								}

								prev = key2;
								s+=2;
								goto next;
							}
						}

						if(prev != ""){
							kangPair[P(prev,key)]++;
						}
						prev = key;
						s+=1;
					}
					else{
						if(prev != ""){
							kangPair[P(prev,key)]++;
						}
						prev = key;
						s+=1;
					}
next:;
				}
			}
		}

		for(int i=0;i<38;i++){
			int maxv = 0;
			int to=0;
			for(int j=0;j<38;j++){
				map<P,int>::iterator it;
				if((it = kangPair.find(P(kang[i],kang[j]))) == kangPair.end()) continue;
				if(maxv < it->second){
					maxv = it->second;
					to = j;
				}
			}
			//cout << kang[i] << endl;
			if(maxv == 0) printf("%s %s %d\n",kang[i].c_str(),"a",0);
			else printf("%s %s %d\n",kang[i].c_str(),kang[to].c_str(),maxv);
		}
	}
}

Measured memory_bytes: 964
#include <cstdio>
#include <algorithm>
#define maxn 100010
using namespace std;

char in[3];
int n,v[3],p[maxn],q[maxn],ans[maxn];
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<3;i++)scanf("%d",&v[i]);
	for(i=1;i<=n;i++)scanf("%s",in),p[i]=in[0]-'A',q[i]=in[1]-'A';
	for(i=1;i<=n;i++){
		if(v[p[i]]>v[q[i]])swap(p[i],q[i]);
		else if(v[p[i]]==v[q[i]]){
			if(i+1<=n&&(q[i]==p[i+1]||q[i]==q[i+1]))swap(p[i],q[i]);
		}
		if(!v[q[i]])return 0*printf("No\n");
		v[p[i]]++,v[q[i]]--,ans[i]=p[i];
	}
	printf("Yes\n");
	for(i=1;i<=n;i++)printf("%c\n",'A'+ans[i]);
	return 0;
}

Measured memory_bytes: 2876
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define pb push_back
template<class T> inline int chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline int chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<29;
const ll LINF = 1LL<<58;

void solve() {
    double x, y;
    cin >> y;
    x = 100;
    int ans = 0;
    while (1) {
        x *= 1.01;
        x = (double) (ll) x;
        ans++;
        if (x >= y) {
            break;
        }
    }
    cout << ans << endl;
    return;
}

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


Measured memory_bytes: 3732
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> PLL;
#define chmax(x, y) do { x = max(x, y); } while(0)
#define chmin(x, y) do { x = min(x, y); } while(0)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (ll i = static_cast<ll>(a); i < static_cast<ll>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;

ll N, M;
ll h[200000];
vector<ll> edges[200000];

signed main() {
  cin >> N >> M;
  rep(i, N)
    cin >> h[i];
  rep(k, M) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  ll ans = 0;
  rep(i, N) {
    ll ok = true;
    for (auto j : edges[i]) {
      if (h[j] >= h[i])
        ok = false;
    }
    if (ok)
      ans++;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int N, a;
  cin >> N;
  int judge = 1;
  
  for(int i=0; i<N; i++) {
  	cin >> a;
    if(a%2==0) {
      if(a%3!=0 && a%5!=0) {
        judge = 0;
        break;
      }
    }
  }
  
  cout << ((judge==1) ? "APPROVED" : "DENIED") << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  int N; cin >> N;
  vector<tuple<string,int,int>> data(N);
  for(int i=0; i<N; i++){
    cin >> get<0>(data.at(i)) >> get<1>(data.at(i));
    get<2>(data.at(i)) = i+1;
  }
  for(int i=0; i<N; i++){
    get<1>(data.at(i)) = 100 - get<1>(data.at(i));
  }
  
  sort(data.begin(),data.end());
  
  for(int i=0; i<N; i++){
    cout << get<2>(data.at(i)) << endl;
  }

}

Measured memory_bytes: 256
x = input()
li = list(map(int,input().split()))
s =[]
for i in range(len(li)):
    if li[i] % 2 == 0:
        s.append(li[i])
o = True
for k in range(len(s)):
    if s[k] % 3 != 0 and s[k] % 5 != 0:
        o = False
    else:
        continue
if o:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
double dp[310][310][310];
int N = 0;

double rec(int i, int j, int k){
    if(dp[i][j][k] >= 0)    return dp[i][j][k];
    if(i == 0 && j == 0 && k == 0)  return dp[0][0][0] = 0.0;
    double res = 0.0;
    if(i > 0)   res += rec(i-1, j, k)*i;
    if(j > 0)   res += rec(i+1, j-1, k)*j;
    if(k > 0)   res += rec(i, j+1, k-1)*k;
    res += N;
    res *= 1.0/(i+j+k);
    return dp[i][j][k] = res;
}
int main(){
    cin >> N;
    int a = 0, b = 0, c = 0;
    for(int i = 0;i < N;i++){
        int ai;
        cin >> ai;
        if(ai == 1) a++;
        else if(ai == 2)    b++;
        else    c++;
    }
    memset(dp, -1, sizeof(dp));
    cout << setprecision(10) << rec(a, b, c) << endl;
}

Measured memory_bytes: 233088
K = input()
L = len(K)
D = int(input())
MOD = 10**9+7

dp = [[[0,0] for _ in range(D)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(K):
    c = int(c)
    for x in range(D):
        for d in range(10):
            y = (x+d)%D
            dp[i+1][y][1] += dp[i][x][1]
            dp[i+1][y][1] %= MOD
            if d > c: continue
            dp[i+1][y][int(d<c)] += dp[i][x][0]
            dp[i+1][y][int(d<c)] %= MOD
print((sum(dp[-1][0]) - 1) % MOD)

Measured memory_bytes: 129884
import java.util.*;
    public class Main {
     
    	public static void main(String[] args) {
    			
    		Scanner scan =new Scanner(System.in);
    		char[]n=scan.next().toCharArray();
    		for (char i:n) {
    			if(i=='1') {
    				System.out.print("9");
    			}else if(i=='9'){
    				System.out.print(1);
    			}else {
    				System.out.print(i);
    			}
    		}
    }
    }
// end 

Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int r=c-(a-b);
    if(r<=0)
        printf("0\n");
    else
        printf("%d\n",r);
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int n, k, a[112345];
int ans;

int main()
{
	while (true)
	{
		memset(a, 0, sizeof(a));
		ans = -1;
		in >> n >> k;
		rep(i, n) { in >> a[i + 1]; }
		if (n == 0 && k == 0) { break; }

		rep(i, n) { a[i + 1] += a[i]; }
		rep(i, n - k + 1)
		{
			auto res = a[i + k] - a[i];
			ans = std::max(ans, res);
		}

		out << ans << std::endl;
	}
	return 0;
}

Measured memory_bytes: 3460