akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
#include <cstring>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

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

    int N, M;
    cin >> N >> M;
    vector<vector<int>> graph(N);
    vector<P> es;
    vector<int> in(N, 0);
    for(int i = 0; i < N - 1 + M; ++i){
        int A, B;
        cin >> A >> B;
        --A, --B;
        graph[A].emplace_back(B);
        es.emplace_back(A, B);
        ++in[B];
    }
    queue<int> que;
    vector<int> ans(N, -1);
    for(int v = 0; v < N; ++v){
        if(!in[v]){
            ans[v] = 0;
            que.emplace(v);
            break;
        }
    }
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int v : graph[u]){
            if(--in[v] == 0){
                ans[v] = u + 1;
                que.emplace(v);
            }
        }
    }
    for(int x : ans)    cout << x << '\n';
}

Measured memory_bytes: 10248
def main():
    K = int(input())
    mod = 7

    if K % 2 == 0:
        print(-1)

    else:
        for i in range(10**7):
            if mod % K == 0:
                print(i+1)
                break
            else:
                mod = (10*mod + 7) % K
        else:
            print(-1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9184
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define mp make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<30)
#define LLINF (1LL<<60)
//#define MOD 998244353
#define MOD 1000000007
#define PI 3.14159265358979
using ll = long long;
using namespace std;

int main(){
    int x[10];
    rep(i,5)cin>>x[i];
    rep(i,5){
        if(x[i]==0){
            cout<<i+1<<endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3580
tbl = [[0 for i in range(13)] for j in range(4)]

n= int(input())
for i in range(n):
	mark, num = input().split()
	num = int(num)-1
	if mark=="S":
		tbl[0][num]=1
	if mark=="H":
		tbl[1][num]=1
	if mark=="C":
		tbl[2][num]=1
	if mark=="D":
		tbl[3][num]=1


for i in range(4):
	for j in range(13):
		if tbl[i][j]==0:
			if i==0:
				print(f'S {j+1}')
			if i==1:
				print(f'H {j+1}')
			if i==2:
				print(f'C {j+1}')
			if i==3:
				print(f'D {j+1}')
				




Measured memory_bytes: 5620
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
before = sum(A)

for i in range(N):
    nokori = B[i]
    for j in range(i,i+2):
        if nokori >= A[j]:
            nokori -= A[j]
            A[j] = 0
        else:
            A[j] -= nokori
            nokori = 0
after = sum(A)

print(before - after)

Measured memory_bytes: 73316
from sys import stdin
N, D = [int(x) for x in stdin.readline().rstrip().split()]
X = [stdin.readline().rstrip().split() for _ in range(N)]
count = 0
for i in range(0, N):
    for j in range(i+1, N):
        distance = 0
        for k in range(0, D):
            distance += abs(int(X[i][k]) - int(X[j][k])) ** 2
        distance = distance ** 0.5
        if(distance.is_integer()):
            count += 1
print(count)

Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

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

int H,W;
char A[1234][1234];

int main() {

	scanf("%d%d", &H,&W);
	rep(i, H) scanf("%s", &A[i]);

	queue<pair<pair<int, int>, int>> q;

	rep(i, H) {
		rep(j, W) {
			if (A[i][j] == '#') q.push({ {i,j},0 });
		}
	}

	int ans = 0;
	int dx[] = { 0,-1,1,0 }, dy[] = { -1,0,0,1 }, dn = 4;
	auto isvalid = [](int i, int j) {
		if (i >= 0 && i < H && j >= 0 && j < W) return true;
		else return false;
	};

	while (!q.empty()) {
		auto c = q.front();
		ans = c.second;
		q.pop();
		rep(t, dn) {
			if (isvalid(c.first.first + dy[t], c.first.second + dx[t]) && A[c.first.first + dy[t]][c.first.second + dx[t]] == '.') {
				A[c.first.first + dy[t]][c.first.second + dx[t]] = '#';
				q.push({ {c.first.first + dy[t],c.first.second + dx[t]},c.second + 1 });
			}
		}
	}


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

	return 0;
}


Measured memory_bytes: 13584
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cctype>
#define rep(x,y,z) for(long long x=y;x<z;++x)
#define dwn(x,y,z) for(long long x=y;x>z;--x)
using namespace std;

typedef long long ll;

int main() {
    ll n;
    cin >> n;
    vector<ll> x(n), y(n), h(n);
    ll num;
    ll h_, a, b;
    rep(i,0,n) {cin >> x[i] >> y[i] >> h[i]; if (h[i] > 0) num = i;}
    for (a = 0; a <= 100; a++) {
        for (b = 0; b <= 100; b++) {
            h_ = h[num] + llabs(a - x[num]) + llabs(b - y[num]);
            bool fg = true;
            for (ll i = 0; i < n; i++) {
                if (max(h_ - llabs(a - x[i]) - llabs(b - y[i]), 0LL) != h[i]) {
                    fg = false;
                    break;
                }
            }
            if (fg) {
                cout << a << " " << b << " " << h_ << endl;
                return 0;
            }
        }
    }
    return 0;
}


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

int64_t mod = 1000000007;
int64_t large = 9223372036854775807;
double PI = 3.141592653589793;

int main()
{
    int N, M, X, tmp;
    cin >> N >> M >> X;
   
    vector<bool> list(N + 1, false);
    for (int i = 0; i < M; i++)
    {
        cin >> tmp;
        list[tmp] = true;
    }
    vector<int> map(N + 1);
    for (int i = 1; i < N + 1; i++)
    {
        map[i] = map[i - 1];
        if(list[i])
            map[i]++;
    }
    cout << min(map[X], map[N] - map[X]);
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int N,x,r,s=0;
    scanf("%d",&N);
    x=N;
    while(x!=0){
        r=x%10;
        s+=r;
        x/=10;
    }
    if(N%s==0)
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}


Measured memory_bytes: 1624
///#pragma GCC optimize("Ofast")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
///#pragma GCC optimize("unroll-loops")

#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;
///template<typename T> using orderset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<bool> vbb;

const ll N = 100001;
const ll MOD = 1000000007;
const ll INF = LLONG_MAX;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rev(a) reverse(all(a))
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define space ' '
#define nl '\n'
#define PI acos(-1)
#define Case(x) cout<<"Case "<<x<<": "
#define strtoint(a) atoi(a.c_str())
#define inttostr(n) to_string(n)

#define coutv(v) for(auto it:v)cout<<it<<space;cout<<nl;
#define cinv(v) for(auto &it:v)cin>>it;


int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int tc=1,cs=0;
    //cin>>tc;
    while(tc--)
    {
        int n,a,b;
        cin>>n>>a>>b;
        for(int i=a;i<=b;i++)
            if(i%n==0)
            return cout<<"OK"<<nl, 0;
        cout<<"NG"<<nl;
    }
}


Measured memory_bytes: 3648
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  long long x; cin >> x;
  vector<long long> height(n+1);
  height[0] = 1;
  FOR(i, 1, n+1) {
    height[i] = height[i-1] * 2;
    height[i] += 3;
  }
  vector<long long> meet(n+1);
  meet[0] = 0;
  FOR(i, 1, n+1) {
    meet[i] = meet[i-1] * 2;
    meet[i] += 1;
  }
  long long ans = 0;
  for (int i = n; i >= 0; --i) {
    if (height[i] == x) {
      ans += meet[i] * 2 + 1;
      break;
    } else if (height[i]/2+1 == x) {
      ans += meet[i] + 1;
      break;
    } else if (height[i]/2+1 < x) {
      ans += meet[i] + 1;
      x -= height[i]/2+1;
    } else {
      --x;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main(){
  int n,t;
  cin >> n >> t;
  vector<pair<int,int>> v(n);
  int mini=1001;
  for (int i=0; i<n;i++){
    int a,b;
    cin >> a >> b;
    pair<int,int> p=make_pair(a,b);
    v[i]=p;
    if ( p.second <= t && p.first < mini) mini = p.first;
  }
  if (mini==1001) cout << "TLE" << endl;
  else cout << mini << endl;
  return 0;
}
  
    


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

using namespace std;

void solve()
{
	vector<double> Vec;
	double height;
	while(cin >> height)
	{
		Vec.push_back(height);
	}
	sort(Vec.begin(), Vec.end());
	cout << Vec[Vec.size() - 1] - Vec[0] << endl;
}

int main()
{
	solve();
	return(0);
}

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

const int MAX_N = 1 << 17;
typedef pair<long long, long long> PLL;
static long long M, N, P[100000], A[100000][3], B[100000][3], INF = 1000000000, ANS = 0;
static PLL DAT[2 * MAX_N - 1];

void init(int N_, int X) {
	N = 1;
	while (N < N_) N *= 2;
	for (int i = 0; i < 2 * N - 1; i++) DAT[i] = { X, X };
}

void update(int K, int A) {
	K += N - 1;
	DAT[K].first = A;
	while (K > 0) {
		K = (K - 1) / 2;
		long long V[4] = {};
		V[0] = DAT[K * 2 + 1].first;
		V[1] = DAT[K * 2 + 1].second;
		V[2] = DAT[K * 2 + 2].first;
		V[3] = DAT[K * 2 + 2].second;
		sort(V, V + 4);
		DAT[K] = { V[3], V[2] };
	}
}

void update2(int K, int A) {
	K += N - 1;
	DAT[K].first = A;
	while (K > 0) {
		K = (K - 1) / 2;
		long long V[4] = {};
		V[0] = DAT[K * 2 + 1].first;
		V[1] = DAT[K * 2 + 1].second;
		V[2] = DAT[K * 2 + 2].first;
		V[3] = DAT[K * 2 + 2].second;
		sort(V, V + 4);
		DAT[K] = { V[0], V[1] };
	}
}

PLL query(int A, int B, int K, int L, int R) {
	if (R <= A || B <= L) return { -1, -1 };
	else if (A <= L && R <= B) return DAT[K];
	else {
		PLL VL = query(A, B, K * 2 + 1, L, (L + R) / 2);
		PLL VR = query(A, B, K * 2 + 2, (L + R) / 2, R);
		long long V[4] = {};
		V[0] = VL.first;
		V[1] = VL.second;
		V[2] = VR.first;
		V[3] = VR.second;
		sort(V, V + 4);
		return { V[3], V[2] };
	}
}

PLL query2(int A, int B, int K, int L, int R) {
	if (R <= A || B <= L) return { M, M };
	else if (A <= L && R <= B) return DAT[K];
	else {
		PLL VL = query2(A, B, K * 2 + 1, L, (L + R) / 2);
		PLL VR = query2(A, B, K * 2 + 2, (L + R) / 2, R);
		long long V[4] = {};
		V[0] = VL.first;
		V[1] = VL.second;
		V[2] = VR.first;
		V[3] = VR.second;
		sort(V, V + 4);
		return { V[0], V[1] };
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> P[i];
	for (int i = 0; i < N; i++) {
		A[i][0] = A[i][1] = -1;
		A[i][2] = i;
		B[i][0] = i;
		B[i][1] = B[i][2] = M;
	}
	M = N;
	init(N, -1);
	for (int i = 0; i < M; i++) {
		PLL p = query(P[i], M, 0, 0, N);
		A[i][0] = p.second;
		A[i][1] = p.first;
		update(P[i] - 1, i);
	}
	init(N, M);
	for (int i = M - 1; i >= 0; i--) {
		PLL p = query2(P[i], M, 0, 0, N);
		B[i][1] = p.first;
		B[i][2] = p.second;
		update2(P[i] - 1, i);
	}
	for (int i = 0; i < M; i++) {
		ANS += (A[i][1] - A[i][0]) * (B[i][1] - B[i][0]) * P[i];
		ANS += (A[i][2] - A[i][1]) * (B[i][2] - B[i][1]) * P[i];
	}
	cout << ANS << endl;
}

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

int main(void){

	while(1){
		int n,pm,pe,pj,pme,pmej,k[10000];
		cin >> n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin >> pm >> pe >> pj;
			pme=(pm+pe)/2;
			pmej=(pm+pe+pj)/3;
			if(pm==100||pe==100||pj==100||pme>=90||pmej>=80)k[i]=1;
			else if(pmej>=70||pmej>=50&&(pm>=80||pe>=80))k[i]=2;
			else k[i]=3;
		}
		for(int i=0;i<n;i++){
			if(k[i]==1)cout << "A" << endl;
			else if(k[i]==2)cout << "B" << endl;
			else cout << "C" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1156
#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define int long long
using namespace std;

signed main(){
	int n,c;
	cin>>n>>c;
	int x[n+1],v[n+1];
	rep(i,n)cin>>x[i+1]>>v[i+1];
	x[0]=v[0]=0;
	int l[n+1],r[n+1],f[n+1],lw[n+1],rw[n+1],fw[n+1];
	rep(i,n+1){
		if(i==0){
			l[i]=f[i]=lw[i]=fw[i]=0;
		}else{
			l[i]=l[i-1]+x[i-1]+v[i]-x[i];
			lw[i]=lw[i-1]+2*x[i-1]+v[i]-x[i]*2;
			f[i]=max(f[i-1],l[i]);
			fw[i]=max(fw[i-1],lw[i]);
		}
	}
	for(int i=n;i>0;i--){
		if(i==n){
			r[i]=v[i]-(c-x[i]);
			rw[i]=v[i]-2*(c-x[i]);
		}else{
			r[i]=r[i+1]+(c-x[i+1])+v[i]-(c-x[i]);
			rw[i]=rw[i+1]+2*(c-x[i+1])+v[i]-2*(c-x[i]);
		}
	}
	r[0]=rw[0]=0;
	int ans=0;
	rep(b,n+1){
		int res=(b-1+n+1)%(n+1);
		ans=max(ans,max(r[b]+fw[res],rw[b]+f[res]));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
#define oo (long long)1e18
#define ll long long
#define setdp memset(dp,-1,sizeof(dp))
const ll mod = 1e9+7;
void _IOS(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);}
#define PI 3.14159265359
int sx,sy,tx,ty;
struct threeElements{
int _1st,_2nd,_3rd;
};
int n,m;
int sp,sp1,ep,ep1;
ll dp[1009][1009];
char a[1009][1009];
bool valid(int i,int j)
{
    return i>=0&&i<n&&j>=0&&j<m&&a[i][j]=='.';
}
bool vis[1009][1009];
ll solve(int i,int j)
{
    if(!valid(i,j)) return oo;
    if(i==ep-1&&j==ep1-1)
        return 0;
    if(vis[i][j])
        return 0;
    vis[i][j]=1;
    if(dp[i][j]!=-1) return dp[i][j];
    ll c1=0,c2=0,c3=0,c4=0,c5=oo;
    ll ans=oo;
    c1=solve(i+1,j);
    c2=solve(i-1,j);
    c3=solve(i,j+1);
    c4=solve(i,j-1);
    ans=min({c1,c2,c3,c4});
    for(int k=-2;k<=2;k++)
    {
        for(int w=-2;w<=2;w++)
        {
            if(valid(i+k,j+w))
            {
                ans=min(ans,1+solve(i+k,j+w));
            }
        }
    }
    vis[i][j]=0;
    return dp[i][j]=ans;
}
int main()
{
   // freopen ("jumping.in","r",stdin);
   _IOS();
    cin>>n;
    int a[1000];
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    cout<<a[n-1]-a[0];
}


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

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 123;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 9;

inline void boost () {
	ios_base::sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
}
char a[1002], a1, a2, b1, b2;

int main () {
	boost ();
	cin >> a + 1;
	int n = strlen (a + 1);
	for (int i = 1;i <= n;i ++) {
		if (a[i] == 'N') a1 = 1;
		if (a[i] == 'S') a2 = 1;
		if (a[i] == 'E') b1 = 1;
		if (a[i] == 'W') b2 = 1;
	}
	if (a1 == a2 && b1 == b2) 
		cout << "Yes";
	else 
		cout << "No";
	return 0;
}

        

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

int main(){
	string s;

	cin>>s;

	int y=(s[5]-'0')*10+s[6]-'0';

	if(y<=4)
  {
		cout<<"Heisei"<<endl;
	}
  else
  {
		cout<<"TBD"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
'use strict'

function Main(input) {
  const N = Number(input.split("\n")[0])
  const vList = input.split("\n")[1].split(" ").map(x => Number(x)).sort((a, b) => a - b)

  let ans = 0
  for(let i=1; i<N; i++) {
    if(ans === 0) {
      ans = (vList[i-1] + vList[i]) / 2
    } else {
      ans = (ans + vList[i]) / 2
    }
  }

  console.log(ans)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim())


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


int main() {
  int N,A,B;
  cin >> N >> A >> B;
  
  int ans = 0;
  if((A * N) < B){
    ans = A * N;
  }else{
    ans = B;
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from itertools import groupby

s = input()
k = int(input())
a = [sum(1 for _ in g) for _, g in groupby(s)]
if len(a) == 1:
    print(len(s) * k // 2)
else:
    r = sum(x // 2 for x in a) * k
    if s[0] == s[-1]:
        r += (a[0] & a[-1] & 1) * (k - 1)
    print(r)


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


using namespace std;
int a[200006];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin >> n;
    for(int i=0;i<n;i++)cin >> a[i];
    int mx=a[n-1];
    for(int i=n-2;i>=0;i--)
    {
        if(a[i]>mx)
        {
            if(a[i]-mx>1)return cout << "No",0;

        }
        else mx=a[i];

    }
    cout << "Yes";

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define db(x) cout<<#x<<"="<<x<<endl
#define deb(x) each(x.begin(),x.end(),(int& y){cout << y <<" ";})
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define j1 j1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

void Main(){

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

  char ban[H+2][W+2];
  int dp[H+2][W+2][2]={}; // tate,yoko

  rep(i,H+2){
    rep(j,W+2){
      if(i==0 or j==0 or i==H+1 or j==W+1){
        ban[i][j]='#';
        continue;
      }
      cin>>ban[i][j];
    }
  }

  int ans=0;

  reps(i,1,H+2){
    reps(j,1,W+2){
      if(ban[i][j]=='#'){
        continue;
      }
      int k;
      if(ban[i-1][j]=='#'){
        k=0;
        while(ban[i+(k++)][j]!='#'){
          ++dp[i][j][0];
        }
      }
      else{
        dp[i][j][0]=dp[i-1][j][0];
      }

      if(ban[i][j-1]=='#'){
        k=0;
        while(ban[i][j+(k++)]!='#'){
          ++dp[i][j][1];
        }
      }
      else{
        dp[i][j][1]=dp[i][j-1][1];
      }

      maxi(ans,dp[i][j][0]+dp[i][j][1]-1);
    }
  }

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

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


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

vector<vector<int>> a(4, vector<int>(2));

void set_ans(double val, int lr)
{
    if (val >= 1.1)
        a.at(0).at(lr)++;
    else if (val >= 0.6)
        a.at(1).at(lr)++; 
    else if (val >= 0.2)
        a.at(2).at(lr)++;
    else
        a.at(3).at(lr)++;
}
int main() {
    double l, r;
    
    while (cin >> l >> r) {
        set_ans(l, 0);
        set_ans(r, 1);
    }

    rep(i, 4) {
        cout << a.at(i).at(0) << " " << a.at(i).at(1) << endl;
    }
}


Measured memory_bytes: 3228
#include<stdio.h>
int main(){
	int i=0,l,n,m,a[12],b;
	while(1){
		b=0;
		scanf("%d",&l);
		if(l==0){
			break;
		}
		for(i=0;i<12;i++){
			scanf("%d%d",&m,&n);
			a[i]=m-n;
		}
		for(i=0;i<12;i++){
			b=b+a[i];
			if(b>=l){
				printf("%d\n",i+1);
				break;
			}
		}
		if(b<l){
			printf("NA\n");
		}
	}
}

Measured memory_bytes: 612
#include <stdio.h>

int main()
{
    int N,K,a,b = 1;
    scanf("%d %d",&N,&K);
    a = N % K;
    if(a == 0)
    {
        printf("%d",a);
    }
    else
    {
        printf("%d",b);
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define erep(i,a,b) for(int i=a;i<=(int)(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>(a);i--)
#define eper(i,a,b) for(int i=((int)(a));i>=b;i--)
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
const int INF=(1<<30)-1;
const int MOD=1000000007;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

const int N_MAX = 100005;
int n, x;
ll a[N_MAX], b[N_MAX], ans;  
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> n >> x;
    rep(i, 0, n) cin >> a[i];
    if (x < a[0]) {
        ans = a[0] - x;
        a[0] = x;
    }
    rep(i, 0, n-1) {
        if (x < a[i] + a[i+1]) {
            ll p = a[i] + a[i+1] - x;
            ans += p;
            a[i+1] -= p;
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
	int a , b;
	cin >> a >> b;
	if(a <= 0 && b >= 0)
		cout << "Zero" << endl;
	else if(a > 0)
		cout << "Positive" << endl;
	else
		cout << (((b - a) & 1) ? "Positive" : "Negative") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 300010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////


int N;
ll D[MAX_N], RD[MAX_N];
ll A[MAX_N];

void pre(ll A[MAX_N], ll D[MAX_N]) {
	vector<pi> stack;
	stack.pb(pi(N - 1, inf));
	D[N - 1] = 0;

	rer(i, N - 1, 0) {
		D[i] = D[i + 1];
		if(A[i] <= A[i + 1]) {
			int cnt = 0;
			while(A[i + 1] >= A[i] * (1ll << (2 * cnt + 2))) cnt++;
			// debug(i, cnt);
			if(cnt) stack.pb(pi(i, cnt));
		}
		else {
			int cnt = 0;
			while(A[i + 1] * (1ll << (2 * cnt)) < A[i]) cnt++;
			while(true) {
				pi p = stack.back(); stack.pop_back();
				if(p.sec < cnt) {
					D[i] += 1ll * (p.fst - i) * p.sec * 2;
					cnt -= p.sec;
				}
				else {
					D[i] += 1ll * (p.fst - i) * cnt * 2;
					if(p.sec - cnt > 0) stack.pb(pi(p.fst, p.sec - cnt));
					break;
				}
			}
		}
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	pre(A, D);
	reverse(A, A + N);
	pre(A, RD);
	reverse(RD, RD + N);
	// debug(vl(D, D + N));
	// debug(vl(RD, RD + N));
	ll res = linf;

	MIN(res, D[0]);
	MIN(res, RD[N - 1] + N);

	rep(i, 0, N - 1) {
		MIN(res, RD[i] + D[i + 1] + i + 1);
		// debug(RD[i] + D[i + 1] + i + 1);
	}
	cout << res << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 6016
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<(int)N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define p(s) cout<<(s)<<endl
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf=1e9+7;

int N,M;
vector<int> edge[51];
int a[51],b[51];
int hashi;
int main() {
	cin>>N>>M;
	REP(i,0,M){
		cin>>a[i]>>b[i];
		a[i]--,b[i]--;
		edge[a[i]].push_back(b[i]);
		edge[b[i]].push_back(a[i]);
	}
	int start=a[0];
	REP(i,0,N){
		if(edge[i].size()<2){
			start=i;
			break;
		}
	}

	REP(i,0,M){
		bool used[51];
		REP(j,0,N) used[j]=false;
		queue<int> q;
	    q.push(start);
	    while(!q.empty()){
	    	int now=q.front();
	    	q.pop();
	    	used[now]=true;
	    	for(auto next:edge[now]){
	    		if((next==b[i]&&now==a[i])||(next==a[i]&&now==b[i])) continue;
	    		if(!used[next]) q.push(next);
	    	}
	    }
	    bool ok=true;
	    REP(j,0,N){
	    	if(!used[j]) ok=false;
	    }
	    if(!ok) {
	    	hashi++;
	    }
	}
	p(hashi);
	return 0;
}


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

using namespace std;

#define N 105

int n, m, d[N][N], f[N][N];

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%d", &d[i][j]);
	for(int i = 0; i <= 100; i++)
		for(int j = 0; j <= 100; j++)
			for(int x = 1; x <= n; x++)
				for(int y = 1; y <= m; y++)
					f[i][j] = max(f[i][j], d[x][y] - i * x - j * y);
	for(int x = 1; x <= n; x++)
		for(int y = 1; y <= m; y++)
		{
			int res = INT_MAX;
			for(int i = 0; i <= 100; i++)
				for(int j = 0; j <= 100; j++)
					res = min(res, f[i][j] + i * x + y * j);
			// cout << x << ' ' << y << ' ' << res << endl;
			if(d[x][y] != res) 
			{
				printf("Impossible\n");
				return 0;
			}
		}
	printf("Possible\n");
	printf("202 %d\n", 101 * 101 + 200);
	for(int i = 1; i <= 100; i++) printf("%d %d X\n", i, i + 1);
	for(int i = 102; i < 202; i++) printf("%d %d Y\n", i, i + 1);
	for(int i = 0; i <= 100; i++)
		for(int j = 0; j <= 100; j++)
			printf("%d %d %d\n", i + 1, 202 - j, f[i][j]);
	printf("1 202\n");
	return 0;
}

Measured memory_bytes: 384
n = int(input())
v_list = list(map(int, input().split()))
v_list.sort()

mix_parts = (v_list.pop(0) + v_list.pop(0)) / 2

while True:
    try:
        mix_parts = (mix_parts + v_list.pop(0)) / 2
    except IndexError:
        break

print(mix_parts)


Measured memory_bytes: 2940
// Problem : B - Distance 
// Contest : AtCoder - AtCoder Beginner Contest 174
// URL : https://atcoder.jp/contests/abc174/tasks/abc174_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define fr(i,a,b) for(int i=a;i<b;i++)
#define frr(i,a,b) for(int i=a;i>=b;i--)
//vector
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pp pop_back
//pair
#define pi pair<int ,int >
#define mk make_pair
#define ff first
#define ss second
//set
#define si set<int>
#define sit set<int>::iterator 
using namespace std;
int main()
{
fast;
int tc;cin>>tc;
ll x;cin>>x;
ll cnt=0;
while(tc--)
{
	ll a,b;cin>>a>>b;
	
	ll ans=(a*a);
	ans+=(b*b);
	ll cmp=x*x;
	if(ans<=cmp) cnt++;
}
cout<<cnt;
return 0;
}

Measured memory_bytes: 3692
import itertools

N, M = list(map(int, input().split()))
K, S = [], []
for _ in range(M):
    temp = list(map(int, input().split()))
    K.append(temp[0])
    S.append(temp[1:])

P = list(map(int, input().split()))

ans = 0
for x in itertools.product(("on", "off"), repeat=N):
    flag = True
    for s, p in zip(S, P):
        count = 0
        for i in s:
            if x[i-1] == "on":
                count += 1
        if count % 2 != p:
            flag = False
    if flag:
        ans += 1
print(ans)


Measured memory_bytes: 41712
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<utility>
using namespace std;
#define MS(m,z) memset(m,z,sizeof(m))
typedef unsigned U; typedef pair<int,int > P; typedef long long ll;
void inp();
int main(){
#ifdef XS
	freopen("at80c.in","r",stdin);
#endif
	inp();
	return 0;
}
const int N = 2e5+100;
struct Tt{ int v,id; };
bool operator < (Tt a,Tt b){return a.v<b.v;}
typedef pair<Tt,P> PP;
priority_queue<PP,vector<PP> ,greater<PP>> pq;
Tt To[N*4],Te[N*4];
int A[N];
#define lson (rt<<1)
#define rson ((rt<<1)+1)
#define mid int m = (L+R)>>1;
#define pl lson,L,m
#define pr rson,m+1,R
const int inf = 0x7fffffff;
void bui(Tt *T,int t,int rt,int L,int R){
	if(L==R){ T[rt].id=L,T[rt].v=(L&1)==t?A[L]:inf; return; }
	mid;
	bui(T,t,pl);
	bui(T,t,pr);
#define pushup T[rt]=min(T[lson],T[rson])
	pushup;
}
void rem(Tt *T,int l,int rt,int L,int R){
	if(L==R){
		T[rt].v=inf;
		return;
	}
	mid;
	if(l<=m){ rem(T,l,pl); }
	else if(l>m){ rem(T,l,pr); }
	pushup;
}
#define que(T,l,r,rt,L,R) __que(((l)&1)?To:Te,(l),r,rt,L,R)
Tt __que(Tt *T,int l,int r,int rt,int L,int R){
	if(l<=L&&R<=r)return T[rt];
	if(r<L||R<l){Tt ans;ans.id=-1,ans.v=inf;return ans;}
	mid;
	return min(__que(T,l,r,pl),__que(T,l,r,pr));
}
void inp(){
	int n;scanf("%d",&n);
	for(int i =1;i<=n;i++)scanf("%d",&A[i]);
	bui(To,1,1,1,n);bui(Te,0,1,1,n);
	PP pp(que(To,1,n,1,1,n),P(1,n));
	pq.push(pp);
	PP nx;
	while(!pq.empty()){
		pp = pq.top();pq.pop();
		Tt tt= que(Te,pp.first.id+1,pp.second.second,1,1,n);
		rem(To,pp.first.id,1,1,n);
		rem(Te,tt.id,1,1,n);
		printf("%d %d ",pp.first.v,tt.v );
		if(pp.first.id!=pp.second.first){
			nx.second.first=pp.second.first;
			nx.second.second=pp.first.id-1;
			nx.first=que(To,nx.second.first,nx.second.second,1,1,n);
			pq.push(nx);
		}
		if(pp.first.id!=tt.id-1){
			nx.second.first=pp.first.id+1;
			nx.second.second=tt.id-1;
			nx.first=que(To,nx.second.first,nx.second.second,1,1,n);
			pq.push(nx);
		}
		if(tt.id!=pp.second.second){
			nx.second.first=tt.id+1;
			nx.second.second=pp.second.second;
			nx.first=que(To,nx.second.first,nx.second.second,1,1,n);
			pq.push(nx);
		}
	}
}
//at80c.cc by xsthunder at Wed Aug  9 22:03:34 2017


Measured memory_bytes: 14580
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
int a[1000005]={0};
struct node{
    ll x,y;
    bool operator<(const node&t)const{
        return 1ll*x*t.y<1ll*t.x*y;
    }
};
int main()
{
    int n,k;
    long long num;
    scanf("%d%d",&n,&k);
    priority_queue<node>q;
    for(int i=0;i<n;i++){
        scanf("%lld",&num);
        q.push({num,1});
    }
    int x,y;
    while(k--){
        if(1.0*q.top().x/q.top().y<0.5)
            break;
        x=q.top().x;
        y=q.top().y;
        q.pop();
        q.push({x,y*2});
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        //cout << q.top().x << " " << q.top().y << endl;
        //cout << (1.0*   q.top().x/q.top().y)<<endl;
        ans+=((1.0*q.top().x/q.top().y));
        q.pop();
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 2420
#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b){
    
    int tmp;

    if(a < b){
        tmp = a;
        a = b;
        b = tmp;
    }

    if(a%b == 0){
        return b;
    }else{
        return gcd(b,a%b);
    }

}


int main(){

    int N;
    long int sum = 0;
    int i, j, k, tmp;

    scanf("%d",&N);

    for(i = 1; i <= N; i++){
        for(j = 1; j <= N; j++){
            for(k = 1; k <= N; k++){

                tmp = gcd(i,j);
                sum += gcd(tmp,k);
            }
        }
    }

    printf("%ld\n",sum);

    return 0;
}

Measured memory_bytes: 1732
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2020;
int n,tot; char s[N];
int v[N],f[N],deps[N],siz[N];
struct Edge{int to,next;}e[N<<1];
void add(int x,int y){
	e[++tot].to=y; e[tot].next=v[x]; v[x]=tot;
}
void dfs(int x,int ff){
	siz[x]=s[x]-'0';
	int mx=-1,y=0; f[x]=deps[x]=0;
	for(int p=v[x];p;p=e[p].next){
		int kp=e[p].to;
		if(kp!=ff){
			dfs(kp,x);
			siz[x]+=siz[kp]; deps[x]+=deps[kp]+siz[kp];
			if(mx<deps[kp]+siz[kp])mx=deps[kp]+siz[kp],y=kp;
		}
	}
	int res=deps[x]-mx;
	if(mx<=res)f[x]=deps[x]/2; 
	else f[x]=res+min(mx-res,f[y]*2)/2;
}
int read(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();
	scanf("%s",s+1);
	for(int a,b,i=1;i<n;i++)
		a=read(),b=read(),add(a,b),add(b,a);
	int ans=1e9;
	for(int i=1;i<=n;i++){
		dfs(i,0);
		if(f[i]*2==deps[i])
			ans=min(ans,f[i]);
	}
	if(ans==1e9)puts("-1");
	else printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
const int C=210001;

ll a[C], F[C], pp[C], dp[C];

ll count(int aa, int b){
	return (a[b]*a[b]+dp[b]-a[aa]*a[aa]-dp[aa])/(2*(a[b]-a[aa]))+1;
}

int main(){
	int n, i, j=0, iF=0, jF=0;
	ll c, aw;
	scanf ("%d %lld", &n, &c);
	scanf ("%lld", &a[0]);
	F[0]=0, pp[0]=-100000, jF=1;
	
	for (i=1;i<n;i++){
		scanf ("%lld", &a[i]);
		for (;iF<jF-1;iF++){
			if (pp[iF]>=a[i])	break;
		}
		if (pp[iF]>a[i])	iF--;
		
		dp[i]=(a[i]-a[F[iF]])*(a[i]-a[F[iF]])+dp[F[iF]]+c;
		
		while (1){
			aw=count(F[jF-1], i);
			if (aw<=pp[jF-1])	jF--;
			else break;
			if (jF==iF)	break;
		}
		F[jF]=i;
		if (jF==iF)	pp[jF]=-100000;
		else pp[jF]=aw;
		jF++;
	}
	printf ("%lld", dp[n-1]);
	
return 0;}

Measured memory_bytes: 6528
import java.text.*;import java.util.*;class Main{public static void main(String[]z){for(Scanner s=new Scanner(System.in);s.hasNext();)System.out.println(new ChoiceFormat("0#light fly|48<fly|51<bantam|54<feather|57<light|60<light welter|64<welter|69<light middle|75<middle|81<light heavy|91<heavy").format(s.nextFloat()));}}

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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

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

    int a, b; cin >> a >> b;
    for (int i = 1; i < 5000; i++) {
        int x = (int)(1.0 * i * 0.08);
        int y = (int)(1.0 * i * 0.1);
        if (x == a && y == b) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,m=MI()
    print((n-1)*(m-1))
main()

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <bitset>
#include <queue>
#include <unordered_set>

using namespace std;
typedef long long ll;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
#define rep(i, n) for(int i = 0;i < n;i++)
const int INF = 1LL << 30;

int MOD = 1000000007;

int main(){
    std::ios_base::sync_with_stdio(false);

    int n,m; cin >> n >> m;
    std::vector<ll> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(), a.end());

    std::vector<pair<ll, int>> v;

    rep(i,m){
        int b; ll c; cin >> b >> c;
        v.push_back(make_pair(c,b));
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    ll ans = 0LL;
    int current = 0;
    rep(i,n){
        if(a[i] < v[current].first){
            ans+=v[current].first;
            v[current].second--;
            if(v[current].second == 0) current++;
        } else{
            ans+=a[i];
        }
    }

    cout << ans  << endl;



    return 0;
}

Measured memory_bytes: 3188
/*
                                Bismillahi-r-Rahmani-r-Rahim
                                        RhIeyAaD
                                    IIT-7th Batch,JU
*/
#include<bits/stdc++.h>
using namespace std;

#define debug(args...){ string _s = #args;replace(_s.begin(),_s.end(),',', ' ');stringstream _ss(_s);istream_iterator<string>_it(_ss);err(_it, args);}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << "=" << a << ", "; err(++it, args...);}

#define ll              long long int
#define MAX             2134567891
#define fr(i,n)         for(i=0;i<n;i++)
#define rep(i,n)        for(i=1;i<=n;i++)
#define rev(i,a,n)      for(i=n;i>=a;i--)
#define FOR(i,a,n)      for(i=a;i<=n;i++)
#define ALL(n)          n.begin(),n.end()
#define mem(x,n)        memset(x,n,sizeof(x))
#define TC(t)           printf("Case %lld: ",t)
#define ans(t,c)        printf("Case %lld: %lld\n",t,c)
#define SETP(n)         cout<<setprecision(n)<<fixed
#define READ            freopen("F:\\Project\\Test_Case.txt","r",stdin)
#define WRITE           freopen("F:\\Project\\Output_Test.txt","w",stdout)
#define IO              ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define PAIR            pair<ll,ll>
#define MP              make_pair
#define pb              push_back
#define eb              emplace_back
#define ff              first
#define ss              second
#define NL              printf("\n");
#define bug(a)          cout<<#a<<" "<<a<<" ";
#define hlw             printf("hlw\n");
#define NN              111
#define MOD             1000000007///10^9
#define N               107 ///10^6->6 zero after 1 **



ll x[N],y[N],vis[N][N],n;
string s,S;
vector<ll>v[111];
vector<PAIR>ANS;
bitset<N>B;
//map <ll,ll> mp;

int main()
{
    //IO;
    //while(1)
    //READ;WRITE;
{
    ll a=0,b=0,c=0,d,e,f,g,i,j,k,l,m,p,q,r,u,w,t,tc=1,in,loc,val,sz,lo,hi,mid,mn=MAX,mx=0,sum=0,ans=0;
//cin>>tc;
rep(t,tc)
{
    cin>>n;
    if(n==3)
    {
        cout<<2<<endl<<1<<" "<<3<<endl<<2<<" "<<3<<endl;
    }
    else if(n==4)
    {
        cout<<4<<endl;
        cout<<"1 2\n";
        cout<<"1 3\n";
        cout<<"2 4\n";
        cout<<"3 4\n";
    }
    else
    {
        m=(n*(n-1))/2;
        rep(i,n)
        {
            for(j=n;j>=1;j--)
            {
                if(i==j)continue;
                v[i].pb(j);
            }
        }

        rep(i,n)
        {
            if(n%2==1)k=n-i;
            else k=n-i+1;

            vis[i][k]=vis[k][i]=1;

        }


        rep(i,n)
        fr(j,v[i].size())
        {
            p=v[i][j];
            if(!vis[i][p])
            {
                ANS.eb(i,p);
                vis[i][p]=vis[p][i]=1;
            }
        }

        cout<<ANS.size()<<endl;
        fr(i,ANS.size())cout<<ANS[i].ff<<" "<<ANS[i].ss<<endl;
    }
}
}
    return 0;
}

/*


*/
/// Check for constraint 0 or 1?
/// Division MOD needs BigMod(a,n-2)
/// long long or double? sqrt or division will work fine??
/// sort(begin(v), end(v), [] (int a, int b) { return a > b; });    /// Lambda Function for manual Sort


Measured memory_bytes: 640
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	while(true){
    		int x=sc.nextInt();
    		int y=sc.nextInt();
    		if(x+y==0)
    		break;
    		if(x<y){
    			System.out.println(x+" "+y);
    		}else{
    			System.out.println(y+" "+x);
    		}
    		}
    }
    }
    


Measured memory_bytes: 36236
#include <stdio.h>

int main(void)
{
	int x = 1, y = 1, i, n;

	for (i = 0; (x != 0) || (y != 0); i++)
	{
		scanf("%d %d", &x, &y);

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

		if ((x != 0) || (y != 0))
		{
			printf("%d %d\n", x, y);
		}
	}
	return 0;
}


Measured memory_bytes: 1916
# def gcd(x, y):
#     if y == 0:
#         return x
#     else:
#         return gcd(y,x%y)
#
#
# def lcm(c, d):
#     return c * d // gcd(max(c, d), min(c, d))


N = int(input())
a = list(map(int,input().split()))
# A = a[0]
# for i in range(1,N-1):
#     A = lcm(A, a[i])
print(sum(a)-len(a))

Measured memory_bytes: 3316
# coding: utf-8
# Your code here!
import copy
N,K=map(int,input().split())
R,S,P=map(int,input().split())
point=score={'r':R,'s':S,'p':P}
T=input()
l=[[]for i in range(K)]
for i in range(N):
  l[i%K].append(T[i])
def get_point(s1,s2):
    num={'r':0,'s':1,'p':2}
    if num[s1]==(num[s2]+1)%3:
        return point[s2]
    else:return 0
def rest(hand):
    if hand=='r':return['s','p']
    elif hand=='s':return['r','p']
    elif hand=='p':return['r','s']
def cal(mini_l):
    size=len(mini_l)
    kind=['r','s','p']
    score={'r':[],'s':[],'p':[]}
    for hand in kind:
        score[hand].append(get_point(mini_l[0],hand))
    for i in range(1,size):
        for hand in kind:
            choice=''
            tmp_score=-1
            for pre_hand in rest(hand):
                if score[pre_hand][i-1]+get_point(mini_l[i],hand)>tmp_score:
                    choice=pre_hand
                    tmp_score=score[pre_hand][i-1]+get_point(mini_l[i],hand)
            score[hand].append(tmp_score)
    tmp_score=-1
    for hand in kind:
        if score[hand][-1]>tmp_score:
            ans=hand
            tmp_score=score[hand][-1]
    return tmp_score
ans=0
for ll in l:
    ans+=cal(ll)
print(ans)        

Measured memory_bytes: 66780
#include <iostream>
#include <math.h>
#include <string>
#define MEN 6
#include <iomanip>
using namespace std;


struct DICE
{
	int num;
};

int main()
{
	DICE A[MEN];
	int out[24];
	int q, x, y;
	int i = 0;

	for (int i = 0; i < MEN; i++)
	{
		cin >> A[i].num;
	}

	cin >> q;

	for (int i = 0; i < q;i++)
	{
		cin >> x >> y;

		if (x == A[0].num)
		{
			if (y == A[1].num)
			{
				out[i] = A[2].num;
			}
			else if (y == A[2].num)
			{
				out[i] = A[4].num;
			}
			else if (y == A[4].num)
			{
				out[i] = A[3].num;
			}
			else if (y == A[3].num)
			{
				out[i] = A[1].num;
			}
		}
		else if (x == A[1].num)
		{
			if (y == A[0].num)
			{
				out[i] = A[3].num;
			}
			else if (y == A[3].num)
			{
				out[i] = A[5].num;
			}
			else if (y == A[5].num)
			{
				out[i] = A[2].num;
			}
			else if (y == A[2].num)
			{
				out[i] = A[0].num;
			}
		}
		else if (x == A[2].num)
		{
			if (y == A[0].num)
			{
				out[i] = A[1].num;
			}
			else if (y == A[1].num)
			{
				out[i] = A[5].num;
			}
			else if (y == A[5].num)
			{
				out[i] = A[4].num;
			}
			else if (y == A[4].num)
			{
				out[i] = A[0].num;
			}
		}
		else if (x == A[3].num)
		{
			if (y == A[0].num)
			{
				out[i] = A[4].num;
			}
			else if (y == A[4].num)
			{
				out[i] = A[5].num;
			}
			else if (y == A[5].num)
			{
				out[i] = A[1].num;
			}
			else if (y == A[1].num)
			{
				out[i] = A[0].num;
			}
		}
		else if (x == A[4].num)
		{
			if (y == A[0].num)
			{
				out[i] = A[2].num;
			}
			else if (y == A[2].num)
			{
				out[i] = A[5].num;
			}
			else if (y == A[5].num)
			{
				out[i] = A[3].num;
			}
			else if (y == A[3].num)
			{
				out[i] = A[0].num;
			}
		}
		else if (x == A[5].num)
		{
			if (y == A[1].num)
			{
				out[i] = A[3].num;
			}
			else if (y == A[3].num)
			{
				out[i] = A[4].num;
			}
			else if (y == A[4].num)
			{
				out[i] = A[2].num;
			}
			else if (y == A[2].num)
			{
				out[i] = A[1].num;
			}
		}
	}

	for (int i = 0; i < q; i++)
	{
		cout << out[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3040
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

#define STARTUP {(cin.tie(0));\
 (ios::sync_with_stdio(false));}

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define VECCIN(vec) const int size = (vec).size(); REP(i,size) cin>>(vec)[i];

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

using ll = long long;
using namespace std;
ll mod = 1'000'000'007;

const int INF = 1'050'000'000;

int main() {
    STARTUP;

    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c - max({ a,b,c }) << endl;
    return 0;
}

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

int main()
{
    int counter[26] = {};
    char ch;
    while (scanf("%c", &ch) != EOF)
    {
        if (ch >= 'a' && ch <= 'z')
            counter[ch - 'a']++;
        else if (ch >= 'A' && ch <= 'Z')
            counter[ch - 'A']++;
    }
    for (int i = 0; i < 26; i++)
        printf("%c : %d\n", 'a' + i, counter[i]);
}


Measured memory_bytes: 3228
Sa = list(input())
Sb = list(input())
Sc = list(input())
S = len(Sa) + len(Sb) + len(Sc) + 10

flag = 'a'


for i in range(S):
    if flag == 'a':
        if len(Sa) == 0:
            break
        flag = Sa[0]
        Sa.pop(0)

    elif flag == 'b':
        if len(Sb) == 0:
            break
        flag = Sb[0]
        Sb.pop(0)

    elif flag == 'c':
        if len(Sc) == 0:
            break
        flag = Sc[0]
        Sc.pop(0)

if flag == 'a':
    print('A')
elif flag == 'b':
    print('B')
else:
    print('C')


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
long long int n, k, r, s, p;
string t;
long long int ans = 0;
long long int max0, max1, max2;
long long int dp[3][100000];
int main(){
	cin >> n >> k >> r >> s >> p;
	cin >> t;
	for(long long int i = 0;i < k;i++){
		if(t[i] == 'r'){
			dp[2][i] = p;
			dp[1][i] = 0;
			dp[0][i] = 0;
		}else if(t[i] == 's'){
			dp[0][i] = r;
			dp[2][i] = 0;
			dp[1][i] = 0;
		}else{
			dp[1][i] = s;
			dp[2][i] = 0;
			dp[0][i] = 0;
        }
			max0 = dp[0][i];
			max1 = dp[1][i];
			max2 = dp[2][i];
		for(long long int j = 1;(j * k + i) < n;j++){
			if(t[j * k + i] == 'r'){
				dp[2][j * k + i] = max(dp[1][(j - 1) * k + i], dp[0][(j - 1) * k + i]) + p;
				dp[1][j * k + i] = max(dp[0][j * k + i - k], dp[2][j * k + i - k]);
				dp[0][j * k + i] = max(dp[1][j * k + i - k], dp[2][j * k + i - k]);
			}else if(t[j * k + i] == 's'){
				dp[0][j * k + i] = max(dp[1][(j - 1) * k + i], dp[2][(j - 1) * k + i]) + r;
				dp[1][j * k + i] = max(dp[0][j * k + i - k], dp[2][j * k + i - k]);
				dp[2][j * k + i] = max(dp[0][j * k + i - k], dp[1][j * k + i - k]);
			}else if(t[j * k + i] == 'p'){
				dp[1][j * k + i] = max(dp[0][(j - 1) * k + i], dp[2][(j - 1) * k + i]) + s;
				dp[0][j * k + i] = max(dp[1][j * k + i - k], dp[2][j * k + i - k]);
				dp[2][j * k + i] = max(dp[0][j * k + i - k], dp[1][j * k + i - k]);
			}
			max0 = dp[0][j * k + i];
			max1 = dp[1][j * k + i];
			max2 = dp[2][j * k + i];
		}
		ans += max(max(max0, max1), max2);
	}
	cout << ans << endl;
}


Measured memory_bytes: 2816