akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;

  N = N % 10;
  if (N == 2 || N == 4 || N == 5 || N == 7 || N == 9)
    cout << "hon" << endl;
  else if (N == 0 || N == 1 || N == 6 || N == 8)
    cout << "pon" << endl;
  else if (N == 3)
    cout << "bon" << endl;
  return 0;
}

Measured memory_bytes: 3488
#include<iostream>

using namespace std;

int main(){

  int data[10001];
  int n;

  for(int i = 0; i <= 10000; i++) data[i] = 1;


  for(int i = 2; i*i <= 10000; i++){
    if(data[i] == 1){
      for(int j = i*2; j <= 10000; j+=i) data[j] = 0;
    }
  }
  data[0] = 0;
  data[1] = 0;

  while(cin >> n){

    int sum = 0;

    for(int i = 1; i <= n; i++){
      if(data[i] == 1 && data[n-i+1] == 1) sum++;
    }

    cout << sum << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <map>  
#include <algorithm>
#include <string>
#include <utility>
#include <deque>
#include <vector>
#include <set>
#include <numeric>

bool dp_search(std::vector<int>& inst, int target, bool is_start) {
	
	int max_point = std::accumulate(inst.begin(), inst.end(), 0);

	if (std::abs(target) > max_point) return false;
	if (inst.size() <= 0) {
		if (target == 0) return true;
		else return false;
	}
	std::vector<std::vector<bool>> dp(inst.size(), (std::vector<bool>((max_point + 1)*2, false)));
	
	
	dp[0][max_point + inst[0]] = true;
	if (is_start == false) dp[0][max_point - inst[0]] = true;
	
	
	for (int i = 1; i < inst.size(); i++) {
		for (int j = -max_point; j <= max_point; j++) {
			if (max_point + j - inst[i] >= 0)
				dp[i][max_point + j] = dp[i][max_point + j] | dp[i - 1][max_point + j - inst[i]];
			if (max_point + j + inst[i] < (max_point + 1) * 2)
				dp[i][max_point + j] = dp[i][max_point + j] | dp[i - 1][max_point + j + inst[i]];
		}
	}
	return dp[inst.size() - 1][max_point + target];
}

int main() {
	std::string instruction;
	std::vector<int> X_inst, Y_inst;
	int x_target, y_target;
	std::cin >> instruction;
	std::cin >> x_target;
	std::cin >> y_target;

	int counter = 0;
	int is_x_direct = true;
	for (int i = 0; i < instruction.length(); i++) {
		if (instruction[i] == 'T') {

			if (is_x_direct) X_inst.push_back(counter);
			else Y_inst.push_back(counter);

			is_x_direct = !is_x_direct;
			counter = 0;
		}
		else {
			counter++;
		}	
	}

	if (is_x_direct) X_inst.push_back(counter);
	else Y_inst.push_back(counter);

	bool result = dp_search(X_inst, x_target, true) & dp_search(Y_inst, y_target, false);


	if (result) std::cout << "Yes" << std::endl;
	else std::cout << "No" << std::endl;
	return 0;

}


Measured memory_bytes: 2304
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
aa = inpl()
cnt = defaultdict(int)
ed = set()

for a in aa:
    ed.add(a)
    cnt[a] += 1

for i in range(M):
    b,c = inpl()
    ed.add(c)
    cnt[c] += b

ed = list(ed)
ed.sort(reverse=True)

tmp = 0
ans = 0
for e in ed:
    s = cnt[e]
    if (N-tmp) <= s:
        ans += (N-tmp)*e
        break
    else:
        ans += e*s
        tmp += s


print(ans)


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;
#define INF 10000000000000
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for(ll i = 1; i < (ll)(n); i++)
#define repN_1(i, n) for(ll i = 0; i < (ll)(n - 1); i++)
#define repM(i, n) for(ll i = (ll)(n - 1); i >= 0; i--)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

int main()
{
	int s, w;

	cin >> s >> w;

	if (s > w)
		cout << "safe" << endl;
	else
		cout << "unsafe" << endl;

	return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long 
#define rep(i, s, n) for(int i = s; i < n; i++)

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll count = 0;
    rep(i, 0, n) {
        cin >> a[i];
        if(a[i] < 0) {
            count++;
        }
    }
    ll ans = 0;
    if(count%2 == 0) {
        rep(i, 0, n) ans += abs(a[i]);
        cout << ans << endl;
    }
    else {
        ll m = abs(a[0]);
        rep(i, 0, n) {
            ans += abs(a[i]);
            m = min(m, abs(a[i]));
        }
        cout << ans - 2*m << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

void Main()
{
    int r;
    cin >> r;

    cout << 2 * r * M_PI << endl;
}

int main()
{
    std::cout << std::fixed << std::setprecision(15);
    Main();
}

Measured memory_bytes: 3784
# coding: utf-8
import sys
import numpy as np
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
# 素因数分解をして、それぞれの因数をどこに入れるか

def cmb(n, k):
    if k < 0 or k > n: return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

def prime_factorize(n): # Nの素因数分解
    A = []
    while n % 2 == 0:
        A.append(2); n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            A.append(f); n //= f
        else:
            f += 2
    if n != 1:
        A.append(n)
    return A

N, M = lr()
primes = prime_factorize(M)
counter = Counter(primes)
answer = 1
for v in counter.values():
    cases = cmb(N-1+v, v)
    answer *= cases
    answer %= MOD

print(answer % MOD)
# np.int64とint型の違いに注意
# 16

Measured memory_bytes: 51480
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <numeric>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define PUSH(n,v) for(int i=0; i<(n); i++) {int j; cin >> j; v.push_back(j);}
#define ALL(v) v.begin(), v.end()
#define print(s) cout << (s) << endl

bool prs[50000];

bool pr(int n) {
    for (int i = 3; i <= sqrt(n); i+=2) {
        if (n % i == 0) return false;
    }
    return true;
}

void solve56(int n) {
    if (n % 2) {
        if (prs[n-2]) cout << 1 << endl;
        else cout << 0 << endl;
    }else if (n == 4) {
        cout << 1 << endl;
    }else {
        int cnt = 0;
        for(int i = 3; i <= n / 2; i+=2) {
            if (prs[i] && prs[n-i]) cnt++;
        }
        cout << cnt << endl;
    }
}

int main() {
    for (int i = 3; i < 50000; i+=2) {
        if (pr(i)) prs[i] = true;
    }
    int n;
    while(cin >> n, n) {
        solve56(n);
    }
    return 0;
}

Measured memory_bytes: 1208
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int main()
{
	char a[100001];
	scanf("%s",a+1);
	for(int i=1;i<=strlen(a+1)-8;i++)
	{
		cout<<a[i];
	}
} 

Measured memory_bytes: 256
n, m = map(int, input().split())
won = set()
d = {}
penalties = 0
for i in range(m):
  x = input().split()
  ID = x[0]
  stat = x[1]
  if ID in won:
    continue
  if stat == "WA":
    if (d.get(ID, None)):
      d[ID] += 1
    else:
      d[ID] = 1
  else:
    won.add(ID)

for item in won:
    penalties += d.get(item,0)
print(len(won), penalties)

Measured memory_bytes: 14052
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class SimulatorBaseball { // Simlate baseball
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private int numIning, outCount, point;
    private int ining = 1;
    private List<Boolean> bases = new ArrayList<>(Arrays.asList(false, false, false));

    // Constructior
    SimulatorBaseball() {

    }

    void initialize() {
        outCount = 0;
        point = 0;
        Collections.fill(bases, false);
    }

    void runGame() {
        String line = null;
        try {
            line = input.readLine();
        } catch (IOException e) {
            System.out.println("IOException for numIning");
        }
        try{
            numIning = Integer.parseInt(line);
        } catch (NumberFormatException e) {
            System.out.println(line + "is not Int");
        }
        

        try {
            while (ining <= numIning){// start game
                line = input.readLine();
                switch (line) {
                case "HIT":
                    for (int i = bases.size() - 1; i >= 0; i--) {
                        Boolean base = bases.get(i);
                        if (base) {
                            if (i == 2) {
                                bases.set(i, false);
                                point++;
                            } else {
                                bases.set(i + 1, true);
                                bases.set(i, false);
                            }
                        }
                    }
                    bases.set(0, true);
                    break;
                case "HOMERUN":
                    int numOnBase = 1;
                    for (Boolean base : bases) {
                        if (base) {
                            numOnBase++;
                        }
                    }
                    point += numOnBase;
                    Collections.fill(bases, false);
                    break;
                case "OUT":
                    outCount++;
                    if (outCount == 3) {
                        System.out.println(point);
                        initialize();
                        ining++;
                    }
                    break;
                default:
                    System.out.println("errorEvent");
                }
            }
        } catch (IOException e) {
            System.out.println("IOException for event");
        }
    }
}

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


Measured memory_bytes: 24180
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <map>
#include <queue>
#include <deque>
#include <set>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define FOR(i,a,b) for (int i = (a) ; i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
//#define repitr(itr, st) for(auto itr = st.begin(); itr != st.end(); ++itr)
#define P_B push_back
#define PO_B pop_back
#define E_B emplace_back
#define M_P make_pair
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl
//#define print(x) printf("%d\n", x)

using namespace std;
using ll = long long;
using Pii = pair<int,int>;
using Pll = pair<ll,ll>;
using VI = vector<int>;
using VL = vector<ll>;
using VVI = vector<vector<int> >;
using VVL = vector<vector<ll> >;
//int dx[4] = {1, 0, -1, 0};
//int dy[4] = {0, 1, 0, -1};
//const ll LINF = (ll)1e18 - 1;
//const int INF = 1e9 - 1;
//int:±2*10^9くらい　ll:±9*10^18くらい


void Main(){
	int x, a;
	cin >> x >> a;
	if(x < a) cout << 0 << endl;
	else cout << 10 << endl;




}

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

  return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
int main(){
    int n,m; cin >> n >> m;
    vector<pair<int,int>> sevenpay(n);
    int a,b;
    rep(i,n){
        cin >> a >> b;
        sevenpay[i] = make_pair(a,b);
    }
    sort(sevenpay.begin(),sevenpay.end());
    priority_queue<int> q;
    int cnt = 0, ans = 0;
    for(int i = 1; i <= m; i++){ //各残り日数毎に見ていく
        while(cnt < n && sevenpay[cnt].first <= i){
            q.push(sevenpay[cnt++].second);
        }
        if(!q.empty()){
            ans += q.top();
            q.pop();
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1660
_ = gets
numbers = gets.chomp.split.map(&:to_i)
counter = 0

def get_devided(arr)
  arr.map { |n| n % 2 == 0 ? n / 2 : nil }
end

devided = get_devided(numbers)

while devided.all? do
  counter += 1
  devided = get_devided(devided)
end

print "#{counter}\n"

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

int main() {
    int N; cin >> N;
    long long int ans = 1;
    for (int i = 1; i <= N; i++) {
        long long int j = i % 1000000007;
        ans *= j;
        ans %= 1000000007;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3592
object Main extends App {
  val n =  scala.io.StdIn.readInt()
  var aMap = scala.collection.mutable.Map.empty[Int, Int]
  val aInput =  scala.io.StdIn.readLine()
  aMap.put(1, 0)
  aInput.split(" ").zipWithIndex.foreach { a =>
    aMap.put(a._2 + 2, 0)
    val jousiCount = aMap.get(a._1.toInt).getOrElse(0)
    aMap.put(a._1.toInt, jousiCount + 1)
  }
  aMap.toVector.sortBy(a => a._1).foreach { a =>
    println(a._2)
  }
}

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

typedef long long ll;

int main(){
    ll n, k;
    cin>> n >> k;
    while(n>k){
        ll x = n/k;
        n=abs(n-x*k);
    }
    while(n>abs(n-k)){
        n = abs(n-k);
    }
    cout<< n <<endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD =  998244353;

  
     signed main(){
     int k;string s;
     cin>>k>>s;int l=s.size();
     for(int i=0;i<min(k,l);i++)cout<<s[i];
     if(k<s.size())cout<<"...";
     cout<<endl;

      }

        

Measured memory_bytes: 3600
#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
	int ma = -1, s = 0;
	for(int i=0;i<3;i++) {
		int x; scanf("%d", &x);
		s += x;
		ma = max(ma, x);
	}
	int k; scanf("%d", &k);
	printf("%d\n", (s-ma) + (ma<<k));
	
	return 0;
}

Measured memory_bytes: 128
fn main() {
    // loop{ //For test
        solve();
    // }
}

#[allow(dead_code)]
fn solve(){
    let H: i64 = read();

    println!("{}", func(H));
}

fn func(hit: i64) -> i64 {
    if hit == 1 {
        return 1;
    }else{
        return 2*func(hit/2)+1;
    }
}

/// 標準入力から一行を読み取り、指定の型に変換する関数
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    let _ = std::io::stdin().read_line(&mut s);
    s.trim().parse().ok().unwrap()
}

/// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

/// 標準入力からn行を読み取り、各行を空白文字で分割し、各要素を指定の型に変換する関数
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

typedef pair<int,int> pii;
typedef pair<pii,pii> pp;

int main(void) {
    int n, w, h;
    while (cin>>n>>w>>h && w && h) {
        vector<pp> g;
        g.push_back(make_pair(make_pair(0,0), make_pair(w,h)));
        vector<int> area;
        area.push_back(w*h);
        while (n--) {
            int a, b;
            cin >> a >> b;
            a--;
            pii lt = g[a].first, rb = g[a].second;
            int w1 = lt.first, h1 = lt.second;
            int w2 = rb.first, h2 = rb.second;
            int tw = w2-w1, th = h2-h1;
            int s = tw*2 + th*2;
            b %= s;
            int type;
            if (b < tw) type = 0;
            else if (b < tw+th) type = 1;
            else if (b < 2*tw+th) type = 2;
            else type = 3;
            
            pp p1, p2;
            switch (type) {
                case 0:
                p1 = make_pair(make_pair(w1,h1), make_pair(w1+b,h2));
                p2 = make_pair(make_pair(w1+b,h1), make_pair(w2,h2));
                break;
                case 1:
                b -= tw;
                p1 = make_pair(make_pair(w1,h1), make_pair(w2,h1+b));
                p2 = make_pair(make_pair(w1,h1+b), make_pair(w2,h2));
                break;
                case 2:
                b -= tw+th;
                p1 = make_pair(make_pair(w1,h1), make_pair(w2-b,h2));
                p2 = make_pair(make_pair(w2-b,h1), make_pair(w2,h2));
                break;
                case 3:
                b -= 2*tw+th;
                p1 = make_pair(make_pair(w1,h1), make_pair(w2,h2-b));
                p2 = make_pair(make_pair(w1,h2-b), make_pair(w2,h2));
                break;
            }
            
            int sum1 = (p1.second.first-p1.first.first) * (p1.second.second-p1.first.second);
            int sum2 = (p2.second.first-p2.first.first) * (p2.second.second-p2.first.second);
            
            area.erase(area.begin()+a);
            g.erase(g.begin()+a);
            if (sum1 > sum2) {
                swap(sum1,sum2);
                swap(p1,p2);
            }
            area.push_back(sum1);
            g.push_back(p1);
            area.push_back(sum2);
            g.push_back(p2);
        }
        sort(area.begin(), area.end());
        for (int i = 0; i < area.size(); i++) cout << area[i] << (i != area.size()-1 ? " " : "\n");
    }
}

Measured memory_bytes: 3172
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>

using namespace std;

#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()

#define REP(i,s,e)	for(int i=(s); i<(e); i++)
#define rep(i,n)	REP(i,0,n)
#define REPE(i,s,e)	for(int i=s; i>e; i--)
#define repe(i,n)	REPE(i,n,-1)


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef vector<vi> vii;

const int IMAX = ((1 << 30) - 1) * 2 + 1;
const int INF = 100000000;
const double EPS = 1e-10;
//int mod=1000000007







int main(){
	int n, q;
	while (cin >> n >> q){
		if (n == 0 && q == 0) break;
		int m, d;
		map<int, int> dat;
		for (int i = 0; i < n; i++){
			cin >> m;
			for (int j = 0; j < m; j++){
				cin >> d;
				dat[d] += 1;
			}
		}
		int Max = 0,ans=0;
		for (map<int, int>::iterator it = dat.begin(); it != dat.end(); it++){
			if (it->second > Max){
				Max = it->second;
				ans = it->first;
			}
		}
		if (Max < q)cout << "0" << endl;
		else cout << ans << endl;
	}
}

Measured memory_bytes: 1204
n = int(input())
l = list(map(int, input().split()))

ans = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            a = sorted([l[i], l[j], l[k]])
            if a[0] == a[1] or a[1] == a[2] or a[2] == a[0]:
                continue
            if a[0] + a[1] > a[2]:
                ans += 1

print(ans)


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

class Main {
  public static void main(String[] args) {
    int[] a = new int[10];
    Scanner cin = new Scanner(System.in);

    for (int i = 0; i < 10; i++) {
      a[i] = cin.nextInt();
    }

    Arrays.sort(a);

    for (int i = 9; i > 6; i--) {
      System.out.println(a[i]);
    }
  }
}

Measured memory_bytes: 26364
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const ll mod = 1000000007;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
  ll a, b;
  cin >> a >> b;
  ll ans = 0;
  for (ll i = a; i <= b; i++) {
    ll tmp = 0;
    string s = to_string(i);
    rep(j, s.size()) {
      if (s.at(j) == s.at(s.size()-1-j)) tmp++;
    }
    if (tmp == s.size()) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define rep2(i,a,n) for(int i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using psi = pair<string, int>;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};
//const ll mod = 1e9+7;
int gcd(int a, int b){if(a<b) swap(a,b); if (a%b == 0){return(b);}else{return(gcd(b, a%b));}}
int lcm(int a, int b){return a * b / gcd(a, b);}

ll N, M, K, H, W, L, R;

int main(){
  cin >> N >> M;
  vvi A(N);
  rep(i,M){
    int a, b; cin >> a >> b; a--; b--;
    A[a].push_back(b);
    A[b].push_back(a);
  }
  
  for(int x : A[0]){
    for(int y : A[x]){
      if (y == N-1) {
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }     
  cout << "IMPOSSIBLE" << endl;
  return 0;
}

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

const ll MAXX = 1e13;

ll n, m;
ll res[1001][50001];

ll cost[10001];
vector<ll> ope[10001];

ll dp(ll pos, ll mask) {
	if (pos > m) {
		if (mask == ((1 << n) - 1)) {
			return 0;
		}
		return MAXX;
	}
	if (res[pos][mask] != -1) {
		//cerr << pos << '\n';
		return res[pos][mask];
	}
	ll sub = mask;
	for (ll i = 0; i < ope[pos].size(); i++) {
		ll x = ope[pos][i];
		sub |= (1 << (x - 1));
	}
	ll ans = MAXX;
	ans = min(ans, dp(pos + 1, mask));
	ans = min(ans, (dp(pos + 1, sub) + cost[pos]));
	res[pos][mask] = ans;
	return res[pos][mask];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("INP.txt", "r", stdin);
    //freopen("OUT.txt", "w", stdout);
	cin >> n >> m;
	memset(res, -1, sizeof(res));
	for (ll i = 1; i <= m; i++) {
		cin >> cost[i];
		ll x;
		cin >> x;
		for (ll j = 0; j < x; j++) {
			ll box;
			cin >> box;
			ope[i].push_back(box);
		}
	}
	ll ans = dp(1, 0);
	if (ans == MAXX) {
		cout << -1 << '\n';
	}
	else {
		cout << ans << '\n';
	}
	return 0;
}

Measured memory_bytes: 391680
<?php
// C
fscanf(STDIN, '%d %d %d', $n, $m, $x);
for ($i = 0; $i < $n; $i++) {
    $a[] = array_map('intval', explode(' ', trim(fgets(STDIN))));
}
$ans = -1;
// bit全探索
for ($i = 0; $i < 2 ** $n; $i++) {
    $sum = array_fill(0, $m + 1, 0);
    for ($j = 0; $j < $n; $j++) {
        if (($i >> $j) & 1) {
            for ($k = 0; $k < $m + 1; $k++) {
                $sum[$k] += $a[$j][$k];
            }
        }
    }
    for ($j = 1; $j < $m + 1; $j++) {
        if ($sum[$j] < $x) continue 2;
    }
    if ($ans === -1) {
        $ans = $sum[0];
    } else {
        $ans = min($ans, $sum[0]);
    }
}
echo $ans;

Measured memory_bytes: 16180
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

template <std::uint_fast64_t MOD> class ModInt {
  using u64 = std::uint_fast64_t;

public:
  ModInt(const u64 val = 0) { value = val % MOD; }

  ModInt operator+(const ModInt rhs) const { return ModInt(*this) += rhs; }
  ModInt operator-(const ModInt rhs) const { return ModInt(*this) -= rhs; }
  ModInt operator*(const ModInt rhs) const { return ModInt(*this) *= rhs; }
  ModInt operator/(const ModInt rhs) const { return ModInt(*this) /= rhs; }

  ModInt &operator+=(const ModInt rhs) {
    value += rhs.value;
    if (value >= MOD) {
      value -= MOD;
    }
    return *this;
  }

  ModInt &operator-=(const ModInt rhs) {
    if (value < rhs.value) {
      value += MOD;
    }
    value -= rhs.value;
    return *this;
  }

  ModInt &operator*=(const ModInt rhs) {
    value = value * rhs.value % MOD;
    return *this;
  }

  ModInt &operator/=(ModInt rhs) {
    *this *= rhs.inv();
    return *this;
  }

  ModInt &operator++(int n) {
    value++;
    if (value >= MOD) {
      value -= MOD;
    }
    return *this;
  }

  ModInt &operator--(int n) {
    if (value == 0) {
      value += MOD;
    }
    value--;
    return *this;
  }

  ModInt inv() { return ModInt::pow(*this, MOD - 2); }

  static ModInt pow(ModInt base, long long int n) {
    ModInt res = ModInt(1);
    while (n) {
      if (n & 1) {
        res *= base;
      }
      base *= base;
      n /= 2;
    }
    return res;
  }

  static ModInt comb(ModInt n, ModInt r) { return comb(n.value, r.value); }

  static ModInt comb(int n, int r) {
    if (n < r)
      return ModInt(0);
    ModInt res = ModInt(1);
    ModInt el = ModInt(1);
    for (int i = 1; i < n + 1; i++) {
      res *= el;
      el++;
    }

    ModInt inv = ModInt(1);
    el = ModInt(1);
    for (int i = 1; i < r + 1; i++) {
      inv *= el;
      el++;
    }
    el = ModInt(1);
    for (int i = 1; i < n - r + 1; i++) {
      inv *= el;
      el++;
    }
    res *= inv.inv();
    return res;
  }

  u64 getValue() const { return value; }

private:
  u64 value;
};

// ここを問題ごとのMODに書き換える
using mint = ModInt<1000000007>;

std::ostream &operator<<(std::ostream &out, const mint &m) {
  out << m.getValue();
  return out;
};

std::istream &operator>>(std::istream &in, mint &m) {
  uint_fast64_t i;
  in >> i;
  m = mint(i);
  return in;
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<mint> ncr(n + 1);
  vector<mint> n1cr(n);
  n1cr[0] = mint(1);
  ncr[0] = mint(1);
  FOR(i, 1, n + 1) { ncr[i] = ncr[i - 1] * mint(n - i + 1) / mint(i); }
  FOR(i, 1, n) { n1cr[i] = n1cr[i - 1] * mint(n - i) / mint(i); }

  mint ans(1);
  REP(i, min(k, n - 1)) { ans += n1cr[i + 1] * ncr[i + 1]; }
  cout << ans << endl;
  return 0;
}


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

int main(){
	int n;
	cin>>n;
	int ans=n%10;
	if(ans==2||ans==4||ans==5||ans==7||ans==9) cout<<"hon";
	else if(ans==0||ans==1||ans==6||ans==8) cout<<"pon";
	else if(ans==3) cout<<"bon";
	//cout<<ans;
	
	return 0;
}

Measured memory_bytes: 3676
package main
import (
  "fmt"
  "os"
)
func main() {
  var s,t string
  var n int
  fmt.Scan(&s)
  t = reverse(s)
  n = len(s)
  for i:=0;i<n;i++ {
    if t[i:i+1] == "b" && s[i:i+1] == "d" { continue }
    if t[i:i+1] == "d" && s[i:i+1] == "b" { continue }
    if t[i:i+1] == "p" && s[i:i+1] == "q" { continue }
    if t[i:i+1] == "q" && s[i:i+1] == "p" { continue }
    fmt.Println("No")
    os.Exit(0)
  }
  fmt.Println("Yes")
}
func reverse(s string) string {
  var r []rune = []rune(s)
  var n int = len(s)
  for i:=0;i<n-i;i++ {
    r[i],r[n-i-1] = r[n-i-1],r[i]
  }
  return string(r)
}

Measured memory_bytes: 1792
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

# class Combination:
#     """
#     comb = Combination(1000000)
#     print(comb(5, 3))  # 10
#     """
#     def __init__(self, n_max, mod=10**9+7):
#         self.mod = mod
#         self.modinv = self.make_modinv_list(n_max)
#         self.fac, self.facinv = self.make_factorial_list(n_max)

#     def __call__(self, n, r):
#         return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

#     def make_factorial_list(self, n):
#         # 階乗のリストと階乗のmod逆元のリストを返す O(n)
#         # self.make_modinv_list()が先に実行されている必要がある
#         fac = [1]
#         facinv = [1]
#         for i in range(1, n+1):
#             fac.append(fac[i-1] * i % self.mod)
#             facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
#         return fac, facinv

#     def make_modinv_list(self, n):
#         # 0からnまでのmod逆元のリストを返す O(n)
#         modinv = [0] * (n+1)
#         modinv[1] = 1
#         for i in range(2, n+1):
#             modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
#         return modinv


n,k = inpl()
g = [[] for i in range(n)]
seen = [-1]*n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def p(n,i):
    count = 1
    for _ in range(i):
        count = count * n % mod
        n -= 1
    return count
def dfs(cur,par=-1):
    res = 1
    c = 0 if par == -1 else 1
    cnt = 0
    for v in g[cur]:
        if v == par:
            continue
        cnt += 1
        res *= dfs(v,cur)
        res %= mod
    return res*p(k-c-1,cnt)
print(dfs(0,-1)*k%mod)

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

int main() {
int a[3][3],i,j,b[3][3];
for(i=0;i<3;i++)
{
   for(j=0;j<3;j++)
  { cin>>a[i][j];
    b[i][j]=0;
  }
}
int n;
cin>>n;
int arr[n];
for(i=0;i<n;i++)
cin>>arr[i];
int k,z=0;
for(k=0;k<n;k++)
{
   z=0;
  for(i=0;i<3;i++)
{
   for(j=0;j<3;j++)
  {
      if(arr[k]==a[i][j])
      {
          b[i][j]=1;
          z=1;
          break;
      }
      if(z==1)
      break;
  }
}  
}
int f=0,num=0;
for(i=0;i<3;i++)
{
   num=0;
   for(j=0;j<3;j++)
   {
       if(b[i][j]==1)
       num++;
   }
   if(num==3)
   f=1;
}
for(i=0;i<3;i++)
{
   num=0;
   for(j=0;j<3;j++)
   {
       if(b[j][i]==1)
       num++;
   }
   if(num==3)
   f=1;
}
if(b[0][0]==1&&b[1][1]==1&&b[2][2]==1)
f=1;
if(b[2][0]==1&&b[1][1]==1&&b[0][2]==1)
f=1;
if(f==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
typedef unsigned long long ull;
typedef long long ll;
#define MAX 200005
using namespace std;

int main() {
  int n;
  ll a;
  cin >> n;
  vector<ll> B(n);
  for(int i=0;i<n;i++) {
    cin >> a;
    B[i] = a-(i+1);
  }
  sort(B.begin(), B.end());
  ll half;
  if(n%2 == 0) {
    half = (B[n/2-1]+B[n/2]) / 2;
  } else {
    half = B[n/2];
  }
  ll max=0;
  for(int i=0;i<n;i++) {
    max += abs(B[i]-half);
  }
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 1792
import Control.Arrow
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = breads >>= print . solve . sort
    where
        solve [x, y, z] = x + y + z * 10
        
breads :: IO [Int]
breads = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

Measured memory_bytes: 380
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define ll long long
using namespace std;
const int MOD = 1000000007;
const long long INF = 1LL << 60;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<ll> a(n);
  bool flag = false;
  ll m = INF;
  ll cnt = 0;
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 0) {
      flag = true;
    }
    if (a[i] < 0) cnt++;
    m = min(m, abs(a[i]));
  }

  if (flag || cnt % 2 == 0) {
    ll num = 0;
    for (ll i = 0; i < n; i++) {
      num += abs(a[i]);
    }
    cout << num << endl;
    return 0;
  } else {
    ll num = 0;
    for (ll i = 0; i < n; i++) {
      num += abs(a[i]);
    }
    num -= 2 * m;
    cout << num << endl;
  }
}

Measured memory_bytes: 3968
#include <stdio.h>

int main(){
	int n, t, a, i, x, h[1000];
	double y[1000];

	scanf("%d", &n);
	scanf("%d", &t);
	scanf("%d", &a);
	x = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &h[i]);
		y[i] = t - h[i] * 0.006 -a;
		if (y[i] < 0) y[i] = -1 * y[i];
		if (y[x] >= y[i]) x =i;
	}
	x++;
	printf("%d", x);
}

Measured memory_bytes: 128
def main():
  n,m = list(map(int,input().split()))
  ab = [map(int, input().split()) for _ in range(n)]
  a, b = [list(i) for i in zip(*ab)]
  cd = [map(int, input().split()) for _ in range(m)]
  c, d = [list(i) for i in zip(*cd)]
  
  for i in range(0,n):
    min=abs(a[i]-c[0])+abs(b[i]-d[0])
    min_index=0
    for j in range(1,m):
      if min>abs(a[i]-c[j])+abs(b[i]-d[j]):
        min=abs(a[i]-c[j])+abs(b[i]-d[j])
        min_index=j
    print(min_index+1)
  
main()

Measured memory_bytes: 9232
N = int(input())
D = list(map(int, input().split()))

if D[0] > 0:
    print("0")
    exit()
    
D.pop(0)
list.sort(D)
if D[0] == 0:
    print("0")
    exit()
    
hoge = 0
nyoro = 1
huga = 1
ans = 1
for i in range(N-1):
    if D[i] == hoge:
        nyoro += 1
    elif D[i] == hoge + 1:
        ans *= huga ** nyoro
        hoge += 1
        huga = nyoro
        nyoro = 1
    else:
        print("0")
        exit()
ans *= huga ** nyoro
print(ans % 998244353)

Measured memory_bytes: 14396
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
template <class T>void UNIQUE(vector<T> &x){
	sort(all(x));
	x.erase(unique(all(x)), x.end());
}

// }}} End Header
inline ll kaijo(ll n){
	ll ans = 1;
	for(ll i=1; i<=n; i++){
		ans*=i;
		ans%=mod;
	}
	return ans;
}

int main() {
	ll n, m, ans = 0;
	cin >> n >> m;
	if(abs(n-m)>1){
		cout << 0 << endl;
		return 0;
	}
	ans = kaijo(n)*kaijo(m);
	if(n == m) ans*=2;
	cout << ans%mod << endl;
	return 0;
}


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

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

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

  int ans=INT_MAX;
  rep_eq(i,a.front(),a.back()) {
    int sum=0;
    rep(j,0,N) {
      int x=pow(a[j]-i,2);
      sum+=x;
    }
    ans=min(ans,sum);
  }

  cout <<ans <<endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int i, dice[7];
    char order[101];
    
    for(i=1;i<7;i++)
        scanf("%d", &dice[i]);
    
    scanf("%s", order);
    
    for(i=0;order[i]!='\0';i++){
        
        dice[0] = dice[1];
        
        switch(order[i]){
                
            case 'E':
                dice[1] = dice[4];
                dice[4] = dice[6];
                dice[6] = dice[3];
                dice[3] = dice[0];
                break;
                
            case 'N':
                dice[1] = dice[2];
                dice[2] = dice[6];
                dice[6] = dice[5];
                dice[5] = dice[0];
                break;
                
            case 'S':
                dice[1] = dice[5];
                dice[5] = dice[6];
                dice[6] = dice[2];
                dice[2] = dice[0];
                break;
                
            case 'W':
                dice[1] = dice[3];
                dice[3] = dice[6];
                dice[6] = dice[4];
                dice[4] = dice[0];
                break;
                
        }
    }
    
    printf("%d\n", dice[1]);
    
    return 0;
}


Measured memory_bytes: 2104
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

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

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

	string A, B;
	
	cin >> A >> B;

	if (A.size() > B.size())
	{
		cout << "GREATER" << endl;
	}
	else if (A.size() < B.size())
	{
		cout << "LESS" << endl;
	}
	else
	{
		int len = A.size();
		bool terminate = false;

		rep(i, len)
		{
			if (A[i] > B[i])
			{
				cout << "GREATER" << endl;
				terminate = true;
				break;
			}
			else if (A[i] < B[i])
			{
				cout << "LESS" << endl;
				terminate = true;
				break;
			}
		}
		if (!terminate)
		{
			cout << "EQUAL" << endl;
		}
	}

	
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define endl '\n'
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;


template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

const ll INF=1e9+7;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n),b(n);
    rep(i,n){
        cin >> a[i] >> b[i];
    }
    ll cnt=0;
    for(ll i=n-1;i>=0;i--){
        if(a[i]+cnt==0) continue;
        ll m=(a[i]+cnt-1)/b[i]+1;
        cnt+=m*b[i]-(a[i]+cnt);
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 4788
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000000;
const int mod = 1000000000+7;
const ll INF = 1LL << 60;
#define rep(i,n) for(ll i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
#define pp pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define fix(n) fixed<<setprecision(n)
#define itr vector<ll>::iterator
#define print(s) cout<<s<<endl
#define input(s) cin>>s
string s;
ll ans,n;
int main() {
	input(n);
	ans += n;
	s = to_string(n);
	rep(i, (1 << s.size() - 1)) {
		if (i == 0) { continue; }
		vector<ll>v;
		rep(j, s.size() - 1)if (1 & (i >> j))v.pb(j);
		v.pb(s.size() - 1);
		ll p = 0;
		rep(j, v.size()) {
			string ss = s.substr(p, v[j] + 1 - p);
			p = v[j]+1;
			ans += stoi(ss);
		}
	}
	print(ans);
	return 0;
}

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

int main () {
    int N; cin >> N;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) {
        cin >> p[i];
    }

    int max = *max_element(p.begin(), p.end());
    vector<int>::iterator maxIt = max_element(p.begin(), p.end());
    size_t maxIndex = distance(p.begin(), maxIt);

    ll sum = 0;
    for (int i = 0; i < N; ++i) {
        if (i == maxIndex) {
            sum += p[maxIndex] / 2;
        } else {
            sum += p[i];
        }
    }

    cout << sum << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x, y;
    cin >> x >> y;
    for(int i = 1;; i++){
        x *= 2;
        if(y < x){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,B=500;
int main(){
	scanf("%d",&n);
	B=min(B,n);cout<<B<<'\n';
	FOR(i,0,B-1)FOR(j,0,B-1) cout<<(i+j)%B+B*((i&1)&&(i+j)%B+B<n)+1<<char(j==B-1?'\n':' ');
}

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

#define M 1046527
#define L 14 

char H[M][L];

int getChar(char ch){
	if(ch=='A') return 1;
	else if(ch=='C') return 2;
	else if(ch=='G') return 3;
	else if(ch=='T') return 4;
	else return 0;
}

long long getKey(char str[]){
	long long sum=0,p=1,i;
	for(i=0;i<strlen(str);i++){
	sum+=p*(getChar(str[i]));
	p*=5;
	}
	return sum;
}

int h1(int key){
	return key%M;
}

int h2(int key){
	return 1+(key%(M-1));
}

int insert(char str[]){
	long long key,i,h;
	
	key=getKey(str);
	for(i=0;;i++) {
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0){
			strcpy(H[h],str);
			return 0;
		}
	}
	
	return 0;
}

int find(char str[]){
	long long key,i,h;
	key=getKey(str);
	
	for(i=0;;i++) {
		h=(h1(key)+i*h2(key)) % M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0)return 0;
	}
	return 0;
}


int main(){
	int i,n,h;
	char str[L],com[9];
	for(i=0;i<M;i++)H[i][0]=0;
	scanf("%d", &n);
	
	for(i=0;i<n;i++){
		scanf("%s %s",com,str);
		if(com[0]=='i'){
			insert(str);
		}else{
			if(find(str)){
				printf("yes\n");
	    	}else{
				printf("no\n");
	    	}
		}
	}
	
	return 0;
}




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

int main(){
    int a;
    cin >> a;
    vstring A(a);

    rep(i,a){
        cin >> A[i];
        sort(A[i].begin(),A[i].end());
    }
    //rep(i,a) cout << A[i] << endl;
    map<string,ll> count;
    ll ans = 0;
    rep(i,a){
        if(count[A[i]] == 0) count[A[i]] = 1;
        else{
            ans += count[A[i]];
            count[A[i]]++;
        }
    }
    //rep(i,a) cout << count[A[i]] << endl;
    cout << ans << endl;
}

Measured memory_bytes: 18176
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int f(int n){
    if(n > 36) return 0;
    int a[4], count = 0;

    for(a[0] = 0;    a[0] <= 9; a[0]++){
    for(a[1] = a[0]; a[1] <= 9; a[1]++){
    for(a[2] = a[1]; a[2] <= 9; a[2]++){
    for(a[3] = a[2]; a[3] <= 9; a[3]++){
        if(a[0] + a[1] + a[2] + a[3] == n){
            do {
                count++;
            }while(next_permutation(a, a+4));
        }
    }}}}
    return count;
}

int main(){
    int n;
    while(cin >> n){
        cout << f(n) << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;

int main()
{
  ll N;
  cin >> N;
  vector<vector<ll>> vec(N,vector<ll> (3));
  REP(i,N){
    cin >> vec.at(i).at(1) >> vec.at(i).at(2);
    vec.at(i).at(0)=vec.at(i).at(1)+vec.at(i).at(2);
  }

  sort(ALL(vec));
  reverse(ALL(vec));
  ll tk = 0;
  ll ao = 0;
  REP(i,N){
    if(i%2==0){
      tk+=vec.at(i).at(1);
    }else{
      ao+=vec.at(i).at(2);
    }
  }

  cout << tk-ao << endl;
}

Measured memory_bytes: 8772
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n, m, a, b;
string str;

int main(){
	cin >> n >> m;
	vector<P> job;
	
	for(ll i = 1; i <= n; i++){
		cin >> a >> b;
		job.push_back(P(-b, a));
	}
	sort(job.begin(), job.end());
	
	set<ll> unuse;
	for(ll j = 0; j < m; j++){unuse.insert(-j);}

	ll ans = 0;
	for(ll i = 0; i < n; i++){
		a = job[i].second;
		b = -job[i].first;
		auto it = unuse.lower_bound(-m+a);
		//cout << m-a << b << *it << endl;
		if(it != unuse.end()){
			ans += b;
			unuse.erase(it);
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6512
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
bool dpx[4002][16020];
int main(){
  bool flag = true,fF=true,xOK=false,yOK=false;
  int x,y,num=0,i,j;
  string s;
  cin >> s;
  cin >> x >> y;
  vector<int> xf,yf;
  s+='T';
  if(s[0]=='T')fF=false;
  for(i=0;i<s.size();i++){
    if(s[i]=='F')num++;
    else{
      if(flag){
        xf.push_back(num);
        flag = false;
      }else{
        yf.push_back(num);
        flag = true;
      }
      num = 0;
    }
  }
  dpx[0][8000+xf[0]]=true;//
  for(i=1;i<xf.size();i++){
    for(j=0;j<16001;j++){
      if(j+xf[i]<16001)dpx[i][j] |= dpx[i-1][j+xf[i]];
      if(j-xf[i]>-1)dpx[i][j] |= dpx[i-1][j-xf[i]];
    }
  }
  //cout << dpx[1][8000+x] << endl;
  if(dpx[i-1][8000+x])xOK=true;
  fill(dpx[0],dpx[4002],0);
  dpx[0][8000]=true;
  for(i=1;i<=yf.size();i++){
    for(j=0;j<16001;j++){
      if(j+yf[i-1]<16001)dpx[i][j] |= dpx[i-1][j+yf[i-1]];
      if(j-yf[i-1]>-1)dpx[i][j] |= dpx[i-1][j-yf[i-1]];
    }
  }
  //cout << dpx[i][8000+y]<< endl;
  if(dpx[i-1][8000+y])yOK=true;
  if(xOK && yOK)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

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

  string S; cin >> S;
  string keyence = "keyence";

  int l = 0, r = 0;
  for (int i = 0; i < keyence.size(); i++) {
    if (S[i] == keyence[i]) l++;
    else break;
  }
  for (int i = 0; i < keyence.size(); i++) {
    if (S[S.size() - 1 - i] == keyence[keyence.size() - 1 - i]) r++;
    else break;
  }

  string ans = "NO";
  if (l + r >= keyence.size()) {
    ans = "YES";
  }
  cout << ans << '\n';
  return 0;
}

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

int main() {
  int N; cin >> N;
  vector<string> S(N);
  for (int i = 0; i < N; i++) cin >> S[i];
  sort(S.begin(), S.end());
  
  int ans = 1;
  for (int i = 1; i < N; i++) {
    if (S[i] == S[i-1]) continue;
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 9524
from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))
a.sort()
asum = list(accumulate(a))

ans = 0
for i in range(n-1):
  if asum[i]*2>=a[i+1]:
    ans += 1
  else:
    ans = 0
print(ans+1)

Measured memory_bytes: 91512