akhauriyash/Code-Regression huggingface dataset:
//适用于稀疏图
//复杂度 mlog(n)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
const int N=1e5+7;
int father[N];
// 边的信息
struct Edge
{
    ll a, b, v;
    /*
    bool operator< (const Edge &W) const
    {
        return v < W.v;
    }
    */
};
Edge edge[N*2];
// 并查集——寻找当前集合的代表元素
int find(int x)
{
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}

// 所有边存储在 Edge edges[M];
// 函数返回最小生成树中所有边的总长度
int cmp3(Edge a,Edge b)
{
    return a.v<b.v;
}
int Kruskal()
{
    int num=0;
    long long res = 0;
    // 初始化并查集代表元素
    for (int i = 1; i <= n; i ++ ) father[i] = i;
    sort(edge+1, edge +1 + m,cmp3);
    for (int i = 1; i <= m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b;
        if (find(a) != find(b))
        {
            father[find(a)] = find(b);
            num++;
            res += edge[i].v;

        }
        if(num==n-1)
            break;
    }
    return res;
}

struct node
{
   ll x,y,id;
}nd[N];
int cmp1(node a,node b)
{
    return a.x<b.x;
}
int cmp2(node a,node b)
{
    return a.y<b.y;
}

int main()
{
    int t;
    cin >> t;
    for(int i=1;i<=t;i++)
    {
        cin >> nd[i].x >> nd[i].y;
        nd[i].id=i;
    }

    sort(nd+1,nd+1+t,cmp1);
    int tot=0;
    for(int i=1;i<t;i++)
    {
        edge[++tot].a=nd[i+1].id; edge[tot].b=nd[i].id; edge[tot].v=nd[i+1].x-nd[i].x;
    }

    sort(nd+1,nd+1+t,cmp2);
    for(int i=1;i<t;i++)
    {
        edge[++tot].a=nd[i+1].id; edge[tot].b=nd[i].id; edge[tot].v=nd[i+1].y-nd[i].y;
    }
    m=tot;
    n=t;
    //cout << "m " << m << endl;
        cout << Kruskal() << endl;
    return 0;
}


Measured memory_bytes: 7680
import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created 2017/06/04.
 */
public class Main {
  public static void main(String[] args) {

    //??\?????¨?????????
    Scanner sc = new Scanner(System.in);
    ArrayList<ArrayList<Integer>> ary_input = new ArrayList<>();
    while (true) {
      ArrayList<Integer> ary = new ArrayList<>();
      int input1 = Integer.parseInt(sc.next());
      int input2 = Integer.parseInt(sc.next());
      if (input1 == 0 && input2 == 0) break;
      ary.add(input1);
      ary.add(input2);
      ary_input.add(ary);
    }
    //System.out.println(ary_input);

    //??????????????????????´?????????????????????????
    ArrayList<ArrayList<StringBuilder>> ary_sb = new ArrayList<>();

    for (ArrayList<Integer> index : ary_input) {
      ary_sb.add(sisaku(index.get(0), index.get(1)));
    }
    //System.out.println(ary_sb);
    
    //??¨?????¢???????????????
    for (int i = 0; i < ary_sb.size(); i++) {
      for (int j = 0; j < ary_sb.get(i).size(); j++) {
        System.out.println(ary_sb.get(i).get(j));
      }
        System.out.println("");
    }
  }

  public static ArrayList<StringBuilder> sisaku(int a, int b) {
    ArrayList<StringBuilder> ary = new ArrayList<>();
    for (int i = 0; i < a; i++) {
      StringBuilder str1 = new StringBuilder("");
      for (int j = 0; j < b; j++) {
        if (i == 0 || i == (a - 1)) {
          str1 = str1.append("#");
        } else {
          if (j == 0 || j == (b - 1)) {
            str1 = str1.append("#");
          } else {
            str1 = str1.append(".");
          }
        }
      }
      ary.add(str1);
    }
    return ary;
  }
}

Measured memory_bytes: 27832
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            line.pop();
            line
        }
    )
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    )
}

fn solve(d: u32, x: u32, aa: Vec<u32>) -> u32 {
    aa.iter().map(|a| ((d-1) / a) + 1).fold(0, |sum, a| sum + a) + x
}

fn main() {
    let n = parse_line!(usize);
    let (d,x) = parse_line!(u32, u32);
    let aa = (0..n).map(|_| parse_line!(u32)).collect::<Vec<_>>();
    println!("{}", solve(d, x, aa));
}

#[test]
fn solve_test() {
    assert_eq!(solve(7,1,vec![2,5,10]), 8);
    assert_eq!(solve(8,20,vec![1,10]), 29);
    assert_eq!(solve(30,44, vec![26,18,81,18,6]), 56);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
long long n,a[3][200]={0},res=0,pref1[200]={0},pref2[200]={0};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>a[1][i];
	for (int i=1; i<=n; i++) cin>>a[2][i];
	for (int i=1; i<=n; i++){
		pref1[i] = pref1[i-1]+a[1][i];
		pref2[i] = pref2[i-1]+a[2][i];
	}
	res=0;
	for (int i=1; i<=n; i++){
		res = max(res,pref1[i]+pref2[n]-pref2[i-1]);
	}
	cout<<res<<"\n";
}

Measured memory_bytes: 256
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define ushi int
#define tapu main
#define nichia (
#define kunn void
#define wara )

using ll = long long;

const int INF = 1073741823;
const int MINF = -1073741823;
const ll LINF = ll(4661686018427387903);
const ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/

int main(){

	int n, m;
	scanf("%d%d", &n, &m);
	vector<vector<int>> ship(n);
	int a, b;
	rep(i, m) {
		scanf("%d%d", &a, &b);
		ship[a - 1].pb(b - 1);
		ship[b - 1].pb(a - 1);
	}
	bool c = false;
	for (auto aa : ship[0]) {
		for (auto aaa : ship[aa]) {
			if (aaa == n - 1)c = true;
		}
	}
	printf("%s\n", c ? "POSSIBLE" : "IMPOSSIBLE");

	Please AC;
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(std::string b){
    if(b == "A") {
        cout << "T" << endl;
    }

    if(b == "T") {
        cout << "A" << endl;
    }

    if(b == "C") {
        cout << "G" << endl;
    }

    if(b == "G") {
        cout << "C" << endl;
    }
}

int main(){
    std::string b;
    std::cin >> b;
    solve(b);
    return 0;
}



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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1; 
    for(int T = 0; T < t ; T++){
        ll n, ans = 0;
        cin >> n;
        ll div[n + 1];
        for(int i = 1; i <= n; i++){
            div[i] = 1;
        }
        for(int i = 2; i <= n; i++){
            for(int j = i; j <= n; j += i){
                div[j]++;
            }
        }
        for(int i = 1; i <= n; i++){
            ans += i*div[i];
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 81724
#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <regex>

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<ll>;
using vpii = vector<pii>;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(b);i>=(a);i--)
#define SORT(a) sort((a).begin(),(a).end());
#define rSORT(a) sort((a).rbegin(),(a).rend());
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end());
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;

//sankou
//vvi = vector<vector<int>>(20, vector<int>(10, 0));

//seiki
//#include <regex>
/*bubun*/
//regex_search("u32", regex("[0-9]"));      // true
/*kanzen*/
//regex_match("u32", regex("(i|u)\\d+"));   // true

int isP(int n) {
    if(n<=1) return 0;
    FOR(i,2,(int)sqrt(n)) {
        if(n%i==0) return 0;
    }
    return 1;
}

int main() {

    int N,H,amax=0,cnt=0;
    cin >>N>>H;
    vi a(N),b(N);
    FOR(i,0,N-1){
        cin >>a[i]>>b[i];
    }
    rSORT(a);
    rSORT(b);
    amax=a[0];
    FOR(i,0,N-1){
        if(b[i]>=amax) {
            cnt++;
            H-=b[i];
            if(H<=0) {
                cout <<cnt<<endl;
                break;
            }
        }
    }
    if(H>0) {
        cnt+=(int)(H/amax);
        if(H%amax!=0) cnt++;
        cout <<cnt<<endl;
    }

    return 0;
}





Measured memory_bytes: 1024
from collections import deque
import itertools
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#print(d)
ans = INF
for i in itertools.permutations(r,len(r)):
    val = 0
    for j in range(1,len(r)):
        val += d[i[j-1]][i[j]]
    ans = min(ans,val)
print(ans)

    


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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int n, k;
double ans;

int main() {
	read(n), read(k);
	for (int i = 1; i <= n; ++i) {
		int t = i;
		double p = 1;
		for (int j = 0; j <= 20; ++j) {
			if (t >= k) {
				ans += 1.0 / n * p;
				break;
			}
			t <<= 1;
			p /= 2.0;
		}
	}
	printf("%.12lf\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include <algorithm>
#include<cstdlib>
#include<cmath>
#include<deque>
#include <numeric>
#include<valarray>
typedef unsigned long long ull;
typedef  long long ll;

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

	ll tmplen = 0;
	ll lenmax = 0;

	for (int i = 0; i < s.size(); i++)
	{

		switch (s[i])
		{
		case 'A':
		case 'C':
		case 'G':
		case 'T':
			tmplen += 1;
			break;
		default:
			if (tmplen > lenmax) lenmax = tmplen;
			tmplen = 0;
			break;
		}

	}
	if (tmplen > lenmax) lenmax = tmplen;
	std::cout << lenmax << std::endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, M = 1e9 + 7;


signed main()
{
	IO_OP;
	
	int n, k;
	cin >> n >> k;
	int neg_cnt = 0, pos_cnt = 0;
	vi a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		if(a[i] < 0) neg_cnt++;
		else pos_cnt++;
	}
	bool yes = false;
	for(int i = 0; i <= min(neg_cnt, k); i += 2) {
		int rem = k - i;
		if(rem <= pos_cnt) {
			yes = true;
			break;
		}
	}
	if(!yes) {
		int ans = 1;
		vi v;
		for(int i = 0; i < n; i++) v.PB(abs(a[i]));
		sort(ALL(v));
		for(int i = 0; i < k; i++) ans = ans * v[i] % M;
		cout << (M - ans) % M << endl;
		return 0;
	}
	vi pos, neg;
	for(int i = 0; i < n; i++) {
		if(a[i] < 0) neg.PB(-a[i]);
		else pos.PB(a[i]);
	}
	sort(ALL(pos), greater<int>());
	sort(ALL(neg), greater<int>());
	int i, j;
	for(i = 0; i + 2 <= min((int)neg.size(), k); i += 2);
	j = k - i;
	while(true) {
		if(i - 2 < 0) break;
		if(j + 2 > pos.size()) break;
		if(pos[j] * pos[j + 1] > neg[i - 1] * neg[i - 2]) {
			j = j + 2;
			i = i - 2;
		} else {
			break;
		}
	}
	int ans = 1;
	for(int k = 0; k < i; k++) ans = ans * neg[k] % M;
	for(int k = 0; k < j; k++) ans = ans * pos[k] % M;
	cout << ans << endl;


}





Measured memory_bytes: 6840
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        FastReader fr = new FastReader();
        int N = fr.nextInt(), K = fr.nextInt();
        String S = fr.next();
        S = S.substring(0, K-1) + (char) (S.charAt(K-1) - 'A' + 'a') + S.substring(K);
        System.out.println(S);
    }
}

class FastReader {

    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException  e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

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

using vi = vector<int>;

int main()
{
    ios_base::sync_with_stdio(0);

    int n; cin >> n;

    vi v(n);

    for(auto& x : v) cin >> x;

    int odd_cnt = 1;

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

        for(int j = v[i] - 1; j <= v[i] + 1; j++)
            odd += j % 2;

        odd_cnt *= odd;
    }

    int total = llround(pow(3, n));

    int ans = total - odd_cnt;

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

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define int           long long
#define	pb            push_back
#define all(a)        (a).begin(),(a).end()
#define sz(x)         (int)x.size()
#define F             first
#define S             second
#define endl          "\n"
#define inf           1000000007
#define FOR(i, a, b)  for(int i=a; i<b; i++)
#define bigboi        1e18
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers. 


void solve(){
	int n, a, b;
	cin>>n>>a>>b;
	int k = n/(a+b);
	cout<<k*a + min(a, n%(a+b))<<endl;	
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 	
	int t=1;
	//cin>>t;
	FOR(i, 1, t+1){	
	//	cout<<"Case #"<<i<<":"<<endl;
		solve();
	}
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
 
}


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

typedef pair<int,int> P;
vector<P> g;
int ans[(1 << 18) + 5];
bool use[1 << 17 + 5];
int main() {
  int m,k;
  cin >> m >> k;
  int tmp = 1;
  for(int i = 0; i < m; i++) tmp *= 2;
  if(k >= tmp) {
    cout << -1 << endl;
    return 0;
  }

  if(m == 0) {
    cout << 0 <<' ' << 0 << endl;
    return 0;
  }
 
  if(m == 1 && k == 1) {
    cout << -1 << endl;
    return 0;
  }

  if(k == 0) {
    for(int i = 0; i < tmp; i++) {
      if(i != tmp - 1) cout << i <<' ' << i <<' ';
      else cout << i <<' '<< i <<endl;
    }
    return 0;
  }
  for(int i = 1; i < tmp; i++) {
    int t = k ^ i;
    if(use[t] || use[i]) continue;
    use[t] = use[i] = true;
    g.push_back(P(t,i));
    // cout << t <<"   "<<i << endl;
  }
  
  for(int i = 0; i < g.size(); i += 2) {
    ans[4 * i] = ans[4 * i + 3] = g[i].first;
    ans[4 * (i + 1)] = ans[4 * (i + 1) + 3] = g[i].second;
    ans[4 * i + 1] = ans[4 * (i + 1) + 2] = g[i+1].first;
    ans[4 * i + 2] = ans[4 * (i + 1) + 1] = g[i+1].second;
  }

  for(int i = 0; i < tmp * 2; i++) {
    if(i != tmp * 2 - 1) cout << ans[i] <<' ';
    else cout << ans[i] << endl;
  }
}


Measured memory_bytes: 3576
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void){
    long long int s;
    int n,k;
    
    scanf("%d %d %lld",&n,&k,&s);
    
    for(int i =0;i<n;i++){
        if(k > 0){
            printf("%lld",s);k--;
        }else if(s == 1000000000){
            printf("1");
        }else{
            printf("%lld",s + 1);
        }
        printf(" ");
    }
    printf("\n");
}


Measured memory_bytes: 1280
N=int(input())

now=0
L=[]
for i in range(N):
    a,b=map(int, input().split())
    L.append((a,b))

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

for i in range(N):
    t=L[i]
    a,b=t
    if now+a<=b:
        now+=a
    else:
        print("No")
        exit()

print("Yes")

Measured memory_bytes: 33396
#include <stdio.h>
int main(void){
  int money;
  int sen=0;
  int ichi=0;
  scanf("%d",&money);
  sen=money/500;
  money=money%500;
  ichi=money/5;
  printf("%d",sen*1000+ichi*5);
  return 0; 
 }

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
string memo[101][101][2];
string rec(int x, int y, int z){
  if(memo[x][y][z] != "U") return memo[x][y][z];
  if(x < 0 || y < 0) assert(false);
  if(x == 0 && y == 0) assert(false);
  if(x == 0){
    if(z == 0) return "Z";
    return memo[x][y][z] = string(y, '1');
  }
  if(y == 0){
    if(x % 2 == 1 && z == 0) return memo[x][y][z] = string(x, '0');
    if(x % 2 == 0 && z == 1) return memo[x][y][z] = string(x, '0');
    return memo[x][y][z] = "Z";
  }
  if(z == 0){
    string res = "0" + rec(x - 1, y, 1);
    if(res[res.size() - 1] == 'Z') return memo[x][y][z] = "Z";
    return memo[x][y][z] = res;
  }else{
    string s = "Z";
    if(rec(x - 1, y , 0) != "Z") s = min(s, "0" + rec(x - 1, y, 0));
    if(rec(x, y - 1, 0) != "Z") s = min(s, "1" + rec(x, y - 1, 0));
    if(rec(x, y - 1, 1) != "Z") s = min(s, "1" + rec(x, y - 1, 1));
    if(s[s.size() - 1] == 'Z') s = "Z";
    memo[x][y][z] = s;
    return s;
  }
}
string itos(int n){
  stringstream ss;
  ss<<n;
  return ss.str();
}

int main(){
  int N;
  REP(y, 101)REP(x, 101)REP(z, 2) memo[x][y][z] = "U";
  while(cin>>N){
    vector<int> a;
    int c0 = 0, c1 = 0;
    REP(i, N){
      int t; cin>>t;
      if(t == 0) c0++;
      else if(t == 1) c1++;
      else a.push_back(t);
    }
    sort(a.begin(), a.end());
    string s = "";
    if(c0 + c1 > 0) s = rec(c0, c1, 1);
    if(s == "Z"){
      if(a.size() > 0){
        s = string(c0 - 1, '0') + itos(a[0]) + "0";
        a.erase(a.begin());
        if(a.size() >=  2 && a[a.size() - 2] == 2 && a[a.size() - 1] == 3) swap(a[a.size() - 2], a[a.size() - 1]);
      }else{
        s = string(c0, '0');
      }
      REP(i, a.size()) cout<<a[i]<<endl;
      REP(i, s.size()) cout<<s[i]<<endl;
    }else{
      if(a.size() >= 2 && a[a.size() - 2] == 2 && a[a.size() - 1] == 3) swap(a[a.size() - 2], a[a.size() - 1]);
      REP(i, a.size()) cout<<a[i]<<endl;
      REP(i, s.size()) cout<<s[i]<<endl;
    }
  }
  return 0;
}

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

int main()
{
ll a , b ;
cin >> a >> b ;
ll te=a+b;
ans=max(te,ans);
ans=max(a-b,ans);
ans=max(a*b,ans);




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


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>

typedef long long ll;

int main(int argc, char* argv[])
{
  int n;
  std::cin >> n;

  ll cnt = 0;
  std::vector< ll > va(n, 0);
  for (ll i = 0; i < n; i++) {
    ll tmp;
    std::cin >> tmp;
    if (tmp <= n) {
      va[tmp-1]++;
    } else {
      cnt++;
    }
  }

  std::vector< ll >::iterator it;
  for (it = va.begin(); it != va.end(); it++) {
    ll no = it - va.begin() + 1;
    if (no > *it) {
      cnt += *it;
    } else {
      cnt += *it - no;
    }
  }

  std::cout << cnt << std::endl;
  return 0;
}


Measured memory_bytes: 1024
/*{{{*/
#include<bits/stdc++.h>

typedef long long 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 FORR(i,a,b) for(ll i=b-1;i>=a;i--)

#define vl vector<ll>
#define pll pair<ll,ll>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;
/*}}}*/

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


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

const int INF = 10000;
int cost[10][10];

void init()
{
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			if(i == j){
				cost[i][j] = 0;
			}else{
				cost[i][j] = INF;
			}
		}
	}
}

int main()
{
	int n;
	while(cin >> n){
		if(n==0)
			break;
		init();
		int a,b,c,m=0;
		for(int i=0;i<n;i++){
			cin >> a >> b >> c;
			cost[a][b] = c;
			cost[b][a] = c;
			if(m < max(a,b))
				m = max(a,b);
		}
		m++;
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				for(int k=0;k<m;k++){
					int cdis = cost[j][i] + cost[i][k];
					if(cdis < cost[j][k]){
						cost[j][k] = cdis;
					}
				}
			}
		}
		int mati,min_cost=100000000;
		for(int i=0;i<m;i++){
			int costs = 0;
			for(int j=0;j<m;j++){
				costs += cost[i][j];
			}
			if(min_cost > costs){
				min_cost = costs;
				mati = i;
			}
		}
		cout << mati << " " << min_cost << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef LL T;

// powmod p^n%mod
T powmod(T p,T n,T mod){
	T q=p%mod;
	T pow=1;
	while(n){
		if(n&1){
			pow*=q;
			pow%=mod;
		}
		q=q*q;
		q%=mod;
		n/=2;
	}
	return pow;
}

LL C[3001][3001];
LL N,M;
LL S[3001][3002];

LL f(LL k){
	LL s=0;
	// (b+1)*S[k][b+1]+S[k][b] は k 元集合の部分集合を b 個の集合に分ける方法の数
	for(int b=0;b<=k;b++){
		s+=((b+1)*S[k][b+1]%M+S[k][b])%M*powmod(2,(N-k)*b,M)%M;
		s%=M;
	}
	return s;
}
int main() {
	cin >> N >> M;
	for(int i=0;i<=3000;i++){
		C[i][0]=1;
		if(i==0){
			S[i][0]=1;
		}
		else{
			S[i][0]=0;
		}
		for(int j=1;j<=i;j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
			C[i][j]%=M;
			S[i][j]=S[i-1][j-1]+j*S[i-1][j]%M;
			S[i][j]%=M;
		}
	}
	LL r=0;
	for(LL i=0;i<=N;i++){
		LL a=f(i);
		LL e=powmod(2,N-i,M-1);
		LL d=powmod(2,e,M);
		LL s=a*d%M;
		s*=C[N][i];
		s%=M;
		if(i%2==0){
			r+=s;
			r%=M;
		}
		else{
			r+=M-s;
			r%=M;
		}
	}
	cout << r << endl;

	return 0;
}



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

int N, X;

int main(){

  cin >> N >> X;

  int m[N];
  int mMin = 1e9;
  int counter = N;

  for(int i = 0; i < N; ++i){
    cin >> m[i];
    X -= m[i];
    if(m[i] < mMin) mMin = m[i];
  }

  counter += X/mMin;
  cout << counter ;

  return 0; 
}

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

int main(void)
{
    long long N, K;
    cin >> N >> K;

    vector<long long> P(N+1);
    vector<long long> C(N+1);
    for (long long i = 1; i < N+1; i++)
    {
        cin >> P[i];
    }
    for (long long i = 1; i < N+1; i++)
    {
        cin >> C[i];
    }

    vector<long long> seen(N+1);
    long long preans = 0;
    long long ans = 0;
    long long now;
    long long count = 0;
    for(long long i = 1; i < N+1; i++)
    {
        now  = i;
        preans = 0;
        count = 1;
        for (long long j = 1; j < N+1; j++)
        {
            seen[j] = 0;
        }

        while(1)
        {
            preans += C[P[now]];
            seen[now] = 1;
            if (seen[P[now]] == 1)
            {
                break;
            }
            now = P[now];
            if (count == K)
            {
                break;
            }
            count++;
        }
        if (preans > 0){
        preans = ((K/count)-1) * preans;
        now = i;
        long long prepreans = preans;
        for (long long j = 0; j < count + (K % count); j++)
        {
            prepreans += C[P[now]];
            now = P[now];
            if (prepreans > preans)
            {
                preans = prepreans;
            }
        }
        if (preans > ans)
        {
            ans = preans;
        }
        if (i == 1)
        {
            ans = preans;
        }
        }
        else
        {
            now = i;
            long long preans = 0;
            long long prepreans = 0;
            for(long long  j = 0; j < count; j++)
            {
                prepreans += C[P[now]];
                now = P[now];
                if (prepreans > preans)
                {
                    preans = prepreans;
                }
                if (j == 0)
                {
                    preans = prepreans;
                }
            }
            if (preans > ans)
        {
            ans = preans;
        }
        if (i == 1)
        {
            ans = preans;
        }
        }

    }
    cout << ans << endl;
}

Measured memory_bytes: 3744
import java.util.*;
public class Main {
    static void solve(){
        Scanner sc = new Scanner(System.in);
        int start = sc.nextInt(), end = sc.nextInt();
        if(start>0&&end>0) System.out.println("Positive");
        else if (start<=0&&end>=0) System.out.println("Zero");
        else 
        System.out.println((end-start)%2==0 ? "Negative" : "Positive");
        sc.close();
    }

    public static void main(String args[]) {
        solve();
    }
}   


Measured memory_bytes: 35772
a=int(input())
b=int(input())
c=int(input())
x=int(input())
cnt=0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i + 100*j + 50*k==x:
        cnt+=1
print(cnt)

Measured memory_bytes: 40176
#include <bits/stdc++.h>
using namespace std;
int res[100000];
int main() {
  int n; cin >> n;
  for (auto i = 1; i <= n; i++) {
    int a; cin >> a;
    res[a - 1] = i;
  }
  for (auto i = 0; i < n - 1; i++) {
    cout << res[i] << " ";
  }
  cout << res[n - 1] << endl;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin>>N>>K;
  vector<double> data(N);
  for(int i=0;i<N;i++)cin>>data[i];
  for(int i=0;i<N;i++)data[i]=(double)(data[i]+1)/2;
  vector<double>sum(N+1,0);
  for(int i=0;i<N;i++){
    sum[i+1]=sum[i]+data[i];
  }
  double ans=0;
  for(int i=0;i+K<=N;i++){
    double tmp=sum[i+K]-sum[i];
    //cout<<tmp<<endl;
    ans=max(ans,tmp);
  }
  cout<<fixed<<setprecision(12)<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
using namespace std;
int main(){
    long long ans=0,ans2=0;
    string s,t,d;
    cin>>s>>t;
    f(i,0,s.size()-t.size()+1){
        d=s.substr(i,t.size());
        ans2=0;
        f(j,0,t.size()){
            if(t[j]==d[j]){
                ans2++;
            }
        }
        ans=max(ans,ans2);
    }
    cout<<t.size()-ans<<endl;
    return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
#define MAX 86400
#define MIN 0
int GetNumEqual( int *pNum );
void MakeTime( int prtS );

int main( void )
{
    int getTimeS;
    if( 0 == GetNumEqual( &getTimeS ) )
    {
        MakeTime( getTimeS );
    }
    return 0;
}

int GetNumEqual( int *pNum )
{
    int getNum;
    
    scanf( "%d" , &getNum );
    
    if( ( getNum >= MIN ) && ( getNum <= MAX ) )
    {
        *pNum = getNum;
        return 0;
    }
    
    return -1;
}

void MakeTime( int prtS )
{
    int prtH=0;
    int prtM=0;
    
    if( prtS < 60 )
    {
        printf("%d:%d:%d\n",prtH,prtM,prtS);
    }
    else
    {
        prtM = prtS/60;
        prtS = prtS%60;
        
        if( prtM < 60 )
        {
            printf("%d:%d:%d\n",prtH,prtM,prtS);
        }
        else
        {
            prtH = prtM/60;
            prtM = prtM%60;
            printf("%d:%d:%d\n",prtH,prtM,prtS);
        }
    }
}

Measured memory_bytes: 1780
S = input()
ans = 0
temp = S[0]
count = 1
seq = []
for i in range(1,len(S)):
    if S[i] == temp:
        count += 1
    else:
        seq.append([temp, count])
        count = 1
        temp = S[i]
seq.append([temp, count])
if seq[0][0] == '>':
    ans += (seq[0][1])*(seq[0][1]+1)//2
for i in range(len(seq)-1):
    if seq[i][0] == '<' and seq[i+1][0] == '>':
        a = (seq[i][1])*(seq[i][1]+1)//2
        b = (seq[i+1][1])*(seq[i+1][1]+1)//2
        ans += a+b-min(seq[i][1],seq[i+1][1])
if seq[-1][0] == '<':
    ans += (seq[-1][1])*(seq[-1][1]+1)//2
print(ans)

Measured memory_bytes: 29084
Class Main
    Public Shared Sub Main()
        Dim N As Integer = Console.ReadLine()
        Dim flg As Boolean = False
        For i As Integer = 0 To 9
            For j As Integer = 0 To 9
                If i * j = N Then
                    flg = True
                    Exit For
                End If
            Next
            If flg Then
                Exit For
            End If
        Next
        Console.WriteLine(If(flg, "Yes", "No"))
        Return
    End Sub
End Class

Measured memory_bytes: 28296
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[sc.nextInt()] = i;
        }
        int cnt = 0;
        int max = 0;
        for (int i = 2; i <= n; i++) {
            if (a[i] > a[i - 1]) {
                cnt++;
            } else {
                max = Math.max(cnt, max);
                cnt = 0;
            }
        }
        max = Math.max(cnt, max);
        System.out.println(n - max - 1);
        //1300
    }
}

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

int findDigits(int num)
{
    int digit = 0;
    while(num > 0)
    {
        num /= 10;
        digit++;
    }
    return digit;
}


int main()
{
    long long N;
    cin >> N;

    int num_test = sqrt(N);
    int ans = N;
    for (int i = 1; i < num_test + 1; i++)
    {
        if (N % i == 0)
        {
            ans = findDigits(N / i);
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 998244353;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N,M;
    cin >> N >> M;
    int ans = 0;
    vector<int>A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<P>vec(M);
    for(int i = 0; i < M; i++) {
        int B,C;
        cin >> B >> C;
        vec[i].first = C;
        vec[i].second = B;
    }
    sort(A.begin(),A.end());
    sort(vec.begin(),vec.end());
    int cnt = M-1;
    for(int i = 0; i < N; i++) {
        if(vec[cnt].first <=A[i]) {
            continue;
        }
        A[i] = vec[cnt].first;
        vec[cnt].second--;
        if(vec[cnt].second == 0) {
            cnt--;
        }
    }
    for(int i = 0; i < N; i++) {
        ans+=A[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 5624
#include<stdio.h>

void y(int x ){
	if(x == 0)
		puts("Thursday");
	else if(x == 1)
		puts("Friday");
	else if(x == 2)
		puts("Saturday");
	else if(x == 3)
		puts("Sunday");
	else if(x == 4)
		puts("Monday");
	else if(x == 5)
		puts("Tuesday");
	else if(x == 6)
		puts("Wednesday");
}

int main(void){
	int M,D;
	while(1){
		int date = 0,ans;
		int m[12] = {31,29,31,30,31,30,31,31,30,31,30,31};
		
		scanf("%d%d", &M, &D);
		if(M == 0 && D  == 0)break;
		for(int i = 1; i <= 12 ; i++){
			for(int j = 1; j <= m[i-1]; j++){
				if(i == M && j == D){
					ans = date;
				}
	//			printf("%d%dú%d\n",i,j,date%7);
	//			y(date%7);
				date++;
			}
		}
		y(ans%7);
	}
	
	return 0;
}

Measured memory_bytes: 0
#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;

typedef long long ll;
typedef pair<int, int> P;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll N, K; cin >> N >> K;
	ll X, Y; cin >> X >> Y;
	
	ll res = X*(ll)min(N,K) + Y*(ll)max(N-K, 0LL);
	cout << res << endl;
		
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] line = scanner.nextLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int w = Integer.parseInt(line[1]);
        int[] weights = new int[n];
        int[] values = new int[n];

        for (int i = 0; i < n; i++) {
            line = scanner.nextLine().split(" ");
            weights[i] = Integer.parseInt(line[0]);
            values[i] = Integer.parseInt(line[1]);
        }

        Long[][] dp = new Long[n][w + 1];
        System.out.println(knapsack(weights, values, 0, w, dp));
    }

    private static long knapsack(int[] weights, int[] values, int currentIndex, int remainingWeight, Long[][] dp) {
        if(remainingWeight <= 0) {
            return 0;
        }

        if (currentIndex >= weights.length) {
            return 0;
        }

        if (dp[currentIndex][remainingWeight] != null) {
            return dp[currentIndex][remainingWeight];
        }

        long choice1 = 0;
        if (weights[currentIndex] <= remainingWeight) {
            choice1 = values[currentIndex] + knapsack(weights, values, currentIndex + 1, remainingWeight - weights[currentIndex], dp);
        }

        long choice2 = knapsack(weights, values, currentIndex + 1, remainingWeight, dp);

        dp[currentIndex][remainingWeight] = Math.max(choice1, choice2);
        return dp[currentIndex][remainingWeight];
    }
}


Measured memory_bytes: 277612
n = int(input())
mod = 10 ** 9 + 7
memo = [{} for i in range(n + 1)]


def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).find('AGC') >= 0:
            return False
    return True


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur >= n:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))


Measured memory_bytes: 3880
use proconio::*;
use std::cmp::max;

fn main() {
    input! {
        n:usize,
        xy:[(i64, i64); n],
    }

    let mut sum = Vec::new();
    let mut dif = Vec::new();
    for e in xy {
        sum.push(e.0 + e.1);
        dif.push(e.0 - e.1);
    }
    sum.sort();
    dif.sort();

    println!("{}", max(sum[n - 1] - sum[0], dif[n - 1] - dif[0]));
}


Measured memory_bytes: 12380
#include <bits/stdc++.h>
#define dbug(x) cout<<#x<<"="<<x<<endl
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const ll mod=(1e9)+7;
int mx=63;
int d[70],e[70];
ll dp[70][2][2][3];
void update(ll &x,ll y) {
	x+=y; x%=mod;
}
ll solve(ll L,ll R) {
	for (int i=0;i<mx;i++) {
		if (R&(1LL<<i)) d[i]=1; else d[i]=0;
		if (L&(1LL<<i)) e[i]=1; else e[i]=0;
	}
	//for (int i=0;i<mx;i++) printf("%d",d[i]); printf("\n");
	//for (int i=0;i<mx;i++) printf("%d",e[i]); printf("\n");
	memset(dp,0,sizeof(dp));
	dp[mx][1][1][0]=1; int C;
	for (int i=mx;i>=1;i--) {
		for (int j=0;j<=1;j++)
		for (int k=0;k<=1;k++)
		for (int B=0;B<=2;B++) {
			//printf("%d %d %d %d %lld\n",i,j,k,B,dp[i][j][k][B]);
			for (int a=0;a<=1;a++)
			for (int b=0;b<=1;b++) {
				if (j&&a>d[i-1]) continue;
				if (k&&b>e[i-1]) continue;
				if (a<b) continue;
				if (B==2) C=2;
				else {
					if (b||B) C=1;
					else if (a-b) C=2;
					else C=0;
				}
				update(dp[i-1][j&(a==d[i-1])][k&(b==e[i-1])][C],dp[i][j][k][B]);
			}
		}
	}
	ll res=0;
	for (int j=0;j<=1;j++)
	for (int k=0;k<=1;k++)
		update(res,dp[0][j][k][1]);
	//printf("%lld\n",res);
	return res;
}
int main() {
	//freopen("1.txt","r",stdin);
	//freopen("1.out","w",stdout);
	ll L,R; read(L); read(R);
	ll ans=solve(R,R)-solve(L-1,R);
	ans=(ans%mod+mod)%mod;
	printf("%lld\n",ans);
	/*ans=0;
	for (int x=1;x<=R;x++)
	for (int y=x;y<=R;y++)
		if (y%x==(x^y)) ans++;
	printf("%lld\n",ans);*/
	return 0;
}

Measured memory_bytes: 256
N = gets.to_i
result = 0

s = 27
while true do
  d4 = s.to_s(4).gsub(/1|2|3/, '1' => '3', '2' => '5', '3' => 7)
  if d4.to_i > N
    break
  end

  if /^[357]+$/.match(d4) && /3/.match(d4) && /5/.match(d4) && /7/.match(d4)
    result += 1
  end

  s += 1
end

puts result


Measured memory_bytes: 2044
#!usr/bim/python
#! -*- coding: utf-8 -*-
na = raw_input()
na = na.split()
n,a = map(int,na)

goukei = 0
i = 0
j = 0
k = 0
status = 0
for i in range(n+1):
    for j in range(n-i+1):
        k = n-(i+j)
        goukei = 10000*i + 5000*j + 1000*k
        if a == goukei:
            status = 1
            break
    if status == 1:
        break
if status == 0:
    i = -1
    j = -1
    k = -1

print i,j,k


Measured memory_bytes: 2692
#include <stdio.h>

int main (void)
{
    int i = 0;
    char s[5];
    char *si;

    si = s;

    gets(s);

    while(*si){
        if (*si == '+') i++;
        if (*si == '-') i--;
        si++;
    }

    printf("%d\n", i);
}


Measured memory_bytes: 128
N,K = map(int,input().split())
S = list(input())
if(S[K-1]=="A"):
    S[K-1]="a"
elif(S[K-1]=="B"):
    S[K-1]="b"
elif(S[K-1]=="C"):
    S[K-1]="c"
print("".join(S))

Measured memory_bytes: 38256
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N=200005;
int a[N];
int vedge[N];
priority_queue<int,vector<int>,less<int> >high;
priority_queue<int,vector<int>,greater<int> >low;
int vis[N];
int main()
{

    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    int ans=n-k+1;
    //cout<<ans<<endl;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int cnt=0;
    for(int i=0,pos=1;i<n-k+1;i++){
        for(int j=i;j<n-1;){
            if(a[j]<a[j+1])pos++,j++;
            if(pos==k){
                cnt++;
                vedge[j-k+1]=1;
                pos=k-1;
            }
            if(a[j]>a[j+1]){
                i=j;
                break;
            }
        }
        pos=1;
    }

    if(cnt!=0)ans=ans-cnt+1;
    //cout<<ans<<endl;
    for(int i=0;i<k;i++){
        high.push(a[i]);
        low.push(a[i]);
    }
    //cout<<" "<<low.top()<<" "<<high.top()<<endl;
    for(int l=0,r=k-1;r<n;l++,r++){
        while(!high.empty()&&vis[high.top()])high.pop();
        while(!low.empty()&&vis[low.top()])low.pop();
        if(!vedge[l]&&a[l]==low.top()&&r+1<n&&a[r+1]>high.top()){
            ans--;
            //cout<<a[l]<<endl;
            low.pop();
            high.push(a[r+1]);
            low.push(a[r+1]);
        }
        else if(!vedge[l]&&r+1<n){
            high.push(a[r+1]);
            low.push(a[r+1]);
        }
        else if(r+1<n){
            high.push(a[r+1]);
            low.push(a[r+1]);
        }
        vis[a[l]]=1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3572
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System;
using static System.Math;
using static System.Console;

class E { static void Main() => new J(); }
class J
{
	int F() => int.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	int MOD = 1000000007;
	public J()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var I = G();
		int N = I[0], M = I[1];
		WriteLine(Calc(N) * Calc(M) % MOD);
	}
	long Calc(int N)
	{
		var x = G();
		var s = new long[N + 1];
		for (var i = 0; i < N; i++) s[i + 1] = s[i] + x[i];
		var ans = 0L;
		for (var i = 0; i < N; i++) ans = (ans + (long)i * x[i] - s[i]) % MOD;
		if (ans < 0) ans += MOD;
		return ans;
	}
}

Measured memory_bytes: 29532
package main

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

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func Min(a, b int) int {
  if a < b { return a }
  return b
}
func Abs(a int) int {
  if a < 0 { a *= -1 }
  return a
}

func main() {
  T := NextIntVec()
  A := NextIntVec()
  B := NextIntVec()
  Takahashi := T[0] * A[0] + T[1] * A[1]
  Aoki := T[0] * B[0] + T[1] * B[1]
  if Takahashi == Aoki {
    Write("infinity")
  } else {
    ans := 0
    X := Min(Takahashi, Aoki) / Abs(Takahashi - Aoki)
    if Takahashi < Aoki {
      if B[0] < A[0] {
        high, low := X + 2, 1
        offset := 0
        for 1 < high - low {
          med := (high + low) / 2
          t := Takahashi * (med - 1) + T[0] * A[0]
          a := Aoki * (med - 1) + T[0] * B[0]
          if t < a {
            high = med
          } else {
            if t == a { offset = 1 }
            low = med
          }
        }
        ans = 2 * low - 1 - offset
      }
    } else {
      if A[0] < B[0] {
        high, low := X + 1, 1
        offset := 0
        for 1 < high - low {
          med := (high + low) / 2
          t := Takahashi * (med - 1) + T[0] * A[0]
          a := Aoki * (med - 1) + T[0] * B[0]
          if a < t {
            high = med
          } else {
            if t == a { offset = 1 }
            low = med
          }
        }
        ans = 2 * low - 1 - offset
      }
    }
    Write(ans)
  }
  Output()
}

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

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

    double res = 0.0;
    rep(i, N) {
        double x;
        string u;
        cin >> x >> u;
        
        if(u=="JPY") {
            res += x;
        } else {
            res += x * 380000.0;
        }
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
a = [0] * H
for i in range(H):
    a[i] = [int(aij) for aij in input().split()]

logs = []
for i in range(H):
    for j in range(W):
        if a[i][j] % 2 == 0:
            continue
        flag = False
        if j != W - 1:
            if a[i][j+1] % 2 == 1:
                a[i][j+1] += 1
                flag = True
                logs.append("{} {} {} {}".format(i+1, j+1, i+1, j+2))
                continue
        if i != H - 1:
            if a[i+1][j] % 2 == 1:
                a[i+1][j] += 1
                flag = False
                logs.append("{} {} {} {}".format(i+1, j+1, i+2, j+1))
                continue
        if not flag:
            if j != W - 1:
                a[i][j+1] += 1
                logs.append("{} {} {} {}".format(i+1, j+1, i+1, j+2))
            elif i != H - 1:
                a[i+1][j] += 1
                logs.append("{} {} {} {}".format(i+1, j+1, i+2, j+1))
print(len(logs))
for log in logs:
    print(log)


Measured memory_bytes: 16236