akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = input()
B = input()
C = input()
ans = 0
for i in range(N):
    a = A[i]
    b = B[i]
    c = C[i]

    if a == b == c:
        continue
    elif a == b:
        ans += 1

    elif a == c:
        ans += 1
    elif c == b:
        ans += 1
    else:
        ans += 2

print(ans)



Measured memory_bytes: 3064
import math
import string


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//math.factorial(n-r)*math.factorial(r)


s = int(input())
# print(s)
# print(s//100)
#print(s % 100)
a = s//100
b = s % 100
if 1 <= a <= 12 and 1 <= b <= 12:
    print("AMBIGUOUS")
elif 1 <= a <= 12:
    print("MMYY")
elif 1 <= b <= 12:
    print("YYMM")
else:
    print("NA")


Measured memory_bytes: 3768
#include<bits/stdc++.h>
using namespace std;
int n,A[1000010],ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
	int sum=0;
	for(int i=1;i<=n;i++){
		if(A[i]<=A[i-1])sum++;
		else {
			ans=max(ans,sum);
			sum=0;
		}
	}
	ans=max(ans,sum);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 640
n = int(input())
s = input()
t = input()

if s == t:
    print(len(s))
    exit(0)

ind = 0
mx = min(len(s), len(t))
mx_len = 0
while ind < mx:
    pre_i = s[-(ind + 1):]
    suf_i = t[:(ind + 1)]
    if pre_i == suf_i:
        mx_len = ind + 1

    ind += 1

ans = len(s) + len(t) - mx_len
print(ans)


Measured memory_bytes: 3064
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a1 = [0]*(n+1)

for i in range(n):
    a1[i+1] = a1[i]+a[i]

ans = 0
c = Counter(a1)
for i in c.values():
    ans += i*(i-1)//2
print(ans)


Measured memory_bytes: 44456
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
long long int m,n,a,b;
vector<int> av;
int x=0,y=0;
int main()
{
	cin>>a>>b;
	n=__gcd(a,b);
m=1; 
	for(int x=2;x<=1e6+5;x++)
	{
	if(n%x==0)
	{
		while(n%x==0)
		{
			n/=x;
		}m++;
	}	
	}
	if(n!=1)
	{m++;
	}
		cout<<m<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int n,m;
    cin >> n >> m;
    string s;
    cin >> s;
    int now = n;
    stack<int> ans;
    bool fl = false;
    while(now>0){
        if(now<=m){
            ans.push(now);
            break;
        }
        for(int i = m;i>=1;i--){
            if(s[now-i]=='0'){
                fl = true;
                ans.push(i);
                now-=i;
                break;
            }
        }
        if(!fl){
            cout << -1 << endl;
            return 0;
        }
        fl = false;
        //cout << now << endl;
    }
    while(!ans.empty()){
        cout << ans.top() << " ";
        ans.pop();
    }
    cout << endl;
}

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

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

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

/*==================================================*/
/*variable*/
int N, X;
int m[110];
/*==================================================*/
/*function*/

/*==================================================*/

int main() {

    cin>>N>>X;
    REP(i,0,N){
        cin>>m[i];
        X -= m[i] ;
    }

    int ans = N;
    sort(m,m+N);

    if(X < 0){
        cout<<0<<endl;
    }else{
        cout<<ans + (X/m[0])<<endl;
    }


    return 0;
}


Measured memory_bytes: 256
def solve(N, Ss):
    a = 0
    b = 0
    both = 0
    ans = 0
    for s in Ss:
        ans += s.count("AB")
        if s[-1] == "A" and s[0] == "B":
            both += 1
        else:
            if s[-1] == "A":
                a += 1
            if s[0] == "B":
                b += 1

    if both > 0:
        ans += both - 1

    if both > 0 and a > 0:
        ans += 1
        a -= 1

    if both > 0 and b > 0:
        ans += 1
        b -= 1

    a = min(N, a)
    b = min(N, b)
    ans += min(a, b)
    return ans

if __name__ == "__main__":
    N = int(input())
    Ss = [input() for _ in range(N)]
    print(solve(N, Ss))


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

int main() {
  int n, k, m = 0, c = 0;
  vector<int> vec(101);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> vec.at(i);
  }

  for (int i = 0; i < n; i++) {
    int a = vec.at(i) - 0;
    int b = k - vec.at(i);

    if (a < 0) {
      a *= -1;
    }
    if (b < 0) {
      b *= -1;
    }

    c = min(a, b);
    m += 2 * c;
  }
  cout << m << endl;
}

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

using namespace std;

constexpr long MOD = 1e9+7;
constexpr long MAX = 1e6;

long mod_pow(long x, long p) {
  long t = 1;
  long u = x;
  while (p) {
    if (p & 1)
      t = t * u % MOD;
    u = u * u % MOD;
    p >>= 1;
  }
  return t;
}

long mod_div(long x) {
  return mod_pow(x, MOD-2);
}

vector<long> prime_list;
unordered_map<long, long> prime_map;
void init() {
  vector<bool> mem(MAX+1, true);
  mem[0] = false;
  mem[1] = false;
  for (long i = 2; i < MAX+1; i++) {
    if (not mem[i])
      continue;
    for (long t = i*2; t < MAX+1; t += i) {
      mem[t] = false;
    }
  }
  for (long i = 0; i <= MAX; i++) {
    if (mem[i])
      prime_list.push_back(i);
  }
  for (int i = 0; i < prime_list.size(); i++) {
    prime_map[prime_list[i]] = i;
  }
}

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

  int N; cin>>N;
  init();
  vector<long> A(N); for (auto& a : A) cin>>a;
  auto lcm = vector<long>(prime_list.size());
  for (int i = 0; i < N; i++) {
    auto a = A[i];
    for (long t = 0; prime_list[t] <= sqrt(A[i]); t++) {
      long cnt = 0;
      auto p = prime_list[t];
      while (a % p == 0) {
        cnt++;
        a /= p;
      }
      lcm[t] = max(lcm[t], cnt);
    }
    if (a != 1) {
      auto id = prime_map[a];
      lcm[id] = max(lcm[id], 1l);
    }
  }
  auto mod_lcm = 1;
  for (int i = 0; i < prime_list.size(); i++) {
    mod_lcm = mod_lcm * mod_pow(prime_list[i], lcm[i]) % MOD;
  }
  long ans = 0;
  for (int i = 0; i < N; i++) {
    ans += mod_lcm * mod_div(A[i]) % MOD;
    ans %= MOD;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 5108
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Quiz006
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();

            int ans1 = 0;
            for (var i = 0; i < s.Length; i++)
            {
                if(i % 2 == 0 && s[i] == '0')
                {
                    ans1++;
                }
                else if(i % 2 == 1 && s[i] == '1')
                {
                    ans1++;
                }
            }

            int ans2 = 0;
            for (var i = 0; i < s.Length; i++)
            {
                if (i % 2 == 0 && s[i] == '1')
                {
                    ans2++;
                }
                else if (i % 2 == 1 && s[i] == '0')
                {
                    ans2++;
                }
            }

            if(ans1 <= ans2)
            {
                Console.WriteLine(ans1);
            }
            else
            {
                Console.WriteLine(ans2);
            }

        }
    }
}


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

int main()
{
    int A, B, num=0;
    string str, rstr;
    istringstream ss;
    cin >> A >> B;
    for (int i = A; i <= B;i++){
        str = to_string(i);
        rstr = str;
        for (int j = 0; j < str.size();j++){
            rstr.at(j) = str.at(str.size() - j-1);
        }
        if (str == rstr)
        {
            num++;
            //cout << str << " " << rstr << endl;
        }
    }
    cout << num << endl;

    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

#define rep(countName, left, right, up) for (ll countName = left; countName < right; countName += up)
#define REP(countName, end) for (ll countName = 0; countName < end; countName++)
#define rev(countName, right, left, down) for (ll countName = right - 1; countName >= left; countName -= down)
#define REV(countName, end) for (ll countName = end - 1; countName >= 0; countName--)

int main(void)
{
    std::vector<int> v(3);
    bool even = true;
    int ans = 0;

    REP(i, 3)
    {
        cin >> v[i];
        if (v[i] % 2 == 1)
        {
            even = false;
        }
    }

    std::sort(v.begin(), v.end());

    if (even)
    {
        ans += (v[2] - v[0]) / 2;
        ans += (v[2] - v[1]) / 2;
    }
    else
    {
        while (!(v[0] == v[1] && v[1] == v[2] && v[0] == v[2]))
        {
            if (v[1] == v[2])
            {
                v[0] += 2;
            }
            else
            {
                v[0]++, v[1]++;
            }
            ans++;
            //cout << v[0] << " " << v[1] << " " << v[2] << endl;
            if (v[1] > v[2] || v[0] > v[2])
            {
                std::sort(v.begin(), v.end());
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <complex>
#define rep(i,n) for(int i=0;i<n;i++)
#define re real()
#define im imag()
using namespace std;
typedef complex<double> P;
int main(){
	while(true){
		int n,mx=1;
		scanf("%d",&n);
		if(n==0) break;
		complex<double> p[300];
		rep(i,n){
			double x,y;
			scanf("%lf%lf",&x,&y);
			p[i]=P(x,y);
		}
		rep(i,n) rep(j,i){
			double d=abs(p[i]-p[j]);
			if(d>2) continue;
			P c=(p[i]+p[j])/2.0,dis=(p[i]-p[j])/d*sqrt(1-d*d/4);
			dis=P(dis.im,-dis.re);
			P cen=c+dis;
			int cnt=0;
			rep(k,n) if(abs(cen-p[k])<=1.0000000001) cnt++;
			mx=max(mx,cnt);
			cen=c-dis;
			cnt=0;
			rep(k,n) if(abs(cen-p[k])<=1.0000000001) cnt++;
			mx=max(mx,cnt);
		}
		printf("%d\n",mx);
	}
	return 0;
}

Measured memory_bytes: 1064
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

// 素数の列挙

vector<int> Eratosthenes( const int N )
{
    vector<bool> is_prime( N + 1 );
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;
    }
    vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

int main(){
    int N;
    cin>>N;
    vector<int> prime=Eratosthenes(55555);
    int cnt=0;
    REP(i,prime.size()){
        if(prime[i]%10==1){
            cout<<prime[i];
            if(cnt==N-1){
                cout<<endl;
                return 0;
            }else{
                cout<<" ";
            }
            cnt++;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FILL(a, value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
 
typedef long long LL;
typedef pair<int, int> PII;

const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = (LL)INF * INF;
const int MAX = 1 << 17;

int r[MAX], c[MAX];
vector<int> idxes[MAX];
vector<LL> vec[MAX];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	FOR(i, 0, m)
	{
		int l;
		cin >> l >> r[i] >> c[i];
		l--;
		idxes[l].push_back(i);
	}
	multiset<LL> s;
	FOR(i, 0, n)
	{
		for(LL x: vec[i])
			s.erase(s.find(x));
		if(i && s.empty())
		{
			cout << "-1\n";
			return 0;
		}
		LL d = i == 0 ? 0 : *s.begin();
		if(i == n - 1)
		{
			cout << d << "\n";
			return 0;
		}
		for(int id: idxes[i])
		{
			s.insert(d + c[id]);
			vec[r[id]].push_back(d + c[id]);
		}
	}
	assert(false);
	return 0;
}

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

int main(){
    int N, K;
    string S;
    cin >> N >> K >> S;
    int diff = 0;
    for(int i=0; i<N-1; i++) if(S[i] != S[i+1]) diff++;
    diff = max(diff-2*K, 0);
    cout << N-1-diff << endl;
    return 0;
}


Measured memory_bytes: 512
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int prevX = 0;
		int prevY = 0;
		int prevT = 0;
		for(int i=0; i<N; i++){
			int t = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			int dx = Math.abs(x-prevX);
			int dy = Math.abs(y-prevY);
			int dt = t-prevT;
			if(dx+dy>dt || (dt-dx-dy)%2==1){
				System.out.println("No");
				return;
			}
			prevX = x;
			prevY = y;
			prevT = t;
		}
		System.out.println("Yes");
		return;
	}
}

Measured memory_bytes: 86064
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
using ll = long long;
using namespace std;
int main(){
    ll n;
    cin >> n;
    vector<ll> vec;
    vec.push_back(0);
    for(int i=0;i<n;i++){
        ll x;cin >> x;
        vec.push_back(x);
    }
    vec.push_back(0);
    vector<ll> vec1;
   // vec1.push_back(0);
   ll sum=0;
    for(int i=0;i<=n;i++){
        vec1.push_back(abs(vec[i+1]-vec[i]));
        sum += abs(vec[i+1]-vec[i]);
    }
    //cout<<sum<<endl;
    //cout<<vec.size()<<endl;
    for(int i=0;i<n;i++){
        cout<<sum-vec1[i]-vec1[i+1]+abs(vec[i+2]-vec[i])<<endl;
    }
}

Measured memory_bytes: 2932
#include <iostream>
#include<vector>
#include<list>
#include<algorithm>

using namespace std;

vector<int> G[100000];
int V[100000];
list<int> ut;
int N;

void dfs(int u){
    V[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v =G[u][i];
        if(!V[v])dfs(v);
    }
    ut.push_front(u);
}

int main(){
    int s,t,M;
    cin>>N>>M;
    for(int i=0;i<N;i++){
        V[i]=0;
    }
    for(int i=0;i<M;i++){
        cin>>s>>t;
        G[s].push_back(t);
    }
    for(int i=0;i<N;i++){
        if(!V[i])dfs(i);
    }
    for(list<int>::iterator it =ut.begin();it !=ut.end();it++){
        cout<<*it<<endl;
    }
    return 0;
}


Measured memory_bytes: 6248
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

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

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

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

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

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

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

// x ** n % mods を求める
pub fn mod_pow(x: i64, n: i64, mods: i64) -> i64 {
    if n == 0 {
        return 1;
    }
    let mut res = mod_pow(x * x % mods, n / 2, mods);
    if n % 2 == 1 {
        res = res * x % mods;
    }
    return res;
}

// (1/n) % mods を求める
pub fn mod_inv(n: i64, mods: i64) -> i64 {
    return mod_pow(n, mods-2, mods);
}

// nCk % mods を求める
pub fn mod_comb(n: i64, k: i64, mods: i64) -> i64 {
    let sum1 = (n-k+1..n+1).fold(1, |ac, x| ac * x % mods);
    let sum2 = (1..k+1).fold(1, |ac, x| ac * x % mods);
    return sum1 * mod_inv(sum2, mods) % mods;
}

// nCk の組み合わせを列挙する
pub fn combination(n: usize, k: usize) -> Vec<Vec<usize>> {
    let mut ans = Vec::new();
    if k == 1 {
        for i in 1..n+1 {
            let mut tmp = Vec::new();
            tmp.push(i);
            ans.push(tmp);
        }
    }
    else {
        for iter in combination(n-1, k-1) {
            let max = iter.iter().max().unwrap();
            for j in *max+1..n+1 {
                let mut tmp = iter.clone();
                tmp.push(j);
                ans.push(tmp);
            }
        }
    }
    ans
}


fn main() {
    input!{
        s: chars,
    }
    if s[1] == 'B' {
        println!("ARC");
    }
    else {
        println!("ABC");
    }
}


Measured memory_bytes: 2088
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000100;
#define cle(n) memset(n,0,sizeof(n))

int n;
int a[maxn];
int b[4];
int main()
{
    cin>>n;

    for(int i=0;i<n;i++)
        {
            cin>>a[i];
            b[a[i]%4]++;
        }

    b[2]%=2;
    b[0]-=b[2];

   // cout<<b[1]+b[3]<<' '<<b[2]<<' '<<b[0]<<endl;

    if((b[1]+b[3]+b[0])%2)
    {
        int t=b[1]+b[3]-1;
        if(b[0]>=t)
       cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    else
    {
        b[0]=b[0]-b[1]-b[3];
        if(b[0]>=0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().rstrip().split()]
X = [int(x) for x in input().rstrip().split()]
X.sort()
X_1 = np.array(X[:M-1], np.int64)
X_2 = np.array(X[1:], np.int64)
X_ = X_2 - X_1
X_ = np.sort(X_)[::-1]
print(X_[N-1:].sum())

Measured memory_bytes: 22320
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[4];
        for(int i = 0; i < N; i++) {
            String tmp = sc.next();
            if(tmp.equals("AC")) {
                arr[0]++;
            } else if(tmp.equals("WA")){
                arr[1]++;
            } else if(tmp.equals("TLE")) {
                arr[2]++;
            } else if(tmp.equals("RE")) {
                arr[3]++;
            }
        }
            System.out.println("AC x " + arr[0]);
            System.out.println("WA x " + arr[1]);
            System.out.println("TLE x " + arr[2]);
            System.out.println("RE x " + arr[3]);
    }
}


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

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

#define rep(i, N) for (ll i = 0; i < (N); i++)
#define For(i, a, b) for (ll i = (a); i < (b); i++)
#define all(A) (A).begin(), (A).end()

int main(){
    ll X, Y;
    cin >> X >> Y;
    ll ans = 1;
    ll tmp = X;
    while (tmp * 2 <= Y) {
        ans++;
        tmp *= 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

/*ソートの時に使う
int sort(const void *a, const void *b){
    return *(int*)a-*(int*)b ;
}
    qsort (data,sizeof(data),sizeof(int),sort); 
*/

int main(void){
    int n,m;
    scanf("%d%d",&n,&m);
    int a[m],b[m];
    bool to[n],from[n];
    for (int i=0; i<n; i++){
        to[i]=false;
        from[i]=false;
    }
    for (int i=0; i<m; i++){
        scanf("%d%d",&a[i],&b[i]);
        if (a[i]==1){
            to[b[i]]=true;
        } else if (b[i]==n){
            from[a[i]]=true;
        }
    }
    for (int i=0; i<n; i++){
        if (to[i]==true && from[i]==true){
            printf("POSSIBLE\n");
            exit(0);        
        } 
    }
    printf("IMPOSSIBLE\n");
	return 0 ;
}

Measured memory_bytes: 2176
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstring>
#include <stdio.h>

using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EPS 1e-8

struct point{
	double x,y,z,r;
	point(double _x, double _y, double _z, double _r):x(_x),y(_y),z(_z),r(_r){};
	point():x(0.0),y(0.0),z(0.0),r(0.0){};
};

inline point add(point &p1, point &p2){
	return point(p1.x+p2.x, p1.y+p2.y, p1.z+p2.z, 0.0);
}
inline point sub(point &p1, point &p2){
	return point(p1.x-p2.x, p1.y-p2.y, p1.z-p2.z, 0.0);
}
inline double dot(point &p1, point &p2){
	return p1.x*p2.x+p1.y*p2.y+p1.z*p2.z;
}
inline point mult(point &p, double k){
	return point(p.x*k,p.y*k,p.z*k,0.0);
}
inline double dist(point &p1, point &p2){
	return sqrt(pow(p1.x-p2.x, 2.0)+pow(p1.y-p2.y, 2.0)+pow(p1.z-p2.z, 2.0));
}

point lp[2222];
point ls[22];
int iss[2222];
double lum[22];

bool intersect(point &a, point &b, point &c){//線分abに点cを中心とする風船がかかわるかどうか
	//1(両方内側にある)
	if(dist(a,c)<c.r-EPS&&dist(b,c)<c.r-EPS)return false;
	//2(片方が内側、片方が外側にある)
	if((dist(a,c)-c.r)*(dist(b,c)-c.r)<-EPS)return true;
	//3(両方が外側にある)
	point ab=sub(a,b);
	point ac=sub(a,c);
	double t=dot(ab,ac)/dot(ab,ab);
	if(EPS<t && t<1.0-EPS){
		point R=mult(ab, -t);
		point Q=add(a,R);
		if(dist(Q,c)<c.r-EPS)return true;
		else return false;
	}else return false;
}

int main(){
	while(1){
		double ans=0.0;
		int n,m,r;
		int tx,ty,tz,tr;
		point e;
		cin>>n>>m>>r;
		if(n==0)return 0;
		memset(iss,0,sizeof(iss));
		REP(i,n){
			scanf("%d%d%d%d",&tx,&ty,&tz,&tr);
			lp[i]=point(tx,ty,tz,tr);
		}
		REP(i,m){
			scanf("%d%d%d%d",&tx,&ty,&tz,&tr);
			ls[i]=point(tx,ty,tz,tr);
		}
		REP(i,1){
			scanf("%d%d%d",&tx,&ty,&tz);
			e=point(tx,ty,tz,0.0);
		}
		REP(i,m)lum[i]=ls[i].r/pow(dist(ls[i],e),2.0);
		REP(i,n)REP(j,m)if(intersect(ls[j], e, lp[i]))iss[i]|=1<<j;
		REP(i,1<<m){
			int cost=0;
			double lu=0;
			REP(j,n)if(iss[j]&i)cost++;
			if(cost>r)continue;
			REP(j,m)if(i&(1<<j))lu+=lum[j];
			ans=max(ans,lu);
		}
		printf("%.5f\n", ans);
	}
}

Measured memory_bytes: 1344
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll val[101], wt[101], dp[110][(int)1e5+10];
     
ll solve(int ith, int cwt, int n) {
    if(ith == n) return 0;
    
    if(dp[ith][cwt] != 0) return dp[ith][cwt];
    
    ll sml = 0;
    
    if(cwt - wt[ith] >= 0) sml = solve(ith + 1, cwt - wt[ith], n) + val[ith];
    
    ll sml1 = solve(ith + 1, cwt, n);
    
    return dp[ith][cwt] = max(sml, sml1);
}
int main() {
    int n, w; cin >> n >> w;
    for(int i=0; i<n; ++i) {
        cin >> wt[i] >> val[i];
    }
    cout << solve(0, w, n);
    return 0;
}

Measured memory_bytes: 78080
#include<stdio.h>

int main(){
  long n,left,right,mid;
  scanf("%ld",&n);
  left=1;
  right=n;
  mid=(left+right)/2;
  while(left<right){
    mid=(left+right)/2;
    if(n-mid>mid*(mid-1)/2)
      left=mid+1;
    else if(n-mid<mid*(mid-1)/2)
      right=mid;
    else
      left=right=mid;
  }
  for(long i=1;i<=left;i++)
    if(i!=(left*(left+1)/2)-n)
      printf("%ld\n",i);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	range(i,1,10)range(j,1,10)if(n==i*j){
		puta("Yes");
		return 0;
	}
	puta("No");
	return 0;
}

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

namespace C044
{
    class C106
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            long K = long.Parse(Console.ReadLine());
            char ot = '1';
            int counter = 1;
            foreach (char c in S)
            {
                if (counter > K) break;
                if (c != '1')
                {                    
                    ot = c;
                    break;
                }
                counter++;
            }
            Console.WriteLine(ot);
        }

    }
}


Measured memory_bytes: 13140
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    string s;
    cin >> s;
    ll c= 0;
    bool iLike = true;
    if(s[0]!= 'A') iLike = false;
    FOR(i,2,s.length()-1){
      if(s[i] =='C') c++;
    }
    if(c != 1) iLike = false;
    F0R(i,s.length()){
      if(s[i] != 'A' && s[i] != 'C'){
        if(s[i] < 97 || s[i] > 122) iLike = false;
      }
    }

    if(iLike) cout << "AC";
    else cout << "WA";
    cout << endl;

    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int cmp(int x,int y)
{
    return x>y;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int a[105];
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        sort(a,a+n,cmp);
        int ans=0;
        for(int i=0;i<n;i++){
            if(i%2) ans-=a[i];
            else ans+=a[i];
        }
        cout<<ans<<endl;
    }
return 0;}


Measured memory_bytes: 256
use strict;
use warnings;

chomp(my $k = <>);
my @num = split(', ', "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51");

print $num[$k-1];

Measured memory_bytes: 640
/*
			   ___ _   _ _   _ _____ 
			  |_  | | | | \ | |  _  |
			    | | | | |  \| | | | |
			    | | | | | . ` | | | |
			/\__/ / |_| | |\  \ \_/ /
			\____/ \___/\_| \_/\___/                       
		 
 		* Copyright (C) - juno
  		* 2020-08-15
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")  
#pragma GCC target("avx,avx2,fma") 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef stack<int> si;
typedef pair<int,int> pi;
typedef vector<pair<long int,int>> vpi;
 
#define li(i, a, b) for (int i=a; i<(b); i++)
#define fl(i, a) for (int i=0; i<(a); i++)
#define ln(i,a,b) for (int i = (b)-1; i >= a; i--)
#define bl(i,a) for (int i = (a)-1; i >0; i--)
#define blm(i,a) for (int i = (a)-1; i >= 0; i--)
#define el "\n"
#define sp " "
#define pb push_back
#define m0(array,n) memset(array,0,n)
#define mem(array,data,n) memset(array,data,n)

void fast(){
	ios::sync_with_stdio(0);
	cin.tie(0);
}
int main(){
	fast();
	string s;
	cin>>s;
	int max=0,c=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='R'){
			c++;
			if(i==s.size()-1){
				if(c>max)max=c;
			}
		}
		else if(s[i]=='S'){
			if(c>max)max=c;
			c=0;
		}
	}
	cout<<max;	
	return 0;
}



Measured memory_bytes: 3648
using System;
using System.Linq;
using System.Collections.Generic;


class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        string[] S = new string[N];
        for(int i=0; i<N; i++) {
            S[i] = Console.ReadLine();
        }
        List<string> Slist = new List<string>(S);

        Slist = Slist.Distinct().ToList();

        Console.WriteLine(Slist.Count());
    }
}

Measured memory_bytes: 49368
n = int(input())
AL = [int(input()) for _ in range(n)]
AL_sort = sorted(AL, reverse=True)
ansL = [0]*n
for i in range(n):
    if AL[i]==AL_sort[0]:
        ansL[i] = AL_sort[1]
    else:
        ansL[i] = AL_sort[0]
for i in range(n):
    print(ansL[i])

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

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> K(N + 1);
    for (int i = 1; i <= N; ++i) cin >> K[i];

    for (int i = 1; i <= N; ++i) {
        cout << "node " << i
             << ": key = " << K[i] << ", ";
        if (i > 1) cout << "parent key = " << K[i / 2] << ", ";
        if (i * 2 <= N) cout << "left key = " << K[i * 2] << ", ";
        if (i * 2 + 1 <= N) cout << "right key = " << K[i * 2 + 1] << ", ";
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3116
#include <iostream>
#include <vector>
using namespace std;
struct edge {int from, to, cost;};
const long long INF = 1000000000;
void bellman_ford(std::vector<edge> & es, std::vector<int> & d, int E, int V, int s) {
  for(int i=0;i<V;i++) d[i] = INF;
  d[s] = 0;
  while(true) {
    bool update = false;
    for(int i=0;i<E;i++) {
      edge e = es[i];
      if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
        d[e.to] = d[e.from] + e.cost;
        update = true;
      }
    }
    if(!update) break;
  }
}
 
int main() {
  int n;
  cin >> n;
  vector<edge> e;
  for(int i=0;i<n;i++) {
    int u, k;
    cin >> u >> k;
    for(int j=0;j<k;j++) {
      int vi, ci;
      cin >> vi >> ci;
      edge ei = {u, vi, ci};
      e.push_back(ei);
    }
  }
  vector<int> d(n);
  bellman_ford(e, d, e.size(), n, 0);
  for(int i=0;i<n;i++) {
    cout << i << " " << d[i] << endl;
  }

}

Measured memory_bytes: 3256
#include <stdio.h>

int main(void)
{
    int w = 0;
    scanf("%d", &w);
    int F=0;
    int f = 0;
    if(w>=500){
    F = w / 500;
    w = w - (500 * F);
    }
    if (w >= 5)
    {
        f = w / 5;
    }
    printf("%d\n", f * 5 + F * 1000);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a,b,p,q;
    cin>>n>>m>>a>>b;
    p=n+m;
    q=a+b;
    if(p>q)
    {
        cout<<"Left"<<endl;
    }
    else if(q>p)
    {
        cout<<"Right"<<endl;
    }
    else if(q==p)
    {
        cout<<"Balanced"<<endl;
    }



}


Measured memory_bytes: 3516
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))

template< class T >
struct CumulativeSum2D
{
    vector< vector< T > > data;
    
    CumulativeSum2D(int W, int H) : data(W + 1, vector< int >(H + 1, 0)) {}
    
    void add(int x, int y, int z)
    {
        ++x, ++y;
        if(x >= data.size() || y >= data[0].size()) return;
        data[x][y] += z;
    }
    
    void build()
    {
        for(int i = 1; i < data.size(); i++) {
            for(int j = 1; j < data[i].size(); j++) {
                data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
            }
        }
    }
    
    T query(int sx, int sy, int gx, int gy)
    {
        return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
    }
};

int main(){
    int N, M, Q;
    cin >> N >> M >> Q;
    CumulativeSum2D<int> trains(N, N);
    for(int i = 0; i < M; i++){
        int L, R;
        cin >> L >> R;
        trains.add(L - 1, R - 1, 1);
    }
    trains.build();
    for(int i = 0; i < Q; i++){
        int p, q;
        cin >> p >> q;
        cout << trains.query(p - 1, 0, N, q) << endl;
    }
}


Measured memory_bytes: 1920
import java.io.*;

class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] str1 = br.readLine().split(" ");
        int r = Integer.parseInt(str1[0]);
        int c = Integer.parseInt(str1[1]);
        int[][] data = new int[r][c];
        int[] sumR = new int[r];
        int[] sumC = new int[c];
        int sumX = 0;

        // Input r x c
        for(int i=0; i<r; i++){
            String[] str2 = br.readLine().split(" ");
            for(int k=0; k<c; k++){
                data[i][k] = Integer.parseInt(str2[k]);
            }
        }

        // calc "sumX and sumR"
        for(int i=0; i<r; i++){
            for(int k=0; k<c; k++){
                sumR[i] += data[i][k];
            }
            sumX += sumR[i];
        }
        // calc "sumC"
        for(int i=0; i<c; i++){
            for(int k=0; k<r; k++){
                sumC[i] += data[k][i];
            }
        }

        // Output
        for(int i=0; i<r; i++){
            for(int k=0; k<c; k++){
                sb.append(data[i][k]).append(" ");
            }
            sb.append(sumR[i]).append("\n");
        }
        for(int k=0; k<c; k++){
            sb.append(sumC[k]).append(" ");
        }
        sb.append(sumX).append("\n");

        System.out.print(sb);
    }
}

Measured memory_bytes: 27628
{-# LANGUAGE BangPatterns, MultiWayIf #-}

import Control.Applicative
import Control.Exception (assert)
import Control.Monad
import Data.List
import Debug.Trace (traceShow, traceShowM)

import Text.Printf (printf)

solve :: Double -> Double -> Double -> Double
solve n m d
    | d == 0    = (n / n ^ 2) * (m - 1)
    | otherwise = ((2 * (n - d)) / n ^ 2) * (m - 1)

main :: IO ()
main = do
    [n, m, d] <- fmap read . words <$> getLine
    printf "%.7f\n" $ solve n m d

Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M;
  cin>>N;
  vector<string> s(N); 

  for(int i=0;i<N;i++){
      cin>>s.at(i);
  }

   cin>>M;
  vector<string> t(M);
  int count=0;
  int max=0;
  
  
  for(int i=0;i<M;i++){
      cin>>t.at(i);
  }

  for(int i=0;i<N;i++){
    count=0;
      for(int j=0;j<N;j++){
          if(s.at(i)==s.at(j)){
              count++;
          }
      }
        for(int k=0;k<M;k++){
          if(s.at(i)==t.at(k)){
              count--;
          }
      }
      if(max<count){
          max=count;
      }
  }
  
  cout<<max<<endl;

}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define INF 11000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;

int main(){
  int n,m;
  cin>>n>>m;
  n--; m--;
  cout<<n*m<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>




#define rep(p,q) for(int i = p;i < q;i++)
#define ll long long

using namespace std;

const int cons = 1e9 + 7;

//77C

int main(void) {
	vector<int> a = vector<int>();
	vector<int> b = vector<int>();
	vector<int> c = vector<int>();

	int n;
	cin >> n;
	rep(0, n) {
		int input;
		cin >> input;
		a.push_back(input);
	}
	rep(0, n) {
		int input;
		cin >> input;
		b.push_back(input);
	}
	rep(0, n) {
		int input;
		cin >> input;
		c.push_back(input);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	int ai, bi, ci;
	ai = bi = ci = 0;
	ll ans = 0;
	//bを固定してcでvalidなｍの
	vector<ll> bcValid = vector<ll>(n);
	//bを固定してaでvalidなもの
	vector <ll > abValid = vector<ll>(n);
	int lastCIndex = 0;
	int lastAIndex = 0;
	rep(0, n) {
		int nowB = b[i];
		
		while (lastCIndex < n && nowB >= c[lastCIndex])lastCIndex++;
	    bcValid[i] = n - lastCIndex;
		while (lastAIndex < n && nowB > a[lastAIndex])lastAIndex++;
		if (lastAIndex > n)abValid[i] = 0;
		else abValid[i] = lastAIndex;
	}
	
	rep(0, n) {
		ans += bcValid[i] * abValid[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
int n9(int m)
{
  return (m / 59049) % 9 + (m / 6561) % 9 + (m / 729) % 9 + 
    (m / 81) % 9 + (m / 9) % 9;
}
int n6(int m)
{
  return (m / 46656) % 6 + (m / 7776) % 6 + (m / 1296) % 6 +
    (m / 216) % 6 + (m / 36) % 6 + (m / 6) % 6 + m % 6;
}
int main(void)
{
  int n, ans = 100000;
  std::cin >> n;
  for(int i = 0; i <= n; i += 9){
    ans = std::min(n9(i) + n6(n - i), ans);
  }
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i,l,r) for(int i=l;i<=r;i++)
signed main()
{  // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,w;
    cin>>n>>w;

     int wt[n+1],v[n+1];

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

    int k[n+1][w+1];


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

        for(int j=0;j<=w;j++)
        {
            if(i==0 || j==0)
                k[i][j]=0;
            else
            {   // k[i][j]=max(k[i][j-1],k[i-1][j]);
                if(wt[i]<=j)
                {
                    k[i][j]=max(k[i-1][j],k[i-1][j-wt[i]]+v[i]);
                }
                else k[i][j]=k[i-1][j];
            }
        }
    }
cout<<k[n][w]<<endl;
    return 0;
}

Measured memory_bytes: 79232
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let N: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let d: Vec<i64> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    };

    let s = d.iter().sum::<i64>();
    let ans = d.iter().map(|&x| x * (s - x)).sum::<i64>() / 2;

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


Measured memory_bytes: 4352
from itertools import accumulate

n, k = list(map(int,input().split(" ")))
s = input()


def solve():
    l=[]
    prev = '1'
    cnt = 0
    for c in s:
        if prev ==c:
            cnt += 1
        else:
            l.append(cnt)
            cnt = 1
        prev = c
    l.append(cnt)
    if prev == '0':
        l.append(0)

    w = 2 * k + 1

    if len(l) <= w:
        return n

    acc = [0] + list(accumulate(l))
    ans = 0
    for i in range(0, len(l) - w + 1, 2):
        ans = max(ans, acc[i + w] - acc[i])
    return ans


print(solve())


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

using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;
    vector<int> a(n,0);
    for(int i=0;i < n;i ++)
    {
        cin >> a[i];
    }
    int ans = 0;
    while(a.size() > k)
    {
        int min = *min_element(a.begin(),a.begin()+k);
        vector<int> m = {min};
        m.insert(m.end(),a.begin()+k,a.end());
        a = m;
        ans += 1;

    }

    cout << ans + 1 << endl;
}

Measured memory_bytes: 1028
date_set = gets.chomp.to_f
date_count = 0

loop  do
  break if date_count == date_set
  (a,b,c) = gets.chomp.split.map(&:to_f).sort
  if c.to_f ** 2 == a.to_f ** 2 + b.to_f ** 2
    puts "YES"
  else
    puts  "NO"
  end
  date_count += 1
end


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

#define REP( i, n )     for( int (i) = 0; (i) < (n); (i)++ )
#define ALL( a )        (a).begin(), (a).end()

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

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

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main(){
    int N, M, X, Y; cin >> N >> M >> X >> Y;
    vector<int> x( N ), y( M );
    REP( i, N ) cin >> x[i];
    REP( i, M ) cin >> y[i];
    sort( ALL( x ) );
    sort( ALL( y ) );

    bool ok = false;
    int Z = X + 1;
    for( int z = Z; z <= Y; z++ ){
        if( x[N - 1] < z && y[0] >= z ) ok = true;
    }

    if( ok ) cout << "No War" << endl;
    else cout << "War" << endl;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

#define int ll
int n;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n) {
        int lb = 2;
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (i == 0) {
                ans += x - 1;
            } else {
                if (x == lb) {
                    ++lb;
                } else if (x < lb + 1) {
                    continue;
                } else {
                    ans += (x - lb - 1) / lb + 1;
                }
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
n, y = map(int, input().split())

for i in range(n+1):
    for j in range(n+1-i):
        if 10000*i + 5000*j + 1000*(n-i-j) == y:
            print(i, j, n-i-j)
            exit()
print(-1, -1, -1)


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

int main(){
    int n;
    std::cin >> n;
    std::vector<int> v(n), o(100001,0), e(100001,0);
    rep(i,n){
        std::cin >> v[i];
        if(i%2) o[v[i]]++;
        else e[v[i]]++;
    }

    auto io = std::distance(o.begin(),std::max_element(o.begin(),o.end()));
    auto ie = std::distance(e.begin(),std::max_element(e.begin(),e.end()));

    std::sort(o.begin(),o.end());
    std::sort(e.begin(),e.end());
    int ans = 0;
    if(io==ie){ //最大の値が同じとき
        ans = std::min(n-o[o.size()-1]-e[e.size()-2],n-o[o.size()-2]-e[e.size()-1]);
    }else{ //最大の値が違うとき
        ans = n - o.back() - e.back();
    }
    std::cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 4540