akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <random>
#include <cstdio>
#include <cstring>
#include <cmath>

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

ll N;
vector<ll> A;

void input() {
    cin >> N;
    A.resize(N);
    for (auto& v : A)
        cin >> v;
//    N = 5;
//    A = {3, 11, 14, 5, 13};
}

ll solve() {
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    unordered_map<ll, int> fmap;
    for (ll i = 0; i < N; i++) {
        fmap[A[i]]++;
    }
    
    ll ans = 0;
    for (auto a : A) {
        if (fmap[a] <= 0)
            continue;
        ll to = 1;
        while (to <= a)
            to <<= 1;
        auto pair = to - a;
        if (fmap.find(pair) != fmap.end() &&
            fmap[pair] >= (pair == a ? 2 : 1)) {
            ans++;
            fmap[a]--;
            fmap[pair]--;
        }
    }
    
    return ans;
}


int main() {
    input();
    cout << solve() << endl;;
    
    return 0;
}



Measured memory_bytes: 13556
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float('inf')
def search(x):
    if len(x)==n:
        if x.count(1)>=k:
            global ans
            m = a[0]
            c = 0
            for i in range(1,n):
                if x[i]==1:
                    c += max(0,m-a[i]+1)
                    m = max(m+1,a[i])
                m = max(m,a[i])
            ans = min(ans,c)
    else:
        search(x+[1])
        search(x+[0])
search([])
print(ans)

Measured memory_bytes: 47960
# include <iostream>
# include <string>
using namespace std;
int main()
{
	int m,k;
	string s;
	cin>>s;
	m=0;
	for(int i=0; i<s.size(); i++)
	{
		if(s[i]=='R')
		{
			k=k+1;	
		}
		else
		{
			m=max(m,k);
			k=0;
		}
	}
	m=max(m,k);
	cout<<m;
}

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

using namespace std;

#define LL long long
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int n;
LL val[1000002],weight[1000002],dp[100002][1025];

int main()
{
    FAST();
    int i,j,k,l,q,x;
    LL w,ans,cur,check;
    cin >> n;
    l=min(1023,n);
    for(i=1;i<=n;i++)cin >> val[i] >> weight[i];
    for(i=1;i<=1e5;i++)
    {
        for(j=1;j<=l;j++)
        {
            if(weight[j] <= i)dp[i][j]=max(dp[i][j/2],val[j]+dp[i-weight[j]][j/2]);
            else dp[i][j]=dp[i][j/2];
        }
    }
    cin >> q;
    while(q--)
    {
        cin >> x >> w;
        if(x <= l)cout << dp[w][x] << '\n';
        else
        {
            vector<int>v;
            while(x > l)v.emplace_back(x),x/=2;
            ans=dp[w][x],k=1 << (int)v.size();
            for(i=1;i<k;i++)
            {
                cur=check=0;
                for(j=0;j<v.size();j++)
                {
                    if((i >> j) & 1)cur+=val[v[j]],check+=weight[v[j]];
                }
                if(check <= w)
                {
                    cur+=dp[w-check][x];
                    ans=max(ans,cur);
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}


Measured memory_bytes: 808552
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int64_t N, A, B;
  cin >> N >> A >> B;
  if(N == 1){
    if(A == B){
      cout << 1 << endl;
    }
    else{
      cout << 0 << endl;
    }
  }
  else if(A > B){
    cout << 0 << endl;
  }
  else{
    cout << (B-A)*(N-2)+1 << endl;
  }
}

Measured memory_bytes: 256
import sys
N,M = map(int, input().split())
mod = 1000000007
if N == 1:
    print(1)
    sys.exit()
a = set()
b = -1
for _ in range(M):
    c = int(input())
    a.add(c)
    if abs(b-c) == 1:
        print(0)
        sys.exit()
    b = c
dp = [0]*(N+2)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, N+2):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i-1]%mod + dp[i-2]%mod
print(dp[N]%mod)

Measured memory_bytes: 9004
#!/usr/bin/env python3
#A

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s,w = LI()
if w >= s:
    print('unsafe')
else:
    print('safe')

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

int main() {
  string S;
  cin >> S;
  rep(i, 5) printf("%c", S[i]);
  printf(" ");
  rep(i, 7) printf("%c", S[i+6]);
  printf(" ");
  rep(i, 5) printf("%c", S[i+14]);
  printf("\n");
}


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    map<string,int> ma;
    for(int i=0;i<n;++i)
    {
        string str;
        cin>>str;
        ma[str]++;
    }
    cout<<ma.size()<<"\n";

}


Measured memory_bytes: 19244
n = int(input())
ls = [[int(x) for x in input().split()] for _ in range(n)]

ls = sorted(ls,key=lambda x:x[1])

now=0

for i in range(n):
    now+=ls[i][0]
    if now<=ls[i][1]:
        pass
    else:
        print("No")
        exit()

print("Yes")

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

int d[555333];

int main() {

    int n,h;
    scanf("%d%d", &h, &n);

    for(int i=0; i<=20000; i++) d[i] = -1;

    d[0] = 0;
    for(int i=0; i<n; i++) {
        int a,b;
        scanf("%d%d", &a, &b);
        if (a > h) a=h;
        for(int j=a; j<=20000; j++) {
            if (d[j-a] != -1) {
                if (d[j] == -1 || d[j-a] + b < d[j]) {
                    d[j] = d[j-a] + b;
                }
            }
        }
    }

    int r=d[h];
    for(int i=h+1; i<=20000; i++) if (d[i] != -1) {
        if (r == -1) r = d[i];
        r=min(r,d[i]);
    }

    printf("%d\n", r);

    return 0;
}

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


int main(){
    int64_t a,b,c,k;
    cin >> a >> b >> c >>k;

    int total;
    if(a>=k){
        total = k;
    }
    else if(b>=k-a){
        total = a;
    }
    else {
        total = a - (k-a-b);
    }

    cout << total <<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

const double PI = 3.1415926535897932384;

int main()
{
    double r;
    cin >> r;

    cout.precision(15);
    cout << fixed << 2 * r * PI << endl;

    return 0;
}

Measured memory_bytes: 3784
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

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

    ll ans = 0;
    ll cnt_a = 0;
    bool flg_a = false;
    bool flg_ab = false;
    for (size_t i = 0; i < s.length(); i++)
    {
        if (s[i] == 'A')
        {
            if (flg_a)
            {
                flg_a = true;
                flg_ab = false;
                cnt_a++;
            }
            else
            {
                flg_a = true;
                flg_ab = false;
                cnt_a = 1;
            }
        }
        else if (s[i] == 'B')
        {
            if (flg_a)
            {
                flg_a = false;
                flg_ab = true;
            }
            else
            {
                flg_a = false;
                flg_ab = false;
                cnt_a = 0;
            }
        }
        else if (s[i] == 'C')
        {
            if (flg_ab)
            {
                ans += cnt_a;
                flg_a = true;
                flg_ab = false;
            }
            else
            {
                flg_a = false;
                flg_ab = false;
                cnt_a = 0;
            }
        }
    }

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

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
const int N = 263000;
int n;
int super;
int cards[20][3];
int dp[25][N];
ll compute(int prev, int mask)
{
    if(mask == super) return 0;
    if(dp[prev][mask] != -1) return dp[prev][mask];
    int over = 0;
    int i;
    FOR0(i, n)
        if(mask&(1<<i)) over++;
    int side = labs(prev - over + 1)%2;
    int ans = inf;
    int cur = 0;
    FOR0(i, n)
    {
        if(!(mask&(1<<i)))
        {
            int cside = labs(i - over)%2;
            if(cards[i][cside] >= cards[prev][side])
                ans = MIN2(ans, cur+compute(i, mask^(1<<i)));
            cur++;
        }
    }
    return dp[prev][mask] = ans;
}
int main()
{
    she_told_me_dont_worry
    cin>>n;
    super = (1<<n) - 1;
    int i, j;
    FOR0(i, n+5)
    {
        FOR0(j, super+5)
        {
            dp[i][j] = -1;
        }
    }
    FOR0(i, n)
        cin>>cards[i][0]; 
    FOR0(i, n)
        cin>>cards[i][1];
    int ans = inf;
    FOR0(i, n)
        ans = MIN2(ans, i+compute(i, 1<<i));
    if(ans == inf)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 24832
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

const int maxn = 100;
int a[maxn];
int b[maxn];

int main() {
    #ifdef LOCAL
    assert(freopen("d.in", "r", stdin));
    #else
    #endif
    ll A, B;
    cin >> A >> B;
    if (A == B) {
        cout << 1 << '\n';
        return 0;
    }
    ll res = B - A + 1;
    int n = 70;
    forn (i, n) {
        a[i] = A & 1;
        A >>= 1;
        b[i] = B & 1;
        B >>= 1;
    }
    while (a[n - 1] == b[n - 1])
        --n;
    assert(n > 0);
    --n;

    //forn (i, n)
        //cerr << a[i];
    //cerr << '\n';
    //forn (i, n)
        //cerr << b[i];
    //cerr << '\n';

    ll x = 0;
    for (int i = n - 1; i >= 0; --i)
        x *= 2, x += a[i];

    int m = 0;
    while (n > 0 && b[n - 1] == 0) {
        ++m;
        --n;
    }

    ll y = 0;
    for (int i = n - 1; i >= 0; --i)
        y *= 2, y += b[i];

    //cerr << x << ' ' << y << ' ' << '\n';
    res += (1ll << n) - y - 1;
    //cerr << "k1 " << (1ll << n) - y - 1 << '\n';
    res += (1ll << (n + m)) - x;
    //cerr << "k2 " << (1ll << (n + m)) - x << '\n';
    if (x < (1ll << n)) {
        res -= (1ll << n) - x;
        //cerr << "k3 " << (1ll << n) - x << '\n';
    }

    cout << res << '\n';
    //cerr << 68833183630578410 << '\n';
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int allMeters = sc.nextInt();
		int numberOfHouse = sc.nextInt();

		int[] housePlase = new int[numberOfHouse];
		List<Integer> moveMeters = new ArrayList<>();
		int allMoveMeters = 0;

		for(int i = 0; i < numberOfHouse; i++) {
			 housePlase[i] = sc.nextInt();
		}
		for(int i = numberOfHouse - 1; i > 0; i--) {
			moveMeters.add(housePlase[i] - housePlase[i - 1]);
		}
		moveMeters.add(allMeters - housePlase[numberOfHouse - 1] + housePlase[0]);
		Collections.sort(moveMeters, Collections.reverseOrder());
		int count = 0;
		for(int li : moveMeters) {
			count++;
			if(count != 1) allMoveMeters = allMoveMeters + li;
		}
		System.out.println(allMoveMeters);
	}
}

Measured memory_bytes: 60624
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    left = [[0] * W for _ in range(H)]
    right = [[0] * W for _ in range(H)]
    up = [[0] * W for _ in range(H)]
    down = [[0] * W for _ in range(H)]

    for h in range(H):
        cnt = 0
        for w in range(W):
            if maze[h][w] == "#":
                cnt = 0
            else:
                cnt += 1
                left[h][w] = cnt

    for h in range(H):
        cnt = 0
        for w in range(W - 1, -1, -1):
            if maze[h][w] == "#":
                cnt = 0
            else:
                cnt += 1
                right[h][w] = cnt

    for w in range(W):
        cnt = 0
        for h in range(H):
            if maze[h][w] == "#":
                cnt = 0
            else:
                cnt += 1
                up[h][w] = cnt

    for w in range(W):
        cnt = 0
        for h in range(H - 1, -1, -1):
            if maze[h][w] == "#":
                cnt = 0
            else:
                cnt += 1
                down[h][w] = cnt

    ans = 0
    for h in range(H):
        for w in range(W):
            tmp = up[h][w] + down[h][w] + left[h][w] + right[h][w] - 3
            if tmp > ans:
                ans = tmp

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 177928
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

//ユークリッドの互除法
ll gcd(ll x,ll y){
    if(x > y) swap(x,y);
    if(x == 0) return y;
    return gcd(x,y%x);
};

int main(){
    int n,x;
    cin >> n >> x;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] = abs(a[i]-x);
    }
    int ans = a[0];
    for(int i = 0; i < n; i++){
        ans = gcd(ans,a[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3780
n = input()
k = (int(n) - 1) // 2
def check(x):
    count = 0
    for i in range(1,x+1):
        if x % i == 0:
            count += 1
    return count
ncount = 0
for i in range(1,k+1):
    if check(2*i+1) == 8:
        ncount += 1
print(ncount)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;

using namespace std;

#define ll  long long

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef unordered_map<int,int> um;
typedef unordered_set<int> us;
typedef priority_queue<int> pq;
typedef deque<int> dq;
typedef queue<int> q;
typedef stack<int> st;

#define f first
#define s second
#define pb push_back
#define mp make_pair

#define rep(i,a,b) for (auto i = a; i < b; i++)
//#define bitset<n> b<n>

/* typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set; */

//indexed_set s;
	//s.insert(2);
	//s.insert(3);
	//s.insert(7);
	//s.insert(9);

	//auto x = s.find_by_order(2);
	//s.order_of_key(7)
	
	//c_p_c();

	//__builtin_clz(x): the number of zeros at the beginning of the number
   // __builtin_ctz(x): the number of zeros at the end of the number
   // __builtin_popcount(x): the number of ones in the number
   // __builtin_parity(x): the parity (even or odd) of the number of ones

void c_p_c()
{
	
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int main(){

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll n;
	cin>>n;
	int cost[n][3];
	
	rep(i,0,n){
		rep(j,0,3){
			cin>>cost[i][j];
		}
	}

	rep(i,0,n-1){

			cost[i+1][0] += max(cost[i][1],cost[i][2]);
			cost[i+1][1] += max(cost[i][0],cost[i][2]);
			cost[i+1][2] += max(cost[i][0],cost[i][1]);
	}

	cout<<max({cost[n-1][0],cost[n-1][1],cost[n-1][2]});

	return 0;
	}


Measured memory_bytes: 1408
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
signed main(){
  ll a,b,c,v=0;
  cin >> a >> b >> c;
  for(int i=0;i<=1000000;i++){
    v+=a;
    v%=b;
    if(v==c){
      cout <<"YES\n";
      return 0;
    }
  }
  cout <<"NO\n";
}


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

#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define mod 1000000007
#define ll long long
#define pb push_back
#define mp make_pair
#define gcd __gcd
#define F first
#define S second
#define PI 3.14159265358979323

using namespace std;



int main()
{
    ll n,w,wt[100010],value[100010],ans=0,mv=0;
    vector<ll>min_wt_for_val(100010,9999999999999);
    min_wt_for_val[0]=0;

    cin>>n>>w;
    for(ll i=1;i<=n;i++){
        cin>>wt[i]>>value[i];
        mv+=value[i];
    }

    for(ll item=1;item<=n;item++){
        for(ll val=100002;val>=value[item];val--){
            min_wt_for_val[val]=min(min_wt_for_val[val],min_wt_for_val[val-value[item]]+wt[item]);
        }
    }
    for(ll i=0;i<=mv;i++) if(min_wt_for_val[i]<=w) ans=max(ans,i);
    cout<<ans<<"\n";

return 0;
}

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

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            Solve();
        }

        public static void Solve()
        {
            var N = int.Parse(Console.ReadLine());
            foreach (var i in Enumerable.Range(1, N))
            {
                var x = Console.ReadLine();
                var y = Console.ReadLine();
                Console.WriteLine(Lcs(x, y));
            }
        }

        static int Lcs(string x, string y)
        {
            var n = x.Length;
            var m = y.Length;
            var dp = new int[n + 1, m + 1];
            foreach (var i in Enumerable.Range(0, n + 1))
            {
                foreach (var j in Enumerable.Range(0, m + 1))
                {
                    if (i == 0 || j == 0)
                    {
                        dp[i, j] = 0;
                    }
                    else if (x[i - 1] == y[j - 1])
                    {
                        dp[i, j] = dp[i - 1, j - 1] + 1;
                    }
                    else
                    {
                        dp[i, j] = Math.Max(dp[i, j - 1], dp[i - 1, j]);
                    }
                }
            }
            return dp[n, m];
        }

    }
}



Measured memory_bytes: 35292
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAX_N=10000+5;
const int INF=0x3f3f3f3f;
struct edge
{
    int to,d,c;
};
vector<edge>G[MAX_N];
typedef pair<int,int> P;
int N,M;
int dis[MAX_N];
int cost[MAX_N];
int ans;
void dijsktra()
{
    priority_queue<P,vector<P>,greater<P> >q;
    dis[1]=0;
    cost[1]=0;
    q.push(P(0,1));
    while(!q.empty())
    {
        P p=q.top();
        q.pop();
        int d=p.first;
        int v=p.second;
        if(d>dis[v])
            continue;
        for(int i=0;i<G[v].size();i++)
        {
            edge es=G[v][i];
            if(dis[es.to]==dis[v]+es.d)
            {
                if(cost[es.to]>es.c)
                    cost[es.to]=es.c;
            }
            if(dis[es.to]>dis[v]+es.d)
            {
                dis[es.to]=dis[v]+es.d;
                cost[es.to]=es.c;
                q.push(P(dis[es.to],es.to));
            }
        }
    }
}
int main()
{
    int u,v,d,c;
    edge e;
    while(scanf("%d%d",&N,&M)==2)
    {
        if(N==0&&M==0)
            break;
        for(int i=1;i<=N;i++)
            G[i].clear();
        while(M--)
        {
            scanf("%d%d%d%d",&u,&v,&d,&c);
            e.to=v;
            e.d=d;
            e.c=c;
            G[u].push_back(e);
            e.to=u;
            G[v].push_back(e);
        }
        memset(dis,0x3f,sizeof(dis));
        memset(cost,0x3f,sizeof(cost));
        dijsktra();
        ans=0;
        for(int i=1;i<=N;i++)
        {
           // printf("%d\n",cost[i]);
            ans+=cost[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
5 5
1 2 2 2
2 3 1 2
1 4 1 1
4 5 1 1
5 3 1 3
*/



Measured memory_bytes: 4796
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ld long double
#define ff first
#define ss second
const ll mod =   1e9 +7  ;
ll multiply(ll a, ll b ){ return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) {     return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////
void solve(){
   int n , m ;
   cin >> n >>m ;
   vector < int > a(n) , dp(n);
   for( int i = 0 ; i < n ; i++) cin >> a[i] ;
   for( int i = 0 ; i < m ; i++){
        int u , v ;
        cin >> u >> v ;
        u--,v--;
        dp[u] = max(dp[u],a[v]);
        dp[v] = max(dp[v],a[u]);
   }
   int cnt = 0 ;
   for( int i = 0 ; i < n ; i++){
        if(a[i]>dp[i])
            cnt++;
   }
   cout << cnt ;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1 ;
    //cin >> t ;
    while(t--){
        solve( );
    }
}


Measured memory_bytes: 3968
#include <stdio.h>
int main(){
   
  int x,y,i,a;
   
  for(i = 0 ; 1 ; i++){
    scanf("%d%d",&x,&y);
    if(x == 0 && y == 0) break;
     
    if(x > y){
      a = x;
      x = y;
      y = a;
    }
    printf("%d %d\n",x,y);
  }
return 0;
}

Measured memory_bytes: 600
import sys
import numpy as np

readline = sys.stdin.readline

n, x, m = map(int, input().split())
l = np.full(m+1,-1)
l[0] = x
s = set()
s.add(x)
lsum = [-1 for i in range(m+1)]
lsum[0] = x
for i in range(1,m+1):
    a = pow(int(l[i-1]),2,m)
    if a in s:
        if n <= i:
            print(lsum[n-1])
            sys.exit()
        j = np.where(l==a)[0][0]
        if j == 0:
            ans = lsum[i-1]
            n -= i
            ans += (lsum[i-1]) * (n//(i-j))
            if n % (i-j) == 0:
                print(ans)
                sys.exit()
            else:
                d = n % (i-j)
                ans += lsum[d-1]
                print(ans)
                sys.exit()
        else:
            ans = lsum[i-1]
            n -= i
            ans += (lsum[i-1] - lsum[j-1]) * (n//(i-j))
            if n % (i-j) == 0:
                print(ans)
                sys.exit()
            else:
                d = n % (i-j)
                ans += lsum[j+d-1] - lsum[j-1]
                print(ans)
                sys.exit()
    else:
        s.add(a)
        l[i] = a
        lsum[i] = lsum[i-1] + a


Measured memory_bytes: 34144
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		double a=scan.nextInt();
		double b=scan.nextInt();
		double C=scan.nextInt();
		C=Math.PI*C/180.0;
		double S=a*b*Math.sin(C)/2.0;
		double L=a+b+Math.sqrt(a*a+b*b-2*a*b*Math.cos(C));
		double h=b*Math.sin(C);
		System.out.printf("%.8f\n",S);
		System.out.printf("%.8f\n",L);
		System.out.printf("%.8f\n",h);
		scan.close();
	}
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> b(n);
	rep(i,n) cin >> b[i];
	vector<int> ans(n);
	for(int i = n-1; i >= 0; --i){
		int id = -1;
		for(int j = b.size()-1; j >= 0; --j){
			if(b[j] == j+1){
				id = j;
				break;
			}
		}
		if(id == -1){
			cout << -1 << endl;
			return 0;
		}
		ans[i] = b[id];
		b.erase(b.begin()+id);
	}
	rep(i,n) cout << ans[i] << endl;
	return 0;
}

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

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int N,Y;
    cin >> N >> Y;
    
    vector<int> ans(3,-1);
    
    for (int a=0; a<=N; a++) {
        for (int b=0; b + a <=N; b++) {
            int c = N - a - b;
            if (10000*a + 5000*b + 1000*c == Y ) {
                ans[0] = a;
                ans[1] = b;
                ans[2] = c;
            } 
        }
    }
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}

Measured memory_bytes: 3200
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		char[] cs = in.next().toCharArray();
		int[] count = new int[3];
		for (int i = 0; i < cs.length; i++) {
			count[cs[i] - 'a']++;
		}
		if (Math.abs(count[0] - count[1]) <= 1 && Math.abs(count[0] - count[2]) <= 1
				&& Math.abs(count[1] - count[2]) <= 1) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
		in.close();
	}
}

Measured memory_bytes: 25428
#include<bits/stdc++.h>                   // below comment for pbds
#include<ext/pb_ds/assoc_container.hpp>   // to use it make ordered_set
#include<ext/pb_ds/tree_policy.hpp>       // all set fnct + = 1. order_of_key(x); // number of 
#define ll long long                      //element strictly smaller than it;
#define ld long double                    // 2. find_by_order(x),pointer el at x pos after sort  use as s.f();
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;                     
using namespace __gnu_pbds;
// assert(a[i]<n ) // if we want to check for special cond , used for debug
// make less_equal in order to make a multiset pbds
const ll Mod = 98765431;

int fast_power(int a,int b,int mod){
	int ans=1;
	while(b>0){
	if(b&1){
	ans=(a*ans)%mod;
	}
	b=b>>1;
	a=(a*a)%mod;
	}
	return ans;
	}


int nCr(int n ,int r)
{
int p= n;
r = min(r,n-r);
int a =1;
int b=1;	
while(r)
{
	a = a*p;
	b = b*r;
	
	int g = __gcd(a,b);
	
	a = a/g;
	b = b/g;
	
	p--;
	r--;	
}	
return a;
	
}

void solve()
{
string s;
cin>>s;
ll n = s.length();
//ll dp[n+2];
//dp[0]=0;
string ans ;


for(ll i=0;i<n;i++)
{
// i+1;
if(s[i]!='?')
{
ans += s[i];	
}
else
{
	ans+='D';
}
	
}

cout<<ans<<endl;
return ;
}

signed main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--)
	{
	solve();	
	}
	
}



Measured memory_bytes: 3836
#![allow(unused_imports)]
#![allow(unused_macros)]
use itertools::Itertools;
use std::cmp::{max, min};
use std::collections::*;
use std::i64;
use std::io::{stdin, Read};
use std::usize;

trait ChMinMax {
    fn chmin(&mut self, other: Self);
    fn chmax(&mut self, other: Self);
}
impl<T> ChMinMax for T
where
    T: PartialOrd,
{
    fn chmin(&mut self, other: Self) {
        if *self > other {
            *self = other
        }
    }
    fn chmax(&mut self, other: Self) {
        if *self < other {
            *self = other
        }
    }
}

pub fn gcd(a: usize, b: usize) -> usize {
    match b {
        0 => a,
        _ => gcd(b, a % b),
    }
}

pub fn lcm(a: usize, b: usize) -> usize {
    a * b / gcd(a, b)
}

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, $var:ident $($r:tt)*) => {
        let $var = parse_val!($it, usize);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, n: usize, m: usize, a: [usize; n]);
    let a: Vec<_> = a.into_iter().map(|ai| ai / 2).collect();
    let mut x = 1usize;
    for &ai in &a {
        x = lcm(x, ai);
        if x > m {
            println!("{}", 0);
            return;
        }
    }
    for &ai in &a {
        if (x / ai) & 1 == 0 {
            println!("{}", 0);
            return;
        }
    }
    let y = m / x;
    let ret = y / 2 + y % 2;
    println!("{}", ret);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int k, n, a[300000];

int dd = 0;
void d() {
	incID(i, dd, n) {
		if(a[i] == 0) { dd = i + 1; continue; }
		a[i]--;
		if(a[i] == 0) { break; }
		dd = 0;
		inc(j, i) { a[j] = k; }
		break;
	}
}

int main() {
	cin >> k >> n;
	
	if(k % 2 == 0) {
		inc(i, n) {
			cout << (i == 0 ? "" : " ") << (i == 0 ? k / 2 : k);
		}
		cout << endl;
		
		return 0;
	}
	
	a[0] = (k + 1) / 2;
	int p = 1;
	incID(i, 1, n) {
		a[i] = (k + 1) / 2;
		if(p) { d(); }
		
		p ^= 1;
	}
	
	dec(i, n) {
		if(a[i] == 0) { break; }
		cout << a[i] << (i == 0 ? "" : " ");
	}
	cout << endl;
	
	return 0;
}


Measured memory_bytes: 3456
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from itertools import combinations # (string,3) 3回
#from collections import deque
#import collections.defaultdict(list)
#import bisect
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    from fractions import gcd
    n = int(input())
    ans = 1
    for i in range(n):
        t = int(input())
        ans = ans * t // gcd(ans,t)
    print(ans)
if __name__ == '__main__':
  main()


Measured memory_bytes: 5052
#include <stdio.h>

int main(void)
{
	int H, W;
	int i,j;
    scanf("%d %d",&H,&W);
    (((H>=1)&&(H<=300))&&((W>=1)&&(W>=300)));
    while(!((H==0)&&(W==0)))
	{
		for (i = 1; i <= H; i++)
		{
			for ( j = 1; j <=W ; j++)
			{
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
		scanf("%d %d",&H,&W);
	}	
	return 0;
}

Measured memory_bytes: 572
#define CPP17
#include <limits>
#include <initializer_list>
#include <utility>
#include <bitset>
#include <tuple>
#include <type_traits>
#include <functional>
#include <string>
#include <array>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <algorithm>
#include <complex>
#include <random>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <regex>
#include <cassert>
#include <cstddef>
#ifdef CPP17
#include <variant>
#endif

#define endl codeforces

#define ALL(v) std::begin(v), std::end(v)
#define ALLR(v) std::rbegin(v), std::rend(v)

using ll = std::int64_t;
using ull = std::uint64_t;
using pii = std::pair<int, int>;
using tii = std::tuple<int, int, int>;
using pll = std::pair<ll, ll>;
using tll = std::tuple<ll, ll, ll>;
using size_type = ssize_t;
template <typename T> using vec = std::vector<T>;
template <typename T> using vvec = vec<vec<T>>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }

template <typename T, std::size_t Head, std::size_t... Tail> 
struct multi_dim_array { using type = std::array<typename multi_dim_array<T, Tail...>::type, Head>; };

template <typename T, std::size_t Head> 
struct multi_dim_array<T, Head> { using type = std::array<T, Head>; };

template <typename T, std::size_t... Args> using mdarray = typename multi_dim_array<T, Args...>::type;

#ifdef CPP17
template <typename T, typename F, typename... Args> 
void fill_seq(T &t, F f, Args... args) { 
    if constexpr (std::is_invocable<F, Args...>::value) { 
        t = f(args...); 
    } else { 
        for (size_type i = 0; i < t.size(); i++) fill_seq(t[i], f, args..., i); 
    } 
}
#endif

template <typename T> vec<T> make_v(size_type sz) { return vec<T>(sz); }

template <typename T, typename... Tail> 
auto make_v(size_type hs, Tail&&... ts) { 
    auto v = std::move(make_v<T>(std::forward<Tail>(ts)...)); 
    return vec<decltype(v)>(hs, v); 
}

namespace init__ { 
struct InitIO { 
    InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } 
} init_io; 
}
#define CPP17


int main() {
    ll n;
    std::cin >> n;
    vec<std::string> vs = { "AC", "WA", "TLE", "RE" };
    vec<ll> cnts(vs.size());
    for (ll i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        for (ll j = 0; j < 4; j++) if (vs[j] == s) cnts[j]++;
    }

    for (ll i = 0; i < 4; i++) std::cout << vs[i] << " x " << cnts[i] << "\n";
    return 0;
}


Measured memory_bytes: 3612
#include <stdio.h>

int main( void ) {
	int i, j, data[ 10 ], top3[ 3 ];

	scanf( "%d %d %d %d %d %d %d %d %d %d", &data[ 0 ], &data[ 1 ], &data[ 2 ], &data[ 3 ], &data[ 4 ], &data[ 5 ],
		&data[ 6 ], &data[ 7 ], &data[ 8 ], &data[ 9 ] );

	for ( i = 0; i < 3; i++ ) {
		int max = data[ 0 ], idx = 0;

		for ( j = 1; j < 10 - i; j++ )
			if ( max < data[ j ] )
				max = data[ idx = j ];
		top3[ i ] = max;

		for ( j = idx; j < 9 - i; j++ )
			data[ j ] = data[ j + 1 ];
	}

	printf( "%d\n%d\n%d\n", top3[ 0 ], top3[ 1 ], top3[ 2 ] );

	return 0;
}

Measured memory_bytes: 600
package main

import (
    "fmt"
)

func main() {
    var bs []byte
    fmt.Scan(&bs)

    const R = 'R'
    const L = 'L'

    rs := make([]int, len(bs))
    bs = append(bs, 'R')

    var mode byte
    var rcnt, lcnt int
    var rpos, lpos int
    for i := range bs {
        if bs[i] == R {
            if mode == R {
                // R => R
                rcnt++
            } else {
                // L => R
                if i != 0 {
                    rs[rpos] = rcnt/2 + rcnt%2 + lcnt/2
                    rs[lpos] = lcnt/2 + lcnt%2 + rcnt/2
                }
                mode = R
                rcnt = 1
            }
        } else {
            if mode == L {
                // L => L
                lcnt++
            } else {
                // R => L
                lpos = i
                rpos = i - 1
                mode = L
                lcnt = 1
            }
        }
    }

    for i := range rs {
        if i == len(rs)-1 {
            fmt.Println(rs[i])
        } else {
            fmt.Printf("%d ", rs[i])
        }
    }
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int arr[(int)10e5+1]={0};

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int h,w;cin>>h>>w;
    for (int i=0;i<w+2;i++){
        cout<<"#";
    }cout<<endl;
    string s;
    for (int i=0;i<h;i++){
        cin>>s;
        cout<<"#";
        cout<<s;
        cout<<"#";
        cout<<endl;
    }for (int i=0;i<w+2;i++){
        cout<<"#";
    }cout<<endl;
    return 0;
}


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

#define y1 as214
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define fr front()
#define pb push_back

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , n) for(int i = 0 ; i < n ; ++i)
#define FORD(i , x , n) for(int i = x ; i >= n ; --i)

#define ll long long
#define oo 1e17
#define int long long

const int N = 2e5 + 5;
int n , C;
int a[N] , dp[N];

struct line
{
    int a , b;
    void operator -= (line const &o)
    {
        a -= o.a;
        b -= o.b;
    }
};

deque < line > dq;

int CCW(line l1 , line l2 , line l3)
{
    l3 -= l2;
    l2 -= l1;
    return l2.a * l3.b - l3.a * l2.b;
}

void add(line x)
{
    while(dq.size() >= 2 && CCW(dq[dq.size() - 2] , dq[dq.size() - 1] , x) >= 0)
        dq.pop_back();
    dq.pb(x);
}

int value(line l , int x)
{
    return l.a * x + l.b;
}

int query(int x)
{
    int l = 0 , r = dq.size() - 1;
    int res = oo;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        res = min(res , value(dq[mid] , x));
        if(mid != 0 && value(dq[mid - 1] , x) < value(dq[mid] , x)) r = mid - 1;
        else if(mid != dq.size() - 1 && value(dq[mid + 1] , x) < value(dq[mid] , x)) l = mid + 1;
        else break;
    }
    return res;
}

main()
{
    //freopen("Z.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> C;
    FOR(i , 1 , n)
        cin >> a[i];
    line x;
    x.a = -2 * a[1];
    x.b = a[1] * a[1] + dp[1] + C;
    add(x);
    FOR(i , 2 , n)
    {
        dp[i] = query(a[i]) + a[i] * a[i];
        x.a = -2 * a[i];
        x.b = a[i] * a[i] + dp[i] + C;
        add(x);
    }
    cout << dp[n];
}


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

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    char a;
    cin >> a;
    if(isupper(a)) cout << "A\n";
    else cout << "a\n";
    return 0;
}


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

#define REP(i,num) for(ll i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){T x; cin >> x; return (x);}
template<typename T=ll,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class ConnectNodeInfo{
	vector<vector<pair<ll,ll>>> graph;
public:
	ConnectNodeInfo(int node_num){
		graph.resize(node_num);
	}
	void AddNonDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
		graph[v].emplace_back(u,w);
	}
	void AddDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
	}
	vector<pair<ll,ll>>& operator[](ll index){
		return graph[index];
	}
	size_t size(){return graph.size();}
};

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

	int N=in();
	ConnectNodeInfo connect(N);
	vector<int> V(N),D(N,-1);
	REP(i,N){
		V[i]=in()-1;
		int k=in();
		REP(j,k){
			int u=in()-1;
			connect.AddDirectionalConnection(V[i],u,1);
		}
	}
	queue<int> Q;
	Q.push(0);
	D[0]=0;
	while(!Q.empty()){
		auto X=Q.front();
		Q.pop();
		for(auto& x:connect[X]){
			if(D[x.first]==-1){
				D[x.first] = D[X]+1;
				Q.push(x.first);
			}
		}
	}
	REP(i,N) out(V[i]+1,D[i]);
	return 0;
}



Measured memory_bytes: 3220
N=int(input())
#another way:
def count_digits(n):
    d=0
    while(n>0):
        d += 1
        n = n//10
    return d
c=0
for i in range(1,N+1):
    if (count_digits(i)%2==1):
        c += 1
print(c)


Measured memory_bytes: 3060
package main

import "fmt"

func main() {
	var h, w int
	fmt.Scan(&h, &w)
	ss := make([]string, h)
	for i := 0; i < h; i++ {
		fmt.Scan(&ss[i])
	}

	gs := [400][400]int{}
	bs := make(map[int]int)
	ws := make(map[int]int)

	var dfs func(i, j, g int)
	dfs = func(i, j, g int) {
		if gs[i][j] > 0 {
			return
		}
		gs[i][j] = g

		if ss[i][j] == '#' {
			bs[g]++
		} else {
			ws[g]++
		}

		dx := []int{0, 0, -1, 1}
		dy := []int{-1, 1, 0, 0}
		for d := 0; d < len(dx); d++ {
			ny := i + dy[d]
			nx := j + dx[d]
			if 0 <= nx && nx < w && 0 <= ny && ny < h {
				if ss[i][j] != ss[ny][nx] {
					dfs(ny, nx, g)
				}
			}
		}
	}

	g := 0
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			if ss[i][j] == '#' && gs[i][j] == 0 {
				g++
				dfs(i, j, g)
			}
		}
	}

	ans := 0
	for g := range bs {
		ans += bs[g] * ws[g]
	}
	fmt.Println(ans)
}


Measured memory_bytes: 108032
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = sorted(LIST())

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

Measured memory_bytes: 21720
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include <iomanip>

using namespace std;
long long gcd(long long, long long);
long long lcm(long long, long long);
int main(){
    long long A, B, C, D;
    cin >> A >> B >> C >> D;
    long long divideC, divideD, divideCD;
    // cout << gcd(C, D) << endl;
    // cout << lcm(C, D) << endl;

    divideC = (B / C) - ((A + C - 1) / C) + 1;
    divideD = (B / D) - ((A + D - 1) / D) + 1;
    divideCD = (B / lcm(C, D)) - ((A + lcm(C, D) - 1) / lcm(C, D)) + 1;
    // cout << divideC << " " << divideD << " " << divideCD << endl;
    cout << (B - A + 1) - (divideC + divideD - divideCD);
}

long long gcd(long long a, long long b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}
long long lcm(long long a, long long b){
    return a * b / gcd(a, b);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>


int main(){
  int N, A, B; cin >> N >> A >> B;
  int retval = 0;

  for (int i=1;i<=N;i++){
    int x = i, sum_digit = 0;
    while (x>0){
      sum_digit += x%10;
      x /= 10;
    }
    if (A<=sum_digit && sum_digit<=B) retval += i;
  }

  cout << retval << endl;

  // cout << fixed << setprecision(6);
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int main(void){
	int x,y,temp,cnt;
	while(1){
		cin>>x>>y;
		if(x+y==0)break;
		if(x<y){
			temp=x;
			x=y;
			y=temp;
		}
		cnt=0;
		while(1){
			x=x%y;
			temp=x;
			x=y;
			y=temp;
			cnt++;
			if(y==0) break;
		}
		cout<<x<<' '<<cnt<<endl;
	}
	return 0;
}

Measured memory_bytes: 3048