akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;

vector<int> dijkstra(int s, Graph<pii> &G) {
    int N = G.size();
    vector<int> dist(N, 1e9);
    dist[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> que;
    que.push({0, s});

    while (!que.empty()) {
        pii p = que.top();
        que.pop();
        int v = p.second;
        if (dist[v] < p.first)
            continue;
        for (auto np : G[v]) {
            int nv = np.first, cost = np.second;
            if (dist[v] + cost < dist[nv]) {
                dist[nv] = dist[v] + cost;
                que.push({dist[nv], nv});
            }
        }
    }

    return dist;
}

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

    int N, M;
    cin >> N >> M;

    Graph<pii> G(N);
    Graph<int> dist;
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }

    for (int i = 0; i < N; ++i)
        dist.push_back(dijkstra(i, G));

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (auto p : G[i]) {
            if (i >= p.first)
                continue;
            if (dist[i][p.first] < p.second)
                ans++;
        }
    }

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


Measured memory_bytes: 384
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        int N = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        long[] A = new long[3*N];
        for(int i=0;i<3*N;i++){
            A[i] = int.Parse(str[i]);
        }
        long[] B1 = new long[N];
        long[] B2 = new long[N];
        Heap H = new Heap(3*N,true);
        for(int i=0;i<N;i++){
            H.push(A[i]);
        }
        long count = 0;
        for(int i=0;i<N;i++){
            H.push(A[i+N]);
            count += H.pop();
            B1[i] = count;
        }
        H = new Heap(3*N,false);
        count = 0;
        for(int i=0;i<N;i++){
            H.push(A[i+2*N]);
        }
        for(int i=N-1;i>=0;i--){
            H.push(A[i+N]);
            count += H.pop();
            B2[i] = count;
        }
        long[] sum = new long[3*N];
        sum[0] = A[0];
        for(int i=1;i<3*N;i++){
            sum[i] = sum[i-1] + A[i];
        }
        count = sum[N-1] - (sum[3*N-1] - sum[N-1] - B2[0]);
        count = Math.Max(count,sum[2*N-1] - B1[N-1] - (sum[3*N-1] - sum[2*N-1]));
        for(int i=0;i<N-1;i++){
            count = Math.Max(count,sum[i+N]-B1[i]-(sum[3*N-1]-sum[i+N]-B2[i+1]));
        }
        sb.Append(count+"\n");
    }
}
class Heap{
    public int size;
    long[] obj;
    bool c;

    public Heap(int maxsize,bool b){
        size = 0;
        obj = new long[maxsize];
        c = b;
    }
    //小さい順ならa<=b
    public bool Compare(long a,long b){
        return (c && a <= b) || (!c && a >= b);
    }
    public void push(long a){
        int i = size;
        size++;
        while(i > 0){
            int p = (i - 1)/2;
            if(Compare(obj[p],a)){
                obj[i] = a;
                break;
            }
            obj[i] = obj[p];
            i = p;
        }
        if(i == 0){
            obj[0] = a;
        }
    }
    public long pop(){
        long t = obj[0];
        int i = 0;
        size--;
        while(2*i+1 < size){
            int p = 2*i+1;
            if(p+1 < size && Compare(obj[p+1],obj[p])){
                p++;
            }
            if(Compare(obj[p],obj[size])){
                obj[i] = obj[p];
                i = p;
            }
            else{
                obj[i] = obj[size];
                break;
            }
        }
        if(2*i+1 >= size){
            obj[i] = obj[size];
        }
        return t;
    }
}

Measured memory_bytes: 45996
def dfs(n, x)
  return P[n] if S[n] < x
  return 0 if x < 1
  return 1 if n.zero?
  x -= 1
  return dfs(n-1, x) if x<=S[n-1]
  x -= S[n-1]
  return P[n-1] + 1 if x==1
  x -= 1
  P[n - 1] + 1 + dfs(n-1, x)
end

N,X=gets.split.map(&:to_i)

S=*P=Array.new(N+2){0}
P[0]=S[0]=1
N.times do |n|
  P[n+1] += 1+2*P[n]
  S[n+1] += 3+2*S[n]
end

p dfs(N, X)


Measured memory_bytes: 1788
n,a,b,c,d=list(map(int,input().split()))
s=input()

if c<d:
    for i in range(a-1,d-1):
        if s[i]=='#' and s[i+1]=='#':
            print('No')
            exit(0)
    print('Yes')
else:
    for i in range(b-1,d):
        if s[i-1]=='.' and s[i]=='.' and s[i+1]=='.':
            break
    else:
        print('No')
        exit(0)
    
    for i in range(a-1,c-1):
        if s[i]=='#' and s[i+1]=='#':
            print('No')
            exit(0)
    
    print('Yes')


Measured memory_bytes: 65656
#include <bits/stdc++.h>
 
using namespace std;
 
//#define MD 1
#define MD 1000000007
 
int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    
    if((abs(a-b)<=d && abs(c-b)<=d)|| abs(a-c)<=d) {
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=505;
const ll inf=1e15;

int n,a[N][N];
ll f[N][N];

struct Sum{
	ll a[N][N];
	void build() {fo(i,1,n) fo(j,1,n) a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];}
	ll query(int lx,int rx,int ly,int ry) {return a[rx][ry]-a[lx-1][ry]-a[rx][ly-1]+a[lx-1][ly-1];}
}s0,s1;

int main() {
	scanf("%d",&n);
	fo(i,1,n) fo(j,1,n) if (i!=j) scanf("%d",&a[i][j]);
	fo(i,1,n) fo(j,i+1,n) s0.a[i][j]=a[i][j];
	fo(i,1,n) fo(j,1,i-1) s1.a[i][j]=a[i][j];
	s0.build();s1.build();
	fo(i,0,n) fo(j,0,i) f[i][j]=inf;
	f[0][0]=0;
	fo(i,0,n) fo(j,0,i) fo(k,i+1,n) f[k][i]=min(f[k][i],f[i][j]+s0.query(i+1,k,i+1,k)+s1.query(k+1,n,j+1,i));
	ll ans=inf;
	fo(i,0,n) ans=min(ans,f[n][i]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 7168
#include <iostream>

void CountingSort(int *A, int * B, int k, int n){
  int C[k+1];
  for(int i=0; i<=k; i++) C[i]=0;
  for(int j=0; j<n; j++) C[A[j]]++;
  for(int i=0; i<k; i++) C[i + 1] += C[i];
  for(int j=n-1; j>=0; j--){
    B[--C[A[j]]] = A[j];
  }
}

int main(){
  int n;
  std::cin >> n;

  int k;
  int A[n], B[n];
  for(int i=0; i<n; i++){
    std::cin >> A[i];
    k = std::max(k,A[i]);
  }
  CountingSort(A, B, k, n);
  for(int i=0; i<n; i++){
    std::cout << B[i];
    if(i != n-1) std::cout << " ";
  }
  std::cout << std::endl;
  return 0;
}



Measured memory_bytes: 35116
#include <cstdio>

int N, M;
int t[21][21];

int main() {
  while (true) {
    scanf("%d", &N);
    if (N == 0) break;
    for (int i=0;i<=20;i++) {
      for (int j=0;j<=20;j++) t[i][j] = 0;
    }
    for (int i=0;i<N;i++) {
      int x, y;
      scanf("%d %d", &x, &y);
      t[x][y]++;
    }
    scanf("%d", &M);
    int rx = 10, ry = 10;
    for (int i=0;i<M;i++) {
      char d;
      int  l;
      scanf(" %c %d", &d, &l);
      for (int j=0;j<l;j++) {
        switch (d) {
        case 'N': ry++; break;
        case 'E': rx++; break;
        case 'S': ry--; break;
        case 'W': rx--; break;
        }
        N -= t[rx][ry];
        t[rx][ry] = 0;
      }
    }
    if (N == 0) puts("Yes");
    else puts("No");
  }
  return 0;
}

Measured memory_bytes: 2476
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

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

    int min_value = P[0];
    int count = 0;
    for(int i=0; i<N; i++) {
        min_value = min(P[i], min_value);
        if(P[i] <= min_value) {
            count++;
        }
    }
    cout << count << endl;
}



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

int main()
{
    string a,b,c;
    char ch='a';
    cin>>a>>b>>c;
    while(true)
    {

        if(ch=='a')
        {
            if(a.empty())   {cout<<"A"; return 0;}
            ch=a[0];
            a.erase(0,1);
        }
        else if(ch=='b')
        {
            if(b.empty())   {cout<<"B"; return 0;}
            ch=b[0];
            b.erase(0,1);
        }
        else if(ch=='c')
        {
            if(c.empty())   {cout<<"C"; return 0;}
            ch=c[0];
            c.erase(0,1);
        }
    }
    return 0;
}


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

int main()
{
    int A, B;
    cin >> A >> B;
    vector<int> array(3);
    array.at(0) = A + B;
    array.at(1) = A - B;
    array.at(2) = A * B;
    sort(array.begin(), array.end());
    cout << array.at(2) << endl;
}

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

int main()
{ 
  int n, sum_h = 1;
  bool flag;
  vector<int> h(20);

  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> h[i];
  for (int i = 1; i < n; i++)
  {
    flag = true;
    for (int j = 0; j < i; j++)
    {
      if (h[i] < h[j])
        flag = false;
    }
    if (flag)
      sum_h++;
  }
  cout << sum_h << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
X = sorted(list(map(int, input().split())))


if N > M:
  print(0)
else:
  Y = []
  for i in range(M-1):
    Y.append(X[i+1] - X[i])

  Y.sort()
  print(sum(Y[:M-N]))

Measured memory_bytes: 13968
using namespace std;

#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

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

    int     N = 0;
    int     M = 0;
    int     m = 0;
    cin >> N >> M;
    int     A[M] = {0};
    int     Sum = 0;
    int     ans = 0;
    for(m = 0; m < M; m++){
        cin >> A[m];
        Sum += A[m];
    }

    if(Sum > N){
        ans = -1;
    }else{
        ans = N-Sum;
    }


    cout << ans << "\n";
    return 0;
    
}

Measured memory_bytes: 3640
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
		if len(os.Args) > 2 {
			wfp, _ = os.Create(os.Args[2])
		}
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	pp := make([]int, n)

	for i := 0; i < n; i++ {
		pp[getNextInt(scanner)-1] = i
	}

	cnt := 0
	c := 0
	for i := 1; i < n; i++ {
		if pp[i] > pp[i-1] {
			c++
			if c > cnt {
				cnt = c
			}
			continue
		}
		c = 0
	}
	c = 0
	for i := 1; i < n; i++ {
		if pp[n-1-i] < pp[n-i] {
			c++
			if c > cnt {
				cnt = c
			}
			continue
		}
		c = 0
	}

	fmt.Fprintln(writer, n-cnt-1)

	writer.Flush()
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define teto(a, b) (((a)+(b)-1)/(b))
#define all(x) x.begin(), x.end()
#define forn(i, n) for(int i = 0; i < (int)n; i++)
#define forne(i, a, b) for(int i = a; i <= b; i++)
#define dbg(msg, var) cerr << msg << " " << var << endl;

using namespace std;

const int MAX = 100010;
const int MOD = 123456789;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-7;

// End Template //

int main()
{sws;

    string s;
    cin >> s;
    if(s[s.size()-1]=='s'){
        cout << s << "es\n";
    }else
        cout << s << "s\n";

    return 0;
}

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

#define _max(_x, _y) ((_x)>(_y)?(_x):(_y))
#define _min(_x, _y) ((_x)>(_y)?(_y):(_x))

int main(void)
{
  int A, B, ans;
  scanf("%d %d", &A, &B);
  //printf("A(%d) B(%d) S(%s)\n", N, Q, S);
  if (A == B) {
    ans = A + A;
  } else {
    ans = _max(A, B);
    ans = ans * 2 - 1;
  }

  printf("%d\n", ans);
  
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long int 
#define fori(i,n) for(int i=0; i<n; ++i)
#define ford(i,n) for(int i=n-1; i>=0; --i)
#define vi vector<int> 
#define vs vector<string>
#define vll vector<ll>
#define di deque<int>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define pqi priority_queue<int>
#define pqll priority_queue<ll>
#define mod1 1000000007
#define mod2 998244353
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gcd __gcd

//Printing template
#define pf2(a,b) cout<<a<<" "<<b<<"\n"
#define pf3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n"
#define pf4(a,b,c,d) cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n"

#define fast_cin() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> i_set;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ll_set; 
/* new_data_set p; */
/* *p.find_by_order(3); The value at third place */
/* p.order_of_key(7); The expected index in the set in sorted order */

bool sortbysec(pair<ll,ll> &p1, pair<ll, ll> &p2){
    return (p1.se<p2.se);
}

int main(int argc, char const *argv[]){
    fast_cin();
    ll n,k,i,sum=0;
    cin>>n>>k;
    vll a(n);
    fori(i,n) cin>>a[i];
    sort(a.begin(), a.end());
    fori(i,max((ll)0,n-k)){
        sum+=a[i];
    }
    cout<<sum<<"\n";
    return 0;
}


Measured memory_bytes: 1792
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int T = sc.nextInt();
	long sum = 0;
	int current = sc.nextInt();
	for(int i = 1; i<N; i++) {
	    int next = sc.nextInt();
	    if(next-current<T) sum += next-current;
	    else sum += T;
	    current = next;
	}
	System.out.println(sum+T);
    }
}

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

using ll=long long;
using namespace std;

#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vll(v) sort((v).begin(), (v).end(), greater<long long>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}

const int IINF=(1<<30);
const ll LLINF = 1LL<<60;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    double r;cin >> r;
    cout << fixed << setprecision(10);
    cout << M_PI*pow(r, 2.0) << " " << 2*M_PI*r << endl;
}


Measured memory_bytes: 3248
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <functional>
#include <queue>
using namespace std;

const int MAX_V = 100010;
using Capacity = int;
using Cost = int;
const auto inf = numeric_limits<Capacity>::max() / 8;

struct Edge {
	int dst;
	Capacity cap, cap_orig;
	Cost cost;
	int revEdge; bool isRev;
	Edge(int dst, Capacity cap, Cost cost, int revEdge, bool isRev)
		:dst(dst), cap(cap), cap_orig(cap), cost(cost), revEdge(revEdge), isRev(isRev) {
	}
};

struct PrimalDual {
	int n;
	vector<vector<Edge> > g;
	PrimalDual(int n_) : n(n_), g(vector<vector<Edge> >(n_)) {}
	void add_edge(int src, int dst, Capacity cap, Cost cost) { // ?????????
		g[src].emplace_back(dst, cap, cost, g[dst].size(), false);
		g[dst].emplace_back(src, 0, -cost, g[src].size() - 1, true);
	}
	Cost solve(int s, int t, int f) {
		Cost res = 0;
		static Cost dist[MAX_V];
		static int prevv[MAX_V], preve[MAX_V];

		while(f > 0) {
			fill(dist, dist + n, inf);
			dist[s] = 0;

			while(true) {
				bool update = false;
				for(int v = 0; v < n; ++v) {
					for(unsigned i = 0; i < g[v].size(); ++i) {
						const auto &e = g[v][i];
						if(e.cap > 0 && dist[e.dst] > dist[v] + e.cost) {
							dist[e.dst] = dist[v] + e.cost;
							prevv[e.dst] = v;
							preve[e.dst] = i;
							update = true;
						}
					}
				}
				if(!update) break;
			}

			if(dist[t] == inf) {
				return -1;
			}
			// s-t ????????????????????£??????????????????
			int d = f;
			for(int v = t; v != s; v = prevv[v]) {
				d = min(d, g[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d * dist[t];
			for(int v = t; v != s; v = prevv[v]) {
				Edge &e = g[prevv[v]][preve[v]];
				e.cap -= d;
				g[v][e.revEdge].cap += d;
			}
		}
		return res;
	}
	// ??????????????????=???????????????-?????¨??????????????¨???
	void view() {
		for(int i = 0; i < g.size(); i++) {
			for(int j = 0; j < g[i].size(); j++) {
				if(!g[i][j].isRev) {
					Edge& e = g[i][j];
					printf("%3d->%3d (flow:%d)\n", i, e.dst, e.cap_orig - e.cap);
				}
			}
		}
	}
};



typedef long long ll;
ll w[10000];
int a[10000];

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

	int M, N, K;
	cin >> M >> N >> K;

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

	PrimalDual pd(K);

	ll sum = 0;
	for(int i = 0; i < K; i++) {
		cin >> a[i];
		a[i]--;
		if(i > 0 && a[i - 1] == a[i]) continue;
		sum += w[a[i]];
	}

	for(int i = 0; i < K - 1; i++) {
		pd.add_edge(i, i + 1, 1000000, 0);
	}
	vector<int> prev(N, -1);
	for(int i = 0; i < K; i++) {
		if(prev[a[i]] != -1 && prev[a[i]] + 1 != i) {
			pd.add_edge(prev[a[i]] + 1, i, 1, -w[a[i]]);
		}
		prev[a[i]] = i;
	}


	ll res = pd.solve(0, K - 1, M - 1);
	//assert(res != -1);
	cout << sum + res << endl;
}

Measured memory_bytes: 4528
// input some integers, output the number of prime numbers if it is included input numbers
#include<iostream>
#include<complex>
bool Prime(int);
int main(){
  int n, input, count=0;
  std::cin >> n;
  for(int i=0; i<n; i++){
    std::cin >> input;
    if(Prime(input)) count++;
  }
  std::cout << count << "\n";
  return 0;
}

bool Prime(int x){
  int i;
  if(x == 2) return true;
  else if(x<2 || x%2==0) return false;
  for(i=3; i<=std::sqrt(x); i+=2) if(x%i==0) return 0;
  return true;
}

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

def keta(cnt,a):
    if 0 < a and a <= 9:
        return cnt 
    else : 
        cnt += 1
        a = a // 10
        
    return keta(cnt,a)

def zyou(a):
    n = 1
    while True :
        if a < n**2 :
            return n
        else : n += 1 
n = zyou(N)

for i in range(n,0,-1):
    if N % i == 0 :
        print("{}".format(keta(1,max(i,N//i))))
        break 


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int dx[4], dy[4];
bool ba[4][4];

int rec(int x,int y) {
  for (;y<4; ++x) {
    if (x==4) {
      y++;x=0;
    }
    if (!ba[x][y]) {
      break;
    }
  }
  if (y==4) return 1;

  // printf("%d,%d\n", x,y);
  // REP(i,4) {
  //   REP(j,4)
  //     cout << ba[j][i] << " ";
  //   cout<< endl;
  // }
  
  ba[x][y] = 1;
  int res = 0;
  REP(i,4) {
    int xx = x+dx[i];
    int yy = y+dy[i];
    if (xx<0||xx>=4||yy<0||yy>=4) continue;
    if (ba[xx][yy]) continue;
    ba[xx][yy] = 1;
    res += rec(x+1, y);
    ba[xx][yy] = 0;
  }
  ba[x][y] = 0;
  return res;
}

int main() {
  while(cin >> dx[0], dx[0]<=3) {
    REP(i,4) {
      if (i)cin >> dx[i];
      cin >> dy[i];
    }
    memset(ba,0,sizeof(ba));
    cout << rec(0,0) << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

struct Data { int time, lane, lap; };

bool is_end(vector<bool>& v)
{
	for (auto i : v)
	{
		if (!i) return true;
	}
	return false;
}

int main()
{
	int n;
	while (cin >> n, n)
	{
		vi v;
		vector<Data> tmp;
		REP(i, n)
		{
			int t, c; cin >> t >> c;
			v.emplace_back(t);
			tmp.push_back(Data{ t, 0, c });
		}
		vector<bool> finish(n);
		int ans = 0;
		while (is_end(finish))
		{
			int time = INF, p;
			REP(i, n)
			{
				if (finish[i]) continue;
				if (tmp[i].time < time)
				{
					time = tmp[i].time;
					p = i;
				}
			}
			ans += time;
			REP(i, n)
			{
				if (finish[i]) continue;
				if (tmp[i].time != time) tmp[i].time -= time;
				else
				{
					if (tmp[i].lane)
					{
						tmp[i].lap--;
						if (tmp[i].lap == 0) finish[i] = true;
						tmp[i].lane = 0;
					}
					else
					{
						tmp[i].lane = 1;
					}
					tmp[i].time = -1;
				}
			}
			int maxf = 0, maxb = 0;
			REP(i, n)
			{
				if (finish[i]) continue;
				if (tmp[i].time != -1)
				{
					if (tmp[i].lane == 0) chmax(maxf, tmp[i].time);
					else chmax(maxb, tmp[i].time);
				}
			}
			REP(i, n)
			{
				if (finish[i]) continue;
				if (tmp[i].time == -1)
				{
					if (tmp[i].lane == 0) tmp[i].time = max(maxf, v[i]);
					else tmp[i].time = max(maxb, v[i]);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
int main()
{	
	int a,b,c;
	cin >> a >> b;
	c=a+b;
	if(c%2==0){
		cout << c/2 << endl;
 	}
 	else{
 		cout << (c+1)/2 << endl; 
 	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<math.h>
#include<utility>
using namespace std;
vector<int> res(26, 0);

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

    bool flag = false;
    int length = p.size();
    int sp;

    for(int sp=0;sp<s.size();sp++){
        int counter = 0;
        for(int i=sp;;i++){
            if(counter >= length) {
                cout << "Yes" << endl;
                return 0;
            }
            
            if(i >= s.size()) i = 0;
            if(p[counter] != s[i]) {
                break;
            }
            counter++;
        }
    }

    cout << "No" << endl;
}


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

typedef long long ll;
typedef unsigned long long ull;
//typedef long double ld;

typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<int> vi;
typedef vector<pair<int, int > > vii;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vll> vvll;

constexpr ll MOD = 1e9+7;
constexpr int INF = 1<<30;
constexpr ll  LINF = 1LL<<60;

#define Sort(x) sort(x.begin(),x.end())
#define Reverse(x) reverse(x.begin(),x.end())
#define ABS(a,b) ((a)<(b)?(b)-(a):(a)-(b))
#define nbit(n) (1ll<<(n))

// sort(begin(x), end(x), greater<ll>());
// lower_bound(a.begin(), a.end(), val): a[i] ≥ valである最左の位置
// upper_bound(a.begin(), a.end(), val): a[i] > valである最左の位置

// Returns minimum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmin(T& a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}

// Returns maximum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmax(T& a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}

// a = (a+b)%MOD;
void addmod(ll& a, ll b) {
  a = (a+b)%MOD;
}

template <typename T>
void dumpContents(const T& v, const string& msg)
{
  cerr << "### " << msg << " ###\n";
  for (const auto& x : v) {
    cerr << x << " ";
  }
  cerr << endl;
}

struct before_main_function {
  before_main_function() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(20)<<fixed;
    #define endl "\n"
  }
} before_main_function;

// ========== end of template ==========
constexpr int N_MAX = 1e5;
ll N, M;
vvi G(N_MAX);

int alt(int color) {
  return color == 1 ? 2 : 1;
}

bool isBipartite(vi& visited, int u, int color) {
  bool ret = true;

  for (auto c : G[u]) {
    if (!visited[c]) {
      visited[c] = alt(color);
      ret = ret && isBipartite(visited, c, alt(color));
    }

    ret = ret && visited[c] != color;
  }

  return ret;
}

int main(int argc, char** argv) {
  cin >> N >> M;
  for (int i=0; i<M; i++) {
    int A, B;
    cin >> A >> B;
    A--; B--; // 0-indexed
    G[A].emplace_back(B);
    G[B].emplace_back(A);
  }

  vi visited(N_MAX);
  bool r = isBipartite(visited, 0, 1);
//cerr << "isBipartite " << r << endl;

  if (r) {
    ll white = 0;
    for (auto x : visited) {
      if (x==1) white++;
    }
    cout << white * (N-white) - M << endl;
    return 0;
  }

  cout << N*(N-1)/2 - M << endl;

  return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  if (N % 1110 < 10) {
    cout << "Yes" << endl;
  }
  else if (N % 1000 == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}  

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


using namespace std;

#define X first
#define Y second

inline int manh_dist(pair<int,int> &s, pair<int,int> &g){
	return abs(s.X - g.X) + abs(s.Y - g.Y);
}


int main(void){
	int n,m;
	char c;
	while(cin >> m >> n){
		if(!(n|m)) break;
		vector<pair<int,int> > nodes[5];
		pair<int,int> s,g;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin >> c;
				if(c == 'S'){
					s.X = i;
					s.Y = j;
				}else if(c == 'G'){
					g.X = i;
					g.Y = j;
				}else if(c == '.'){
				}else{
					nodes[c-'0'-1].push_back(make_pair(i,j));
				}
			}
		}
				
		int ret = 1 << 28;
		int tmp_min;
		int attr = -1;
		for(int i=0;i<5;i++){ //i:ツ堕ョツ青ォ
			//cout << 1 << endl;
			int dp[5][1000];
			fill((int *)dp, (int *)dp+5*1000, 1<<28);
			tmp_min = 1 << 28;
			
			//sツつゥツづァツつスツづづィツ陳つッツづゥツ堕ョツ青ォツづ個値ツづーツ更ツ新
			for(int j=0;j<nodes[(i+1)%5].size();j++){
				dp[(i+1)%5][j] = min(dp[(i+1)%5][j], manh_dist(s, nodes[(i+1)%5][j]));
			}
			//ツ篠淞づ個堕ョツ青ォツ暗按古」ツづーツ計ツ算ツつオツづつ「ツつュ
			for(int cur = (i+1)%5; cur != i; cur = (cur+1)%5){
				int next = (cur+1)%5;
				for(int p=0;p<nodes[cur].size();p++){
					for(int q=0;q<nodes[next].size();q++){
						dp[next][q] = min(dp[next][q], dp[cur][p] + manh_dist(nodes[cur][p], nodes[next][q]));
					}
				}
			}
			int end = i-1;
			if(end < 0) end = 4;
			//ツ催古」ツづ個要ツ素ツつゥツづァGツづ慊づづ個仰猟猟」ツづーツ嘉鳴。ツつオツづ計ツ算
			for(int j=0;j<nodes[end].size();j++){
				tmp_min = min(tmp_min, dp[end][j]+manh_dist(g, nodes[end][j]));
			}
			if(ret > tmp_min){
				ret = tmp_min;
				attr = i;
			}
		}
		if(attr == -1){
			cout << "NA" << endl;
		}else{
			cout << attr+1 << " " << ret << endl;
		}
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-3;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int n;
vector<int> G[5001];
vector<int> g;
bool used[5001];
int cnt[5001];
int dfs(int id) {
	used[id] = true;
	int res = 1;
	bool isg = true;
	rep(j, G[id].size()) {
		int to = G[id][j];
		if (used[to])continue;
		int subres = dfs(to);
		res += subres; if (subres > n / 2)isg = false;
	}
	if (n - res > n / 2)isg = false;
	if (isg)g.push_back(id);
	return cnt[id]=res;
}
ll p[5001];
ll pas[5001][5001];
void init() {
	p[0] = 1;
	rep1(i, 5000) {
		p[i] = p[i - 1] * i%mod;
	}
	rep(i, 5001) {
		rep(j, 5001) {
			if (i == 0 || j == 0)pas[i][j] = 1;
			else pas[i][j] = (pas[i][j - 1] + pas[i - 1][j]) % mod;
		}
	}
}
ll dp[5001][5001]; int sz;
int main() {
	init();
	cin >> n;
	rep(i, n - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0);
	if (g.size() == 2) {
		cout << p[n / 2] * p[n / 2] % mod << endl;
	}
	else {
		fill(used, used + n, false);
		dfs(g[0]);
		vector<int> v;
		rep(i, G[g[0]].size()) {
			v.push_back(cnt[G[g[0]][i]]);
		}
		sz = 1; dp[0][0] = 1;
		rep(i, v.size()) {
			rep(j, v[i]+1) {
				rep(k, sz) {
					dp[i + 1][j + k] += dp[i][k] * pas[v[i] - j][j] % mod*pas[v[i] - j][j] % mod*p[j]%mod;
					dp[i + 1][j + k] %= mod;
				}
			}
			sz += v[i];
		}
		ll ans = 0;
		rep(i, sz + 1) {
			ll csum = dp[v.size()][i];
			csum = csum * p[sz - i] % mod;
			if (i % 2)csum = (-csum + mod) % mod;
			(ans += csum) %= mod;
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 375168
import bisect

N = int(input())
S = list(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)

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

using namespace std;
int main(void){
    // Your code here!
    string s,t,u;
    cin>>s;
    if(s[0]=='9'||s[1]=='9'){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var b = cin.Read[0];

            if (b == 'A')
                WriteLine('T');
            else if (b == 'T')
                WriteLine('A');
            else if (b == 'C')
                WriteLine('G');
            else if (b == 'G')
                WriteLine('C');
        }

        static long GcdArray(long[] array)
        {
            var ans = array[0];
            for(var i=1; i<array.Length; i++)
            {
                ans = Gcd(ans, array[i]);
            }
            return ans;
        }

        static long Gcd(long a, long b)
        {
            var v = new[] { a, b };
            while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
            return v[0];
        }

        static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

Measured memory_bytes: 11220
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

N = int(input())
L = divisor(N)
L = sorted(L)
ans = float("inf")

for i in L:
    p = i
    q = N // i
    temp = (p-1)+(q-1)
    ans = min(ans, temp)

print(ans)

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

const int MXN=100005;

int N,W;
ll dp[MXN];

int main(){
  scanf("%d%d",&N,&W);
  for(int i=1;i<=N;++i){
    int w,v;
    scanf("%d%d",&w,&v);
    for(int i=W;i>=w;--i){
      dp[i]=max(dp[i],dp[i-w]+v);
    }
  }
  printf("%lld\n",dp[W]);
}


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

int n, d, lst = 0;
long long ans = 0, c;

int add(int l, int r) {
    if (l + r >= 10) {
        ans += 2;
    } else {
        ans++;
    }
    return (l + r - 1) % 9 + 1;
}

int init(int d) {
    int st = d, ret = 0;
    for (int i = 0; i < 9; i++) {
        ret += (st + d >= 10) + 1;
        st = (st + d - 1) % 9 + 1;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d >> c;
        int st = d, tmp = init(d);
        c--; ans += (c / 9) * tmp; c %= 9;
        while (c--) {
            ans += (st + d >= 10) + 1;
            st = (st + d - 1) % 9 + 1;
        }
        if (i != 1) {
            ans += (lst + st >= 10) + 1;
        }
        lst = (lst + st - 1) % 9 + 1;
    }
    cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=1000000007;


int main() {
  string s;
  cin >> s;
  int size=s.size();
  vector<int> a(size);
  for(int i=0;i<size;i++){
    if(s.at(i)=='A' || s.at(i)=='C' ||
       s.at(i)=='G' || s.at(i)=='T'){
         a.at(i)=1;
       }
  }
  int k=0;
  priority_queue<int> pq;
  for(int i=0;i<size;i++){
    if(a.at(i)==1){
      if(i==size-1){
        k++;
        pq.push(k);
      }
      else
        k++;
    }
    else{
      pq.push(k);
      k=0;
    }
  }
  cout << pq.top() << endl;
}



Measured memory_bytes: 3616
#include<stdio.h>
int main(void){
int W, H, x, y, r;
scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
if (x + r <= W && y + r <= H && x >= r && y >= r){
  printf("Yes\n"); 
 }else {
  printf("No\n");
 }
return 0;
}




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

int  main(){

int n,x,m;
vector<int> vm;

cin >> n >> x;

for(int i=0;i<n;i++){
cin >>m;
vm.push_back(m);
}
int min = vm[0];
for(int i = 0; i < n; i++){
    if(vm[i]<min){
     min=vm[i];
	}
	x -= vm[i];
}

cout << n + x/min << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
#define modulo 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9

int A, B, C;

bool isSame() {
	if (A == B && A == C) return true;
	else return false;
}

bool isOdd() { // 奇数があるかどうか
	bool a, b, c;
	a = (A % 2 == 1);
	b = (B % 2 == 1);
	c = (C % 2 == 1);
	return (a || b || c);
}

void change() {
	int a = (B + C) / 2;
	int b = (A + C) / 2;
	int c = (A + B) / 2;
	A = a; B = b; C = c;
}

int main() {
	cin >> A >> B >> C;
	int ans = 0;

	while (!isOdd()) {
		if (isSame()) {
			ans = -1;
			break;
		}
		change();
		ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
	int r, c, q;
	int A[50000], B[50000], ord[50000];
	bool row[50000], col[50000];
	while(cin >> r >> c >> q, r){
		for(int i=0;i<q;i++) scanf("%d %d %d", &A[q-i-1], &B[q-i-1], &ord[q-i-1]);
		memset(row, false, sizeof(row));
		memset(col, false, sizeof(col));
		int lestR = r, lestC = c;
		long long res = 0;
		for(int i=0;i<q;i++){
			if(A[i]==0){
				if(row[B[i]]) continue;
				if(ord[i]==1) res += lestC;
				lestR--;
				row[B[i]] = true;
			} else {
				if(col[B[i]]) continue;
				if(ord[i]==1) res += lestR;
				lestC--;
				col[B[i]] = true;
			}
		}
		cout << res << endl;
	}
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(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 DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
vl modinv;
void fillModInv(ll n, ll mod){
  modinv = vl(n+1);
  modinv[1] = 1;
  FOR(i,2,n+1){
    modinv[i] = modinv[mod%i] * (mod - mod/i) % mod;
  }
}
/*}}}*/
int main() {
  ll a,b,n;
  cin >> a >> b >> n;
  ll k = min(b-1,n);
  ll ans = a * k / b;
  
  //cout << fixed << setprecision(10);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <limits>

using namespace std;

int main()
{
  string s;
  cin >> s;
  cin.get();
  cin.ignore(numeric_limits<streamsize>::max(), '\n');

  string command;
  int start, finish;
  while (cin >> command >> start >> finish) {
    if (command == "replace") {
      string replacement;
      cin >> replacement;
      s.replace(start, finish - start + 1, replacement);
    } else if (command == "print") {
      cout << s.substr(start, finish - start + 1) << endl;
    } else if (command == "reverse") {
      reverse(&s[start], &s[finish+1]); 
    }
  }
}



Measured memory_bytes: 3208
import sys

dic = {}
for i in range(ord('a'), ord('z') + 1):
    dic[chr(i)] = 0

for line in sys.stdin:
    for i in range(len(line)):
        char = line[i].lower()
        if char in dic.keys():dic[char] += 1

for i in range(ord('a'), ord('z') + 1):
    print("{} : {}".format(chr(i), dic[chr(i)]))

Measured memory_bytes: 7412
#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
	int n,max_num = -1000001,min_num = 1000001,tmp;
	long long int sum = 0;
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		scanf("%d",&tmp);
		sum += tmp;
		max_num = max(max_num,tmp);
		min_num = min(min_num,tmp);
	}
	printf("%d %d %lld\n",min_num,max_num,sum);
}


Measured memory_bytes: 2756
n = int(input())
a = list( map(int, input().split())) 
b = list( map(int, input().split())) 
ans = 0
for i in range(len(a)-1):
    if a[i] >= b[i]:
        ans += b[i]
    else:
        ans += a[i]
        ans += a[i+1] - max(a[i+1] - (b[i]-a[i]),0) 
        a[i+1] = max(a[i+1] - (b[i]-a[i]),0)

print(ans)

Measured memory_bytes: 18476
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // トポロジカルソート
  int V, E; cin >> V >> E;
  vector<vector<int> > edge(V, vector<int>());
  vector<int> h(V, 0);
  REP(i, E){
    int x, y; cin >> x >> y;
    edge[x].push_back(y);
    h[y]++;
  }
  queue<int> q;
  REP(i, V){
    if(h[i] == 0) q.push(i);
  }
  vector<int> ans;
  while(!q.empty()){
    int i = q.front(); q.pop();
    ans.push_back(i);
    for(int j : edge[i]){
      h[j]--;
      if(h[j] == 0) q.push(j);
    }
  }
  if(ans.size() == V){
    cout << 0 << endl;
  }else{
    cout << 1 << endl;
  }
}


Measured memory_bytes: 3228
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

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

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

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

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

fn main() {
    input! {
        k: usize,
        s: usize
    }

    //test
    //
    /*
    let k: usize = 2;
    let s: usize = 2;
    */

    let mut ans: usize = 0;

    for x in 0..k + 1 {
        for y in 0..k + 1 {
            if (x + y) > s {
                break;
            }
            if (x + y + k) >= s {
                ans = ans + 1;
            }
        }
    }

    //assert_eq!(ans, 6);
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
string s;
int n;
vector<int> v;
bool judge(int k){
  if(2*k<=n+1) return true;
  int t=n-k+1,sum=0;
  for(int i=1;i<=t;i++){
    if(sum%2==0) sum+=v[i];
    else sum+=(1-v[i]);
    sum%=2;
  }
  for(int i=t+1;i<=k;i++){
    if((v[i]+sum)%2!=0) return false;
  }
  return true;
}
int main(){
  cin>>s;
  n=s.length();
  v.push_back(0);
  for(int i=0;i<n;i++) v.push_back(s[i]=='0'?0:1);
  int lb=1,rb=n+1;
  while(rb-lb>1){
    int mid=(lb+rb)/2;
    if(judge(mid)) lb=mid;
    else rb=mid;
  }
  cout<<lb<<endl;


  cout<<endl;
}


Measured memory_bytes: 1020
package main

import (
	"fmt"
	"os"
	"bufio"
)

type Directions int
const (
	up = iota
	upRight
	right
	downRight
	down
	downLeft
	left
	upLeft
)

type Area rune
const (
	Bomb = '#'
	Space = '.'
)

func main() {
	var H,W int
	input := bufio.NewScanner(os.Stdin)

	fmt.Scan(&H)
	area := make([]string,H)
	sampleArea:= make([]string,H) 

	fmt.Scan(&W)

	for i := 0;i < H;i++ {
		input.Scan()
		sampleArea[i] = input.Text()
	}
	
	for y,str := range sampleArea {
		runeArray := make([]rune,W)
		for x,char := range str {
			if Bomb == char {
				runeArray[x] = Bomb
				continue
			}
			runeArray[x] = rune(countBomb(sampleArea,W,H,x,y) + '0')
		}
		area[y] = string(runeArray)
	}
	
	for _,str := range area {
		fmt.Println(str)
	}
}

func countBomb(area []string,xMax int,yMax int,x int,y int) int {
	var count int
	for dir := up;dir <= upLeft;dir++ {
		if look(Directions(dir),area,x,y) {
			count++
		}
	}
	return count
}

func look(direction Directions,area []string,x int,y int) bool{
	switch direction {
	case up:
		if 0 == y || Space == area[y - 1][x]{
			return false 
		}
	case upRight:
		if len(area[y]) - 1 == x || 0 == y || Space ==  area[y - 1][x + 1] {
			return false
		}
	case right:
		if len(area[y]) - 1 == x || Space == area[y][x + 1] {
			return false
		}
	case downRight:
		if len(area[y]) - 1  == x || len(area) - 1 == y || Space == area[y + 1][x + 1] {
			return false
		}
	case down:
		if len(area) - 1 == y || Space == area[y + 1][x]{
			return false
		}
	case downLeft:
		if len(area) - 1 == y || 0 == x || Space == area[y + 1][x - 1] {
			return false
		}
	case left:
		if 0 == x || Space == area[y][x - 1] {
			return false
		}
	case upLeft:
		if 0 == x || 0 == y || Space == area[y - 1][x - 1] {
			return false
		}
	}
	return true
}



Measured memory_bytes: 640