akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
 public static void main(String...args) {
  final java.util.Scanner sc = new java.util.Scanner(System.in);
   final int count = sc.nextInt();
   Integer[] array = new Integer[count];
   for(int i=0;i<count;i++)array[i] = sc.nextInt();
   Arrays.sort(array,Comparator.reverseOrder());
   int ans = 0;
   for(int j=0;j<count;j++){
     int price = 0;
     if(j==0){
       price = array[j]/2;
     }else{
       price = array[j];
     }
     ans+=price;
   }
   System.out.println(ans);
 }
}

Measured memory_bytes: 22612
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
#include<stack>
#include<string.h>
#include<list>
#include<limits>
#include<bitset>
#include<ctype.h>
#include<set>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=10000;
const ll INF=1000000000;
const int MAX=100001;
const double EPS=1e-10;
int main(){
    ll n,k;
    cin>>n>>k;
    ll ans=k;
    for(int i=1;i<n;i++){
        ans*=k-1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
N,X=map(int,input().split())
L=list(map(int,input().split()))
D=0

#print(L)
#print(D)

for i in range(N):
  #print(i+2,end=" ")
  #print(L[i],end=" ")
  D=D+L[i]
  #print(D)
  if D>X:
    print(i+1)
    exit()
    
print(N+1)

Measured memory_bytes: 2940
#include <iostream>
#include <math.h>
#include <map>
#include <list>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;


int main() {
	int n, m;
	cin >> n >> m;
	map<int, list<pair<int , int>>> town;
	town.clear();
	int ken = 0, val = 0;
	string ans[100000] = {""};
	for (int i = 0; i < m; ++i) {
		cin >> ken >> val;
		town[ken].push_back(pair<int, int>(val, i));
	}
	for (int i = 1; i <= n; ++i) {
		town[i].sort();
		list<pair<int , int>>::iterator it = town[i].begin();
		int cnt = 1;
		while (it != town[i].end()) {
			stringstream strStream;
			strStream << setfill('0') << right << setw(6) << i;
			strStream << setfill('0') << right << setw(6) << cnt;
			ans[(*it).second] = strStream.str();
			++it;
			++cnt;
		}
	}
	for (int i = 0; i < m; ++i) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 16512
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<stdio.h>
#include<iostream>
#include<numeric>
using namespace std;

int main() {
	int a, p;
	cin >> a >> p;
	cout << (3 * a + p) / 2 << endl;
}


Measured memory_bytes: 256
n,a,b = map(int,input().split())
x = list(map(int,input().split()))
"""
率直に左からまわる.
"""
ans = 0
now = x[0]
for i in range(1, n):
	kyori = x[i]-now
	ans += min(a*kyori, b)
	now = x[i]
print(ans)

Measured memory_bytes: 14352
N=int(input())
V=[float(s) for s in input().split() ]
V=sorted(V)

for i in range(0,N-1):
    Ave=float((V[0]+V[1])/2)
    V.pop(0)
    V.pop(0)
    V.append(Ave)
    V=sorted(V)
print(V[0])

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll n,r;
    cin>>n>>r;
    if(n>=10)
        cout<<r<<endl;
    else
    {
        cout<<r+(10-n)*100<<endl;
    }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            if(i*j==n) {cout<<"Yes";return 0;}
        }
    }
    cout<<"No";
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>){

    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val haveSnack = BooleanArray(n)

    repeat(k){
        val d = readLine()!!.toInt()
        readLine()!!.split(" ").forEach {
            haveSnack[it.toInt()-1] = true
        }
    }
    println(haveSnack.filter { !it }.count())
}



Measured memory_bytes: 39116
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>
int main(void){
int a,b,c;
    scanf("%d %d",&b,&c);
    if(b == c)printf("Yes");
    else printf("No");
return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG_OUTPUT
#define DEBUG_LOG(s) cout << s << endl;
#else
#define DEBUG_LOG(s) void();
#endif

bool is_prime(const int n) {
    if(n == 1) return false;
    for (int64_t i = 2; i * i <= n; i++) {
        if(n % i == 0) return false;
    }
    return true;
}

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

    vector<pair<int, int>> n(q);
    for (auto i = 0; i < q; i++) cin >> n[i].first >> n[i].second;

    vector<pair<bool, int>> prime(100001, make_pair(false, 0));
    // 2は素数だけど(2+1)/2=1は素数ではないので初期化不要
    for (auto i = 3; i < 100000; i += 2) {
        prime[i].first = (is_prime(i) and is_prime((i + 1) / 2));
        prime[i].second = prime[i - 1].second + prime[i].first;
        prime[i + 1].second = prime[i].second;
        // cout << i << " " << prime[i].second << " " << prime[i + 1].second << endl;
    }

    for (auto i = 0; i < q; i++) {
        int ans = prime[n[i].second].second - prime[n[i].first - 1].second;
        // cout << prime[n[i].second].second << " " << prime[n[i].first - 1].second << endl;
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define llu unsigned long long int
int main()
{
    llu a,b,x;
    cin>>a>>b>>x;

    if(a==0)
        cout<<((b/x)+1)<<endl;
    else
        cout<<((b/x)-((a-1)/x))<<endl;
    return 0;
}


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

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

using namespace std;

int main()
{
	int N;

	cin >> N;

	int ans = 0;

	for (int i = 1; i <= N; i += 2)
	{
		int y = 0;
		for (int h = 1; h <= i; h++) {
			if (i % h == 0)y++;
		}
		if (y == 8) ans++;
	}

	cout << ans << endl;

	return 0;
}

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

int fact(int n){
	if (n == 0){
		return 1;
	}
	else{
		return n * (fact(n - 1));
	}
}

int main()
{
	int n, s;
	vector <int> v;
	vector <int>::iterator vi;
	for (int i = 0; i <= 9; i++){
		v.push_back(i);
	}
	while (cin >> n >> s, n || s){
		int repeat = fact(10 - n);
		int counter = 0;
		int anscounter = 0;
		do{
			counter++;
			if (counter % repeat != 0){
				continue;
			}
			int sum = 0;
			vi = v.begin();
			for (int i = 0; i < n; i++, vi++){
				sum += *vi;
			}
			if (sum == s){
				anscounter++;
				vi = v.begin();
			}
		} while (next_permutation(v.begin(), v.end()));
		cout << anscounter / fact(n)<< endl;
	}
	return 0;
}

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

int main(){
    int N;
    vector<pair<int, int> > W;

    cin >> N;

    for(int i=0;i<N;++i){
        int a, b;
        cin >> a >> b;
        W.push_back({a, b});
    }

    sort(W.begin(), W.end(), [](pair<int, int> x, pair<int, int> y){
        return x.second < y.second;
    });
    int t = 0;
    for(auto x:W){
        //cout  << x.first << " " << x.second << endl;
        t += x.first;
        if(t > x.second){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
ll MAX(ll a,ll b,ll c){return max(a,max(b,c));}
ll MIN(ll a,ll b,ll c){return min(a,min(b,c));}
int main(){
    ull n,k;
    ull res = 0;
    cin >> n >> k;
    ull h[110000];
    rep1(i,n) cin >> h[i];
    ull count[110000]={0};
    rep1(i,k){
        ull a,b;
        cin >> a >> b;
        if(h[a] > h[b]){
            count[b]++;
        }
        else{
            count[a]++;
            if(h[a] == h[b]) count[b]++;
        }
    }
    rep1(i,n){
        if(count[i] == 0) res++;
    }
    cout << res << endl;
}

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

int main(){
	int q; scanf("%d",&q);
	for(int i=0;i<q;i++){
		int c,a,n;
		scanf("%d%d%d",&c,&a,&n);
		int res=min(n,min(c,a));
		c-=res,a-=res,n-=res;
		int x=min(a,c/2);
		res+=x;
		a-=x,c-=x*2;
		res+=c/3;
		printf("%d\n",res);
	}
}

Measured memory_bytes: 1188
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;

const long long INF = 1LL << 60;  // どういう意味だろうか

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() {
	int N, M, C;
	int B[22] = { };
	int A[22][22] = { };
	int ans = 0;
	int sum = 0;

	cin >> N >> M >> C;
	for (int i = 0; i < M; i++) {
		cin >> B[i];
	}

	for (int j = 0; j < N; j++) {
		for (int i = 0; i < M; i++) {
			cin >> A[j][i];

			sum += A[j][i] * B[i];
		}
		sum += C;

		if (sum > 0) {
			ans++;
		}
		sum = 0;
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

int read()
{
  int x=0,f=1;
  char ch=getchar();
  while((ch<'0')||(ch>'9'))
    {
      if(ch=='-')
        {
          f=-f;
        }
      ch=getchar();
    }
  while((ch>='0')&&(ch<='9'))
    {
      x=x*10+ch-'0';
      ch=getchar();
    }
  return x*f;
}

const int maxn=300;
const int inf=0x3f3f3f3f;

int n,m,a[maxn+4][maxn+4],in[maxn+4],mx[maxn+4],ans;

int main()
{
  n=read();
  m=read();
  for(int i=1; i<=n; ++i)
    {
      for(int j=1; j<=m; ++j)
        {
          a[i][j]=read();
        }
    }
  ans=n;
  int cnt=0;
  while(cnt<m)
    {
      for(int j=1; j<=m; ++j)
        {
          mx[j]=0;
        }
      for(int j=1; j<=n; ++j)
        {
          int nowi=-1;
          for(int k=1; k<=m; ++k)
            {
              if(!in[a[j][k]])
                {
                  nowi=a[j][k];
                  break;
                }
            }
          ++mx[nowi];
        }
      int now=-1;
      for(int j=1; j<=m; ++j)
        {
          if((!in[j])&&(mx[j]>now))
            {
              now=mx[j];
            }
        }
      ans=std::min(ans,now);
      for(int j=1; j<=m; ++j)
        {
          if((!in[j])&&(mx[j]==now))
            {
              in[j]=1;
              ++cnt;
            }
        }
    }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 512
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, a[N];

inline void read_input() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
}

inline void solve() {
	sort(a, a + n, greater<int>());
	for (int i = 1; i <= n; i++)
		if (a[i] <= i) {
			int k = 0;
			while (a[i + k] == i)
				k++;
			cout << (k & 1 || a[i - 1] - i & 1? "First": "Second");
			return;
		}
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007

int main(){
  FIO;
  // ifstream cin("input");
  int n;
  cin>>n;
  string a;
  set<string>answer;
  int i;
  for(i=0;i<n;i++){
    cin>>a;
    answer.insert(a);
  }
  cout<<answer.size()<<endl;
  return 0;  
}

Measured memory_bytes: 19256
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let a: i32 = sc.read();
    let b: i32 = sc.read();
    let mut k: i32 = sc.read();
    let mut mint = std::cmp::min(a, b);

    loop {
        if a % mint == 0 && b % mint == 0 {
            k -= 1;
            if k == 0 {
                println!("{}", mint);
                return;
            }
        }
        mint -= 1;
        if mint == 0 {
            return;
        }
    }
}



Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  int count = 0;
  for(int i = 0;i < N;i++){
    int x;
    cin >> x;
    if(x >= K){
      count++;
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

typedef struct edge{ll s,g;}E;
int edgehikaku(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}

ll n,m;
E e[200010];
int id[100010];
void readgraph(){
	scanf("%lld%lld",&n,&m);
	rep(i,0,m){
		ll x,y;
		scanf("%lld %lld",&x,&y);
		x--,y--;
		e[2*i].s=x;
		e[2*i].g=y;
		e[2*i+1].s=y;
		e[2*i+1].g=x;
	}
	m*=2;
	qsort(e,m,sizeof(E),edgehikaku);

	int p=0;
	rep(i,1,n){
		while(p<m&&e[p].s<i)p++;
		id[i]=p;
	}
	id[n]=m;
}


ll v[100010];
ll d[100010];
ll c[100010];
ll dp[100010][11];

void dfs(ll vv,ll dd,ll cc){
	if(dp[vv][dd])return;
	rep(i,0,dd+1)if(!dp[vv][i])dp[vv][i]=cc;
	if(dd==0)return;
	rep(i,id[vv],id[vv+1])dfs(e[i].g,dd-1,cc);
}

int main(){
	readgraph();
	int q;
	scanf("%d",&q);
	rep(i,0,q){
		scanf("%lld%lld%lld",v+i,d+i,c+i);
		v[i]--;
	}
	for(int i=q-1;i>=0;i--)dfs(v[i],d[i],c[i]);
	rep(i,0,n)printf("%lld\n",dp[i][0]);
	
}

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

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    vector<vector<ll>> count(n, vector<ll>(27, 0));
    for(int i = 0; i < n; ++i){
        string s;
        cin >> s;
        for(char c : s){
            count.at(i).at(c - 'a')++;
        }
    }

    vector<ll> mincount(27, 100);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 27; ++j){
            mincount.at(j) = min(mincount.at(j), count.at(i).at(j));
        }
    }

    string ans;
    for(int i = 0; i < 27; ++i){
        for(int j = 0; j < mincount.at(i); ++j){
            ans.push_back('a' + (char)i);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1144
import java.util.Scanner;

class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println((a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) ? "Possible" : "Impossible");
    }
}


Measured memory_bytes: 21716
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,i,j,k,a[1000010],ans;
int main(){
	scanf("%d",&n);for (i=1;i<=n;i++) scanf("%d",&a[i]);
	k=0;for (i=2;i<=n+1;i++) if (a[i]!=a[i-1]) ans+=(i-k-1)/2,k=i-1;printf("%d\n",ans);return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <new>

using namespace std;

int main(){
    int ans,A,B;
    int out = 1;

    cin >> A >> B;

    while(B > out){
        out += A - 1;
        ans++;
    }

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


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
  int a[100][100], b, n, m, l;
  long c[100][100]={0};
  cin >> n >> m >> l;
  for(int i=0; i < n; i++){
    for(int j=0; j < m; j++){
      cin >> a[i][j];
    }
  }
  for(int i=0; i<m; i++){
    for(int j=0; j<l; j++){
      cin >> b;
      for(int k=0; k<n; k++){
        c[k][j] += a[k][i]*b;
      }
    }
  }
  for(int i=0; i<n; i++){
    for(int j=0; j<l; j++){
      cout << (j ? " " : "") << c[i][j];
    }
    cout << endl;
  }
  return 0;
}




Measured memory_bytes: 3196
#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;

#define MIN(a,b) ((a)<(b)?(a):(b))


int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int s = n - 1;
	while (s >= 0) {
		///cerr << s << ":";
		cout << a[s] << " ";
		s -= 2;
	}
	s = n%2;
//	cerr << endl;
	while (s <n) {
		//cerr << s << ":";
		cout << a[s] << " ";
		s += 2;
	}

	return 0;
}


Measured memory_bytes: 2944
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if false
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

ll = inputs[0][0]
rr = inputs[0][1]

# body
if $debugFlag
  p ll
  p rr
end

def calc(r)
  if r[0] == 1
    return ((r+1)/2 % 2)
  else
    return ((r+1)/2 % 2) ^ r
  end
end

puts calc(ll-1) ^ calc(rr)


Measured memory_bytes: 1788
import math

n=int(input())
L={}
for i in range(n):
    s="".join(sorted(list(input())))
    if s not in L.keys():
        L[s]=1
    else:
        L[s]+=1

ans=0
for v in L.values():
    if v!=1:
        ans += math.factorial(v)/(math.factorial(2)*math.factorial(v-2))
print(int(ans))

Measured memory_bytes: 17932
S = input()
k = 'Yes'

for i in range(len(S)):
	if i % 2 == 0:
		if S[i] == 'L':
			k = 'No'
			break 
	else:
		if S[i] == 'R':
			k = 'No'
			break
	
print(k)


Measured memory_bytes: 2940
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

long long int result[40] = {};

void solve(long long int n)
{
	// cout << n << endl;
	if(n > 0){
		long long int ketanum = 0;
		long long int cnt = 1;
		while(cnt < n){
			ketanum += 2;
			cnt += pow(2, ketanum);
		}
		result[ketanum] = 1;
		solve(n - pow(2, ketanum));
	} else if (n < 0) {
		long long int ketanum = 1;
		long long int cnt = 2;
		while(cnt < -n){
			ketanum += 2;
			cnt += pow(2, ketanum);
		}
		result[ketanum] = 1;
		solve(n + pow(2, ketanum));
	}
}

int main()
{
	long long int n;
	cin >> n;
	solve(n);
	long long int s = 39;
	while(s > 0 && result[s] == 0) s--;
	for(long long int i = s; i >= 0; i--){
		cout << result[i];
	}
	cout << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N;
vector<int> Tree[200002];
queue<int> Q[3]; 
int ans[200002];
int guuki[200002];

/*
「すべての頂点の組 (i,j)について、頂点 iと頂点jの距離が3であるならば、
piと pjの和または積が3の倍数である。」の対偶は、
「[pi≡1かつpj≡1]または[pi≡2かつpj≡2](mod3)ならば、iとjの距離は3でない」
である。
頂点1からの距離が偶奇でわけたときに、3の距離となるときは頂点が偶と奇。
*/
void dfs(int idx, int mod2) { // mod2は0or1
  guuki[idx] = mod2;
  mod2=mod2?0:1;
  rep(i, Tree[idx].size()) {
    int next = Tree[idx][i];
    if (guuki[next]<0) dfs(next, mod2);
  }
}

bool assign_and_pop(int idx, int mod3) {
  if (Q[mod3].empty()) return false;
  ans[idx] = Q[mod3].front();
  Q[mod3].pop();
  return true;
}

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

  cin >> N;
  int a,b;
  rep(i, N-1) {
    cin >> a >> b;
    a--;b--;
    Tree[a].push_back(b);
    Tree[b].push_back(a);
  }
  fill(guuki, guuki+N, -1);
  dfs(0, 0);
  int even = 0;
  int odd = 0;
  rep(i, N) {
    Q[(i+1)%3].push(i+1);
    assert(guuki[i]>=0);
    if (guuki[i]) odd++;
    else even++;
  }
  bool odd_flag = odd<=N/3; // 距離が奇数の頂点がN/3以下
  bool even_flag = even<=N/3; // 距離が偶数の頂点がN/3以下
  if (odd_flag) {
    rep(i, N) {
      if (guuki[i]) assign_and_pop(i, 0);
      else {
        bool ok = assign_and_pop(i, 1);
        if (ok) continue;
        bool ok2 = assign_and_pop(i, 2);
        if (ok2) continue;
        assign_and_pop(i, 0);
      }
    }
  }
  else if (even_flag) {
    rep(i, N) {
      if (!guuki[i]) assign_and_pop(i, 0);
      else {
        bool ok = assign_and_pop(i, 1);
        if (ok) continue;
        bool ok2 = assign_and_pop(i, 2);
        if (ok2) continue;
        assign_and_pop(i, 0);
      }
    }
  }
  else {
    rep(i, N) {
      if (guuki[i]) {
        bool ok = assign_and_pop(i, 1);
        if (!ok) assign_and_pop(i, 0);
      } else {
        bool ok = assign_and_pop(i, 2);
        if (!ok) assign_and_pop(i, 0);
      }
    }
  }
  rep(i, N) {
    assert(ans[i]<=N);
    cout << ans[i] << ' ';
  }
  cout << endl;
  return 0;
}


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

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> vvi;
typedef vector<vl> vvl;
typedef vector<vector<pii> > vvpii;

#define pb push_back
#define endl '\n'
#define INF (int)1e9
#define EPS 1e-9
#define gcd __gcd
#define rs resize
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define by(T, x) [](const T& a, const T& b) { return a.x < b.x; } //for struct sorting

void printV(vector<int> v){
	for(int i = 0; i < v.size(); i++){
		cout << v[i] << " " ;
	}
	cout << endl;
}

void print2V(vvi v){
	FOR(i, 0, v.size()){
		FOR(j, 0, v[i].size()){
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
}


ll n, val[5000], sum, dp[5000][5000];

ll opt(ll i, ll j){
//	cout<< "inside with: " << i << " " << j << endl;
	if(i > j){
//		cout << "invalid indices" << endl;
		return 0;
	}
	if(i == j){
//		cout << "equal indices" << endl;
		return val[i];
	}
	if(dp[i][j] != -1){
//		cout << "already calculated" << endl;
		return dp[i][j];
	}
	dp[i][j] = max( val[i]+min( opt(i+2, j), opt(i+1, j-1) ), val[j]+min( opt(i+1, j-1), opt(i, j-2) ) );
//	cout << "returning: " << dp[i][j] << " for: " << i << " " << j << endl;
	return dp[i][j];	
}

int main(){
	memset(dp, -1, sizeof dp);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> val[i];
		sum += val[i];
	}
	ll x = opt(1, n);
//	cout << "ans is: " << x << endl;
	cout << 2*x - sum;
}

Measured memory_bytes: 195712
N, Y = map(int, input().split())
a = min(Y // 10000, N) + 1
for i in range(a):
  b = min((Y - (10000 * i)) // 5000, N - i) + 1
  for j in range(b):
    if 10000 * i + 5000 * j + 1000 * (N - i - j) == Y:
      print(i, j, N - i - j)
      break
  else:
    continue
  break
else:
  print('-1 -1 -1')

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

using namespace std;
long long dp[100005];
int main()
{
    long long v,c,n,i,maxim = 0,w;
    cin >> n >> w;
    for(long long t = 1;t<= n;t++){
        cin >> c >> v;
        for(i = w;i >= c;i--){
            dp[i] = max(dp[i],dp[i-c] + v);
            maxim = max(maxim,dp[i]);
        }
    }
    cout << maxim;
    return 0;
}


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

using namespace std;

class DICE{
public:
    int top;
    int bottom;
    int right;
    int left;
    int front;
    int back;
    void South();
    void North();
    void East();
    void West();
    void LF();
    void RF();
};

void DICE::South(){
    int temp = back;
    back = top;
    top = front;
    front = bottom;
    bottom = temp;
}

void DICE::North(){
    int temp = front;
    front = top;
    top = back;
    back = bottom;
    bottom = temp;
}

void DICE::West(){
    int temp = left;
    left = top;
    top = right;
    right = bottom;
    bottom = temp;
}

void DICE::East(){
    int temp = right;
    right = top;
    top = left;
    left = bottom;
    bottom = temp;
}

void DICE::RF(){
    int temp = front;
    front = left;
    left = back;
    back = right;
    right = temp;
}

void DICE::LF(){
    int temp = front;
    front = right;
    right = back;
    back = left;
    left = temp;
}


int main(){
    int n;
    cin>>n;
    string ans = "Yes";

    DICE d[100];

    for(int i= 0;i<n;i++)
    {
        cin>>d[i].top>>d[i].back>>d[i].right>>d[i].left>>d[i].front>>d[i].bottom;

        for(int count=0;count<4;count++)
        {
            if(d[i].top == d[i].back)d[i].South();
        }
        for(int count=0;count<4;count++)
        {
            if(d[i].back == d[i].right)d[i].RF();
        }
    }

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

            if(d[j].top != d[i].top)
            {
                d[j].South();
                if(d[j].top != d[i].top)
                {
                    d[j].South();
                    if(d[j].top != d[i].top)
                    {
                        d[j].South();
                        if(d[j].top != d[i].top)
                        {
                            d[j].South();
                            if(d[j].top != d[i].top)
                            {
                                d[j].East();
                                if(d[j].top != d[i].top)
                                {
                                    d[j].East();
                                    d[j].East();
                                }
                            }
                        }
                    }
                }
            }

            if(d[j].back != d[i].back)
            {
                d[j].RF();
                if(d[j].back != d[i].back)
                {
                    d[j].RF();
                    if(d[j].back != d[i].back)
                    {
                        d[j].RF();
                        if(d[j].back != d[i].back){
                            d[j].RF();
                        }
                    }
                }
            }

            if(d[i].top == d[j].top &&
                d[i].bottom == d[j].bottom &&
                d[i].right == d[j].right &&
                d[i].left == d[j].left &&
                d[i].front == d[j].front &&
                d[i].back == d[j].back){
                    ans = "No";
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

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

int gcd(int a,int b){
    while(b){
        a=a%b;
        swap(a,b);
    }
    return a;
}

int x;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>x;
    cout<<360/gcd(x,360)<<endl;

    return 0;
}

Measured memory_bytes: 3648
S = input()

if S[0] != 'A':
    print("WA")
    exit()
if S[2:-1].count('C') != 1:
    print("WA")
    exit()
if S.replace("A", "").replace("C", "").islower() == False:
    print("WA")
    exit()
print("AC")


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


int main()
{


	fastio;
	ll t,n,m;
	cin>>n;
	map<string,int> mp;
	while(n--)
	{
		string s;
		cin>>s;
		mp[s]++;

	}

	cout<<"AC"<<" x "<<mp["AC"]<<endl;
	cout<<"WA"<<" x "<<mp["WA"]<<endl;
	cout<<"TLE"<<" x "<<mp["TLE"]<<endl;
	
	cout<<"RE"<<" x "<<mp["RE"]<<endl;
	
	return 0;
		

		
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#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 ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

int main()
{
    INIT;
    char in[120];
    int n;
    scanf("%d", &n);
    pair<pair<string, int>, int> p[110];
    REP(i,n){
        int t; scanf("%s%d",in,&t);
        string tmp=in;
        p[i] = make_pair(make_pair(in, -t),i);
    }
    sort(p, p+n);
    REP(i,n) printf("%d\n", p[i].second+1);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, a[N], b[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) a[i] = 1;
    b[1] = 1;
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x]--;
        a[y]++;
        if (b[x]) {
            b[y] = 1;
            if (!a[x]) b[x] = 0;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (b[i]) ans++;
    printf("%d\n", ans);
    return 0;
}

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

int main(){
  int n,i;
  cin>>n;
  long long x=0,a[n];
  for(i=0;i<n;i++){
    cin>>a[i];
    if(i%2==0) x+=a[i];
    else x-=a[i];
  }
  cout<<x;
  for(i=0;i<n-1;i++){
    x=(a[i]-x/2)*2;
    cout<<" "<<x;
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 2048
encoder = {
    "A": "00000",
    "B": "00001",
    "C": "00010",
    "D": "00011",
    "E": "00100",
    "F": "00101",
    "G": "00110",
    "H": "00111",
    "I": "01000",
    "J": "01001",
    "K": "01010",
    "L": "01011",
    "M": "01100",
    "N": "01101",
    "O": "01110",
    "P": "01111",
    "Q": "10000",
    "R": "10001",
    "S": "10010",
    "T": "10011",
    "U": "10100",
    "V": "10101",
    "W": "10110",
    "X": "10111",
    "Y": "11000",
    "Z": "11001",
    " ": "11010",
    ".": "11011",
    ",": "11100",
    "-": "11101",
    "'": "11110",
    "?": "11111"
}
decoder={
    "101":" ",
    "000000":"'",
    "000011":",",
    "10010001":"-",
    "010001":".",
    "000001":"?",
    "100101":"A",
    "10011010":"B",
    "0101":"C",
    "0001":"D",
    "110":"E",
    "01001":"F",
    "10011011":"G",
    "010000":"H",
    "0111":"I",
    "10011000":"J",
    "0110":"K",
    "00100":"L",
    "10011001":"M",
    "10011110":"N",
    "00101":"O",
    "111":"P",
    "10011111":"Q",
    "1000":"R",
    "00110":"S",
    "00111":"T",
    "10011100":"U",
    "10011101":"V",
    "000010":"W",
    "10010010":"X",
    "10010011":"Y",
    "10010000":"Z"
}

def encode(strings):
    retval=""
    for s in strings:
        retval+=encoder[s]
    return retval

def decode(strings):
    for i in range(len(strings)+10):
        if strings[:i:] in decoder:
            return decoder[strings[:i:]]+decode(strings[i::])
    return ""


while True:
    try:
        print(decode(encode(input())))
    except EOFError:
        break



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

typedef long long ll;
#define pii pair<ll , ll>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 100005

ll n , m;
ll a[MAXX];
ll b[MAXX];
ll c[MAXX];

int main()
{
    _FastIO;
    cin >> n >> m;
    multiset<ll> ms;
    multiset<ll>::iterator it;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
        ms.insert(a[i]);
    }
    vector<pair<ll , ll> > v;
    for(ll i = 0; i < m; i++){
        cin >> b[i] >> c[i];
        v.push_back({c[i] , b[i]});
    }
    sort(v.begin() , v.end());
    ll p = v.size();
    p--;
    while((*(ms.begin())) < (v[p].first) && p != -1){
        ll h = v[p].second;
        ll y = 0;
        ll f = v[p].first;
        while((*(ms.begin())) < f && y < h){
            it = ms.begin();
            ll k = *it;
            ms.erase(it);
            ms.insert(f);
            y++;
        }
        p--;
    }
    ll ans = 0;
    for(it = ms.begin(); it != ms.end(); it++){
        ans += (*it);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8952
#include "bits/stdc++.h"

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

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cerr << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) (__VA_ARGS__)

using namespace std;
using ll = long long;
using P = pair<int, int>;

void Main() {
  int n;
  cin >> n;
  vector<int> x(n), y(n) , h(n);
  rep(i, n) cin >> x[i] >> y[i] >> h[i];
  rep(i, 101) rep(j, 101) {
    int H = 0;
    bool flag = true;
    rep(k, n)  if (h[k] != 0) {H = h[k] + abs(x[k] - i) + abs(y[k] - j); break;}
    rep(k, n) {
      if (h[k] == 0 && H <= abs(x[k] - i) + abs(y[k] - j)) continue;
      if (h[k] > 0 && H == h[k] + abs(x[k] - i) + abs(y[k] - j)) continue;
      flag=false;
      break;
    }
    if (flag) {
      printf("%d %d %d\n", i, j, H);
      return;
    }
  }
}

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


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

int main() {

  long L, R;
  cin >> L >> R;

  long answer = 2018;

  if (L + 2019 < R) {
    R = L + 2019;
  }

  for (long i = L; i <= R; i++){
    for (long j = i + 1; j <= R; j++) {
      long a_ = (i % 2019) * (j % 2019) % 2019;
      answer = min(answer, a_);
    }
    
  }

  cout << answer << endl;

}

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

main(){

  ll L,R;
  cin>>L>>R;
  if(R-L>2020)puts("0");
  else{
    ll ans=(1LL<<60);
    for(ll i=L;i<=R;++i){
      for(ll j=i+1;j<=R;++j){
        ll tmp=(i*j)%2019;
        ans=min(ans,tmp);
      }
    }
    cout<<(ans)<<endl;
  }

}

Measured memory_bytes: 256
#include <stdio.h>

void graph(int n){ /*nÔÚÌíÞÌACXª¢­Â é©ð\¦·éOt */
	int i;
	if (n != 0){  /*àµAACXª1ÂÅàê½Èç*/
		for (i = 0; i < n; i++) {
			printf("*");
		}
		printf("\n");
	}
	else{ /*»¤ÅÈ¯êÎ */
		printf("-\n");
	}
}

int main(void)
{
	int i;
	int j;
	int n; /*ACXÌ */
	int bice; /*N©ªÁ½ACX*/
	int ice[10]; /*ACXÌíÞ*/
	
	scanf("%d", &n);
	
	while(n != 0){
		/*for¶Ì(i = 0;c;i++);ÌcÌªÉÓ. 10ÈÌ©AACXÌÈÌ©ðµÁ©è©Éßæ¤!*/
		for (i = 0; i < 10; i++){ /*ice[ÈñÆ©]Ìú»*/
			ice[i] = 0;
		}
		for (i = 0; i < n; i++) { /*»ê¼êÌÁ½ACXÌíÞÌm©ß*/
			scanf("%d", &bice);
			ice[bice]++;
		}
		for(i = 0; i < 10; i++){
			graph(ice[i]);
		}
		
		scanf("%d", &n);
	}
	
	return (0);
}

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

#define ll long long
#define ss second
#define ff first
#define pb push_back

using namespace std;

const int N = 1e6 + 69, mod = 1e9 + 7;

int n, m;

double answer = 1;

double P[N];

double dp[3000][3000];

int main(){

        ios :: sync_with_stdio(0);

        cin >> n ;

        for(int  i =1 ; i <= n; i++){
                cin >> P[i];
        }

        dp[0][0] = 1;

        for(int i = 1; i <= n; i++){
                for(int j = 0; j <= i; j++){
                        if(j && dp[i-1][j-1] != 0) dp[i][j] += dp[i-1][j-1] * P[i];
                        if(dp[i-1][j] != 0) dp[i][j] += dp[i-1][j]*(1 - P[i]);

                        if(i == n && j > n - j) answer += dp[i][j];
                }
        }

        printf("%.10f", answer - 1);

}


Measured memory_bytes: 70272
#include "iostream"
using namespace std;

int main(int argc, char const *argv[])
{
	int n, x=0;
	int count=0;
	int num[100];
	int temp=0;
	int i,j,k=0;

	while(true)
	{
		count=0;
		cin >> n >> x;


		for(i=0;i<100;i++)
		{
			num[i]=0;
		}
		for(i=0;i<n;i++)
		{
			num[i]=i+1;
		}

		if(x==0 && n==0)
		{
			break;
		}


		for(i=0;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				for(k=j+1;k<n;k++)
				{
					// cout <<"index is "<<  i << " "<< j << " " << k <<endl;
					// cout <<num[i] << " "<< num[j] << " " << num[k] <<endl;
					temp = num[i] + num[j] + num[k];
					if(temp == x)
					{
						count++;
					}
				}
			}
		}
		cout << count <<endl;
	}

	return 0;
}


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

int main () {
  int n;
  string s;
  cin >> n >> s;

  int num=0,max=0;
  for(int i=0;i<n;i++) {
    if(s[i] == 'I') {
      num++;
      if(max < num) max=num;
    }
    else num--;
  }
  cout << max << endl;
  return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;

#define FOR(i,f,t) for(int i=(int)f; i<(int)t; i++)
#define FORR(i,f,t) for(int i=(int)f; i>(int)t; i--)
#define ms(obj, val) memset(obj, val, sizeof(obj))
#define pb push_back
#define SYNC ios_base::sync_with_stdio(false)
#define inf 2248012
#define mp make_pair
#define F first
#define S second
#define ri(x) scanf("%d",&x)
#define rii(x,y) scanf("%d %d",&x,&y)
#define riii(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define lri(x) scanf("%lld",&x)
#define lrii(x,y) scanf("%lld %lld",&x,&y)
#define lriii(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> ii;

const int MAXN = 1e5+3; //AREGLAAAAAAAAR!!!!

int memo[4],a[4];
int main(){
	FOR(i,0,3) ri(a[i]);
	int ans = 1e9;
	FOR(i,0,3){
		memo[i]=1;
		int cant=0;
		FOR(j,0,3){
			if(memo[j]) continue;
			memo[j]=1;
			FOR(w,0,3){
				if(memo[w]) continue;
				memo[w]=1;
				cant=abs(a[j]-a[i])+abs(a[w]-a[j]);
				cant=min(cant,abs(a[j]-a[i])+abs(a[w]-a[i]));
				memo[w]=0;
			}
			memo[j]=0;
		}
		memo[i]=0;
		ans=min(cant,ans);
	}
	printf("%d\n",ans);
}


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UF{
    vector<int>par,sz;
    void init(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

signed main(){
    int N,M;
    while(cin>>N>>M,N||M){
        vector<tuple<int,int,int>>es;
        rep(i,M){
            int a,b,c;
            cin>>a>>b>>c;
            a--;b--;
            es.pb(make_tuple(c,a,b));
        }
        sort(all(es));
        int cnt=0;
        UF uf;uf.init(N);
        rep(i,M){
            int c,a,b;
            tie(c,a,b)=es[i];
            if(uf.same(a,b))continue;
            uf.unite(a,b);
            cnt++;
            if(cnt==N/2){
                cout<<c<<endl;
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3400
from collections import defaultdict 

def multi_input():
    return map(int, input().split())

N, M = multi_input()
pS = [input().split() for _ in range(M)]

l = ['WA' for _ in range(N+1)]
d = defaultdict(int)
a = 0
for i, j in pS:
    i = int(i)
    if l[i] == 'WA':
        if j == 'WA':
            d[i] += 1
        else:
            a += 1
            l[i] = 'AC'

p = 0
for key, value in d.items():
    if l[key] == 'AC':
        p += value
           
print(a, p)

Measured memory_bytes: 39324
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define f0(i,a,b) for(int i=a;i<b;i++)
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define f2(i,a,b) for(int i=a;i>b;i--)
#define f3(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define int long long
#define fi first
#define se second
#define ncr(n,r) fact[n]*modInv(fact[r])*modInv(fact[n-r])
#define modInv(a) binExp(a,mod-2)
#define mod 1000000007
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define os_find(k) find_by_order(k)
#define os_order(k) order_of_key(k)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define make_graph(k) int x,y; f0(i,0,k){cin>>x>>y; adj[x].pb(y); adj[y].pb(x);}
#define test int t;cin>>t;while(t--)

double dp[301][301][301];
double expected[301][301][301];

signed main()
{
    fast

    #ifndef ONLINE_JUDGE
        freopen("inputf.in","r",stdin);
        freopen("outputf.in","w",stdout);
    #endif

    int n;
    cin>>n;

    int x;
    vector<int> cnt(4);
    f0(i,0,n)
    {
    	cin>>x;
    	cnt[x]++;
    }


    
    f1(i,0,n) f1(j,0,n) f1(k,0,n) dp[i][j][k] = expected[i][j][k] = 0;

    dp[cnt[1]][cnt[2]][cnt[3]] = 1;
    f3(k,n,0)
    {
    	f3(j,n,0)
    	{
    		f3(i,n,0)
    		{
    			if(i==0 && j==0 && k==0 || (i+j+k) > n) continue;

    			double probWaste = (double) (n - (i+j+k)) / n;
    			double expWaste = probWaste / (1 - probWaste) + 1;

    			expected[i][j][k] += expWaste * dp[i][j][k];

    			if(k!=0)
    			{
    				double p = (double) k / (i+j+k);
    				dp[i][j+1][k-1] += dp[i][j][k] * p;
    				expected[i][j+1][k-1] += (expected[i][j][k]) * p;
    			}
    			

    			if(j!=0)
    			{
    				double p = (double) j / (i+j+k);
    				dp[i+1][j-1][k] += dp[i][j][k] * p;
    				expected[i+1][j-1][k] += (expected[i][j][k]) * p;
    			}
    			

    			if(i!=0)
    			{
    				double p = (double) i / (i+j+k);
    				dp[i-1][j][k] += dp[i][j][k] * p;
    				expected[i-1][j][k] += (expected[i][j][k]) *p;
    			}
    		}
    	}
    }

    cout<<fixed<<setprecision(10)<<expected[0][0][0];
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;
const ll INF=-10000000000;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}

//a,b x
int main(){
	ll A,B; cin>>A>>B;
  if(A+B<10) cout<<A+B;
  else cout<<"error";
      
}

Measured memory_bytes: 256
N = int(input())
CSF = [[int(_) for _ in input().split()] for _ in range(N-1)]

dp = [[0] * N for _ in range(N)]
for i in range(N):
    dp[i][i]=0
    for j in range(i,N-1):
        if dp[i][j] <= CSF[j][1]:
            dp[i][j+1] =CSF[j][0] + CSF[j][1]
        else:
            dp[i][j+1] = CSF[j][0] + CSF[j][2]*(1+(dp[i][j]-1)//CSF[j][2])

[print(dp[_][N-1]) for _ in range(N)]

Measured memory_bytes: 9168
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
 
ans = b[a[0]-1]
for i in range(1,n):
    ans += b[a[i]-1]
    if a[i]-a[i-1]==1:
        ans += c[a[i-1]-1]
print (ans)

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

          #define pb push_back
          #define cend(s) return cout << s, 0;
          using namespace std;
			int drr[3232];
          typedef long long ll;
          int main()
          {
            int n;
            cin >> n;
            n %= 10;
            if(n == 2 || n == 4 || n == 5 || n == 7 || n == 9)
              cend("hon");
            if(n == 0 || n == 1 || n == 6 || n == 8)
              cend("pon");
            cend("bon");      
          }

Measured memory_bytes: 3636
/// Code by Leonardo16
///   “It is not the strength of the body, but the strength of the spirit.”   —  J.R.R. Tolkien
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
//#pragma GCC target("avx2")

#define int long long
#define ll long long
#define sz size
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define fst first
#define scd second
#define vi vector<int>
#define vii vector<ii>
#define vs vector<string>
#define pb push_back
#define pf push_front
#define fl '\n'
#define el endl
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
/// Functions
#define db(x) cerr << #x << ": " << (x) << '\n';
#define random() __builtin_ia32_rdtsc()
#define lg2(x) 31-__builtin_clz(x)
#define lg2ll(x) 63-__builtin_clzll(x)
#define pi acos(-1)
#define YN(x) cout<<((x)?("YES"):("NO"))<<fl;
#define yn(x) cout<<((x)?("Yes"):("No"))<<fl;
#define des(x,s1,s2,end1,end2) cout<<((x)?(s1):(s2))<<fl;if(x){end1;}else{end2;}
#define precision(x) cout.setf(ios::fixed);cout.precision(x);
/// Red-Black Tree Template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
//#define less_than(n) order_of_key(n)
//#define en_pos(n) find_by_order(n)
/// Prime numbers  173,179,311,331,737,1009,2011,2027,3079,4001,100003
///=====================================================================

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

   int n;
   cin>>n;
   if(n%1000==0)cout<<0;
   else
   cout<<1000-(n%1000);
return 0;}




Measured memory_bytes: 3640
from sys import stdin
def input():
    return stdin.readline().strip()

n, k = map(int, input().split())
xy  = []
for _ in range(n):
    i, j = map(int, input().split())
    xy.append((i, j))

xy.sort()

# decide left, right, down
ans = float('inf')
for left in range(n-k+1):
    for right in range(left+k-1, n):
        choose = sorted(xy[left:right+1], key=lambda x: x[1])
        for down in range(len(choose)-k+1):
            area = (xy[right][0] - xy[left][0]) * (choose[down+k-1][1] - choose[down][1])
            if area < ans:
                ans = area

print(ans)

Measured memory_bytes: 73448