akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    #[allow(unused_mut)]
    let mut s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

const MOD: i64 = 1e9 as i64 + 7;

fn solve(vs: &Vec<Vec<usize>>, x: usize, parent: Option<usize>) -> (i64, i64) {
  let mut black = 1;
  let mut white = 1;
  for &child in vs[x].iter() {
    if let Some(parent) = parent {
      if child == parent {
        continue;
      }
    }
    let (b, w) = solve(&vs, child, Some(x));
    black = black * w % MOD;
    white = white * (b + w) % MOD;
  }
  (black, white)
}

fn main() {
  input!{
    n: usize,
    es: [(usize1, usize1); n-1]
  }
  let mut vs = vec![vec![]; n];
  for &(x, y) in es.iter() {
    vs[x].push(y);
    vs[y].push(x);
  }
  let (black, white) = solve(&vs, 0, None);
  println!("{}", (black + white) % MOD);
}


Measured memory_bytes: 24316
#include <stdio.h>

void BubbleSort(int a[],int n){
  int i,j,temp,cnt=0;

  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(a[j-1]>a[j]){
        temp=a[j];
        a[j]=a[j-1];
        a[j-1]=temp;
        cnt++;
      }
    }
  }

  for(i=0;i<n;i++){
    if(i>0)printf(" ");
    printf("%d",a[i]);
  }
  printf("\n");
  printf("%d\n",cnt);

}

int main(void){
  int n,a[100],i;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }

  BubbleSort(a,n);

  return 0;
}

Measured memory_bytes: 1800
#include <iostream>

using namespace std;

int main() {
	int n, t, a[200000],ans = 0;
	cin >> n >> t;
	for (int i = 0; i < n; i++)cin >> a[i];

	for (int i = 0; i < n;) {
		int st = a[i], en = a[i] + t;
		while (i < n && a[i] <= en) {
			en = a[i] + t;
			i++;
		}
		ans += en - st;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
struct data{
    int x;
    int y;
    int h;
};
int main(){
    
    bool flag=false;
    data temp;
    vector<data> position;
    int N,H,rank;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> temp.x >> temp.y >> temp.h;
        position.push_back(temp);
        if(temp.h!=0) rank=i;
    }
    
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            H=position[rank].h+abs(i-position[rank].x)+abs(j-position[rank].y);
            for(int k=0;k<N;k++){
                if(position[k].h!=0){
                    if(H!=position[k].h+abs(i-position[k].x)+abs(j-position[k].y)){
                        flag=true;
                        break;
                    }
                } else {
                    if(H>position[k].h+abs(i-position[k].x)+abs(j-position[k].y)){
                        flag=true;
                        break;
                    }
                }
            }
            if(flag){
                flag=false;
            } else {
                cout << i << ' ' << j << ' ' << H;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("avx,avx2,fma")
using namespace std;

#define _ << ": " <<
#define watch1(var1) (cerr << (#var1) _ var1 << '\n')
#define watch2(var1, var2) cerr << (#var1) _ var1 << ", " << (#var2) _ var2 << '\n'
#define watch3(var1, var2, var3) cerr << (#var1) _ var1 << ", " << (#var2) _ var2 << ", " << (#var3) _ var3 << '\n'
#define wloop(size, arr) cerr << (#arr) << ": "; for (int i = 0; i < size; i++) cerr << arr[i] << " \n"[i+1 == size]

template<typename... Args>
void read(Args&... args) { ((cin >> args), ...); }

template<typename... Args>
void show(Args... args) { ((cout << args << " "), ...); }

#define ints(a...) int a; read(a)
#define longs(a...) int64_t a; read(a)
#define IN(a) for (auto &it : a) cin >> it

const int N = 1e6 + 1;

void solve() {
    ints(n);
    vector<int> v(n);
    vector<int> fq(N);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        fq[v[i]]++;
    }
    int cnt = 0;
    for (int i = 1; i < N; i++) {
        if (fq[i] == 1) cnt++;
        if (fq[i]) for (int j = i + i; j < N; j += i) fq[j] = 0;
    }
    show(cnt);
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1; 
    // cin >> T;
    while (T--) solve();
    return 0;
}




Measured memory_bytes: 7896
l = input().split()
n1 = int(l[0])
n0 = int(l[1])
n = int(l[2])
k = int(l[3])

ans = 0

if k >= n1:
    ans += n1

else:
    ans += k

k -= n1

k -= n0

if k > 0:
    ans -= k

print(ans)

Measured memory_bytes: 9192
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
int main()
{
	long N, S;
	cin >> N >> S;
	long waru = 998244353;
	vector<long> dp(S + 1);//パターン、初期値を掛ける
	vector<long> pure(S + 1), filled(S+1);//初期値とそこに紐づくパターン数
	vector<long> A(N);
	for (long& a : A) {
		cin >> a;
	}
	long count = 0;
	for (int i = 0; i < N; i++)
	{
		pure = vector<long>(S + 1);
		for (int k = S + 1 - A[i]-1; k >=0 ; k--)
		{
			if (k + A[i] == S) {
				count =(count+ dp[k] * (N - i) )% waru;
				/*for (int m = 0; m < dp[k].size(); m++)
				{
					count += (dp[k][m] + 1) * (N - i) % waru;
					//break;
				}*/
			}
			else if (pure[k] == 0 && filled[k]==1) {
				dp[k + A[i]] = (dp[k + A[i]] + dp[k])%waru;//.insert(dp[k + A[i]].end(), dp[k].begin(), dp[k].end());
				pure[k + A[i]] = 1;
				filled[k+A[i]] = 1;
			}


		}
		if (A[i] < S) {
			dp[A[i]]+=i+1;
			filled[A[i]] = 1;
		}
		if (A[i] == S)
		{
			count =(count+ (N - i) * (i + 1)) % waru;
		}

	}
	cout << count;
	return 0;
}

Measured memory_bytes: 384
def max(a,b); a > b ? a : b end
def min(a,b); a < b ? a : b end
def swap(a,b); a, b = b, a  end
def yn(f); puts f ? "Yes" : "No" end

def yes(f=nil); f.nil? ? (puts "Yes"; exit) : (puts f ? "Yes" : "No") end
def no(f=nil);  f.nil? ? (puts "No";  exit) : (puts f ? "No" : "Yes") end

inf = Float::INFINITY
mod = 10 ** 9 + 7

n = gets.to_s.to_i
#a = gets.to_s.split.map{|e|e.to_i}
#m = Array.new(n){ gets.to_s.split.map{|e|e.to_i} }
#s = gets.to_s.chomp

if [2, 4, 5, 7, 9].include?(n%10)
  puts "hon"
elsif [0, 1, 6, 8].include?(n%10)
  puts "pon"
else
  puts "bon"
end

Measured memory_bytes: 14248
n = int(input())

arms = []
for i in range(n):
  x, l = [int(i) for i in input().split(' ')]
  arms.append({"st": x-l, "ed": x+l})

arms.sort(key=lambda x: x["ed"])

n_arm = 1
tot_end = arms[0]["ed"]

for i in range(1, n):
  if tot_end <= arms[i]["st"]:
    n_arm += 1
    tot_end = arms[i]["ed"]

print(n_arm)


Measured memory_bytes: 41696
from collections import Counter
n = int(input())
lst = list(map(int, input().split()))

lst1 = lst[::2]
lst2 = lst[1::2]

count1 = Counter(lst1)
count2 = Counter(lst2)
  
if count1.most_common()[0][0] != count2.most_common()[0][0]:
  ans = n - count1.most_common()[0][1] - count2.most_common()[0][1]

else:
  if len(count1) != 1 and len(count2) != 1:
    k = max(count1.most_common()[0][1] + count2.most_common()[1][1], count1.most_common()[1][1] + count2.most_common()[0][1])
    ans = n - k
  elif len(count1) == 1 and len(count2) == 1:
    ans = n//2
  else:
    if len(count1) < len(count2):
      ans = n//2 - count2.most_common()[0][1]
    else:
      ans = n//2 - count1.most_common()[0][1]
print(ans)

Measured memory_bytes: 19040
# C - Switches

N, M = map(int, input().split())
ks = []
for i in range(M):
    ks.append(list(int(x) for x in input().split()))
p = list(int(x) for x in input().split())

ans = 0
for i in range(2**N):
    # flg:一つでも電球が点灯しない場合はFalse
    flg = True
    for j in range(M):
        # cnt:電球ごとのスイッチONの数
        cnt = 0
        for k in range(ks[j][0]):
            if i>>(ks[j][k+1]-1)&1:
                cnt += 1
        if p[j]!=(cnt%2):
            flg = False
    if flg == True:
        ans += 1

print(ans)

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
//////////////
int cal(int N) {
	int ter = 0;
	while (N) {
		ter += (N % 10);
		N /= 10;
	}
	return ter;
}
void solve() {
	int N, A, B;
	cin >> N >> A >> B;
	int ans = 0;
	for (int i = 1; i <= N; ++i) {
		int ter = cal(i);
		if (A <= ter && ter <= B) {
			ans += i;
		}
	}
	cout << ans << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 256
import java.util.Scanner;

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

        int N = sc.nextInt();
        int M = sc.nextInt();

        System.out.println(solve(N, M));

        sc.close();
    }

    static int solve(int N, int M) {
        int result = -1;
        for (int i = 1; i * i <= M; ++i) {
            if (M % i == 0) {
                if (i >= N) {
                    result = Math.max(result, M / i);
                }
                if (M / i >= N) {
                    result = Math.max(result, i);
                }
            }
        }

        return result;
    }
}

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

const int maxn=5005;
const int mod=1e9+7;
int n,m,mm,sz,ans,k;
bool bad;
int p[maxn],a[maxn],pw[maxn],fac[maxn];
int dp[maxn],f[maxn],g[maxn];
vector<int>edge[maxn];
bool vis[maxn];

void Add(int &a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}

void dfs(int x){
	vis[x]=true;
	sz++;
	if(!~p[x])bad=true;
	for(int i=0;i<int(edge[x].size());i++)
		if(!vis[edge[x][i]])dfs(edge[x][i]);
}

int main(){
	scanf("%d",&n);
	fac[0]=pw[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=1LL*fac[i-1]*i%mod;
		pw[i]=1LL*pw[i-1]*(n-1)%mod;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
		if(~p[i])edge[i].push_back(p[i]),edge[p[i]].push_back(i);
		else k++;
	}
	for(int i=1;i<=n;i++)if(!vis[i]){
		sz=0;
		bad=false;
		dfs(i);
		if(bad)a[++m]=sz;
		else mm++;
	}
	ans=1LL*mm*pw[k]%mod;
	dp[0]=1;
	for(int i=1;i<=m;i++)
		for(int j=i-1;j>=0;j--)
			Add(dp[j+1],1LL*dp[j]*a[i]%mod);
	dp[1]=(dp[1]+mod-m)%mod;
	for(int j=1;j<=m;j++)
		Add(ans,1LL*dp[j]*fac[j-1]%mod*pw[m-j]%mod);
	printf("%d\n",int((1LL*n*pw[k]+mod-ans)%mod));
	return 0;
}

Measured memory_bytes: 4144
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ARC094C {
    class Program {
        static void Main(string[] args) {
            int[] input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            Array.Sort(input);
            int A = input[0];
            int B = input[1];
            int C = input[2];
            int fir = C - B;
            int sec = -1000;
            if ((C - (A + fir)) % 2 == 0) {
                sec = (C - (A + fir)) / 2;
            } else {
                sec = (C - (A + fir)) / 2 + 2;
            }
            Console.WriteLine(fir + sec);
        }
    }
}


Measured memory_bytes: 13396
n=int(input())
s=input()
c=s.count
a=c('R')*c('G')*c('B')
for i in range(n):
  for j in range(i+2,n,2):
    if s[i]!=s[i+j>>1]!=s[j]!=s[i]:
      a-=1
print(a)

Measured memory_bytes: 67980
//**KEEP IT SHORT AND SIMPLE**

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define REP(i,a,b) for (int i = a; i < b; i++)
#define NL '\n'
#define F first
#define S second
#define dot(a, b) (conj(a) * (b)).real()
#define cross(a, b) (conj(a)* (b)).imag()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef bool bl;
typedef vector < vector<long long> > vvl;
typedef vector <long long> vll;
typedef pair <long long, long long> pll;
typedef map <long long, long long> mll;
typedef map <long long, bool> mlb;
typedef priority_queue<long long, vector<long long>, greater<long long> > minPq;
typedef tuple<ll, ll, ll> line;
typedef complex<double> point;
const double pi = 2 * acos(0.0);
const int OO = 0x3f3f3f3f;
ll ans[100005][5];
int main()
{
    IO
    ll n, Max = 0;
    cin >> n;
    ll arr[n][3];
    REP(i, 0, n)
        REP(j, 0, 3)
            cin >> arr[i][j];
    REP(i, 0, 3)
        ans[0][i] = arr[0][i];
    REP(i, 1, n)
    {
        ans[i][0] = max(ans[i - 1][1], ans[i - 1][2]) + arr[i][0];
        ans[i][1] = max(ans[i - 1][0], ans[i - 1][2]) + arr[i][1];
        ans[i][2] = max(ans[i - 1][0], ans[i - 1][1]) + arr[i][2];
    }
    REP(i, 0, 3)    Max = max(Max, ans[n - 1][i]);
    cout << Max;
    return 0;
}


Measured memory_bytes: 6528
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>


typedef long double ld;
typedef long long ll;

using namespace std;

string builds(int a, int b) {
	char c = b + '0';
	string ret = "";
	for (int i = 0; i < a; i++) {
		ret += c;
	}
	return ret;
}

int main() {
	int a, b;
	string s1, s2;
	cin >> a >> b;
	s1 = builds(a, b);
	s2 = builds(b, a);
	if (s1 < s2) {
		cout << s1 << endl;
	} else {
		cout << s2 << endl;
	}

	return 0;
}


Measured memory_bytes: 3016
#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define FOR(i, first, last) for (int i = (first); i < (last); ++i)
#define REP(i, n) FOR(i, 0, n)
#define CLR(a) memset((a), 0, sizeof(a))
#define DUMP(x) std::cerr << #x << " = " << (x) << std::endl;

inline int to_int(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T> inline string to_string(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

typedef unsigned long long ull;
typedef unsigned long ul;

int main() {
  ull N;
  cin>>N;
  
  ull m = (ull)std::sqrt(N);
  cout << m*m << endl;

  return 0;
}


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

int ans;
bool mark[10][10];

void init()
{
for(int i=0;i<10;i++)
{
    for(int j=0;j<10;j++)
    mark[i][j]=false;
}
}

int main()
{

ans=0;

int H,W,K;
cin>>H>>W>>K;
char c[10][10];

for(int i=0;i<H;i++)
{
for(int j=0;j<W;j++)
cin>>c[i][j];
}

for(int h=0;h<(1<<H);h++)
{
    for(int w=0;w<(1<<W);w++)
    {
        init();int count =0;
        for(int i=0;i<H;i++)
        {
            if(h & (1<<i)) 
            {for(int m=0;m<W;m++)
            mark[i][m]=true;
            }
        }
        for(int j=0;j<W;j++)
        {
            if(w & (1<<j)) 
            {for(int n=0;n<H;n++)
            mark[n][j]=true;
            }
        }
        for(int i=0;i<H;i++)
        {
            for(int j=0;j<W;j++)
            if(c[i][j]=='#' && mark[i][j]==false)count++;
        }
        if(count==K)ans++;
    }
}
cout <<ans;   
}

Measured memory_bytes: 3612
#include<iostream>
using namespace std;
int main(){
	long long int n,hap=0;
	cin>>n;
	while(n>=500){
			n-=500;
			hap+=1000;
		}
    while(n>=5){
    	n-=5;
    	hap+=5;
    }
    cout<<hap;
	return 0;
}

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

const int INF = 1 << 29;

int N, M, S[100], D[100];

int his[1 << 15][100];
int dp[1 << 15];

int solve() {
    fill(dp, dp + (1 << N), INF);
    {
        int sum_d = 0;
        for (int i = 0; i < M; ++i) {
            sum_d += D[i];
            his[0][i] = D[i];
        }
        dp[0] = sum_d;
    }

    for (int b = 1; b < (1 << N); ++b) {
        int sw = 0;
        for (int i = 0; i < N; ++i)
            if ((b & (1 << i)) != 0) sw += S[i];

        for (int i = 0; i < N; ++i) {
            if ((b & (1 << i)) == 0) continue;

            int bb = b ^ (1 << i);
            int nhis[100], cost = 0;
            for (int j = 0; j < M; ++j) {
                nhis[j] = min(his[bb][j], abs(D[j] - sw));
                cost += nhis[j];
            }
            if (cost < dp[b]) {
                dp[b] = cost;
                for (int j = 0; j < M; ++j)
                    his[b][j] = nhis[j];
            }
        }
    }

    return dp[(1 << N) - 1];
}

int main(void) {
    while (true) {
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        for (int i = 0; i < N; ++i) { cin >> S[i]; }
        for (int i = 0; i < M; ++i) { cin >> D[i]; }
        sort(D, D+M);
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 16040
import java.util.Scanner;

public class Main {

	static int n, m;
	static int[] a, b;
	static boolean[] vis;
	static boolean[][] connected;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		a = new int[m]; b = new int[m]; connected = new boolean[n][n]; vis = new boolean[n];
		for(int i = 0 ; i < m ; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			a[i]--; b[i]--;
			connected[a[i]][b[i]] = connected[b[i]][a[i]] = true;
		}
		int ans = 0;
		for(int i = 0 ; i < m ; i++) {
			for(int j = 0 ; j < n ; j++) {
				vis[j] = false;
			}
			connected[a[i]][b[i]] = connected[b[i]][a[i]] = false;
			dfs(0);
			boolean bridge = false;
			for(int j = 0 ; j < n ; j++) {
				if(vis[j] == false) bridge = true;
			}
			if(bridge == true) ans++;
			connected[a[i]][b[i]] = connected[b[i]][a[i]] = true;
		}
		System.out.println(ans);
	}

	public static void dfs(int x) {
		if(vis[x] == true) return;
		vis[x] = true;
		for(int i = 0 ; i < n ; i++) {
			if(connected[x][i] == true) {
				dfs(i);
			}
		}
	}
}

Measured memory_bytes: 23892
def main():
    N, A, B = map(int, input().split())
    cnt = 0
    for i in range(1, N + 1):
        val = sum(list(map(int, list(str(i)))))
        if A <= val <= B:
            cnt += i
    print(cnt)


if __name__ == '__main__':
    main()

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

int main(){
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	k++;
	// should get all numbers to at least k+1;

	int asum = 0;
	int amax = 0;
	for(int i = 0; i < n; i++){
		a[i] = k - a[i];
		if(a[i] < 0) a[i] = 0;
		asum += a[i];
		amax = max(amax, a[i]);
	}
	if(asum > k-1 || amax > (k - amax) ){
		cout << -1 << '\n';
		return 0;
	}
	vector<set<int> > f(k);
	vector<int> bb(k-1);
	for(int i = 0; i < k; i++){
		for(int j = 0; j < n; j++){
			f[i].insert(j);
		}
	}
	int last_val = -1;
	for(int s = 0; s < k-1; s++){
		int best = (last_val + 1) % n;
		for(int i = 0; i < n; i++){
			if(i == last_val) continue;
			if(a[i] > a[best]){
				best = i;
			}
		}
		last_val = best;
		bb[s] = best;
		f[s].erase(best);
		f[s+1].erase(best);
		a[best]--;
	}

	vector<int> ans;
	for(int i = 0; i < k; i++){
		if(i > 0) ans.push_back(bb[i-1]);
		for(int x : f[i]){
			ans.push_back(x);
		}
	}
	cout << int(ans.size()) << '\n';
	for(int x : ans){
		cout << x + 1 << ' ';
	}
	cout << '\n';
}

Measured memory_bytes: 384
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
const int INF = 1000000000;
const int MOD = 1000000009;
const ll INFL = 1e18;
int dp[1000005][2];
int main(){
	string s;
	cin >> s;
	reverse(s.begin(),s.end());
	s += '0';
	int n = s.size();

	for(int i = 0;i <= n;i++){
		for(int j = 0;j < 2;j++){
			dp[i][j] = INF;
		}
	}

	dp[0][0] = 0;
	for(int i = 0;i < n;i++)for(int j = 0;j < 2;j++){
		int x = s[i] - '0';
		x += j;
		for(int a = 0;a < 10;a++){
			int ni = i+1,nj = 0;
			int b = a-x;
			if(b < 0){
				nj = 1;
				b += 10;
			}
			dp[ni][nj] = min(dp[ni][nj],dp[i][j]+a+b);
		}
	}

	int ans = dp[n][0];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 9220
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
  int H,W;
  cin >> H >> W;
  bool elmnt;
  vector<bool> hcheckline(H),wcheckline(W);
  vector<vector<char>>data(H,vector<char>(W));
  REP(i,H){
    REP(j,W)cin >> data.at(i).at(j);
  }

  REP(i,H){
    elmnt=1;
    REP(j,W){
      if(data.at(i).at(j)=='#'){
	elmnt=0;
	wcheckline.at(j)=1;
      }
    }
    if(elmnt==0)hcheckline.at(i)=1;
  }

  //output
  REP(i,H){
    if(hcheckline.at(i)==1){
      REP(j,W){
	if(wcheckline.at(j)==1){
	  cout << data.at(i).at(j);
	}
      }
      cout << endl;
    }
  }
}


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

using namespace std;

int main() {
	//int x;
	//cin>>x;
	//x -= 400;
	//x /= 200;
	
	//cout<< 8 - x<<endl;
	
	int a, b, c, k;
	cin>>a>>b>>c>>k;
	
	while(b <= a) {
		b = 2*b;
		k--;
	}
	while(c <= b) {
		c *= 2;
		k--;
	}
	if(k >= 0)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main(){
  long long A,B;
  double k;
  cin >> A >> B;
  if((A+B) % 2 == 0){
    cout << (A+B)/2 << endl;
  }else{
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};

int cnt[100000];


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);


    ll n;
    cin>>n;

    for(ll i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            for(int k=1;k<=100;k++){
                cnt[i*i+j*j+k*k+i*j+i*k+j*k]++;
            }
        }
    }
    for(int i=1;i<=n;i++)cout << cnt[i] << endl;
}

Measured memory_bytes: 3840
import math
n = int(input())

ans = 0
for i in range(n):
    for j in range(n):
        if i > j:
            continue
        for k in range(n):
            if j > k:
                continue
            # print(i, j, k)
            g = math.gcd(i+1, math.gcd(j+1, k+1))
            # print(math.gcd(i+1, math.gcd(j+1, k+1)))
            if i != j and j != k:
                ans += g * 6
            elif i == j and j == k:
                ans += g
            else:
                ans += g * 3
            # ans += math.gcd(i+1, math.gcd(j+1, k+1))

print(ans)

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

int main(){
	int N, X, Y, i, j;
	scanf("%d%d%d", &N, &X, &Y);
	X--;
	Y--;
	vector<int> ans(N, 0);
	for(i = 0; i < N; i++){
		for(j = i + 1; j < N; j++){
			ans[min(j - i, abs(X - i) + abs(Y - j) + 1)]++;
		}
	}
	for(i = 1; i < N; i++){
		printf("%d\n", ans[i]);
	}
	return 0;
}

Measured memory_bytes: 256
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	a := nextInts(n)
	sort.Sort(sort.IntSlice(a))

	ans := n
	double := 0
	for l := 0; l < n; {
		r := l
		for r+1 < n && a[r+1] == a[l] {
			r++
		}
		cnt := r - l + 1
		if cnt%2 == 0 {
			double++
		}
		if cnt > 2 {
			ans -= ((cnt - 1) / 2) * 2
		}
		l = r + 1
	}

	ans -= ((double + 1) / 2) * 2

	puts(ans)
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <cstdlib>
#include <utility>
#include <climits>
#include <queue>
#include <cmath>
using namespace std;

// ori: 0 = 右向き, 1 = 下向き, 2 = 左向き, 3 = 上向き
struct state{
    int cost, x, y, ori;
    state(int c_, int x_, int y_, int ori_) : cost(c_), x(x_), y(y_), ori(ori_){}
    bool operator>(const state& other) const {
        return cost > other.cost;
    }
};

template<class T>
using Matrix = vector<vector<T>>;

int c[4];
int w, h;
// 右下左上
constexpr int dx[] = {1, 0, -1, 0};
constexpr int dy[] = {0, 1, 0, -1};

int dijkstra(const Matrix<int>& m){
    priority_queue<state, vector<state>, greater<state>> q;
    q.push(state(0, 0, 0, 0));
    // d[x][y][(x, y)にいる時のロボットの向き]
    Matrix<vector<int>> d(w, vector<vector<int>>(h, vector<int>(4, INT_MAX)));
    d[0][0][0] = 0;

    while(!q.empty()){
        state s = q.top();
        q.pop();

        if(s.x == w-1 && s.y == h-1) break;

        for(int ope = 0; ope < 4; ++ope){ // 全ての命令を行う
            int cost = 0;
            int ori = s.ori;
            if(ope != m[s.x][s.y]) cost = c[ope];
            if(ope != 0){ // 向きを変える
                if(ope == 1) ori = (ori + 1) % 4;// 右折
                else if(ope == 2) ori = (ori + 2) % 4; // 反転
                else ori = (ori + 3) % 4; // 左折
            }
            int next_x = s.x + dx[ori];
            int next_y = s.y + dy[ori];
            if(next_x < 0 || next_x >= w) continue;
            if(next_y < 0 || next_y >= h) continue;
            if(d[next_x][next_y][ori] > d[s.x][s.y][s.ori] + cost){
                d[next_x][next_y][ori] = d[s.x][s.y][s.ori] + cost;
                q.push(state(d[next_x][next_y][ori], next_x, next_y, ori));
            }
        }
    }

    int ans = INT_MAX;

    for(int e : d[w-1][h-1]) ans = min(ans, e);

    return ans;
}

int main(){
    while(true){
        cin >> w >> h;
        if(!w) break;
        Matrix<int> m(w, vector<int>(h));

        for(int i = 0; i < h; ++i)
            for(int j = 0; j < w; ++j)
                cin >> m[j][i];

        for(int i = 0; i < 4; ++i) cin >> c[i];

        cout << dijkstra(m) << endl;
    }

    return EXIT_SUCCESS;
}



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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main()
{
    string S;
    cin >> S;

    REP(i,3){
        if(S[i] == S[i+1]){
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 100010;
const int L = 11;

int f[N][L];
struct edge{
	int x,nxt;
}e[N*2];
int h[N],tot;
int n,m,q;
int col[N],val[N];

void inse(int x,int y){
	e[++tot].x=y;
	e[tot].nxt=h[x];
	h[x]=tot;
}

int main(){
	n=get();m=get();
	fo(i,1,m){
		int x=get(),y=get();
		inse(x,y);
		inse(y,x);
	}
	q=get();
	fo(i,1,q){
		int x=get(),d=get(),c=get();
		f[x][d]=i;
		val[i]=c;
	}
	fd(i,10,1)
		fo(x,1,n){
			for(int p=h[x];p;p=e[p].nxt)
			f[e[p].x][i-1]=max(f[e[p].x][i-1],f[x][i]);
			f[x][i-1]=max(f[x][i-1],f[x][i]);
		}
	fo(i,1,n)printf("%d\n",val[f[i][0]]);
	return 0;
}

Measured memory_bytes: 7296
N = int(input())
*b, = map(int, input().split())
ans = []

for i in range(N)[::-1]:
    n = i+1
    if b[i]:
        ans.append(n)
        
        tmp = 1
        while tmp*tmp <= n:
            if n % tmp == 0:
                b[tmp-1] ^= 1
                if tmp != n//tmp:
                    b[n//tmp-1] ^= 1
            tmp += 1

M = len(ans)
print(M)
if ans:
    print(*ans)


Measured memory_bytes: 73436
N,Q = map(int,input().split())
s = input()

cnt = 0
n = [0]
for i in range(N-1):
    if s[i]+s[i+1] == 'AC':
        cnt += 1
    n.append(cnt)


for i in range(Q):
    l,r = map(int,input().split())
    print(n[r-1]-n[l-1])

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

int main() {
  int a, b, c, x, y; cin >> a >> b >> c >> x >> y;
  int total = min(a+b, 2*c) * min(x, y) + (max(x, y) - min(x, y)) * min((min(x, y) == x ? b : a), 2*c);
  cout << total << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

#define ll long long
#define ull unsigned long long

#define	max	1000000007

ll gcd(ll a, ll b) {
	if (a < b)
		swap(a, b);
	while (ll r = a % b)
		a = b, b = r;
	return b;
}

class mod
{
public:
	ll val;

	mod(ll v)
	{
		val = v % max;
	}

	mod()
	{
		val = 0;
	}

	void operator -=(const mod &v)
	{
		val -= v.val;

		if (val < 0)
			val += max;
	}

	void operator +=(const mod &v)
	{
		if (val + v.val >= max)
			val -= max;
		val += v.val;
	}

	void operator +=(ll &v)
	{
		if (val + v >= max)
			val -= max;
		val += v;
	}

	void operator *=(const mod &v)
	{
		val *= v.val;
		val %= max;
	}

	void operator *=(ll &v)
	{
		val *= v;
		val %= max;
	}

	ll modinv(ll a)
	{
		ll b = max, u = 1, v = 0;
		while (b)
		{
			ll t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= max;
		if (u < 0)
			u += max;
		return u;
	}

	void operator /=(const mod &v)
	{
		val *= modinv(v.val);
		val %= max;
	}

	void operator /=(ll &v)
	{
		val *= modinv(v);
		val %= max;
	}
};

int main()
{
	int n;
	cin >> n;
	vector<ll> a(n);
	map<ll, vector<int>> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (m.find(i - a[i]) == m.end())
			m[i - a[i]] = { i };
		else
			m[i - a[i]].push_back(i);
	}

	ll r = 0;
	for (int i = 0; i < n; i++)
	{
		ll t = i + a[i];
		if (m.find(t) == m.end())
			continue;
		r += m[t].end() - lower_bound(m[t].begin(), m[t].end(), i);
	}
	
	printf("%lld", r);
	return 0;
}

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

P operator -(P a, P b){
    return make_pair(a.first - b.first, a.second - b.second);
}
P operator +(P a, P b){
    return make_pair(a.first + b.first, a.second + b.second);
}
P operator *(double a, P b){
    return make_pair(a*b.first, a*b.second);
}
P operator /(P a, double b){
    return make_pair(a.first/b, a.second/b);
}

void koch_curve(vector<P>& pnt, P p1, P p2, int n){
    if(!n) return;
    P dp = p2 - p1;
    P dv = dp/3;
    P s = p1 + dv, t = p1 + 2*dv;
    P u = p1 + dp/2 + 0.5*sqrt(3)*make_pair(-dv.second, dv.first);
    koch_curve(pnt, p1, s, --n);
    pnt.push_back(s);
    koch_curve(pnt, s, u, n);
    pnt.push_back(u);
    koch_curve(pnt, u, t, n);
    pnt.push_back(t);
    koch_curve(pnt, t, p2, n);
    return;
}

int main(){
    int n; cin >> n;
    vector<P> pnt;

    P p1 = make_pair(0.0, 0.0); pnt.push_back(p1);
    P p2 = make_pair(100.0, 0.0);
    koch_curve(pnt, p1, p2, n);
    pnt.push_back(p2);

    for(P p : pnt) cout << p.first << ' ' << p.second << endl;
    return 0;
}


Measured memory_bytes: 3412
#include<iostream>
#include<string>
#include<ctype.h>
using namespace std;

int main(){
    string S; cin>>S;

    if(S[0]!='A'){
        cout<<"WA"<<endl;
        return 0;
    }
    int count=0;
    for(int i=1;i<S.length();i++){
        if(isupper(S[i])){
            if(i==1||i==S.length()-1||S[i]!='C'){
                cout<<"WA"<<endl;
                return 0;
            }
            count++;
        }
    }
    if(count!=1){
        cout<<"WA"<<endl;
        return 0;
    }
    cout<<"AC"<<endl;
    
}


Measured memory_bytes: 256
var
  s:ansistring;
begin
  readln(s);
  while (s<>'') do begin
    if (pos('dreamereraser',s)=1) then
      delete(s,1,13)
    else if (pos('dreamererase',s)=1) then
      delete(s,1,12)
    else if (pos('dreameraser',s)=1) then 
      delete(s,1,11)
    else if (pos('dreamerase',s)=1) then
      delete(s,1,10)
    else if (pos('dreamer',s)=1) then
      delete(s,1,7)
    else if (pos('eraser',s)=1) then
      delete(s,1,6)
    else if (pos('dream',s)=1) then
      delete(s,1,5)
    else if (pos('erase',s)=1) then
      delete(s,1,5)
    else begin
      writeln('NO');
      exit;
    end;
  end;
  writeln('YES');
end.
  


Measured memory_bytes: 1380
N=int(input())
S=[]
for _ in range(N):
    _=input()
    S.append(_)
import collections
a=collections.Counter(S)
b=max(a.values())
new_a=[k for k, v in a.items() if v==b]
new_a.sort()
for i in range(len(new_a)):
    print(new_a[i])




Measured memory_bytes: 164668
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache
setrecursionlimit(10**6)
input=stdin.readline

s=input().rstrip()
a=["","SAT","FRI","THU","WED","TUE","MON","SUN"]
print(a.index(s))


Measured memory_bytes: 2940
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <cctype>
using namespace std;
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T>
inline void read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return ;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1:1;
    ret = (c == '-') ? 0:(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return ;
}
inline void outi(int x) {if (x > 9) outi(x / 10);putchar(x % 10 + '0');}
inline void outl(ll x) {if (x > 9) outl(x / 10);putchar(x % 10 + '0');}

int main()
{
    int d,t,s;
    cin>>d>>t>>s;
    if(t*s>=d)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}



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

using namespace std;

int main()
{
    string s;
    cin >> s;
    int char1 = 0,char2 = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i]=='T') {
            if(char2) {
                --char2;
            } else {
                ++char1;
            }
        } else {
            ++char2;
        }
  }
  cout << char1 + char2 << endl;
}


Measured memory_bytes: 640
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
    #define SORT(v, n) sort(v, v+n);
    #define VSORT(v) sort(v.begin(), v.end());
    #define llong long long
    #define pb(a) push_back(a)
    #define INF 999999999
    using namespace std;
    typedef pair<int, int> P;
    typedef pair<llong, llong> LP;
    typedef pair<int, P> PP;
    typedef pair<llong, LP> LPP;
    //vector<tuple<long long, long long, long long>>vec;

    int dy[]={0, 0, 1, -1, 0};
    int dx[]={1, -1, 0, 0, 0};

    int main()
    {
        int n;
        cin>>n;
        int k;
        cin>>k;
        int ans=k*(int)pow(k-1,n-1);
        cout<<ans<<endl;
    }

Measured memory_bytes: 256
#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/C-.py
#
import collections

n = int(input())
l = [str(input()) for i in range(n)]
# l = ["beat", "vet", "beet", "bed", "vet", "bet", "beet"]
c = collections.Counter(l)
number_of_words = len(c)
counted_list = c.most_common()
ans_before_sort = [counted_list[0][0]]

for i in range(number_of_words-1):
    if counted_list[i][1] == counted_list[i+1][1]:
        ans_before_sort.append(counted_list[i+1][0])
    else:
        break

ans_after_sort = sorted(ans_before_sort)
print('\n'.join(ans_after_sort))


Measured memory_bytes: 51824
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
ll read()
{
	ll tmp=0;char c=getchar(),f=1;
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9'){tmp=tmp*10+c-48;c=getchar();}
	return tmp*f;
}
using namespace std;
ll a[310][310];
int use[310][310];
int n;
ll ans=0;
int main()
{
	int i,j,k;
	n=read();
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=read(),ans+=a[i][j],use[i][j]=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++){
				if(i==j||j==k||i==k)continue;
				if(use[i][j]&&(a[i][j]==a[i][k]+a[k][j]))ans-=a[i][j],use[i][j]=0;
				else if(a[i][j]>a[i][k]+a[k][j]){
					printf("-1\n"); return 0;
				}
			}
	printf("%lld\n",ans>>1);
	return 0;
}

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

ll getnum(ll b,int s){
  ll r=0,x=1;
  for(int i=0;i<=s;i++){
    if((b&(1<<i)))r+=x;
    x*=2;
  }
  return r;
}

ll stoll(string s){
  ll r=0,x=16;
  for(int i=0;i<s.size();i++){
    if('0'<=s[i]&&s[i]<='9')r=r*x+s[i]-'0';
    else r=r*x+s[i]-'a'+10;
  }
  return r;
}

int main(){
  int d;
  string s;
  ll b[9],ans;
  cin>>d;
  while(d--){
    for(int i=0;i<9;i++)cin>>s,b[i]=stoll(s);
    ans=0;
    for(int i=0;i<32;i++){
      ll sum=0;
      for(int j=0;j<8;j++)sum+=getnum(b[j],i);
      int f=0;
      for(int j=0;j<=i;j++)
	if((sum&(1LL<<j))!=(b[8]&(1LL<<j)))f=1;
      if(f){
	ans|=(1LL<<i);
	for(int j=0;j<9;j++)b[j]^=(1LL<<i);
      }
    }
    printf("%llx\n",ans);
  }
  return 0;
}

Measured memory_bytes: 1212
a=[]
c=[]
b=int(input())
for x in input().split(" "):
    a.append(int(x))
    
for x in a:
    c.append(x)

c.sort()

n=0
i=0

while i<b:
    if a[i]!=c[i]:
        n+=1
    i+=1

if n==2 or n==0:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 3064
import math
n,m= map(int,input().split(' '))
arr= list(map(int,input().split(' ')))

votes= sum(arr)
lim=math.ceil(votes/(4*m))
m_arr= [i for i in arr if i>= lim]
if len(m_arr)>=m:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
from collections import deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]


t = dict()

for i in range(1, n + 1):
    t[i] = set()


for a, b in ab:
    t[a].add(b)
    t[b].add(a)


def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)

            stack.extend(graph[vertex] - visited)
    return visited

seen = set()
length = 0
for i in range(1, n+1):
    if i not in seen:
        ans = dfs(t, i)
        for num in ans:
            seen.add(num)

        if len(ans) > length:
            length = len(ans)

print(length)

Measured memory_bytes: 129664
using System;

class Program
{
  static void Main(string[] args)
  {
    var strLine = Console.ReadLine().Split(' ');
    var D = Double.Parse(strLine[0]);
    var T = Int32.Parse(strLine[1]);
    var S = Double.Parse(strLine[2]);
    if (D / S <= T)
    {
      Console.WriteLine("Yes");
    }
    else
    {
      Console.WriteLine("No");
    }
  }
}


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

int main(void){
    int count = 0;
    std::string yoho,kekka;
    std::cin>>yoho;
    std::cin>>kekka;
    if(yoho[0]==kekka[0])count++;
    if(yoho[1]==kekka[1])count++;
    if(yoho[2]==kekka[2])count++;
    std::cout<<count;
    return (0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    set<int> t;
    rep(i,3){
        int a;cin>>a;
        t.insert(a);
    }
    cout<<t.size()<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Mod(n) n % 1000000007
int main()
{
    int A,B;
    string s;
    cin >> A >> B >> s;
    bool can = true;
    if(s[A] != '-')
        can = false;
    for(int i = 0;i < A + B + 1;i++)
    {
        if(i == A)
            continue;
        
        if(s[i] == '-')
            can = false;
    }
    cout << (can ? "Yes\n" : "No\n");
}


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

int main(){
  int n,k;
  cin>>n>>k;
  int dp[n], h[n];

  for(int i=0; i<n; i++){dp[i]=999999999; cin>>h[i]; }
  dp[0]=0;
  dp[1]=abs(h[1]-h[0]);

  for(int i=0; i<n; i++){
    for(int j=1; j<=k; j++){
      if(i+j<n) dp[i+j]=min(dp[i+j], dp[i]+abs(h[i]-h[i+j]));
    }
  }

  cout<<dp[n-1];

}


Measured memory_bytes: 1024
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        long L = scanner.nextLong();
        long dist[][] = new long[N][N];
        long graph[][] = new long[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(i==j){
                    graph[i][j] = Long.valueOf(0);
                }else{
                    graph[i][j]= Long.MAX_VALUE/2;
                }
            }
        }
        for(int i=0; i<M; i++){
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            long C = scanner.nextLong();
            A--;
            B--;
            graph[A][B] = C;
            graph[B][A] = C;
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                for(int k=0; k<N; k++){
                    if(graph[j][k] > graph[j][i] + graph[i][k]){
                        graph[j][k] = graph[j][i] + graph[i][k];
                    }
                }
            }
        }
        int graph2[][] = new int[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(i==j){
                    graph2[i][j] = 0;
                }else if(graph[i][j] <= L){
                    graph2[i][j] = 1;
                }else{
                    graph2[i][j] = Integer.MAX_VALUE / 2;
                }
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                for(int k=0; k<N; k++){
                    if(graph2[j][k] > graph2[j][i] + graph2[i][k]){
                        graph2[j][k] = graph2[j][i] + graph2[i][k];
                    }
                }
            }
        }
        int Q = scanner.nextInt();
        for(int i=0; i<Q; i++){
            int from = scanner.nextInt()-1;
            int to = scanner.nextInt()-1;
            if(graph2[from][to] >= Integer.MAX_VALUE /2){
                System.out.println(-1);
            }else{
                System.out.println(graph2[from][to]-1);
            }
        }
    }
}

Measured memory_bytes: 93448
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 5e36+7;
int mod = 998244353;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    cin >> N;
    vector<int>A(N),B(N);
    vector<P>cnt(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        cnt[i].first = A[i]+B[i];
        cnt[i].second = i;
    }
    sort(cnt.rbegin(),cnt.rend());
    int Takahashi = 0,Aoki = 0;
    for(int i = 0; i < N; i++) {
        ((i%2 == 0)?Takahashi+=A[cnt[i].second]:Aoki+=B[cnt[i].second]);
    }
    cout << Takahashi-Aoki << endl;
}


Measured memory_bytes: 6344
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int N = getint();
	int D[100001] = {};
	rep(i, N) (*(D + getint()))++;
	int S = 0;
	int kotae = 0;
	for (int i = 100000; i > 0; i--) {
		S += *(D + i);
		if (S == N / 2) kotae++;
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 768
N, W = map(int, input().split())
dp = [0] * (W + 1)
v = w = 0
for _ in range(0, N):
    v, w = map(int, input().split())
    for j in range(W, w - 1, -1):
        if dp[j] < dp[j - w] + v:
            dp[j] = dp[j - w] + v
print(dp[W])

Measured memory_bytes: 7928
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define pii pair<int, int>
priority_queue<ll, vector<ll>, greater<ll>> mn; //上  小根堆         小到大
priority_queue<ll, vector<ll>, less<ll>> mx;    //下       大根堆      大到小
map<ll, ll> mp;
inline int read()
{
    int x = 0;
    bool t = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = getchar();
    if (ch == '-')
        t = true, ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = x * 10 + ch - 48, ch = getchar();
    return t ? -x : x;
}
ll mod = 1e9 + 7;
int main()
{
   ll a[6];
   rep(i,1,5) { cin>>a[i] ;}
 rep(i,1,5) { if(!a[i]){cout<<i<<endl;return 0; } }
    return 0;
}


Measured memory_bytes: 3636