akhauriyash/Code-Regression huggingface dataset:
# 長さ 4 の数字列 S が与えられます。
# あなたは、この数字列が以下のフォーマットのどちらであるか気になっています。
# YYMM フォーマット:
# 西暦年の下 2 桁と、月を 2 桁で表したもの (例えば 1 月なら 01) をこの順に並べたもの
# MMYY フォーマット:
# 月を 2 桁で表したもの (例えば 1 月なら 01) と、西暦年の下 2 桁をこの順に並べたもの
# 与えられた数字列のフォーマットとして考えられるものが
# YYMM フォーマットのみである場合 YYMM を、
# MMYY フォーマットのみである場合 MMYY を、
# YYMM フォーマット と MMYY フォーマットのどちらの可能性もある場合 AMBIGUOUS を、
# どちらの可能性もない場合 NA を出力してください。

s = gets.chomp

yymm = false
mmyy = false

front = s[0].to_i * 10 + s[1].to_i
back = s[2].to_i * 10 + s[3].to_i

yymm = true if 0 < back && back < 13
mmyy = true if 0 < front && front < 13

if yymm && mmyy
    puts "AMBIGUOUS"
elsif yymm
    puts "YYMM"
elsif mmyy
    puts "MMYY"
else
    puts "NA"
end

Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
const int N = 2001;
int b[N][N],w[N][N];
// w[i][j] : min cost to move i+1 white ball to pos i+j+1 with i white & j black ball in front 
// need to find the number of balls behind that be move in front
int pw[N][N],pb[N][N];		// (i,j)	so bong white <= j in front ith black
int type[2*N],val[2*N];
int posw[N],posb[N];
int b_b[N],b_w[N];
int w_behind[N][N],b_behind[N][N];
int dp[N][N];
const int inf = 1e8;
int n;
void p1()
{
	int i,j;
	for(i=0;i<=n;i++)	for(j=0;j<=n;j++)	b_behind[i][j]=w_behind[i][j] = 0;
	for(i=0;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			w_behind[i][j] = w_behind[i][j-1];
			if(posw[j]>posb[i])	w_behind[i][j]++;
		}
	}
	for(i=0;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			b_behind[i][j] = b_behind[i][j-1];
			if(posb[j]>posw[i])	b_behind[i][j]++;
		}
	}
}
void p2()
{
	int i,j;
	for(i=0;i<=n;i++)	b_b[i]=b_w[i]=0;
	for(i=0;i<=n;i++)
	{
		for(j=posb[i];j<=2*n;j++)
		{
			if(type[j]==0&&val[j]<i)
			{
				b_b[i]++;
			}
		}
	}
	for(i=0;i<=n;i++)
	{
		for(j=posw[i];j<=2*n;j++)
		{
			if(type[j]==1&&val[j]<i)
			{
				b_w[i]++;
			}
		}
	}
}
void p3()
{
	int i,j;
	for(i=0;i<=n;i++)	for(j=0;j<=n;j++)	pw[i][j]=pb[i][j]=0;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			pb[i][j] = b_b[i] + w_behind[i][j];
			pw[i][j] = b_w[i] + b_behind[i][j];
		}
	}
}
void p4()
{
	int i,j;
	for(i=0;i<=n;i++)	for(j=0;j<=n;j++)	b[i][j]=w[i][j]=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<=n;j++)
		{
			b[i][j] = posb[i+1] + pb[i+1][j];
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<=n;j++)
		{
			w[i][j] = posw[i+1] + pw[i+1][j];
		}
	}
}
int main()
{
	int i,j;
	scanf("%d",&n);
	char c;
	posb[0]=posw[0]=0;
	bool c1=true,c2=true;
	for(i=1;i<=2*n;i++)
	{
		scanf(" %c %d",&c,&val[i]);
		if(c=='B')	
		{
			type[i]=0;
			posb[val[i]]=i;
		}
		else		
		{
			type[i]=1;
			posw[val[i]]=i;
		}
	}
	for(i=1;i<n;i++)
	{
		if(posb[i]>posb[i+1])
		{
			c1 = false;
			break;
		}
	}
	for(i=1;i<n;i++)
	{
		if(posw[i]>posw[i+1])
		{
			c2 = false;
			break;
		}
	}
	if(c1==true&&c2==true)
	{
		printf("0");
		return 0;
	}
	p1();p2();p3();p4();
/*	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			printf("%d ",pb[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			printf("%d ",pw[i][j]);
		}
		printf("\n");
	}
	printf("\n");		*/
/*	for(i=0;i<n;i++)
	{
		for(j=0;j<=n;j++)
		{
			printf("%d ",b[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<=n;j++)
		{
			printf("%d ",w[i][j]);
		}
		printf("\n");
	}
	printf("\n");	*/
	for(i=0;i<=n;i++)	for(j=0;j<=n;j++)	dp[i][j]=inf;
	dp[0][0]=0;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			if(dp[i][j]!=inf)
			{
				dp[i+1][j] = min(dp[i+1][j] , dp[i][j] + b[i][j] - (i+j+1));
				dp[i][j+1] = min(dp[i][j+1] , dp[i][j] + w[j][i] - (i+j+1));
			}
		}
	}
	printf("%d",dp[n][n]);
}


Measured memory_bytes: 113380
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  int A, V, B, W;
  cin >> A >> V >> B >> W;
  int T;
  cin >> T;

  if (W >= V)
  {
    cout << "NO" << endl;
    return 0;
  }

  int diff = std::abs(A - B);
  int diff_speed = V - W;
  int mn_time = (diff + diff_speed - 1) / diff_speed;

  if (mn_time > T)
  {
    cout << "NO" << endl;
    return 0;
  }

  cout << "YES" << endl;

  return 0;
}


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

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

  int n;
  cin >> n;

  int d[MAX] = {};

  for (int i = 1; i <= 100; ++i) {
    for (int j = 1; j <= 100; ++j) {
      for (int k = 1; k <= 100; ++k) {
        int v = i*i + j*j + k*k + i*j + i*k + j*k;
        if (v > MAX) continue;
        ++d[v];
      }
    }
  }

  for (int i = 1; i <= n; ++i) cout << d[i] << '\n';

  return (0);
}


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

int main() {

  string S = "";
  string T = "";

  cin >> S >> T;

  for (int i = 0; i < S.length(); i++) {
    if (S[i] != T[i]) {
      cout << "No" << endl;
      return 0;
    }
  }

  if (T.length() != S.length() + 1) {
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    //freopen("in.txt","r",stdin);
    ll n,k;
    scanf("%lld%lld",&n,&k);
    n%=k;
    printf("%lld\n",min(n,k-n));
    return 0;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;


void solve()
{
	int a, b;
	cin >> a >> b;
	cout << max(0, a - 2 * b);
}

int main()
{
	fastio;
	solve();

	return 0;
}

Measured memory_bytes: 256
S = input()[::-1]
import sys
sys.setrecursionlimit(1000)
c = ['maerd', 'remaerd', 'esare', 'resare']

def dfs(s):
    L = len(s)
    while 1:
        if L==0:
            return True
        if L<5:
            return False
        if s[:5] in c:
            s = s[5:]
            L -= 5
        elif L>=6 and s[:6]=='resare':
            s = s[6:]
            L -= 6
        elif L>=7 and s[:7]=='remaerd':
            s = s[7:]
            L -= 7
        else:
            return False

if dfs(S):
    print('YES')
else:
    print('NO')
        

Measured memory_bytes: 3316
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cstring>
#include<cmath>
#include <numeric>
#include<queue>
#include<climits>
#include<cstdio>


#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 ((LLONG_MAX) / (2))
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;
typedef pair<ll,int> LL_IP;
#define INF 1e9+7

int main(){

    string s;
    cin >> s;
    int len = s.length();
    int ans = 0;
    bool flag = true;
    string t = s.substr(0,1);

    for(int i = 1;i < s.length();i++){
        if(s[i] != '9'){
            flag = false;
        }
    }

    if(flag){
        ans = stoi(t) + 9*(len-1);
    }else{
        ans = stoi(t) + 9*(len-1)-1;
    }

   
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

x, y, c = [], [], []
for _ in range(M):
    xi, yi, ci = map(int, input().split())
    x.append(xi)
    y.append(yi)
    c.append(ci)

# print(A, B, M)
# print(a)
# print(b)
# print(x)
# print(y)
# print(c)

# M個全部試す or min同士
cost1 = min(a) + min(b)
cost = [cost1]

for j in range(M):
    xj, yj, cj = x[j], y[j], c[j]
    costj = a[xj - 1] + b[yj - 1] - cj
    cost.append(costj)

print(min(cost))

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

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> u(n/2), v(n/2); for (int i = 0; i < n/2; i++) cin >> u[i] >> v[i];

    int v_max = 100000;
    vector<int> x(v_max), y(v_max);
    for (int i = 0; i < n/2; i++) {
        x[u[i]]++;
        y[v[i]]++;
    }

    int x_first_index = distance(x.begin(), max_element(x.begin(), x.end()));
    int y_first_index = distance(y.begin(), max_element(y.begin(), y.end()));
    bool flag = (x_first_index != y_first_index);

    sort(x.begin(), x.end(), greater<int>());
    sort(y.begin(), y.end(), greater<int>());

    int ans = n + 1;
    if (flag) {
        ans = n - x[0] - y[0];
    } else {
        ans = min(ans, min(n - x[0] - y[1], n - x[1] - y[0]));
    }

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

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define here(x) cout << " #x = " << x << endl;
#define show(x) {for( auto ii : x) cout << ii << setw(4); cout << endl;}
#define shop(n,x) {for(int i = 0; i < n; i++) cout << x << setw(4); cout << endl;}
#define ff first
#define ss second
#define sq(x) (x*x)
#define endl '\n'
#define en " "
#define pb push_back
#define mpair make_pair
ll mod=1000000007;
double pi=3.1415926536;
ll dp[300000];
ll win(ll a[], ll n, ll k)
{
	if(k >=0 && dp[k] != -1)
		return dp[k];
	if(k <= 0)
		return 2;

	for(ll i = 0; i < n; i++)
	{
		if(k - a[i] <= 0)
			return 2;
		ll p = win(a, n, k - a[i]);
		if(p == 2)
			return dp[k] = 1;
	}
	return dp[k] = 2;
}
int main()
{
	fastio();
	int tt = 1;
	//cin >> tt;
	while(tt--)
	{
		// go fast 		check		//		CHECK -> if()   else if()
		
		ll n, x=0, m=0, y=0, d=1, k=mod;
		cin >> n >> k;
		ll a[n];
		memset( dp, -1, sizeof(dp));
		dp[0] = 2;
		for(ll i = 0; i < n; i++)
		{
			cin >> a[i];
			dp[a[i]] = 1;
		}
		x = win(a, n, k);
		if(x == 1)
			cout << "First" << endl;
		else
			cout << "Second" << endl;
	}
}

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

using namespace std;

int main(){
    string S; cin >> S;
    const int N = S.size();
    int K; cin >> K;
    int res = 0;
    vector<vector<vector<int>>> dp(K+1, vector<vector<int>>(N, vector<int>(N, 0)));
    for(int d=N-1;d>=0;d--){
        for(int i=0;i+d<N;i++){
            int j = i+d;
            for(int k=0;k<=K;k++){
                if(k < K && S[i] != S[j]){
                    res = max(res, dp[k][i][j] + 2);
                    if(i+1 < N && j > 0){
                        dp[k+1][i+1][j-1] = max(dp[k+1][i+1][j-1], dp[k][i][j] + 2);
                    }
                }
                if(S[i] == S[j]){
                    res = max(res, dp[k][i][j] + (i==j ? 1 : 2));
                    if(i+1 < N && j > 0){
                        dp[k][i+1][j-1] = max(dp[k][i+1][j-1], dp[k][i][j] + (i==j ? 1 : 2));
                    }
                }
                if(i+1 < N) dp[k][i+1][j] = max(dp[k][i+1][j], dp[k][i][j]);
                if(j > 0) dp[k][i][j-1] = max(dp[k][i][j-1], dp[k][i][j]);
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 109952
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        if(N % 111 == 0){
            System.out.println(N);
            return;
        }
        int DN = N/111;
        System.out.println(111 * (DN + 1));
    }
}


Measured memory_bytes: 22100
fn read<T: std::str::FromStr>() -> T {
	let mut s = String::new();
	std::io::stdin().read_line(&mut s).ok();
	s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
	read::<String>().split_whitespace()
		.map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
	(0..n).map(|_| read_vec()).collect()
}

pub trait LexicalPermutation {
	/// Return `true` if the slice was permuted, `false` if it is already
	/// at the last ordered permutation.
	fn next_permutation(&mut self) -> bool;
}
impl<T> LexicalPermutation for [T] where T: Ord {
	/// Original author in Rust: Thomas Backman <serenity@exscape.org>
	fn next_permutation(&mut self) -> bool {
		// These cases only have 1 permutation each, so we can't do anything.
		if self.len() < 2 { return false; }

		// Step 1: Identify the longest, rightmost weakly decreasing part of the vector
		let mut i = self.len() - 1;
		while i > 0 && self[i-1] >= self[i] {
			i -= 1;
		}

		// If that is the entire vector, this is the last-ordered permutation.
		if i == 0 {
			return false;
		}

		// Step 2: Find the rightmost element larger than the pivot (i-1)
		let mut j = self.len() - 1;
		while j >= i && self[j] <= self[i-1]  {
			j -= 1;
		}

		// Step 3: Swap that element with the pivot
		self.swap(j, i-1);

		// Step 4: Reverse the (previously) weakly decreasing part
		self[i..].reverse();

		true
	}
}

fn main() {
	let n: usize = read();
	let mut a: Vec<usize> = Vec::new();
	let mut graph: Vec<Vec<isize>> = vec![vec![-1; n]; n];
	for i in 0..n {
		let count: usize = read();
		for _ in 0..count {
			let tmp: Vec<usize> = read_vec();
			graph[i][tmp[0] - 1] = tmp[1] as isize;
		}
	}

	let mut ans = 0;
	for bit in 0..(1 << n) {
		let mut d: Vec<isize> = vec![0; n];
		for i in 0..n {
			if bit & (1 << i) != 0 {
				d[i] = 1;
			}
		}

		let mut ok: bool = true;
		for i in 0..n {
			if d[i] == 1 {
				for j in 0..n {
					if graph[i][j] == -1 { continue; }
					if graph[i][j] != d[j] { ok = false; }
				}
			}
		}

		if ok {
			let mut tmp_count = 0;
			for i in 0..n {
				if d[i] == 1 { tmp_count += 1; }
			}
			ans = std::cmp::max(ans, tmp_count);
		}
	}

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


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

typedef long long ll;
const int maxn=5e3+10,mod=1e9+7;
int n,size[maxn],maxd[maxn],rt;
ll dp[maxn],ans;
vector<int> g[maxn];
ll fac[maxn],c[maxn][maxn];

void dfs1(int pos,int fa){
	size[pos]=1;
	for(int i=0;i<g[pos].size();++i)
		if(g[pos][i]!=fa){
			dfs1(g[pos][i],pos);
			size[pos]+=size[g[pos][i]];
			maxd[pos]=max(maxd[pos],size[g[pos][i]]);
		}
	maxd[pos]=max(maxd[pos],n-size[pos]);
}

int main(){
	fac[0]=1;
	for(int i=1;i<maxn;++i)
		fac[i]=fac[i-1]*i%mod;
	for(int i=0;i<maxn;++i){
		c[i][0]=1;
		for(int j=1;j<=i;++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0);
	for(int i=1;i<=n;++i)
		if(maxd[i]<=n/2)
			if(rt){
				printf("%lld\n",fac[n/2]*fac[n/2]%mod);
				return 0;
			}
			else
				rt=i;
	dfs1(rt,0);
	dp[0]=1;
	for(int i=0;i<g[rt].size();++i){
		int now=size[g[rt][i]];
		for(int i=n;i;--i)
			for(int j=i-1;~j&&i-j<=now;--j)
				(dp[i]+=dp[j]*c[now][i-j]%mod*c[now][i-j]%mod*fac[i-j])%=mod;
	}
	for(int i=0;i<=n;++i)
		(ans+=(i&1?-1:1)*dp[i]*fac[n-i])%=mod;
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}

Measured memory_bytes: 195200
import java.util.Scanner;



public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] array = new int[6 + 1];
		array[0] = 0;
		for (int i = 1; i < array.length; i++) {
			array[i] = scan.nextInt();
		}
		String order = scan.next();
		scan.close();
		Dice dice = new Dice(array);
		array = dice.roll(dice.getNum(), order);
		System.out.println(array[1]);
	}
}
	

class Dice {
	int[] num = new int[6 + 1];
	Dice() {
	}

	Dice(int[] array) {
		for (int i = 0; i < array.length; i++) {
			this.num[i] = array[i];
		}
	}
	
	public int[] getNum() {
		return this.num;
	}
	
	public int getNumber(int i) {
		return this.num[i];
	}
	
	// ??????????????¢??????????????????
	public int[] roll(int[] ary, String order) {
		int now_1 = 1;	int now_2 = 2;	int now_3 = 3;	int tmp;
		int[] array = ary;
		char[] check = {'N', 'E', 'S', 'W'};
		for (int i = 0; i < order.length(); i++) {
			for (int j = 0; j < check.length; j++) {
				if (order.charAt(i) == check[j]) {
					switch (j + 1) {
						case 1:
							tmp = now_1;
							now_1 = now_2;
							now_2 = 7 - tmp;
							break;
						case 2:
							tmp = now_1;
							now_1 = 7 - now_3;
							now_3 = tmp;
							break;
						case 3:
							tmp = now_1;
							now_1 = 7 - now_2;
							now_2 = tmp;
							break;
						case 4:
							tmp = now_1;
							now_1 = now_3;
							now_3 = 7 - tmp;
							break;
					}
				}
			}
		}
		int[] cp_array = new int[array.length];
		cp_array[1] = array[now_1]; cp_array[2] = array[now_2];
		cp_array[3] = array[now_3]; cp_array[4] = array[7 - now_3];
		cp_array[5] = array[7 - now_2]; cp_array[6] = array[7 -now_1];
		return cp_array;
	}
	
	public void print(int[] array) {
		for (int i = 1; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}
}

Measured memory_bytes: 26340
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-6;
long long n,y;
double x1,x2;
int main(){
    while(cin>>n){
        cin>>y;
        int i;
        for(i=0;i<=n;i++){
            x1=((y*1.0)/1000-4*i-n)/9;
            int ans=n-x1-i;
            //cout<<abs(x1-(int)x1)<<endl;
            if(abs(x1-(int)x1)<eps&&x1>=0&&ans>=0){
                cout<<x1<<" "<<i<<" "<<(n-x1-i)<<endl;
                break;
            }
        }
        if(i==n+1)
            cout<<-1<<" "<<-1<<" "<<-1<<endl;
    }
    return 0;
}


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

namespace AtCoderPractice
{
    class MixJuice
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split();
            int[] p = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var n = int.Parse(input[0]);
            var k = int.Parse(input[1]);
            var sum = 0;
            var query = p.OrderBy(x => x).ToArray();
            for(int i = 0; i < k; i++)
            {
                sum += query[i];
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 28412
import fractions
 
a, b, c, d = map(int, input().split())
 
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
cd = lcm(c, d)
 
div_c = b // c - (a-1)//c
div_d = b // d - (a-1)//d
div_cd = b // cd - (a-1)//cd
count = b - a + 1 - div_c - div_d + div_cd
print(count)

Measured memory_bytes: 5048
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
LL Q, A, M;

LL phi(LL x) {
    LL ret = x;
    for(LL i = 2; i * i <= x; i++)
        if (x % i == 0) {
            ret = ret * (i - 1) / i;
            while (x % i == 0) x /= i;
        }
    if (x > 1) ret = ret * (x - 1) / x;
    return ret;
}

LL Pow(LL x, LL p, LL Mo) {
    LL ret = 1;
    for(; p; p = p / 2, x = (x * x) % Mo)
        if (p & 1) ret = (ret * x) % Mo;
    return ret;
}

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;return a;
    } else {
        LL ret = exgcd(b, a % b, y, x);
        y -= x * (a / b);
        return ret;
    }
}

LL sol(LL A, LL M) {
    if (M == 1) return 1;
    LL p = phi(M), g = __gcd(M, p);
    LL x = sol(A, g);
    LL tx = x % p, Ax = Pow(A, x, M), X, Y;
    exgcd(M, p, X, Y);
    X = (X * ((tx - Ax) / g)) % (p / g);
    if (X <= 0) X += (p / g);
    return Ax + X * M;
}
    
int main() {
    cin >> Q;
    while (Q--) {
        cin >> A >> M;
        LL K = sol(A, M);
        //cout << (Pow(A, K, M) == K % M) << endl;
        cout << K << endl;
    }
}


Measured memory_bytes: 256
package main

import (
        "fmt"
        "strconv"
        "strings"
)

func main() {
        var a string
        fmt.Scan(&a)
        b := strings.Split(a, "/")
        var year int
        var month int
        var day int
        year, _ = strconv.Atoi(b[0])
        month, _ = strconv.Atoi(b[1])
        day, _ = strconv.Atoi(b[2])
        if year > 2019 {
                fmt.Println("TBD")
                return
        } else if year < 2019 {
                fmt.Println("Heisei")
                return
        } else {
                if month > 4 {
                        fmt.Println("TBD")
                } else if month < 4 {
                        fmt.Println("Heisei")
                } else {
                        if day > 30 {
                                fmt.Println("TBD")
                        } else {
                                fmt.Println("Heisei")
                        }
                }
        }
}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using tsii = tuple<string, int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    int n,ans=0,before=-2;
    cin>>n;
    vector<int> a(n),b(n),c(n-1);
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++)
    {
        cin>>b[i];
    }
    for (int i = 0; i < n-1; i++)
    {
        cin>>c[i];
    }
    for (int i = 0; i < n; i++)
    {
        int now=a[i];
        ans+=b[now];
        if(now==before+1)
        {
            ans+=c[before];
        }
        before=now;
    }
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <random>

using namespace std;

int main(){
  int paths[4] = {};
  for(int i=0;i <3;i++){
    int buf,buf2;
    cin >> buf>>buf2;
    paths[buf-1]++;
    paths[buf2-1]++;
  }
  int cnt = 0;
  for(int i=0;i<4;i++){
    if(paths[i] & 1){
      cnt++;
    }
  }
  cout << ((cnt == 1 || cnt >2) ? "NO" : "YES")<< endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int a, b, c, d, e, k;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;
    cin >> e;
    cin >> k;
    if (b - a <= k && c - a <= k && d - a <= k && e - a <= k && c - b <= k && d - b <= k && e - b <= k && d - c <= k && e - c <= k && e - d <= k)printf("Yay!");
    else printf(":(");
}

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

int main() {
	int a,b;
	cin >>a>>b;
	if(a>b){
		cout<<"a > b"<<endl;
	}else{
		if(a<b){
			cout<<"a < b"<<endl;
		}else{
			cout<<"a == b"<<endl;
		}
	}
}

Measured memory_bytes: 3072
using System;

namespace ITP1_6_B
{
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            bool[,] have = new bool[4, 13];

            for (int i = 0; i < n; i++)
            {
                string[] str = Console.ReadLine().Split(' ');

                if (str[0] == "S") have[0, int.Parse(str[1]) - 1] = true;

                else if (str[0] == "H") have[1, int.Parse(str[1]) - 1] = true;

                else if (str[0] == "C") have[2, int.Parse(str[1]) - 1] = true;

                else have[3, int.Parse(str[1]) - 1] = true;
            }

            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 13; j++)
                {
                    if (have[i, j] != true)
                    {
                        if (i == 0) Console.WriteLine("S {0}", j + 1);

                        else if (i == 1) Console.WriteLine("H {0}", j + 1);

                        else if (i == 2) Console.WriteLine("C {0}", j + 1);

                        else Console.WriteLine("D {0}", j + 1);
                    }
                }
            }
       }
    }
}

Measured memory_bytes: 9168
#include <iostream>

#define _for(i, j, k) for(int i = j; i <= k; i++)

using std::cin;
using std::cout;

typedef long long ll;

ll a[110][110], b[110][110], c[110][110];

int main() {
	int n, m, l;
	cin >> n >> m >> l;
	_for(i, 1, n) {
		_for(j, 1, m) cin >> a[i][j];
	}
	_for(i, 1, m) {
		_for(j, 1, l) cin >> b[i][j];
	}
	_for(i, 1, n) {
		_for(j, 1, l) {
			_for(k, 1, m) c[i][j] += a[i][k] * b[k][j];
		}
	}
	_for(i, 1, n) {
		bool f = 1;
		_for(j, 1, l) {
			if(f) f = 0;
			else cout << ' ';
			cout << c[i][j];
		}
		cout << '\n';
	}
	return 0;
}


Measured memory_bytes: 3368
n = int(input())
s = input()
white_count = 0
black_count = 0

for c in s:
    if c == ".":
        white_count += 1

maybe_answer_list = []

maybe_answer_list.append(white_count + black_count)

for c in s:
    if c == "#":
        black_count += 1
    else:
        white_count -= 1
    maybe_answer_list.append(white_count + black_count)

print(min(maybe_answer_list))

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

bounds = [0]

for i in range(1, n+1):
  bounds.append(bounds[i-1] + l[i-1])
  
count = 0

for i in range(len(bounds)):
  if bounds[i] <= x:
    count += 1
    
print(count)

Measured memory_bytes: 38384
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;

string s,t;
int n;

int main(){
	cin >> n;
	cin >> s >> t;
	for(int i = 0;i < n;i ++) cout << s[i] << t[i];
	cout << endl;
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  
  string ans;
  ans = "Yes";
  if(n%2 == 1){
    cout << "No" << endl;
    return 0;
  }
  //cout << s[1] << endl;
  for(int i=0;i<n/2;i++){
    if(s[i]!=s[n/2+i]) ans = "No" ;
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;

int main(void){
    int n,k;
    string s;
    cin >> n >> k >> s;
    s[k-1]=s[k-1]-'A'+'a';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 764
#include <stdio.h>

int gcd(int x, int y) {
	if (y == 0)
		return x;
	return gcd(y, x % y);
}

int main() {
	int n, ans = 0, a;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		ans = gcd(ans, a);
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define MOD 1000000007
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(v) (v).begin() , (v).end()
#define sumof(v) accumulate(all(v), 0LL, plus<ll>())
#define maxof(v) max_element(all(v))
#define minof(v) min_element(all(v))
#define inf INT_MAX

int main(){
    FASTIO
    int x; cin>>x;
    if(x>=30) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3648
#include<cstdio>
long long x,s=101,n;
int main(){
    scanf("%lld",&n);
    for(register int i=0;i<n;++i){
        scanf("%lld",&x);
        short cnt=0;
        while(!(x%2)){
            x/=2;
            ++cnt;
        }
        s=s<cnt?s:cnt;
    }
    printf("%lld\n",s);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstring>
#define re register int
using namespace std;

int n,tmp,even,odd;

int main()
{
	std::cin>>n;
	
	for(re i=1;i<=n;i++)
	{
		std::cin>>tmp;
		if(tmp%2==0)
			even++;
		else
			odd++;
	}
	
	if((even==n)||(odd%2==0))
		std::cout<<"YES";
	else
		std::cout<<"NO";
		
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>

using namespace std;

int main()
{
	int n, e=0;
	long long int a, b, c, d;
	scanf("%d %lld %lld %lld %lld", &n, &a, &b, &c, &d);
	
	for(int i=1; i<=n; i++){
		if(b-(n-i)*d+(i-1)*c<=a && a<=b-(n-i)*c+(i-1)*d){
			e=1;
		}
	}
	if(e==0){
		printf("%s\n", "NO");
	}else{
		printf("%s\n", "YES");
	}
	return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < n; ++i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define stl_repr(itr, x) for (auto itr = x.rbegin(); itr != x.rend(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

using llong = long long int;

const static int MOD = 1000000000 + 7;
const static int inf = INT_MAX / 2;
const static llong INF = 1LL << 61;
const static int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main (int argc, char *argv[]) {
    cin.tie(0); 
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<long double> ingredient(n);
    rep(i, n) cin >> ingredient[i];
    
    sort(all(ingredient));
    for (int i = 0; i < n - 1; ++i) {
        ingredient[i + 1] = (ingredient[i] + ingredient[i + 1]) / 2;
    }

    cout << ingredient[n - 1] << endl;
    
    return 0;
}

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

#define ll long long

int main()
{
    string s;
    cin>>s;
    if(s[0]=='R'&&s[1]=='R'&&s[2]=='R')
    {
        cout<<3<<endl;
    }
    else if((s[0]=='R'&&s[1]=='R')||(s[2]=='R'&&s[1]=='R'))
    {
        cout<<2<<endl;
    }
    else if(s[0]=='R'||s[1]=='R'||s[2]=='R')
    {
        cout<<1<<endl;
    }
    else
    {
        cout<<0<<endl;
    }


}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    VI a(n);
    REP(i,n) {
        cin >> a[i];
        a[i]--;
    }
    int now=0, cnt=0;
    while ( now!=1 ) {
        if ( a[now]==now ) {
            cout << -1 << '\n';
            return 0;
        }
        cnt++;
        int next=a[now];
        a[now]=now;
        now=next;
    }
    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 3716
H, W = map(int, input().split())
A = [input() for _ in range(H)]

while '.' * W in A:
    A.remove('.' * W)

remove_j = set()
for j in range(W):
    if set([A[i][j] for i in range(len(A))]) == {'.'}:
        remove_j.add(j)

active_j = set(range(W)) - remove_j
active_j = sorted(list(active_j))
for a in A:
    print(''.join([a[j] for j in active_j]))


Measured memory_bytes: 3188
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

template<typename T>
struct Monoid {
  T id;
  fn<T(T, T)> op;
  Monoid(T e, fn<T(T, T)> f)
    : id(e), op(f) {
  }
};

template<typename T>
class SegT {
private:
  vector<T> data;
  Monoid<T> monoid;
  int size = 1;

public:
  SegT(const int &n, const Monoid<T> &m = Monoid<int>(INF, [](int a, int b) { return min(a, b); }))
    : monoid(m) {
    while (size < n) size *= 2;
    data = vector<T>(2 * size, monoid.id);
  }

  void update(int i, const T &x) {
    i += size;
    data[i]                = x;
    while (i /= 2) data[i] = monoid.op(data[i * 2], data[i * 2 + 1]);
  }

  // fold [a, b) by monoid.op
  T fold(const int &a, const int &b, const int &k = 1, const int &l = 0, int r = -1) {
    if (r == -1) r = size;
    if (r <= a || b <= l) return monoid.id;
    if (a <= l && r <= b) return data[k];
    return monoid.op(fold(a, b, k * 2, l, (l + r) / 2),
                     fold(a, b, k * 2 + 1, (l + r) / 2, r));
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  SegT<int> t(n, Monoid<int>(2147483647, [](int a, int b) { return min(a, b); }));
  while (q--) {
    int com, x, y;
    cin >> com >> x >> y;
    if (com) {
      cout << t.fold(x, y + 1) << endl;
    } else {
      t.update(x, y);
    }
  }
}

Measured memory_bytes: 4940
#include<stdio.h>
#define N 100000

int parent(int i){return i/2;}
int left(int i){return 2*i;}
int right(int i){return 2*i+1;}

int main(){
    int Htw,i,Atw[N+1];

    scanf("%d",&Htw);
    for(i=1;i<=Htw;i++)scanf("%d",&Atw[i]);

    for(i=1;i<=Htw;i++){
        printf("node %d: key = %d, ",i,Atw[i]);
        if(parent(i)>=1)printf("parent key = %d, ",Atw[parent(i)]);
        if(left(i)<=Htw)printf("left key = %d, ",Atw[left(i)]);
        if(right(i)<=Htw)printf("right key = %d, ",Atw[right(i)]);
        printf("\n");
    }

    return 0;
}


Measured memory_bytes: 2112
//#define LOCAL

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <climits>

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

#define int long long

using namespace std;

int N;
int A;
map<int, int> cnt;

int mod_pow(int x, int n, int mod) {
    if (n == 0) return 1;
    int res = mod_pow(x * x % mod, n / 2, mod);
    if (n & 1) res = res * x % mod;
    return res;
}

signed main()
{
#ifdef LOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif

    cin >> N;
    rep(i,N) {
        cin >> A;
        cnt[A]++;
    }

    if (N % 2 == 0) {
        for (int i=1; i<=N-1; i+=2) {
            if (cnt[i] != 2) {
                cout << 0 << endl;
                return 0;
            }
        }
    } else {
        if (cnt[0] != 1) {
            cout << 0 << endl;
            return 0;
        }
        for (int i=2; i<=N-1; i+=2) {
            if (cnt[i] != 2) {
                cout << 0 << endl;
                return 0;
            }
        }
    }

    cout << mod_pow(2, N / 2, 1000000007) << endl;
}


Measured memory_bytes: 4224
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,ans=0;//n-switch,m-lit
struct lit
{
	int num;
	int ask[17];
	int ode;//odevity
	int cnt=0;
};
int fun(int x[])
{
	int i;
	for(i=1;i<=n;i++)
		if(x[i]!=1)
		{
			x[i]=1;
			return 0;
		}
		else
			x[i]=0;
			return 0;
}
int main(){
	//输入 
	cin>>n>>m;
	int x[n+7];memset(x,0,sizeof(x));
	lit b[m+7];
	for(int i=1;i<=m;i++)
	{
		cin>>b[i].num;
		for(int j=1;j<=b[i].num;j++)
		{
			cin>>b[i].ask[j];
		}
	}
	for(int i=1;i<=m;i++)
		cin>>b[i].ode;
	//功能 
	for(int i=1;i<=pow(2,n);i++)//开关组合数 
	{
		fun(x);
		for(int j=1;j<=m;j++)//灯数 
		{
			b[j].cnt=0;
			for(int k=1;k<=b[j].num;k++)//每灯关联开关数 
			{
				if(x[b[j].ask[k]]==1)
				{
					b[j].cnt++;
					continue;
				}
			}
			if(b[j].cnt%2==b[j].ode)
			{
				if(j<m) continue;
				else 
					ans++;
			}
			else break;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>

struct Range {
    Range(size_t min, size_t max) : valid(min <= max), min(min), max(max) {}
    bool valid;
    size_t min, max;
};


size_t div_ceil(size_t x, size_t y) {
    size_t div = x / y;
    if (x % y == 0) {
        return div;
    } else {
        return div + 1;
    }
}

Range without_tax(size_t rate, size_t value) {
    const size_t min = div_ceil(100 * value, rate);
    const size_t max = (100 * value + 99) / rate;
    return Range(min, max);
}

Range isect(const Range &a, const Range &b) {
    return Range(std::max(a.min, b.min), std::min(a.max, b.max));
}

int main() 
{
    size_t a, b;
    std::cin >> a >> b;
    auto r8 = without_tax(8, a);
    auto r10 = without_tax(10, b);
    auto r = isect(r8, r10);
    if (r.valid) {
        std::cout << r.min << std::endl;
    } else {
        std::cout << -1 << std::endl;
    }
    return 0;
}


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

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  int N, K;
  while(cin >> N >> K,N){
  VI xs(K); REP(i,K) cin >> xs[i];
  SORT(xs);

  int ans = 1;
  if(xs[0] == 0){
	ans = 2;
	int prv = -10, ok = 1, p = 0;
	VI n(2, 0);
	FOR(i,1,K){
	  if(prv == xs[i]-1){
		prv = xs[i];
		++n[p];
		ans = max(ans, 1+(ok?0:n[1-p])+n[p]);
	  }
	  else if(prv == xs[i]-2){
		prv = xs[i];
		p = 1 - p;
		n[p] = 1;
		ok = 0;
		ans = max(ans, 1+n[0]+n[1]);
	  }
	  else{
		ok = 1;
		prv = xs[i];
		n[0] = n[1] = 0;
		n[p] = 1;
	  }
	}
  }
  else{
	int prv = -1, num = 0;
	REP(i,K){
	  if(prv == xs[i]-1){
		prv = xs[i];
		ans = max(ans, ++num);
	  }
	  else{
		prv = xs[i];
		num = 1;
	  }
	}
  }
  
  cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1524
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

vector<vector<P>> v(15, vector<P>(15));

vector<vector<bool>> bit_full_search(int N) {
  vector<vector<bool>> res;
  res.resize(1<<N);
  for (int bit = 0; bit < (1<<N); bit++) {
    rep(i,N) {
      res.at(bit).push_back((bit & 1<<i));
    }
  }
  return res;
}

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

  int n;
  cin >> n;

  v.resize(n);
  rep(i,n) {
    int a;
    cin >> a;
    v.at(i).resize(a);
    rep(j,a) {
      int x,y; cin >> x >> y;
      v.at(i).at(j) = P(x,y);
    }
  }

  // 嘘か真か調べ上げる
  auto res = bit_full_search(n);
  int ans = 0;
  for (auto x: res) {
    bool success = true;
    rep(i,n) {
      auto vv = v.at(i);
      for (auto p: vv) {
        if (x.at(i)) {
          if (p.second != x.at(p.first-1)) {
            success = false;
          }
        }
      }
    }
    if (success) {
      ans = max(ans, accumulate(all(x), 0));
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2560
#include <iostream>

using namespace std;

const int mod = 1'000'000'007;
int sum[401][401], map[400][401];

int main()
{
	int n, c, a[400], b[400];
	cin >> n >> c;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < n; ++i) cin >> b[i];

	for (int i = 1; i <= 400; ++i) {
		long long cur = 1;
		for (int j = 0; j <= c; ++j) {
			sum[i][j] = cur;
			cur = (cur*i) % mod;
		}
	}
	for (int j = 0; j <= c; ++j)
		for (int i = 1; i <= 400; ++i) sum[i][j] = (sum[i][j] + sum[i - 1][j]) % mod;

	for (int j = 0; j <= c; ++j) map[0][j] = sum[b[0]][j] - sum[a[0] - 1][j];
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j <= c; ++j) {
			int ss = 0;
			for (int k = 0; k <= j; ++k) {
				ss = (ss + (map[i - 1][k] * (long long)(sum[b[i]][j - k] - sum[a[i] - 1][j - k]))) % mod;
			}
			map[i][j] = ss;
		}
	}

	cout << (map[n - 1][c] + mod) % mod << endl;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#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 DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define VPII vector<pair<int,int> >
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const LL MOD = 1e9+7;
const int INF = 1<<30;
int MAXN = 1e5+2;
const double eps = 1e-13;

int main(){
	LL n;
	scanf("%lld",&n);
	REPP(a,1,3501){
		REPP(b,1,3501){
			if((4LL*a*b-n*b-n*a)<=0)continue;
			if((n*a*b) % (4LL*a*b-n*b-n*a)==0){
				printf("%d %d %lld\n",a,b,(n*a*b)/(4LL*a*b-n*b-n*a));
				return 0;
			}
		}
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<utility>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,m,n) for(ll i=m;i<n;i++)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FORR(i,n,m) for(ll i=n;i>=m;i--)

int main(){
    ll a,b,ans=0;
    cin >> a >> b;
    FOR(i,a,b+1){
        if( i/10000 == i%10 ){
            if((i%10000)/1000 == (i%100)/10){
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = list(map(int, input().split()))
Q = int(input())
T = list(map(int, input().split()))

def binary_search(target_num, head, tail):
    idx = int((head+tail)/2)
    if target_num == S[idx]:
        return True
    elif target_num < S[idx]:
        if head == idx:
            return False
        return binary_search(target_num, head, idx-1)
    else:
        if tail == idx:
            return False
        return binary_search(target_num, idx+1, tail)


match_count = 0
for target_num in T:
    if binary_search(target_num, 0, len(S)-1):
        match_count += 1

print(str(match_count))


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

int main() {
  int N;
  cin >> N;
  
  vector<int> tako(N);
    for(int i = 0; i < N; i++){
      cin >> tako.at(i);
    }
  
  int sum = 0;
  
  for(int i = 0; i < N; i++){
    sum += tako.at(i);
  }
  
  int count = 0;
  
  for(int i = 0; i < N; i++){
    count += (sum - tako.at(i)) * tako.at(i);
  }
  
  cout << count / 2 << endl;
  
}
 

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<climits>
using namespace std;
typedef long long ll;
#define ip(arr, n) for(int i=0; i<n; i++) cin>>arr[i];
#define op(arr, n) for(int i=0; i<n; i++) cout<<arr[i]<<" ";
#define fstIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MAX 100005
#define Inf 1000000000005

ll n,k;
ll arr[MAX], dp[MAX]={0};

void bottomUp(){
    dp[0]=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(arr[i]-arr[i+j]));
        }
    }
    cout<<dp[n-1]<<endl;
}

ll solve(ll pos){
    if(pos >= n-1) return 0;

    if(dp[pos]!=-1){return dp[pos];}

	ll ans=INT_MAX;

	for(int j=1; j<=k&& pos+j<n; j++){
		ans = min(ans, abs(arr[pos]-arr[pos+j]) + solve(pos+j));
	}

	dp[pos]=ans;
	return dp[pos];
}

void topDown(){
    memset(dp, -1, sizeof(dp));
    cout<<solve(0)<<endl;
}

int main(){
    cin>>n>>k;
    ip(arr, n);
    // for(int i=0; i<n+5; i++) dp[i]=Inf;
    // bottomUp();
    topDown();
    return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int main()
{
	int n=read(),a=read(),b=read();
	cout<<min(b,n*a)<<endl;
	return 0;
}


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

int main()
{
	int ans=1;
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		ans=fmin(2*ans,k+ans);
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

int main(){
    int n, x;
    int sum, max, min, min_sum;
    int i, j, k;
    vector<int> v;
    
    cin >> n;
    
    max = 0;
    for (i=0; i<n; i++) {
        cin >> x;
        if (i==0){
            min = x;
        }
        
        if (x>max) {
            max = x;
        }else if(x<min){
            min = x;
        }
        v.push_back(x);
    }
    
    if (min>0) {
        min = 0;
    }
    for (j=min; j<=max; j++) {
        sum = 0;
        for (k=0; k<n; k++) {
            sum += ( (v[k]-j)*(v[k]-j) );
        }
        if (j==min) {
            min_sum = sum;
        }else if (min_sum>sum){
            min_sum = sum;
        }
    }
    cout << min_sum << endl;
    
}

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

using namespace std;
const int N=1e6+55;
int dp[105][N];
int w[105];
int v[105];
int n,W;

int bt(int i , int j)
{
	if(i==-1)
	{
		if(j==0)
			return 0;
		return (int)1e9+55;
	}
	int &ret=dp[i][j];
	if(dp[i][j]!=-1)
		return ret;
	ret=bt(i-1,j);
	if(j-v[i]>=0)
		ret=min(bt(i-1,j-v[i])+w[i],ret);
	return ret;
}

main()
{
	memset(dp,-1,sizeof dp);
	cin>>n>>W;
	int sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
		sum+=v[i];
	}
	
	int ans=0;
	for(int i=0;i<=sum;i++)
	{
		if(bt(n-1,i)<=W)
		ans=i;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 820608
N = int(input())
A = {}

for i in range(N):
    num = int(input())
    tmp = [list(map(int, input().split())) for _ in range(num)]
    A[i] = tmp

ans = 0
# bit: pattern of hornest 1 and unkind 0
for bit in range(2**N):
    tmp = bit
    flag = True
    # check
    for i in range(N):
        if not (bit >> i & 1):  # case of unkind => continue
            continue
        # case of honest
        for x, y in A[i]:
            if (bit >> (x - 1) & 1) != y:   # check if really honest
                flag = False
                break
    if flag:
        ans = max(ans, bin(bit).count("1"))
print(ans)

Measured memory_bytes: 74148