akhauriyash/Code-Regression huggingface dataset:
m = int(input())
while m:
    m -= 1
    ax, ay, bx, by = map(int, input().split())
    n = int(input())
    dx, dy = bx - ax, by - ay
    intersections = set()
    while n:
        n -= 1
        sx, sy, tx, ty, o, l = map(int, input().split())
        tdx, tdy = tx - sx, ty - sy
        asx, asy = sx - ax, sy - ay
        denom = dx * tdy - dy * tdx
        if not denom:
            continue
        r = (tdy * asx - tdx * asy) / denom
        s = (dy * asx - dx * asy) / denom
        if not 0 < r < 1 or not 0 < s < 1:
            continue
        px = ax + r * dx
        intersections.add((px, o == l))

    if not intersections:
        print(0)
        continue

    pl, counter = -1, -1
    for px, l in sorted(intersections):
        if pl != l:
            counter += 1
            pl = l
    print(counter)

Measured memory_bytes: 7560
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <set>
#include <map>

using namespace std;

int main(int argc, char const *argv[])
{
    int n, alice, bob;
    vector<int> a;

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    sort(a.begin(), a.end());

    while(true)
    {
        alice += a.back();
        a.pop_back();
        if(a.size()==0) break;

        bob += a.back();
        a.pop_back();
        if(a.size()==0) break;
    }

    cout << alice-bob << "\n";

    return 0;
}

Measured memory_bytes: 256
s = input()

i = 0
answer = 0
before = ""
current = ""
while i < len(s):
    current = s[i]
    while before == current:
        i += 1
        if i == len(s):
            break
        current += s[i]
    if i == len(s):
        break
    before = current
    answer += 1
    i += 1
print(answer)


Measured memory_bytes: 3500
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
using namespace std;

int main(void)
{
    int N, M;
    cin >> N >> M;
    if(N == M){
        cout << "Yes";
    }else
    {
        cout << "No";
    }
    return 0;
}

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

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

int main() {
    int N; long long X;
    cin >> N >> X;
    vector<long long> x(N); for (int i = 0; i < N; ++i) cin >> x[i], x[i] -= X;
    long long g = abs(x[0]);
    for (int i = 0; i < N; ++i) g = GCD(g, abs(x[i]));
    cout << g << endl;
}

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

int64_t count[0x100];
constexpr int64_t k1e9p7 = 1e9 + 7;

int main(int argc, char *argv[]) {
  int64_t N;
  std::string S;
  std::cin >> N >> S;
  for(int c : S) count[c]++;
  int64_t ans = 1;
  for(int i = 'a'; i <= 'z'; i++){
    if(!count[i]) continue;
    ans = ans * (count[i] + 1) % k1e9p7;
  }
  ans -= 1;
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 512
'''
X:スタート地点
0, N:ゴール地点
m は料金所の個数。aを料金所とする
## 入力１
5 3 3
1 2 4
↓
0 1 2 3 4 5
  a a   a
0     X   N

## 考え方
Xより左にあるaの数と、右にあるaの数を比較して小さい方の数を出力

'''
n, m, x = map(int, input().split())
A = list(map(int, input().split()))

# print(A)

# マスを初期化
cells = [0]*(n+1)
# マスにaを代入
for a in A:
    cells[a] = 1

# xからみて左右のa数をカウント
l_count = sum(cells[:x])
r_count = sum(cells[x+1:])
# print(l_count, r_count) # debug
# a数が小さい方を出力
print(min(l_count, r_count))

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

using namespace std;

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

struct state {
  int t, s, d;
};
bool cmp(state const& lhs, state const& rhs) {
  return lhs.t < rhs.t;
}

int main() {
  
  int N, M;
  while(cin >> N >> M && (N|M)) {
    vector<state> v;
    rep(i, M) {
      int t, s, d; cin >> t >> s >> d; s--, d--;
      v.push_back((state){t, s, d});
    }
    sort(v.begin(), v.end(), cmp);
    vector<bool> g(N);
    g[0] = 1;
    rep(i, M) {
      g[v[i].d] = g[v[i].d] || g[v[i].s];
    }
    int ans = 0;
    rep(i, N) {
      if(g[i]) { ans++; }
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1704
#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<vector<char> > data;

string parse(string msg){
  string res = "";
  int state = 0;
  int time = 0;
  for(auto c : msg){
    if(c == '0'){
      if(time == 0) continue;

      if(time % data[state-1].size() == 0){
        res += data[state-1][data[state-1].size() - 1];
      }else{
        res += data[state-1][time % data[state-1].size() - 1];
      }
      time = 0;
    }else{
      int num = c - '0';
      if(state != num){
        state = num;
        time = 1;
      }else{
        time++;
      }
    }
  }
  return res;
}

void init(){
  data.push_back({'.',',','!','?',' '});
  data.push_back({'a','b','c'});
  data.push_back({'d','e','f'});
  data.push_back({'g','h','i'});
  data.push_back({'j','k','l'});
  data.push_back({'m','n','o'});
  data.push_back({'p','q','r','s'});
  data.push_back({'t','u','v'});
  data.push_back({'w','x','y','z'});
}

int main(){
  int n;
  string msg;
  init();
  cin >> n;
  for(int i=0;i<n;i++){
    cin>> msg;
    cout << parse( msg ) << endl;
  }
  return 0;
}

Measured memory_bytes: 3148
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
#define REP(i,m,n) for(LL i=(m);i<(n);i++)

int main(){
  int h,w;
  cin >> h >> w;
  VVI che(h+10, VI(w+10,0));
  VS s(h),ans(h);
  REP(i,0,h){
    cin >> s.at(i);
    REP(j,0,w){
      ans.at(i) += "0";
    }
  }
  
  REP(i,0,h){
    REP(j,0,w){
      if(s.at(i)[j] == '#'){
        REP(a,i,i+3){
          REP(b,j,j+3){
            che.at(a).at(b)++;
          }
        }
        che.at(i+1).at(j+1) -= 1000;
      }
    }
  }
  REP(i,0,h){
    REP(j,0,w){
      if(che.at(i+1).at(j+1) >= 0){
        ans.at(i)[j] += che.at(i+1).at(j+1);
      }
      else{
        ans.at(i)[j] = '#';
      }
    }
  }
        
  REP(i,0,h){
    cout << ans.at(i) << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3656
require 'matrix'
N, M, L = gets.split.map &:to_i
A = Matrix[* (1..N).map{ gets.split.map(&:to_i)}]
B = Matrix[* (1..M).map{ gets.split.map(&:to_i)}]
puts (A * B).to_a.map{|e| e * ' '}

Measured memory_bytes: 9828
#include <bits/stdc++.h>
#define bug cout<<"bug"<<endl
using namespace std;
const int inf=1e9+7;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(false);
	string s;
	cin>>s;
	for(int i=0;i<(int)s.size();i++)
	{
		for(int j=i+1;j<(int)s.size();j++)
		{
			if(s[i]=='C' && s[j]=='F')
			{
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
S = input().split()
[A,B] = [int(i) for i in S]

Alow = A*100//8
Ahi  = (A+1)*100//8

Blow = B*100//10
Bhi  = (B+1)*100//10

#print(Alow,Ahi,Blow,Bhi)

Aran = [i for i in range(Alow,Ahi+1) if int(i*0.08) == A]
Bran = [i for i in range(Blow,Bhi+1) if int(i*0.10) == B]


resRan = sorted(list(set(Aran) & set(Bran)))
#print(resRan)
if len(resRan) !=0:
  print(resRan[0])
else:
  print(-1)


Measured memory_bytes: 38384
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3000 + 50;
const int mod = 1e9 + 7;
int n;
double ans = 1e9;
double x[N],y[N];
double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
//    ios::sync_with_stdio(false);
//    cin.tie(NULL);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%lf%lf", x + i, y + i);
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            for (int k = j + 1; k < n; ++k)
            {
                double a1 = ((x[i] * x[i] - x[j] * x[j]) + (y[i] * y[i] - y[j] * y[j])) / 2;
                double a2 = ((x[i] * x[i] - x[k] * x[k]) + (y[i] * y[i] - y[k] * y[k])) / 2;
                double tmp = (y[i] - y[j]) * (x[i] - x[k]) - (x[i] - x[j]) * (y[i] - y[k]) + 1e-10;
                double rx = ((y[i] - y[j]) * a2 - (y[i] - y[k]) * a1) / tmp;
                double ry = ((x[i] - x[k]) * a1 - (x[i] - x[j]) * a2) / tmp;
                double r = dis(x[i], y[i], rx, ry);
                int f = 1;
                for (int l = 0; l < n; ++l)
                {
                    double d = dis(x[l], y[l], rx, ry);
                    if (d - 1e-8 > r)
                    {
                        f = 0;
                        break;
                    }
                }
                if (f)
                    ans = min(ans, r);
            }
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
        {
            double rx = (x[i] + x[j]) / 2;
            double ry = (y[i] + y[j]) / 2;
            double r = sqrt((x[i] - rx) * (x[i] - rx) + (y[i] - ry) * (y[i] - ry));
            int f = 1;
            for (int k = 0; k < n; ++k)
                if (sqrt((x[k] - rx) * (x[k] - rx) + (y[k] - ry) * (y[k] - ry)) - 1e-8 > r)
                {
                    f = 0;
                    break;
                }
            if (f)
                ans = min(ans, r);
        }
    printf("%.10f\n", ans);
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pii>
#define read(FILE)  freopen(FILE, "r", stdin);
#define out(FILE) freopen(FILE, "w", stdout);
#define clr(x, y) memset(x,y,sizeof(x));
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define rep(i, m, n) for(int i=m ; i<n ; i++)
#define forr(i, m, n) for(int i=m ; i<=n ; i++)
#define endl '\n'
#define pb push_back
#define re return
const int N = 1e3 + 5;
const ll OO = 1e9 + 7;
using namespace std;
ll n;
bool check(ll x)
{
    ll t=n;
    while(t%x==0) t/=x;
    re t%x==1;
}
int sol(ll n)
{
    int res=0;
    for(int i=2;i<=n/i;++i) if(n%i==0)
        {
            if(check(i)) ++res;
            if((ll)i*i==n) continue;
            if(check(n/i)) ++res;
        }
    re res;
}

int main() {
    IO;
    cin>>n;
    if(n==2)
    {
        re cout<<1,0;
    }
    int ans=2;
    ans+=sol(n);
    ans+=sol(n-1);
    cout<<ans;


}


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

struct node{

  int key;
  node *next, *prev;

};

node *nil;

void insert_node(int key){
  node *x = (node *)malloc(sizeof(node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

void delete_node(node *t){
  if(t == nil) return; 
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

node* seach_node(int key){
  node *seach = nil->next;
  while(1){
    if(seach->key == key) break;
    if ( seach == nil ) break;
    seach = seach->next;
  }
  return seach;
}

void malloc_node(){
  nil = (node *)malloc(sizeof(node));
  nil->next = nil;
  nil->prev = nil;
}



int main(){

  int n;
  char str[20];
  int key;

  scanf("%d", &n);

  malloc_node();

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

    scanf("%s",str);
    if(str[0] == 'i' || strlen(str) == 6) scanf("%d",&key);

    // cout << str << " " << key << " " << i << " " << n << endl;


    if(str[0] == 'i'){
      insert_node(key);
    }else if(str[0] == 'd'){
      if(strlen(str) > 6){
	if(str[6] =='F') delete_node(nil->next);
	else if(str[6] == 'L') delete_node(nil->prev);
      }else delete_node(seach_node(key));
    }
    



  }
  
  node *ans = nil->next;
  int cnt = 0;
  while(ans != nil){
    if(cnt > 0) printf(" ");
    cnt++;
    printf("%d", ans->key);
    ans = ans->next;
  }
  printf("\n");


  return 0;

}

Measured memory_bytes: 32236
import java.util.Scanner

fun main(args: Array<String>){
    val scn = Scanner(System.`in`)

    val str = scn.nextLine()
    val n = str.length - 1

    if(n==0){
        print(str)
        return
    }

    var sum = 0L
    var bit = 0
    while(bit < (1 shl n)){

        var st = StringBuilder(str)
        var count = 1
        (0 until n).forEach { i ->
            if ((1 and (bit shr i)) == 1){
                st.insert(i+count, '+')
                count++
            }
        }
        sum += st.split("+").map(String::toLong).sum()

        bit++
    }

    print(sum)

}

Measured memory_bytes: 36200
K=int(input())
even, odd = 0,0

# K以下の偶数と奇数の個数を数える
if K % 2 == 0:
  even = K // 2
  odd = K // 2 
  
elif K % 2 == 1:
  even = K // 2
  odd = K // 2 + 1
  
print( even * odd)

Measured memory_bytes: 2940
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	a := make([]int, n+1)
	for i := 0; i < n+1; i++ {
		sc.Scan()
		a[i], _ = strconv.Atoi(sc.Text())
	}

	b := make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		b[i], _ = strconv.Atoi(sc.Text())
	}

	count := 0
	rest := 0

	if a[0] <= b[0] {
		count += a[0]
		rest = b[0] - a[0]
	} else {
		count += b[0]
	}

	for i := 1; i < n; i++ {
		if a[i] <= b[i]+rest {
			if a[i]-rest > 0 {
				rest = b[i] - a[i] + rest
			} else {
				rest = b[i]
			}
			count += a[i]
		} else {
			count += b[i] + rest
			rest = 0
		}
	}

	if a[n] < rest {
		count += a[n]
	} else {
		count += rest
	}

	fmt.Println(count)
}


Measured memory_bytes: 4736
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
public class Main {
	int N,X;
	int[] a;
	boolean[] isPrime,dp;

	public void setPrime(){
		isPrime[0] = isPrime[1] = false;
		for(int i = 2;i <= 1000000;i++){
			if(!isPrime[i])continue;
			isPrime[i] = true;
			for(int j = 2;j * i <= 1000000;j++){
				isPrime[j * i] = false;
			}
		}
	}

	public void solve() {
		isPrime = new boolean[1000000 + 1];
		Arrays.fill(isPrime, true);
		setPrime();

		while(true){
			N = nextInt();
			X = nextInt();

			if(N + X == 0)break;
			a = new int[N];
			for(int i = 0;i < N;i++){
				a[i] = nextInt();
			}

			dp = new boolean[X + 1];
			dp[0] = true;
			for(int i = 0;i < N;i++){
				for(int j = 0;j <= X - a[i];j++){
					if(dp[j] && j + a[i] <= X){
						dp[j + a[i]] = true;
					}
				}
			}

			boolean find = false;
			for(int i = X;i >= 0;i--){
				if(dp[i] && isPrime[i]){
					out.println(i);
					find = true;
					break;
				}
			}
			if(!find)out.println("NA");
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 61236
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    int N; cin >> N;
    vector<ll> A(N), S(N+1);
    for(int i=0; i<N; i++) cin >> A[i], S[i+1] = S[i] + A[i];

    ll ans = 1LL << 60;
    for(int i=1; i<N; i++) {
        ll L = S[i] - S[0];
        ll R = S[N] - S[i];
        ans = min(ans, abs(L - R));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=55,mod=1e9+7;
int n,k;
struct mat
{
	int a[N][N];
	void init1()
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				a[i][j]=0;
	}
	void init2()
	{
		init1();
		for(int i=1;i<=n;i++)
			a[i][i]=1;
	}
}a,ans;
mat mul(mat a,mat b)
{
	mat c;
	c.init1();
	for(int i=1;i<=n;i++)
		for(int k=1;k<=n;k++)
			for(int j=1;j<=n;j++)
				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
	return c;
}
main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a.a[i][j];
	ans.init2();
	while(k)
	{
		if(k&1) 
			ans=mul(ans,a);
		a=mul(a,a);
		k>>=1;
	}
	int sum=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			sum=(sum+ans.a[i][j])%mod;
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 512
# -*- coding: utf-8 -*-

def main():
    import sys

    N,D = list(map(int, sys.stdin.readline().split()))
    XY_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(N) ]

    cnt = 0

    for X,Y in XY_list:
        if (X**2 + Y**2) <= D**2:
            cnt += 1
    
    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 45380
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (h : n : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  as <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  putStrLn $ if h <= sum as then "Yes" else "No"

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 5116
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[] A = new int[N];
        int[] m = new int[N+1];
        m[0] = 0;
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt() % M;
            m[i+1] = (m[i] + A[i]) % M;
        }

        Map<Integer, Integer> map = new HashMap<>();
        int[] a = new int[N+1];
        long sum = 0;
        for (int i = 0; i < N + 1; i++) {
            Integer i2 = map.get(m[i] % M);
            if (i2 == null) {
                i2 = 0;
                map.put(m[i], i2);
            }
            sum += i2;
            map.put(m[i], i2 + 1);
        }

        System.out.println(sum);
    }

    private class MyScanner {
        String[] s;int i;BufferedReader br;String reg = " ";
        MyScanner () { s = new String[0];i = 0;br = new BufferedReader(new InputStreamReader(System.in)); }
        public String next() {
            try {
                if (i < s.length) return s[i++]; String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0); i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}


Measured memory_bytes: 49876
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i < (ll)(n); ++i)
#define MAX 10e10;
typedef long long  ll;

using namespace std;

int ans, cnt;

int main() {

	int N;
	cin >> N;
	
	vector<int> X(N);
	rep(i, N) {
		cin >> X[i];
	}

	int hpmin;
	rep(i, 100) {
		int hp = 0;
		rep(j, N) {
			hp += abs(i - X[j]) * abs(i - X[j]);
		}
		if (i == 0) {
			hpmin = hp;
		}
		if (hp < hpmin) {
			hpmin = hp;
		}
	}

	cout << hpmin << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define pb push_back
#define mod2 998244353
#pragma GCC optimize("-O2")
#define mod3 127
#define mod 1000000007
#define MAXN 1000000000
#define v32 vector<int>
#define v64 vector<lli>
#define v1024 vector<vector<int>>
#define v4096 vector<vector<lli>>
#define vt vector
#define f(x, y, z) for (lli x = y; x < z; x++)
#define fd(x, y, z) for (lli x = y; x > z; x--)
#define lb lower_bound
#define ld long double
#define m64 map<lli, lli>
#define m32 map<int, int>
#define m64it map<lli, lli>::iterator
#define m32it map<int, int>::iterator
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
#define ist insert
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define p_q priority_queue
#define min_p_q priority_queue<int, vt<int>, greater<int>>
using namespace std;
using namespace __gnu_pbds;
lli tmod(lli x, lli y)
{
    return (x % y + y) % y;
}
template <typename T>
void DEBUG_ARR(vt<T> a)
{
    f(i, 0, a.size()) cout << a[i] << " ";
    cout << "\n";
}
lli power(lli x, lli y) 
{
    lli res = 1;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x)%mod; 
        y = y>>1; 
        x = (x*x)%mod;
    }
    if(res<0)res+=mod;
    return res; 
}


int main()
{
    fastio;
    lli n;
    cin>>n;
    lli c[n];f(i,0,n)cin>>c[i];
    sort(c,c+n);
    lli ans=0;
    f(i,0,n){
        ans=(ans+(((n-i+1)*c[i])%mod)*power(2,2*n-2))%mod;
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 1792
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();
   int T = sc.nextInt();
   int[] ti = new int[N];
   for(int i = 0;i<N;i++) ti[i] = sc.nextInt(); 
   
   int sum = 0;
   for(int i = 0;i<N;i++)
   {
     if(i==N-1) sum += T;
     else
     {
       if(ti[i+1]-ti[i] > T) sum += T;
       else sum += ti[i+1]-ti[i];
     }
   }
   System.out.println(sum);
 }
}

Measured memory_bytes: 66256
n = int(input())
a = []
for i in range(n):
    a.append(int(input()) - 1)

visited = [False] * n
f = 0
visited[f] = True
cnt = 0
while True:
    cnt += 1
    t = a[f]
    if t == 1:
        flg = True
        break
    if visited[t]:
        flg = False
        break
    visited[t] = True
    f = t
print(cnt) if flg else print(-1)

Measured memory_bytes: 13768
N, M, C = map(int, input().split())
B = list(map(int, input().split()))


ans = 0
for i in range(N):
    A = list(map(int, input().split()))
    Score = sum([a * b for a, b in zip(A, B)]) + C
    if Score > 0:
        ans += 1

print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

void solve(long long N, std::vector<long long> A)
{
    vector<ll> L(N);
    vector<ll> R(N);
    L[0] = A[0];
    R[N - 1] = A[N - 1];

    for (int i = 1; i <= N - 1; i++)
    {
        L[i] = gcd(L[i - 1], A[i]);
    }

    for (int i = N - 2; i >= 0; i--)
    {
        R[i] = gcd(R[i + 1], A[i]);
    }

    ll ans = -1;
    for (int i = 0; i < N; i++)
    {
        if (i == 0)
        {
            ans = max(ans, R[i + 1]);
        }
        else if (i == N - 1)
        {
            ans = max(ans, L[i - 1]);
        }
        ans = max(ans, gcd(L[i - 1], R[i + 1]));
    }
    cout << ans << endl;
}

int main()
{
    long long N;
    scanf("%lld", &N);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 2560
import java.util.*;
import java.io.PrintWriter;
public class Main {
	
	static PrintWriter out;
	static Scanner sc;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		
		int n=sc.nextInt();
		char a[]=sc.next().toCharArray();
		TreeSet<Integer> w=new TreeSet<>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return Integer.compare(o2, o1);
			}
			
		});
		ArrayList<Integer> r=new ArrayList<>();
		for(int i=0;i<n;i++) {
			if(a[i]=='W')w.add(i);
			else r.add(i);
		}
		int ans=r.size();
		int k=ans;
		for(int i=0;i<k;i++) {
			if(a[i]=='R')ans--;
		}
		
		out.println(ans);
		
		sc.close();
		out.close();
		
	}
}


Measured memory_bytes: 51752
/* 	* In the name of GOD 
	* Thanks God */
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define int long long

int32_t main(){
	int n, k;
	cin >> n >> k;
	if (k > n)
		k = n;
	k = n - k;
	int a[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	int sum = 0;
	for (int i = 0; i < k; i++) 
		sum += a[i];
	cout << sum;
}


Measured memory_bytes: 5084
#include <stdio.h>
int main(){
    int a,b,i,memory[3000]={0},cnt=0,allcnt=0;
    while(1){
        scanf("%d %d",&a,&b);
        if(a==0&&b==0) break;
        if(allcnt>=1){
            puts("");
        }
        for(i=a;i<=b;i++){
            if(i%400==0){
                memory[cnt]=i;
                cnt++;
            }else if(i%100!=0&&i%4==0){
                memory[cnt]=i;
                cnt++;
            }
        }
        if(cnt!=0){
            for(i=0;i<cnt;i++){
                printf("%d\n",memory[i]);
                memory[i]=0;
            }
        }else{
            printf("NA\n");
        }
        cnt = 0;
        allcnt++;
    }
    return 0;
}

Measured memory_bytes: 632
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000000007;
#define ll long long

int c[10][10];
void dfs()
{
	for (int k = 0; k < 10; k++) {
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
			}
		}
	}
}
int main()
{
	int H, W;
	cin >> H >> W;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> c[i][j];
		}
	}
	dfs();
	int ans = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int A;
			cin >> A;
			if (A != -1) {
				ans += c[A][1];
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int main (){
  int n=0,i=0,a[100],ans = 0;
  float ave=0,sum=0,diff,tmp;
  scanf("%d",&n);
  //printf("%d\n",n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    sum = sum+a[i];
    //printf("%d\n",sum);
    //printf("%d\n",a[i]);     
  }
  ave = sum/n;
  diff = 10000;
  //printf("%f\n",diff); 
  for(i=0;i<n;i++){
    if(diff>abs(ave-a[i])){
      diff = abs(ave-a[i]);
      //printf("%f\n",diff);      
      ans = i;
      
    }
  }  
  printf("%d\n",ans);
  //printf("%d\n",ans);  
  //printf("%f\n",ave);
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

LIM = 10 ** 18

N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    quit()

ans = 1
for a in A:
    ans *= a
    if ans > LIM:
        ans = -1
        break
print(ans)

Measured memory_bytes: 21600
n = int(input())
s = [int(input()) for _ in range(n)]
tots = sum(s)
if tots % 10 > 0:
   print(tots)
else:
   t = [x for x in s if x % 10 > 0]
   if len(t) == 0:
      print(0)
   else:
      t.sort()
      print(tots-t[0])


Measured memory_bytes: 9104
#include <iostream>
#include <queue>
#include <string>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int n; cin>>n;
    while(n--){
        int out=0, p=0, b=0;
        while(out!=3){
            string s; cin>>s;
            if(s[0]=='O') out++;
            else if(s.back()=='T'){
                b++;
                if(b>=4) b--, p++;
            }
            else p+=b+1, b=0;
        }
        cout<<p<<endl;
    }
}

Measured memory_bytes: 1200
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc=new Scanner(System.in);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int C=sc.nextInt();
		int D=sc.nextInt();
		int one_size=A*B;
		int two_size=C*D;
		if(one_size>=two_size) {
			System.out.println(one_size);
		}else {
			System.out.println(two_size);
		}
	}

}


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

//文字列sの中に文字列pが存在するか

int main()
{
	string s, p;
	int j = 0,Pcount,Scount;
	cin >> s >> p;
	s += s;
	Pcount = p.size(), Scount = s.size() / 2;

	for (int i = 0; i < Scount; i++) {
		for (int j = 0; j < Pcount; j++) {
			if (s[i + j] != p[j]) {
				break;
			}
			if (j == Pcount - 1) {
				cout << "Yes" << endl;
				exit(0);
			}
		}
	}

	cout << "No" << endl;

	return 0;
}


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

int d(int k)
{
    if(k<0)return -1;
    if(k==0)return 0;
    return 1;
}

int main()
{
    int a,b;cin>>a>>b;
    if(d(a)!=d(b)){cout<<"Zero\n";return 0;}
    if(d(a)==1){cout<<"Positive\n";return 0;}
    if(((b-a)%2)==0)cout<<"Negative\n";
    else cout<<"Positive\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define input freopen("/Users/shahadat/Desktop/input.txt", "r", stdin)

int const MOD = 1e9 + 7;
int const N = 105;
int const MX = 1e5;
using namespace std;

int num[N], fn[N];

int wt[N], vl[N];
int dp[100010];
int32_t main(){
    memset(dp, -1, sizeof dp);
    int n, w;
    cin>>n>>w;
    
    for(int i = 1; i<=n; i++){
        cin>>wt[i]>>vl[i];
    }
    
    dp[0] = 0;
    for(int i = 1; i<=n; i++){
        int val = vl[i];
        int weight = wt[i];
        for(int j = MX-val; j>=0; j--){
            if(dp[j] != -1){
                if(dp[j+val] == -1)
                    dp[j+val] = dp[j] + weight;
                else{
                    dp[j + val] = min(dp[j+val], dp[j] + weight);
                }
            }
        }
    }
    for(int i = MX; i>=0; i--){
        if(dp[i] != -1 && dp[i] <= w){
            cout<<i<<endl;
            break;
        }
    }
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

inline int swap(int* a, int* b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

inline void Sort(int* num)
{
	int i, j;
	for (i = 1; i < 3; i++)
	{
		for (j = 0;j < i; j++)
		{
			if (num[i] < num[j]) swap(num[i], num[j]);
		}
	}
}

int main()
{
	int num[3];
	cin >> num[0] >> num[1] >> num[2];
	Sort(num);
	cout << num[0] << " " << num[1] << " " << num[2] << endl;
	return 0;
}


Measured memory_bytes: 3104
N = int(input())
XL = []
for _ in range(N):
    x, l = map(int, input().split())
    XL.append([x - l, x + l])
XL.sort(key=lambda x: x[1])

res = 0
now = -10 ** 9
for s, e in XL:
    if now <= s:
        now = e
        res += 1

print(res)


Measured memory_bytes: 25536
h,w=map(int,input().split())
s=[input() for _ in range(h)]
yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]
count=0
for i in range(h):
    a=[0]
    for j in range(w):
        if s[i][j]=="#":
            a.append(j+1)
    a.append(w+1)
    for j in range(1,len(a)):
        for k in range(a[j-1],a[j]-1):
            yoko[i][k]=a[j]-a[j-1]-1
for i in range(w):
    a=[0]
    for j in range(h):
        if s[j][i]=="#":
            a.append(j+1)
    a.append(h+1)
    for j in range(1,len(a)):
        for k in range(a[j-1],a[j]-1):
            tate[k][i]=a[j]-a[j-1]-1

ans=1
for i in range(h):
    for j in range(w):
        ans=max(ans,yoko[i][j]+tate[i][j]-1)
print(ans)


Measured memory_bytes: 122968
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll MOD = 1e9+7;
//LLONG_MIN

//

int main(void){
	bool can=true;
	ll h,w,x=0,y=0;
	string s[10];
	cin>>h>>w;
	rep(i,h)cin>>s[i];
	while(x<w-1 || y<h-1){
		s[y][x]='*';//通った場所は別の文字にする
		if(s[y][x+1]=='#' && s[y+1][x]=='#'){
			can=false;
			break;
		}else if(s[y][x+1]=='#'){
			x++;
		}else if(s[y+1][x]=='#'){
			y++;
		}else{
			can=false;
			break;
		}
		s[y][x]='*';
		// printf("%lld,%lld\n",x,y);
	}
	rep(i,h)rep(j,w)if(s[i][j]=='#')can=false;
	cout<<(can?"Possible":"Impossible")<<endl;
	return 0;
}

Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: Vec<usize> = iterator.next().unwrap().chars().map(|c| c.to_digit(10).unwrap() as usize).collect();

    let mut sum: usize = 0;
    for ni in n {
        sum += ni;
        sum %= 9;
    }
    if sum == 0 {
        "Yes".to_string()
    } else {
        "No".to_string()
    }
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main(){
	
	fastio;
	int n ;
	cin  >> n ;
	int arr[n+2];
	for(int i = 1 ; i <= n ; i ++)
		cin >> arr[i];
	ll ans = 0;
	for(int i = 1 ; i <= n-1 ; i ++){
		if(arr[i+1]<arr[i])
		{
			ans +=(llabs(arr[i+1]-arr[i]));
			arr[i+1] = arr[i];
		}
	}
	cout << ans << "\n";
	
}


Measured memory_bytes: 4420
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
long long int a[300000];
long long int b[300000];
long long int c[300000];
int main()
{
    long long int n,i,j,k,ci=0;
    scanf("%lld",&n);
    for(i=0;i<=n;i++)
        b[i]=0;
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        b[a[i]]++;
    }
    c[0]=0;
    c[1]=0;
    c[2]=1;
    for(i=3;i<=n+5;i++)
    {
        c[i]=c[i-1]+i-1;
    }
    for(i=1;i<=n;i++)
    {
        ci+=c[b[i]];
    }
    for(i=1;i<=n;i++)
    {
        if(b[a[i]]<=1)
            printf("%lld\n",ci);
        else
        {
            k=b[a[i]]-1;
            printf("%lld\n",ci-k);
        }
    }
    return 0;
}


Measured memory_bytes: 8320
#-*-coding:utf-8-*-

def main():
    grid_list = []
    for i in range(3):
        grid_list.append(list(map(int, input().split())))
    
    if grid_list[0][0] - grid_list[0][1] == grid_list[1][0] - grid_list[1][1] == grid_list[2][0] - grid_list[2][1] and \
        grid_list[0][2] - grid_list[0][1] == grid_list[1][2] - grid_list[1][1] == grid_list[2][2] - grid_list[2][1] and \
        grid_list[1][0] - grid_list[0][0] == grid_list[1][1] - grid_list[0][1] == grid_list[1][2] - grid_list[0][2] and \
        grid_list[2][0] - grid_list[1][0] == grid_list[2][1] - grid_list[1][1] == grid_list[2][2] - grid_list[1][2]:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()
    

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

int main() {
  string S;
  cin >> S;
  int len = S.size();
  int n = len - 1;
  while(n >= 0){
    if(n <= 3) {
      cout << "NO" << endl;
      return 0;
    }
    if(S.at(n) == 'm') {
      if(S.substr(n - 4, 5) == "dream"){
         n -= 5;
        continue;
      }else{
        cout << "NO" << endl;
        return 0;
      }
    }
    if(S.at(n) == 'e') {
      if(S.substr(n - 4, 5) == "erase"){
         n -= 5;
        continue;
      }else{
        cout << "NO" << endl;
        return 0;
      }
    }
    if(S.at(n) == 'r') {
      if(S.at(n-2) == 'm') {
        if(n < 6){
          cout << "NO" << endl;
          return 0;
        }
        if(S.substr(n - 6, 7) == "dreamer"){
          n -= 7;
          continue;
        }else{
          cout << "NO" << endl;
          return 0;        
        }
      }
      if(S.at(n-2) == 's') {
        if(n < 5){
          cout << "NO" << endl;
          return 0;
        }
        if(S.substr(n - 5, 6) == "eraser"){
          n -= 6;
          continue;
        }else{
          cout << "NO" << endl;
          return 0;
        }
      }
    }
    cout << "NO" << endl;
    return 0; 
  }
  cout << "YES" << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;


int main(){
  int N;
  cin>>N;
  //even pattern
  int num;
  if(N%2==0){
    cout<<N*(N-2)/2<<"\n";
    num=N+1;
    for(int i=1;i<=N;++i){
      for(int j=i;j<=N;++j){
        if(i==j | i+j==N+1){
          continue;
        }
        else{
          cout<<i<<" "<<j<<"\n";
        }
      }
    }
  }
  //odd pattern
  else{
    cout<<(N-1)*(N-1)/2<<"\n";
    num=N;
    //line from top
    for(int i=1;i<N;++i){
      cout<<i<<" "<<N<<"\n";
    }
    //line independent from top
    for(int i=1;i<N;++i){
      for(int j=i;j<N;++j){
        if(i==j | i+j==N){
          continue;
        }
        else{
          cout<<i<<" "<<j<<"\n";
        }
      }
    }
  }
return 0;
}


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

int main(){

	double base_x = 0,base_y = 0,pre_x,pre_y,current_x,current_y,sum = 0,right,left,bottom,z;


	scanf("%lf,%lf",&base_x,&base_y);
	scanf("%lf,%lf",&current_x,&current_y);
	right = sqrt((current_x-base_x)*(current_x-base_x)+(current_y-base_y)*(current_y-base_y));
	pre_x = current_x;
	pre_y = current_y;

	while(scanf("%lf,%lf",&current_x,&current_y)!=EOF){
		bottom = sqrt((current_x-pre_x)*(current_x-pre_x)+(current_y-pre_y)*(current_y-pre_y));
		left = sqrt((current_x-base_x)*(current_x-base_x)+(current_y-base_y)*(current_y-base_y));

		z = (left+right+bottom)/2;
		sum += sqrt(z*(z-left)*(z-right)*(z-bottom));
		right = left;
		pre_x = current_x;
		pre_y = current_y;
	}

	printf("%.6lf\n",sum);

    return 0;
}

Measured memory_bytes: 2708
#include <stdio.h>
#include <bitset>
using namespace std;
int main(){
	int i;
	int N;
	int A;
	int S = 0;
	bitset<2000 * 2000> bs;
	bs[0] = 1;

	for (scanf("%d", &N); N--;){
		scanf("%d", &A);
		bs |= (bs << A);
		S += A;
	}
	
	S = (S >> 1) + (S & 1);
	while (!bs[S]) S++;
	printf("%d",S);

	return 0;
}



Measured memory_bytes: 1664
#ifdef _DEBUG
#define _CRT_SECURE_NO_WARNINGS
#define REL
#endif
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>

//#pragma GCC optimize("Ofast")
//#pragma target("sse", "sse1")

#define mp make_pair
#define pb push_back

#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

mt19937 gen(34);
//mt19937_64 gen(41);

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("rps2.in", "r", stdin);
	//freopen("rps2.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//----------------------------------------------//
	string s;
	cin >> s;
	for (int i = 0; i < 3; i++) {
		if (s[i] == '7') {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	//----------------------------------------------//

	return 0;
}




Measured memory_bytes: 3656
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
map<int,set<int>>mp;
int main(){
ll  n,k;
cin>>n>>k;
vector<ll> a(n),sum(n+1,0);
for(int i=0;i<n;i++){
    cin>>a[i];
    sum[i+1]=sum[i]+a[i];
}
ll ans=0;
for(int i=0;i<=n;i++){
   int now=(sum[i]-i)%k;
   int b=i-k+1;
   auto ite=mp[now].lower_bound(b);
   if(ite!=mp[now].begin())mp[now].erase(mp[now].begin(),ite);
   ans+=(int)mp[now].size();
   mp[now].insert(i);
}
cout<<ans<<endl;
}



Measured memory_bytes: 31488
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#include <cassert>
 

using namespace std;

char nth_letter(long long n)
{
    assert(n >= 1 && n <= 26);
    return "abcdefghijklmnopqrstuvwxyz"[n-1];
}

int main() {
    long long n;
    cin >> n;
    
    vector<int> a(100001);
    for(int i=0; i<100001; i++){
        a[i]=0;
    }
    
    for(int i=1; i<200; i++){
        for(int j=1; j<200; j++){
            for(int k=1; k<200; k++){
                int ans = i*i + j*j + k*k + i*j + j*k + i*k;
                if(ans<100001){
                    a[ans-1]++;
                }
            }
        }
    }
    
    for(int i=0; i<n; i++){
        cout << a[i] << endl;
    }
    
    return 0;
 }


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

namespace {
   constexpr int g1 = 1000 * 1000 * 1000, si = 1001 * 1002, si_log = 8 + 10, mod = static_cast<int>(1e9) + 7;
   constexpr long double eps = 1.0e-9;
   int n, m, br[256];
   string ar[1234];
}

int64_t sol() {
   auto ret = 0 * numeric_limits<int64_t>::max();
   if (n < m) swap(n,m);

   int od = 0; for (int c = 0; c < 256; c++) od += br[c] & 1;

   if (0 == (m & 1) || 0 == (n& 1)) {
      if (od)
         return 0 + ret;
   }
   
   if (1 == m) {
      if (n & 1)
         return 1 == od;
      return 0 == od;
   }

   vector<int> ma;
   int sig = 0;

   for (int c = 0; c < 256; c++) {
      if (br[c]) {
         ma.push_back(br[c]);
         sig += 1 == br[c];
      }
   }
   if (1 == ma.size())
      return 1;
   if (1 < sig)
      return 0;

   if (n & 1) {
      if (m & 1) {
         for (int i = 0; i < (int)ma.size(); i++) {
            if (0 == (ma[i] & 1))
               continue;

            int co[4] = { 0 };
            {
               const auto rem2 = (ma[i] + 3) & 3;
               co[rem2]++;
               co[ma[i] & 3]--;
            }

            for (int j = 0; j < (int)ma.size(); j++) {
               const auto rem = ma[j] & 3;
               co[rem]++;
            }

            if (co[1] || co[3])
               continue;
            if (co[2]*2 <= m+n-1)
               return 1;
         }

         return 0;
      }
   }
   else {
      if (0 == (m & 1)) {
         for (const auto &ce : ma) {
            if (ce & 3)
               return 0;
         }
         return 1;
      }
   }

   if (m & 1)
      swap(n, m);
   assert(n & 1 && 0 == (m&1));
   int re4 = 0;
   for (const auto &ce : ma) re4 += ce & 2;
   return ret + re4 <= m;
}

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

   while (cin >> n >> m)
   {
      memset(br, 0, sizeof br);
      //for (int i = 0; i <= n; ++i) { gr[i].clear(); }
      //for (int i = 1; i <= n; ++i) cin >> ar[i];
      for (int i = 0; i < n; ++i) {
         cin >> ar[i];
         assert(m == (int)ar[i].size());
         for (int j = 0; j < m; j++) br[ar[i][j]]++;
      }
      auto s =
         sol();
      cout << (s ? "Yes" : "No") << '\n';
#ifndef _DEBUG
      break;
#endif
   }
   return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
ans = 0
for i in range(1,N+1):
    if i >= K:
        ans += 1/N
        continue
    for n in range(1,1000000):
        i *= 2
        if i >= K:
            ans += (1 / N) * (0.5 ** n)
            break
print(ans)


Measured memory_bytes: 2940