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

int main() {
  long long n,wsum;
  cin >> n >> wsum;
  vector<long long> v(n);
  vector<long long> w(n);
  for(long long i=0;i<n;i++) {
    cin >> w.at(i) >> v.at(i);
  }
  vector<vector<long long>> dp(n+1,vector<long long>(wsum+1,0));
  for(long long i=0;i<n;i++) {
    for(long long j=1;j<wsum+1;j++) {
      if(w.at(i)<=j) {
        dp.at(i+1).at(j)=max(dp.at(i+1).at(j),dp.at(i).at(j-w.at(i))+v.at(i));
      }
      dp.at(i+1).at(j)=max(dp.at(i+1).at(j),dp.at(i).at(j));
    }
  }
  cout << dp.at(n).at(wsum) << endl;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
#define int long long

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define DEBUGP(x) cerr << #x << ": " << x.first << " \t" << x.second << '\n'

int n;
VI a;
int q;
VI m;

bool isOK(int k, int i, int d){
    if (d == m[k]) return true;
    if (i == n) return false;
    return isOK(k, i+1, d + a[i]) || isOK(k, i+1, d);
}

signed main()
{
    cin >> n;
    REP(i, n){
        int x;
        cin >> x;
        a.push_back(x);
    }
    cin >> q;
    REP(i, q){
        int x;
        cin >> x;
        m.push_back(x);
    }

    REP(i, q){
        if (isOK(i, 0, 0)){
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3164
#import<atcoder/all>
using std::cin;int N,Q,i,a;main(){cin>>N>>Q;atcoder::fenwick_tree<long>b(N);for(;i<N;b.add(i++,a))cin>>a;for(;cin>>i>>a>>N;Q--){i&&std::cout<<b.sum(a,N)<<' ';if(!i)b.add(a,N);}}

Measured memory_bytes: 8204
n=int(input())
a=[]
for i in range(n):
  a.append((input()))
if(len(a)==len(set(a))):
  for i in range(n-1):
    if(a[i][-1]!=a[i+1][0]):
      print("No")
      exit(0)
  print("Yes")
else:
  print("No")
  exit(0)

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

const int M = 2005;
const int N = 30005;
const int o = 15000;

bool ab[N],ac[N],bc[N];

bool match(char x,char y) {
    return x=='?' || y=='?' || x==y;
}

string a,b,c;
int la,lb,lc;

signed main() {
    ios::sync_with_stdio(false);
    cin>>a>>b>>c;
    la=a.length();
    lb=b.length();
    lc=c.length();
    for(int i=0;i<la;i++) for(int j=0;j<lb;j++)
        if(!match(a[i],b[j])) ab[i-j+o]=1;
    for(int i=0;i<la;i++) for(int j=0;j<lc;j++)
        if(!match(a[i],c[j])) ac[i-j+o]=1;
    for(int i=0;i<lb;i++) for(int j=0;j<lc;j++)
        if(!match(b[i],c[j])) bc[i-j+o]=1;
    int ans=N;
    for(int i=-2*M;i<=2*M;i++) for(int j=-2*M;j<=2*M;j++) {
        if(!ab[i+o] && !ac[j+o] && !bc[j-i+o]) {
            ans=min(ans, max(la,max(lb+i,lc+j))-min(0,min(i,j)));
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 384
def main():
	N, M = map(int, input().split())
	LR = [0]*M
	for i in range(M):
		LR[i] = list(map(int, input().split()))

	LR.sort(key=lambda x: x[1])

	l, r = LR[0][0], LR[0][1]
	ans = 1
	for i in range(1, M):
		if LR[i][0] < r:
			l = max(l, LR[i][0])
		else:
			ans += 1
			l = LR[i][0]
			r = LR[i][1]
	print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 29080
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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

  int n;
  cin >> n;

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

  vector<ll> march(5, 0);
  for (int i = 0; i < n; i++) {
    switch (sv[i][0]) {
      case 'M':
        march[0]++;
        break;
      case 'A':
        march[1]++;
        break;
      case 'R':
        march[2]++;
        break;
      case 'C':
        march[3]++;
        break;
      case 'H':
        march[4]++;
        break;
    }
  }

  ll ans = 0;

  for (int i = 0; i < 5; i++) {
    for (int j = i + 1; j < 5; j++) {
      for (int k = j + 1; k < 5; k++) {
        ans += march[i] * march[j] * march[k];
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 100005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}
ll n, m;
char arr[30][30];
ll cnt = 0, cnt2 = 0;
ll dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool visited[30][30];
bool valid(ll i, ll j) {
  return i > 0 && i <= n && j > 0 && j <= m && !visited[i][j] &&
         arr[i][j] != '#';
}

void dfs(ll i, ll j) {
  visited[i][j] = true;
  if (arr[i][j] == 'K')
    cnt2++;
  for (ll k = 0; k < 4; k++) {
    ll ni = i + dir[k][0];
    ll nj = j + dir[k][1];
    if (valid(ni, nj)) {
      dfs(ni, nj);
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  string s;
  cin >> s;

  ll start = 0;
  ll n = s.length();
  ll res[n + 5];
  res[0] = 0;
  /*
  if (s[0] = '>') {
    ll len = 0;
    int prev1 = start;
    while (start < s.length() && s[start] == '>') {
      start++;
      len++;
    }

    for (int i = prev1; i <= start; i++)
      res[i] = len--;
  }
  */

  for (ll i = start; i < s.length();) {
    if (s[i] == '<') {
      res[i + 1] = res[i] + 1;
      i++;
    } else {
      ll len = 0;
      int prev1 = i;
      while (i < s.length() && s[i] == '>') {
        i++;
        len++;
      }

      res[prev1] = max(res[prev1], len);
      len--;
      for (int j = prev1 + 1; j <= i; j++)
        res[j] = len--;
    }
  }

  ll ans = 0;
  for (ll i = 0; i <= n; i++) {
    //   cout << res[i] << " ";
    ans += res[i];
  }
  // cout << en;
  cout << ans << en;

  return 0;
}

Measured memory_bytes: 4764
N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if (data[j-1][1] != p) and (j > 0):
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))

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

int main(void){
    long long int n, y;
    cin >> n >> y;
    for(long long int i = 0; i <= n; i++){
        if(10000*i > y) break;
        for(long long int j = 0; j <= n; j++){
            if(10000*i + 5000*j > y) break;
            long long int k = n - i - j;
            if(i + j + k == n && 10000*i+5000*j+1000*k == y){
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
}

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

#define int long long

using namespace std;

#ifdef LOCAL 
#include "/media/brayand/BrayanD/debugger.h"
#else
#define db(...) false
#define dbg(...) false
#endif

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

    int H, W;
    cin >> H >> W;

    set<pair<int,int>> st;
    set<pair<int,int>> ist;

    for(int i = 1 ; i <= W ; i++)
    {
    	st.insert({i,0});
    	ist.insert({0,i});
    }

    for(int i = 0 ; i < H ; i++)
    {
    	db(st);
    	db(ist);
    	if(i)
    	{
    		if(ist.size())cout << (*ist.begin()).first + i << '\n';
    		else cout << -1 << '\n';
    	}

    	int a, b;
    	cin >> a >> b;

    	b++;

    	vector<pair<int,int>> vect;

    	while(1)
    	{
    		auto it = st.upper_bound({a,-1});
    		if(it == st.end())break;
    		if((*it).first > b)break;
    		vect.push_back(*it);
    		st.erase(it);
    	}

    	db(vect);

    	if(vect.size() == 0)continue;

    	for(auto x : vect)
    	{
    		ist.erase({x.second,x.first});
    	}


    	int value = vect.back().second + abs(vect.back().first - (b));
    	int pos = (b);

    	if(pos != W+1)
    	{
    		st.insert({pos,value});
    		ist.insert({value,pos});
    	}
    }
    	db(st);
    	db(ist);

    if(ist.size())cout << (*ist.begin()).first + H << '\n';
    else cout << -1 << '\n';

    return 0;
}

Measured memory_bytes: 28576
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

namespace my
{
	//-----------------------------------------------------------------------------
	inline char cn()
	{
		static char buf[1000010],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
	}
	#define cn getchar
	template<class TY>void read(TY &x)
	{
		x=0;int f1=1;char ch=cn();
		while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
		while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
	}
	char Output[1000100],Zk[100];int op_top=0,Zk_top;
	void fcheck(int Type=0){if(Type||op_top>=1000000)fwrite(Output,1,op_top,stdout),op_top=0;}
	template<class TY>inline void write(TY x)
	{
		if(x==0){Output[op_top++]='0';fcheck();return;}
		if(x<0)Output[op_top++]='-',x=-x;
		Zk_top=0;while(x)Zk[++Zk_top]=x%10+'0',x/=10;
		while(Zk_top)Output[op_top++]=Zk[Zk_top--];fcheck();
	}
	#define K_G Output[op_top++]=' '
	#define H_C Output[op_top++]='\n'
	//--------------------------------------------------------------------------------------------
	
	//--------------------------------------------------------------------------------------------
	#define ll long long
	#define uint unsigned int
	#define ull unsigned long long
	#define INV(x) ksm(x,mod-2)
	#define inf 999999999
	#define mod 998244353
	
	template<class TY>void add(TY &x,TY y){x=(x+y>=mod?x+y-mod:x+y);}
	template<class TY>void dec(TY &x,TY y){x=(x-y<0?x-y+mod:x-y);}
	template<class TY>TY add(TY x){return x>=mod?x-mod:x;}
	template<class TY>TY dec(TY x){return x<0?x+mod:0;}
	//
	int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
	int *fac,*inv_fac,*inv;
	void work_math(const int N)
	{
		fac=new int[N+5];inv_fac=new int[N+5];inv=new int[N+5];
		inv[1]=1;for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fac[0]=inv_fac[0]=1;for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
		inv_fac[N]=INV(fac[N]);
		for(int i=N-1;i>=1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;
	}
	int C(int x,int y){return 1ll*fac[x]*inv_fac[y]%mod*inv_fac[x-y]%mod;}
	//
	template<class TY>TY gcd(TY x,TY y){return !y?x:gcd(y,x%y);}
	template<class TY>TY exgcd(TY a,TY b,TY &x,TY &y){
		if(!b)return x=1,y=0,a;
		TY re=exgcd(b,a%b,y,x);
		return y-=a/b*x,re;
	}
	//
	template<class TY>void discretization(TY *arr,int St,int Ed){
		vector<TY>Arr;Arr.clear();
		for(int i=St;i<=Ed;i++)Arr.push_back(arr[i]);
		sort(Arr.begin(),Arr.end());
		for(int i=St;i<=Ed;i++)arr[i]=lower_bound(Arr.begin(),Arr.end(),arr[i])-Arr.begin()+1;
	}
	//-----------------------------------------------------------------------------------------------
	
	//----------------------------------------------------------------------------------------------- 
	char s[4];
	
	void main()
	{
		scanf("%s",s+1);
		int tot=0,ans=0;
		for(int i=1;i<=3;i++)
		if(s[i]=='R')tot++;
		else ans=max(ans,tot),tot=0;
		ans=max(ans,tot);
		write(ans);
		fcheck(1);return;
	}
}

int main(){my::main();return 0;}

Measured memory_bytes: 3128
from bisect import*
def _add(data,k,x):
    while k<=N:
        data[k]+=x
        k+=k&-k
def add(l,r,x):
    _add(data0,l,-x*(l-1))
    _add(data0,r,x*(r-1))
    _add(data1,l,x)
    _add(data1,r,-x)
def _get(data,k):
    s=0
    while k:
        s+=data[k]
        k-=k&-k
    return s
def query(l,r):
    return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)
N,d,a,*t=map(int,open(0).read().split())
data0=[0]*(N+1)
data1=[0]*(N+1)
z=sorted(zip(*[iter(t)]*2))
y=[x for x,_ in z]
c=0
for i,(x,h)in enumerate(z,1):
    h-=query(i,i+1)
    t=0--max(0,h)//a
    j=bisect(y,x+d+d)
    add(1,j+1,t*a)
    c+=t
print(c)

Measured memory_bytes: 127788
<?php
//前提条件$size>=2
$size = fgets(STDIN);
$v = fgets(STDIN);
//$vを配列にする
$array = explode(" ", $v);

//配列内に0があれば出力は配列絶対値の和
if(in_array(0,$array)){
  $allPlus = true;
}else{
  $allPlus = false;
}

$arrayAbs = [];
if($allPlus){
  foreach($array as $n){
    if($n < 0){
      $n = abs($n);
    }
    $arrayAbs[] = $n;
  }
  echo array_sum($arrayAbs);
//配列内のマイナスの数が偶数なら出力は絶対値合計、奇数なら絶対値最小値1つのみマイナス
}else{
  $min = abs($array[0]);
  $minusCounter = 0;
  foreach($array as $n){
    if($n < 0){
      $n = abs($n);
      $minusCounter++;
    }
    //if文の判定が先に行われ、その後上記の$n=abs($n)が実行されるため下記でもう一度$absが必要
    if($min > abs($n)){
      $min = $n;
    }
    $arrayAbs[] = $n;
  }
  if($minusCounter%2 === 0){
    echo array_sum($arrayAbs);
  }else{
    //最小値のみ引くことと、全ての和から最小値を2回引くことは同義
    echo array_sum($arrayAbs)-2*$min;
  }
}


Measured memory_bytes: 36852
N, K = map(int, input().split())
MOD = 998244353
S = []
for _ in range(K):
    S.append(tuple(map(int, input().split())))

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
            dp[i] %= MOD
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD

print(dp[N])


Measured memory_bytes: 24488
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(a) (a).begin(), (a).end()
typedef vector<int> vi;
const int INF = 1LL << 60; //10e18+10e17ちょっとくらい
const int MOD = 1000000007;
const int MAX_N = 200100;

int dp[1010][20010];
signed main()
{
    //  以降 cin の入力元が 'input.txt' になる
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    int h, n;
    cin >> h >> n;
    vector<pair<int, int>> vin;
    rep(i, n)
    {
        int a, b;
        cin >> a >> b;
        vin.emplace_back(a, b);
    }

    rep(i, 1010)
    {
        rep(j, 20010)
        {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    rep(i, n)
    {
        int d = vin[i].first;
        int c = vin[i].second;
        rep(j, 20010)
        {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            if (dp[i + 1][j] != INF)
                if (j + d < 20010)
                    dp[i + 1][j + d] = min(dp[i + 1][j + d], dp[i + 1][j] + c);
        }
    }
    int ans = INF;
    for (int i = h; i < 20010; i++)
    {
        ans = min(ans, dp[n][i]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 158208
from operator import itemgetter
import heapq
N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))
X.sort(key=itemgetter(0))
Y.sort(key=itemgetter(0))

import sys
sys.setrecursionlimit(10**6)


class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False
u = UnionFind(N)
q = []
for i in range(N-1):
    q.append((X[i+1][0]-X[i][0], X[i+1][1], X[i][1]))
    q.append((Y[i+1][0]-Y[i][0], Y[i+1][1], Y[i][1]))
q.sort(key=itemgetter(0))
ans = 0
for elem in q:
    cost, a, b = elem
    if u.union(a, b):
        ans += cost
print(ans)


Measured memory_bytes: 54488
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if (n == 0 && m == 0) {
				break;
			}
			int[] h = new int[n+1];
			int[] w = new int[m+1];
			for(int i=1;i<=n;i++) {
				h[i] = h[i-1] + sc.nextInt();
			}
			for(int i=1;i<=m;i++) {
				w[i] = w[i-1] + sc.nextInt();
			}
			HashMap<Integer, Integer> a = count(h);
			HashMap<Integer, Integer> b = count(w);
			int ans = 0;
			for(Entry<Integer,Integer> p:b.entrySet()) {
				if (a.containsKey(p.getKey())) {
					ans += a.get(p.getKey()) * p.getValue();
				}
			}
			System.out.println(ans);
		}
	}

	static HashMap<Integer,Integer> count(int[] x) {
		int n = x.length;
		HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				int d = x[j] - x[i];
				if (count.containsKey(d)) {
					count.put(d, count.get(d) + 1);
				}else{
					count.put(d, 1);
				}
			}
		}
		return count;
	}

}

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


typedef long long ll;


int main() {
	string S;
	cin >> S;
	int ans = 0;
	for (int i = 0; i < 3; ++i) {
		int cnt = 0;
		int p = 0;
		while (i + p < 3 && S[i + p] == 'R') {
			++cnt; ++p;
		}
		ans = max(ans, cnt);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3200
package main

import (
	"fmt"
	"math"
)

func min(a, b int) int {
	if a >= b {
		return b
	}
	return a
}
func main() {
	var a, s [5]int
	minTime := math.MaxInt32
	for i := range a {
		fmt.Scan(&a[i])
	}
	for i, v := range a {
		s[i] = ((v + 9) / 10) * 10 // 直近の10の倍数への切り上げ
	}
	sumTime := 0
	for i, v := range a {
		sumTime = v
		for j, w := range s {
			if i == j {
				continue
			} else {
				sumTime += w
			}
		}
		minTime = min(minTime, sumTime)
	}
	fmt.Println(minTime)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
const ll MAX = 9000000000000000000;
#define fin(ans) cout << (ans) << endl;
#define all(a) a.begin(), a.end()
template <typename T>
void Sort(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (sort(n.begin() + a, n.end()));
  }
  else
  {
    return (sort(n.begin() + a, n.begin() + b));
  }
}
template <typename T>
void V(T &n)
{
  for (ll i = 0; i < n.size(); i++)
  {
    cin >> n[i];
  }
}
void Main()
{
  ll n, k; cin >> n >> k;
  vll h(n); V(h);
  Sort(h);
  ll ans = MAX;
  for(ll i = 0;i < n - k + 1;i++)
  {
    ll a = abs(h[i] - h[i + k - 1]);
    ans = min(ans, a);
  }
  fin(ans);
  return;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  Main();
  return 0;
}


Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
int x[]=new int[100002];
Arrays.fill(x,0);
int h;
for(int i=1;i<=n;i++){
h=sc.nextInt();
h++;
x[h]++;
x[h+1]++;
x[h-1]++;
}
Arrays.sort(x);
System.out.println(x[100001]);

	}}

Measured memory_bytes: 49832
N,K = map(int,input().split())
ans=0

for i in range(1,N+1):
    p=1
    sc=i
    cnt=0
    while 1<=sc<=K-1:
        cnt +=1
        p /=2
        sc *=2
    #print(i,cnt,p/N)
    ans += p/N
print(ans)

Measured memory_bytes: 2940
#include<iostream>
using namespace std; // 575

int main() {
	int N;
	cin >> N;
	cout << (N - 1) * (N - 1) / 2 << endl;
	for (int i = 1;i <= N;++ i) for (int j = i + 1;j <= N;++ j) if (i + j != N / 2 * 2 + 1) cout << i << " " << j << endl;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

やるだけ
*/

Measured memory_bytes: 256
n = int(input())
x = [int(i) for i in input().split()]
xs = sorted(x)
d = dict()
for i in range(n):
  if xs[i] not in d:
    d[xs[i]] = i
for i in range(n):
  print(xs[n // 2 - int(d[x[i]] >= n // 2)])

Measured memory_bytes: 39552
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<int> vec(N);
    int count = 0;
    for(int i = 0; i < N; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());
    for(int i = 0; i < N; i++){
        for(int j = i+1; j < N; j++){
            for(int t = j+1; t < N; t++){
                if(vec[i] + vec[j] > vec[t]){
                    count ++;
                }
            }
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
YES, NO, Yes, No = "YES", "NO", "Yes", "No"
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def ceil(a, b):return (a + b - 1) // b


def solve():
    N, A, B = map(int, input().split())
    if (A - B) % 2 != 0:
        print("Borys")
    else:
        print("Alice")


def main():
    solve()


if __name__ == '__main__':
    main()


Measured memory_bytes: 4200
#include <stdio.h>

int main(void)
{ 
  int n;
  int d[50];
  int sum = 0;
  int i, j;
  
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++)
    scanf("%d", &d[i]);
    
  for (int i = 0; i < n-1; i++)
    for (int j = i+1; j < n; j++)
      sum += d[i]*d[j];
  
  printf("%d", sum);
  
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b, a%b);
}
int arr[20];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
    string s; cin >> s;
    int n=s.size();
    int ans=1e9;
    int cnt=0;
    for(int i=0; i<n; ++i){
        if(i%2==0){
            if(s[i]=='1'){
                cnt++;
            }
        }else{
            if(s[i]=='0'){
                cnt++;
            }
        }
    }
    ans = min(ans, cnt);
    cnt=0;
    
    for(int i=0; i<n; ++i){
        if(i%2!=0){
            if(s[i]=='1'){
                cnt++;
            }
        }else{
            if(s[i]=='0'){
                cnt++;
            }
        }
    }
    cout << min(ans, cnt) << endl;
	return 0;

}

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

int main() {
        long long int n;
        cin>>n;
        long long int a[n];
        for(int i=0;i<n;i++)
        cin>>a[i];
        long long int ans=0;
        long long int m=0;
        for(int i=0;i<n;i++)
        {
            m = max(m,a[i]);
            if(a[i]<m)
            ans = ans + (m-a[i]);
        }
        cout<<ans;
	    return 0;
}

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

  int main(){
    ll N, K;
    cin >> N >> K;
    ll A[N];
    rep(i,N) cin >> A[i];
    ll cnt_A = 0;
    ll ans;
    for(int i = 0; i < N; i++){
      for(int j = i - 1; j >= 0; j--){
        if( A[j] > A[i] ) cnt_A++;
      }
    }

    ll cnt_B = 0;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        if(A[i] > A[j]) cnt_B++;
      }
    }

    // ans = 

    ans = ( cnt_A * K + ( K * (K-1) / 2 ) % MOD * cnt_B ) % MOD;

    cout << ans << endl;

    return 0;
  }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
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;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    long long N;
    cin >> N;
    vector<int> a(N); // amari
    REP(i, N) { cin >> a[i]; }
    vector<int> b(N, 0);
    // cout << N / 2 << endl;
    for(int i = N - 1; i > N / 2 - 1; i--) {
        b[i] = a[i];
        // cout << "i+1" << i + 1 << " b;" << b[i] << endl;
    }
    // cout << "maji" << endl;
    for(int i = N / 2 - 1; i >= 0; i--) {
        int tmp = 0;
        for(int j = 2 * (i + 1); j <= N; j += (i + 1)) {
            tmp += b[j - 1];
        }
        if(tmp % 2 == a[i]) {
            b[i] = 0;
        } else {
            b[i] = 1;
        }
    }
    // cout << "maji" << endl;
    cout << accumulate(b.begin(), b.end(), 0) << endl;
    REP(i, N) {
        if(b[i] > 0) {
            cout << i + 1 << " ";
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 2432
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	float a,b,c,d,e,f,g,x,y,ans;
	float B,C,E,F,j,k,l;
	while(cin>>a>>b>>c>>d>>e>>f){
		B=b*d;
		C=c*d;
		E=a*e;
		F=a*f;
		j=B-E;
		k=C-F;
		y=k/j;
		x=(c-b*y)/a;
		printf("%.3lf %.3lf\n",x,y);
	}
	return 0;
}

Measured memory_bytes: 3140
#include<stdio.h>

int main(){
  int x,y,r,a;

  scanf("%d",&x);
  scanf("%d",&y);

  //if(1 > x || y > 10^9){
  //return 0;
    //}

  if(y > x){
    a = x;
    x = y;
    y = a;
  }


  r = x % y;
  while(r != 0){
    x = y;
    y = r;
    r = x % y;
  }

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

 
  return 0;
}



Measured memory_bytes: 2144
#include <stdio.h>
int main()
{
    int mat1[101][101];
    int mat2[101][101];
    double mat3[101][101];
    int ra,rb,rc;
    int i,j,k;
    scanf("%d %d %d", &ra, &rb, &rc);
    for(i=0; i<ra; i++)
    {
        for(j=0; j<rb; j++){
            scanf("%d", &mat1[i][j]);
        }
    }
    for(i=0; i<rb; i++)
    {
        for(j=0; j<rc; j++){
            scanf("%d", &mat2[i][j]);
        }
    }
    for(i=0; i<ra; i++)
    {
        for(j=0; j<rc; j++)
        {
            for(k=0; k<rb; k++)
            {
                mat3[i][j] += mat1[i][k] * mat2[k][j];
            }
        }
    }
    for(i=0; i<ra; i++)
    {
        for(j=0; j<rc; j++)
        {
            if(j != rc-1) printf("%.0lf ", mat3[i][j]);
            else printf("%.0lf", mat3[i][j]);
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2776
#include <bits/stdc++.h>
using namespace std;
const int DP_ISZE = 600000;
const int INF = 100000009;

int dp[DP_ISZE];
int c[21];

int main(){
	int N, m;
	cin >> N >> m;
	for(int i=0; i<m; i++) cin >> c[i];
	for(int i=0; i<DP_ISZE; i++) dp[i] = INF;
	
	dp[0] = 0;
	
	for(int i=0; i<m; i++){
		for(int n=0; n+c[i]<=N; n++) dp[n+c[i]] = min(dp[n+c[i]], dp[n]+1);
	}
	
	cout << dp[N] << endl;
	
	return 0;
}


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

using namespace std;

int main (){
  int N,Y;
  cin >> N >> Y;
  vector<int> answer(3,0);
  bool sw = false;
  for(int i = 0; i < N + 1; i++){
    for(int j = 0; j < N + 1; j++){
      int k = N - i - j;
      if(k < 0){break;}
      if(10000*i + 5000*j +1000*k == Y){
        answer.at(0) = i;
        answer.at(1) = j;
        answer.at(2) = k;
        sw = true;
      }
      if(sw == true){break;}
    }
    if(sw == true){break;}
  }
  if(sw == false){answer = {-1,-1,-1};}
  cout << answer.at(0) << " " << answer.at(1) << " " << answer.at(2) << endl;
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t h, w, k;
    cin >> h >> w >> k;

    vector<vector<bool>> a(h, vector<bool>(w, true));
    int64_t si, sj;
    for (auto i : irange(0L, h)) {
        string s;
        cin >> s;

        for (auto j : irange(0L, w)) {
            if (s[j] == '#') {
                a[i][j] = false;
            } else if (s[j] == 'S') {
                si = i;
                sj = j;
            }
        }
    }

    const int64_t di[4] = {-1L, 1L, 0L, 0L};
    const int64_t dj[4] = {0L, 0L, -1L, 1L};

    vector<vector<int64_t>> dist(
            h, vector<int64_t>(w, numeric_limits<int64_t>::max()));
    queue<pair<int64_t, int64_t>> q;
    dist[si][sj] = 0;
    q.emplace(si, sj);

    int64_t ans = numeric_limits<int64_t>::max();
    while (!q.empty()) {
        auto i = q.front().first;
        auto j = q.front().second;
        q.pop();

        int64_t r = (min({i, j, h - i - 1, w - j - 1}) + k - 1) / k;

        ans = min(ans, r + 1);

        if (r == 0 || dist[i][j] == k) {
            continue;
        }

        for (auto t : irange(0L, 4L)) {
            auto ni = i + di[t];
            auto nj = j + dj[t];

            if (!a[ni][nj]) {
                continue;
            }

            if (dist[ni][nj] > dist[i][j] + 1) {
                dist[ni][nj] = dist[i][j] + 1;
                q.emplace(ni, nj);
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 5376
#include <iostream>
using namespace std;
int main(){
  int a,b,r,A,B,tmp;
  while(cin>>a>>b){
    A = a; B = b;
    if(b>a){
      tmp=a;a=b;b=tmp;
    }
    while(1){
      r = a % b;if(r == 0) break;
      a = b;
      b = r;
    }
    cout << b <<" "<< A/b*B << endl;
  }
}

Measured memory_bytes: 3088
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        l: usize,
        r: usize,
        d: usize,
    }
    let mut count = 0;
    for i in l..=r {
        if i % d == 0 {
            count += 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 2092
import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
  cc = c+1
  if cc > maxc:
    cc = 1
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,cc)
      cc += 1
      if cc > maxc:
        cc = 1

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])


Measured memory_bytes: 79880
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kamol Paul
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define long long long
typedef pair < long , long > pii;

class DCaracalVsMonster {
public:

	void solve(std::istream& in, std::ostream& out) {
        long n;
        long ans=0;
        in>>n;
        long k=1;
        while (n){
            ans+=k;
            n/=2;
            k <<= 1;
        }
        out<<ans<<endl;
	}
};


int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
	DCaracalVsMonster solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int n,s,a[100],i,j,x,y;
	s=0;
	x=0;
	y=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(a[i]<a[j]){
				s=a[i];
				a[i]=a[j];
				a[j]=s;
			}
		/*	printf("i=%d j=%d\n",a[i],a[j]);
			printf("\n");*/
		}
	}
	for(i=0;i<n;i++){
		if(i%2==0){
			x+=a[i];
		//	printf("x=%d\n",x);
		}
		else{
			y+=a[i];
			//printf("y=%d\n",y);
		}
	}
	x=x-y;
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <functional>
#include <array>
#include <climits>
//#include "debug.h"
using namespace std;

#define A first
#define B second
 
typedef long long ll;
constexpr int MOD = 1e9 + 7;

inline int mulmd(ll a, ll b){
  ll ret = (a * b) % MOD;
  return (int) ret;
}

inline int power(ll x, ll y, int m){
  ll res = 1;
  x = x % m;
  while(y > 0){
    if(y & 1){
      res = mulmd(res, x);
    }
    y = y >> 1;
    x = mulmd(x, x);
  }
  return (int) res;
}

inline int submd(ll a, ll b){
  ll ret = (a - b);
  if(ret < 0) ret += MOD;
  return (int) ret;
}

inline int addmd(ll a, ll b){
  ll ret = (a + b) % MOD;
  return (int) ret;
}

inline int invPow(ll a){
  return power(a, MOD - 2, MOD);
}

inline int divmd(ll a, ll b){
  ll ret = mulmd(a, invPow(b));
  return (int) ret;
}

void solve() {
  int N;
  cin >> N;

  vector<int> dp(N + 1, 0);
  dp[0] = 1;
  for(int i = 3; i <= N; i++){
    for(int j = 3; j <= i; j++){
      dp[i] = addmd(dp[i], dp[i - j]);
    }
  }
  cout << dp[N];
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  T = 1;
  //cin >> T;
  while(T--){
    solve();
  }
}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#include<functional>
//#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i, x) for(ll i = 0; i < x; i++)
#define rep2(i, x) for(ll i = 1; i <= x; i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ld pi = 3.141592653589793238;

/*bool isprime(int p) {
	if (p == 1) return false;
	for (int i = 2; i < p; i++) {
		if (p % i == 0) return false;
	}
	return true;
}*/
/*ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}*/
/*ll keta(ll n) {
	ll res = 0;
	while (n >= 1) {
		res += n % 10; n /= 10;
	}
	return res;
}*/
/*ll modpow(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y % 2) { res *= x; res %= mod; }
		x = x * x % mod; y /= 2;
	}
	return res;
}
ll nCk(ll n, ll k) {
	ll a = 1, b = 1;
	for (int h = n - k + 1; h <= n; h++) { a *= h; a %= mod; }
	for (int h = 1; h <= k; h++) { b *= h; b %= mod; }
	return a * modpow(b, mod - 2) % mod;
}*/
//printf("%.10f\n", n);

signed main() {
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	string s, t;
	ll n, m, a = 0, b = 0, c = 0, cnt = 0, ans = 0;
	cin >> n;
	if (n == 0) { cout << "1\n"; }
	else { cout << "0\n"; }


	return 0;
}

Measured memory_bytes: 3596
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD (long long)1000000007
using namespace std;

int main(void){
    int n,ans=0,count;
    string s,S,T;
    vector<int> uses(26,0),uset(26,0);
    cin >> n >> s;
    for(int i=0; i<n; i++){
        S=s.substr(0,i);
        T=s.substr(i,n-i);
        for(int j=0; j<26; j++){
            uses[j]=0;uset[j]=0;
        }
        count=0;
        for(int j=0; j<S.length(); j++){
            uses[ S[j]-'a' ]++;
        }
        for(int j=0; j<T.length(); j++){
            uset[ T[j]-'a' ]++;
        }
        for(int j=0; j<26; j++){
            if(uses[j]!=0 && uset[j]!=0)count++;
        }
        ans=max(ans,count);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<climits>
#include<set>
#include<map>
#define ll long long
using namespace std;

int main() {
	ll h, w;
	cin >> h >> w;
	vector<string>s(h);
	for (ll i = 0; i < h; i++) {
		cin >> s[i];
	}
	for (ll i = 0; i < h; i++) {
		for (ll j = 0; j < w; j++) {
			if (i == 0) {
				if (j == 0) {
					if (s[i][j] == '#' 
						&& (s[i][j] != s[i + 1][j] &&
						s[i][j] != s[i][j + 1])) {
						cout << "No" << endl;
						exit(0);
					}
				}
				else if (j==w-1) {
					if (s[i][j] == '#'
						&& (s[i][j] != s[i + 1][j] &&
							s[i][j - 1] != s[i][j])) {
						cout << "No" << endl;
						exit(0);
					}
				}
				else {
					if (s[i][j] == '#' 
						&& (s[i][j] != s[i + 1][j] &&
						s[i][j] != s[i][j + 1] &&
						s[i][j - 1] != s[i][j])) {
						cout << "No" << endl;
						exit(0);
					}

				}
					
			}
			else if (i == h - 1) {
				if (j == 0) {
					if (s[i][j] == '#'
						&& (s[i][j] != s[i - 1][j] &&
							s[i][j] != s[i][j + 1])) {
						cout << "No" << endl;
						exit(0);
					}
				}
				else if (j == w - 1) {
					if (s[i][j] == '#'
						&& (s[i][j] != s[i - 1][j] &&
							s[i][j - 1] != s[i][j])) {
						cout << "No" << endl;
						exit(0);
					}
				}
				else {
					if (s[i][j] == '#'
						&& (s[i][j] != s[i - 1][j] &&
							s[i][j] != s[i][j + 1] &&
							s[i][j - 1] != s[i][j])) {
						cout << "No" << endl;
						exit(0);
					}
				}

			

			}
			else {
				if (j == 0) {
					if (s[i][j] == '#'
						&& (s[i][j] != s[i + 1][j] &&
							s[i-1][j] != s[i][j]&&
							s[i][j + 1] != s[i][j])) {
						cout << "No" << endl;
						exit(0);
					}


				}
				else if (j == w - 1) {
					if (s[i][j] == '#'
						&& (s[i][j] != s[i + 1][j] &&
							s[i - 1][j] != s[i][j] &&
							s[i][j - 1] != s[i][j])) {
						cout << "No" << endl;
						exit(0);
					}
				}
				else {
					if (s[i][j] == '#'
						&& (s[i - 1][j] != s[i][j] &&
							s[i][j] != s[i + 1][j] &&
							s[i][j] != s[i][j + 1] &&
							s[i][j - 1] != s[i][j])) {
						cout << "No" << endl;
						exit(0);
					}

				}
			}
			
		}
	}
	cout << "Yes" << endl;
}



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

using namespace std;
using LL = long long;
const LL LINF = 1e18;
const LL MOD = 1e9+7;


int main(){
    int N;cin >> N;
    vector<int> vec;
    vector<pair<int,int>> ans;
    for(int a = 0;a < N;a++){
        int b;cin >> b;
        vec.push_back(b);
    }
    if(abs(*max_element(vec.begin(),vec.end())) > abs(*min_element(vec.begin(),vec.end()))){
        for(int a = 0;a < N;a++){
            ans.push_back({max_element(vec.begin(),vec.end())-vec.begin(), a});
        }
        for(int a = 0;a < N-1;a++){
            ans.push_back({a,a+1});
        }
    }else{
        for(int a = 0;a < N;a++){
            ans.push_back({min_element(vec.begin(),vec.end())-vec.begin(), a});
        }
        for(int a = N-1;a >= 1;a--){
            ans.push_back({a,a-1});
        }
    }
    cout<<ans.size()<<endl;
    for(int a = 0;a < ans.size();a++){
        cout<<ans.at(a).first+1<<" "<<ans.at(a).second+1<<endl;
    }
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	ll x,y;
	cin >> x >> y;
	
	int ret = 0;
	if(abs(x)<abs(y)){
		if(x < 0)ret ++;
		ret += abs(y)-abs(x);
		if(y < 0)ret ++;
	}
	else if(abs(x)>abs(y)){
		if(x > 0)ret ++;
		ret += abs(x)-abs(y);
		if(y > 0)ret ++;
	}
	else {
		if(x != y)ret = 1;
	}
	cout << ret << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N; cin >> N;
	cout << !N << '\n';
	return 0;
}

Measured memory_bytes: 3620
h,w=map(int,input().split())
s=[input() for i in range(h)]

for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      check=0
      for x,y in [1,0],[-1,0],[0,1],[0,-1]:
        ny=i+y
        nx=j+x
        if 0<=ny<=h-1 and 0<=nx<=w-1:
          if s[ny][nx]=='#':
            check=1
      if check==0:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 3064
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

a = list(input())
a = [int(i) for i in a]
for fl in itertools.product(range(2),repeat=3):
    now = a[0]
    for i,x in enumerate(fl):
        if x:
            now += a[i+1]
        else:
            now -= a[i+1]
    if now == 7:
        L = str(a[0])
        for i,x in enumerate(fl):
            tmp = '+' if x else '-'
            L += tmp + str(a[i+1])
        print(L+'=7')
        quit()
        

Measured memory_bytes: 63980
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            int n = Integer.parseInt(br.readLine());
            String str = br.readLine();
            int max = 0;
            for (int i = 1; i < n; i++) {
                String a = str.substring(0, i);
                String b = str.substring(i, n);
                int count = strCount(a, b);
                if (count > max) {
                    max = count;
                }
            }
            System.out.println(max);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static int strCount(String a, String b) {
        int ret = 0;
        int arr1[] = new int[26];
        int arr2[] = new int[26];
        for (int i = 0; i < a.length(); i++) {
            char ch = a.charAt(i);
            int index = (int)ch - 97;
            arr1[index]++;
        }
        for (int i = 0; i < b.length(); i++) {
            char ch = b.charAt(i);
            int index = (int)ch - 97;
            arr2[index]++;
        }
        for (int i = 0; i < 26; i++) {
            if (arr1[i] > 0 && arr2[i] > 0) {
                ret++;
            }
        }
        return ret;
    }
}


Measured memory_bytes: 23252
"""
ビスケット生産装置を起動すると、起動してから A 秒後、2A 秒後、3A 秒後、... (A の倍数秒後) に B

枚ずつビスケットを生産します。

ビスケット生産装置を起動してから T+0.5
秒後までに生産されるビスケットの合計枚数を求めてください。

return int(T/A) * B

test : A = 3 , B = 2 , T = 6
kotae : 4
"""

s = input().split(" ")
s = [int(s[i]) for i in range(3)]
A = s[0]
B = s[1]
T = s[2]
print(int(T/A) * B)

Measured memory_bytes: 3060
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import math


def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []

    for i in range(limit):
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)
        for j in range(limit):
            if j >= len(A):
                break
            if A[j] % prime == 0:
                A.pop(j)
                continue

    for a in A:
        P.append(a)

    return P


n = int(readline())
prime_list = eratosthenes(55555)
ans = []
cnt = 0
for check in prime_list:
    if check % 5 == 1 and check > 10:
        ans.append(check)
        cnt += 1
        if cnt == n:
            print(*ans)
            exit()


Measured memory_bytes: 5424
n = int(input())
x, y = [list(map(int, input().split())) for _ in range(2)]
print(sum([abs(x[i] - y[i]) for i in range(n)]))
print(pow(sum([(x[i] - y[i]) ** 2 for i in range(n)]), 1/2))
print(pow(sum([abs(x[i] - y[i]) ** 3 for i in range(n)]), 1/3))
print(max([abs(x[i] - y[i]) for i in range(n)]))



Measured memory_bytes: 5648
using System;
using System.Collections.Generic;
using System.Linq;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var N = input[0];
            var M = input[1];
            var Cities = new List<int[]>();            
            for (int i = 0; i < M; i++)
            {
                input = ReadArrayInt();
                var P = input[0];
                var Y = input[1];
                Cities.Add(new int[] { i, P, Y, 0 });
            }
            Cities = Cities.OrderBy(x => x[1]).ThenBy(x => x[2]).ToList();
            var tmp = Cities[0][1];
            var cnt = 1;
            Cities[0][3] = 1;
            for (int i = 1; i < M; i++)
            {
                if (Cities[i][1] == tmp) Cities[i][3] = ++cnt;
                else { tmp = Cities[i][1];cnt = 1;Cities[i][3] = cnt; }
            }

            foreach(var city in Cities.OrderBy(x => x[0]))
            {
                Console.WriteLine(string.Format("{0:000000}", city[1]) + string.Format("{0:000000}", city[3]));
            }            

            Console.WriteLine();
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 32804
#include<stdio.h>

int main() {
	int n,m,i,j;
	scanf("%d %d", &n, &m);
	
	int A[n][m],b[m],c[n];
	for(i = 0; i < n; i++) {
		for(j = 0; j < m; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	for(i = 0; i < m; i++) {
		scanf("%d", &b[i]);
	}
	for(i = 0; i < n; i++) {
		c[i] = 0;
		for(j = 0; j < m; j++) {
			c[i] += A[i][j] * b[j];
		}
		printf("%d\n",c[i]);
	}
	
	
	return 0;
}

Measured memory_bytes: 640
def popcount_parity(x, a):
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    x ^= x >> 32
    x ^= x >> 64
    x ^= x >> 128
    x ^= x >> 256
    x ^= x >> 512
    x ^= x >> 1024
    x ^= x >> 2048
    x ^= x >> 4096
    x ^= x >> 8192
    x ^= x >> 16384
    x ^= x >> 32768
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    x ^= x >> 1048576
    return x & a

N = int(input()) - 1 << 1
s = 1
while N:
    l = N & -N
    s |= s << l
    N ^= l

A = input()
if "2" in A:
    a = ~int(A, 4)
    print(popcount_parity(a & s, 1))
else:
    a = int(A, 4)
    print(popcount_parity(a & (s << 1), 2))

Measured memory_bytes: 6112
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m; cin>>n>>m; 
    vector <vector<int>> ship(n ,vector <int>( ));
    n--;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        a--; b--;
        ship[a].push_back(b);
        ship[b].push_back(a);
    }
    int x = ship[0].size();
    for(int i=0;i<x;i++){
        int a =  ship[0][i];
        for(int j=0;j<ship[a].size();j++){
            if(ship[a][j] == n)  {cout<<"POSSIBLE"<<endl; return 0;}
        }
    }
   
     cout<<"IMPOSSIBLE"<<endl;
}


Measured memory_bytes: 12016