akhauriyash/Code-Regression huggingface dataset:
A, B, C, D, E, F = map(int, input().split())
rs = []
for a in range(0, F, 100*A):
  for b in range(0, F, 100*B):
    x = a+b
    if x == 0 or x > F:
      continue
    for c in range(0, F, C):
      for d in range(0, F, D):
        y = c+d
        if not(x+y <= F):
          break
        # if 100*y/(x+y) <= 100*E/(100+E):
        if not(y*100 <= E*x):
          break
        rs.append((100*y/(x+y), x+y, y))
c, z, y = max(rs)
print(z, y)


Measured memory_bytes: 107644
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String w = sc.next().toLowerCase();
        String t;
        int count = 0;

        while( !((t=sc.next()).equals("END_OF_TEXT")) ){
            if(t.toLowerCase().equals(w)) count++;
        }

        System.out.println(count);
    }
}


Measured memory_bytes: 26044
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

ll mod = 1000000007;
ll N;
ll Prev[6005], Next[6005];
ll ans;

int main() {
    cin >> N >> mod;
    for(ll i = 0; i <= 3 * N; i++) {
        Prev[i] = 1;
    }
    ans = 1;
    for(int timer = 0; timer < N; timer++) {
        for(ll rest = 0; rest <= 3 * N; rest++) Next[rest] = 0;
        for(ll rest = 0; rest <= 3 * N; rest++) {
            if(rest >= 2) {
                Next[rest-2] += Prev[rest] * (rest - 1);
                Next[rest-2] %= mod;
            }
            if(rest >= 3) {
                Next[rest-3] += Prev[rest] * (rest - 1) * (rest - 2);
                Next[rest-3] %= mod;
            }
        }
        for(ll rest = 3 * N - 1; rest >= 0; rest--) {
            Next[rest] += Next[rest+1];
            Next[rest] %= mod;
        }
        ans += Next[0];
        ans %= mod;
        swap(Prev, Next);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <cmath>
#include <stdio.h>
#include <sstream>
#define int_inf 1000000000 //1e9
#define ll_inf  1000000000000000000 //1e18
using namespace std;
template <typename T> std::string to_string(const T& t){
	std::ostringstream os; os<<t; return os.str();
}

int main(){
	int r, g, b;
	cin>>r>>g>>b;
	if((g*10+b)%4==0) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}




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

using namespace std;

int main(void) {
    int N, d[3010], X;
    cin >> N;
    for (int i=0;i<N;i++) cin >> d[i]; 
    X = 0;
    for (int i=0;i<N;i++) X += d[i]-1;
    cout << X << endl;
    return 0;
}

Measured memory_bytes: 256
R, C, K = map(int, input().split())
goods = [[0] * C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    goods[r-1][c-1] = v

dp = [[[0] * C for _ in range(4)] for _ in range(R)]
dp[0][1][0] = goods[0][0]
for i in range(R):
    for j in range(4):
        for k in range(C):
            if i < R - 1:
                dp[i+1][0][k] = max(dp[i+1][0][k], dp[i][j][k])
                dp[i+1][1][k] = max(dp[i+1][1][k], dp[i][j][k] + goods[i+1][k])
        
            if k < C - 1:
                dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k])
                if j < 3:
                    dp[i][j+1][k+1] = max(dp[i][j+1][k+1], dp[i][j][k] + goods[i][k+1])

res = 0
for i in range(4):
    res = max(res, dp[R-1][i][C-1])

print(res)

Measured memory_bytes: 430308
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc =  new Scanner(System.in);
    long x = sc.nextLong();
    long count = 0;
    long num = 100;

    while(num<x){
      count++;
      num = num + (long)((double)num * 0.01);
    }

    System.out.println(count);
  }
}

Measured memory_bytes: 35780
'use strict'

process.stdin.resume();
process.stdin.setEncoding('utf8');
var N,M;
var mo=1000000007;
// 標準入力がくると発生するイベント
process.stdin.on('data', function (chunk) {
    chunk.trim().split('\n').forEach(function(line) {
		var arr=line.split(" ");
		N=arr[0];
		M=arr[1];
    });
});
// EOFがくると発生するイベント

function check(Num,N,M){
	
	//作るべきSの数
	let makeS = Num - N;
	if (makeS <= 0) makeS = 0;
	//Sを作るのに使う分をMから引く
	M -= makeS * 2;
	//足りなかったらNG
	if (M < 0) return false;
	N = Num;
	//この時点でCが足りていたらOK、足りて無かったらNG
	if (N * 2 <= M){
		return true;
	}
	else return false;

}

process.stdin.on('end', function () {
	N=parseInt(N);
	M=parseInt(M);
	let maxScc = 1000000000000/2;
	let minScc = 0;
	//binsearch
	let left = minScc,right=maxScc;
	while (right - left != 1){
		let mid = Math.floor((left + right) / 2);
		if (check(mid, N, M)) left = mid;
		else right = mid;
		//console.log(right)
	}
	let ans = check(right, N, M) ? right : left;
	console.log(ans);
});

Measured memory_bytes: 21192
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int r;
	cin>>r;
	ld Radius = r;
	ld pi = 3.14159265359;
	cout<<fixed<<setprecision(8)<<2*pi*Radius<<"\n";
	return 0;
}

Measured memory_bytes: 3764
import java.util.Scanner;

class Main {
	public static void main(String... args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();

		int acCnt = 0;
		int ngCnt = 0;

		int[] ng = new int[n + 1];
		boolean[] ok = new boolean[n + 1];

		for(int i = 0; i < m; i++) {
			int p = scan.nextInt();
			String s = scan.next();
			if(!ok[p] && s.equals("AC")) {
				ok[p] = true;
			}else if(!ok[p] && s.equals("WA")) {
				ng[p]++;
			}
		}
		for(int i = 1; i <= n; i++) {
			if(ok[i]) {
				acCnt++;
				ngCnt += ng[i];
			}
		}
		System.out.println(acCnt + " " + ngCnt);
	}
}


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

template<typename T> class Dijkstra {
public:
  using pit = pair<int, T>;
  struct edge {
    int to; T cost;
  };
  int N;
  vector<vector<edge>> G;
  vector<T> D;
  Dijkstra(int n) : N(n), G(n), D(n, numeric_limits<T>::max()) {}
  void add(int now, int next, T cost) {
    G.at(now).push_back((edge) {next, cost});
  }
  void solve(int start) {
    priority_queue<pit, vector<pit>, greater<pit>> Q;
    D.at(start) = 0;
    Q.push(pit(start, 0));
    while (Q.size()) {
      auto [now, dist] = Q.top();
      Q.pop();
      for (auto &[next, cost] : G.at(now)) {
        if (dist + cost < D.at(next)) {
          D.at(next) = dist + cost;
          Q.push(pit(next, D.at(next)));
        }
      }
    }
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int H, W, sh, sw, gh, gw;
  cin >> H >> W >> sh >> sw >> gh >> gw;
  sh--, sw--, gh--, gw--;
  int st = 0, go = 0;
  vector<vector<pair<int, char>>> S(H, vector<pair<int, char>>(W));
  for (int i = 0, id = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      char c;
      cin >> c;
      if (i == sh && j == sw) st = id;
      if (i == gh && j == gw) go = id;
      S.at(i).at(j) = {id++, c};
    }
  }
  
  vector<int> mh(4), mw(4);
  mh = {-1, 0, 1, 0};
  mw = {0, 1, 0, -1};

  Dijkstra<long> D(H * W);
  for (int h = 0; h < H; h++) {
    for (int w = 0; w < W; w++) {
      for (int i = h - 2; i <= h + 2; i++) {
        for (int j = w - 2; j <= w + 2; j++) {
          if (i < 0 || i >= H || j < 0 || j >= W) continue;
          if (S.at(i).at(j).second == '.') D.add(S.at(h).at(w).first, S.at(i).at(j).first, 1);
        }
      }
      for (int i = 0; i < 4; i++) {
        int nh = h + mh.at(i);
        int nw = w + mw.at(i);
        if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
        if (S.at(nh).at(nw).second == '.') D.add(S.at(h).at(w).first, S.at(nh).at(nw).first, 0);
      }
    }
  }

  D.solve(st);

  if (D.D.at(go) == LONG_MAX) return cout << -1 << "\n", 0;
  cout << D.D.at(go) << "\n";
}


Measured memory_bytes: 368712
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    if N%2==1:
        print(0)
    else:
        ans = 0
        for i in range(1,100):
            ans += N//((5**i)*2)
        print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli mod=1000000007;

int main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
  	string s;
  	cin>>s;
  	int a=0,b=0;
  	for(int i=0;i<3;++i){
  		if(s[i]=='A')
  			a++;
  		else
  			b++;
  	}
  	if(a&&b)
  		cout<<"Yes"<<endl;
  	else
  		cout<<"No"<<endl;
}

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

int main() {
  int N;
  cin >> N;
  string str;
  vector<int> S(4);
  
  rep(i,N) {
    cin >> str;
    if (str == "AC") {
      S.at(0)++;
    } else if (str == "WA") {
      S.at(1)++;
    } else if (str == "TLE") {
      S.at(2)++;
    } else if (str == "RE") {
      S.at(3)++;
    } 
  }
  
  rep(i,4) {
    if (i == 0) {
      str = "AC";
    } else if (i == 1) {
      str = "WA";
    } else if (i == 2) {
      str = "TLE";
    } else if (i == 3) {
      str = "RE";
    }
    cout << str << " x " << S.at(i) << endl;
  }    
}


Measured memory_bytes: 3624
#include<stdio.h>

int selectionSort(int A[],int N);

int main(void){
  int A[100],N;
  int i;
  int n = 0;

  scanf("%d",&N);
  
  for(i = 0;i < N;i++){
    scanf("%d",&A[i]);
  }

  n = selectionSort(A,N);

  for(i = 0;i < N;i++){
    if(i != 0){
      printf(" ");
    }
    printf("%d",A[i]);
  }
  
  printf("\n%d\n",n);

  return 0;
}



int selectionSort(int A[],int N){
  int i,j;
  int n = 0;
  int temp;
  int minj;

  for(j = 0;j < N-1;j++){
    minj = j;
    for(i = j;i <= N-1;i++){
      if(A[i] < A[minj]){
	minj = i;
      }
    }
    temp = A[j];
    A[j] = A[minj];
    A[minj] = temp;
    if(j != minj){
      n++;
    }
  }
  
  return n;
}




Measured memory_bytes: 2108
#include<iostream>
#include<algorithm>
#define maxn 200005
using namespace std;
typedef long long ll;
int a[maxn];
int main(){
       int n;
       cin>>n;
       for(int i=1;i<=n;i++) cin>>a[i];
       
       ll ans  =0;
       for(int i=2;i<=n;i++){
       	if(a[i] < a[i-1]){
       		ans += a[i-1] -a[i];
       		a[i] = a[i-1];
		   }
	   }
	   cout<<ans<<endl;
}

Measured memory_bytes: 4272
#include<iostream>
#include<map>

using namespace std;

int x[50],y[50];

int main(){
  int i,j;
  int n;
  cin >> n;
  for(i = 0;i < n;i++){
    cin >> x[i] >> y[i];
  }
  map<pair<int,int>,int> m;
  int ans = 0;
  for(i = 0;i < n;i++){
    for(j = 0;j < n;j++){
      if(i==j)continue;
      pair<int,int> p;
      p.first = x[j]-x[i];
      p.second = y[j]-y[i];
      if(m.find(p) == m.end()) m[p] = 1;
      else m[p] += 1;
      ans = (ans>m[p])?ans:m[p];
    }
  }
  cout << n-ans << endl;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;

#define dump(x) cerr << #x << " : " << x << '\n'
#define MOD(x, y) (((y) + (x) % (y)) % (y))

int main(int argc, char* argv[])
{
	int M;
	scanf("%d", &M);
	printf("%d\n", 48 - M);

	return 0;
}


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

int main ()
{
	int r,g,b;  cin>>r>>g>>b;
	 int l=(r*100+g*10+b);
	 if(l%4==0){
		 cout<<"YES"<<endl;
	 }
	 else 
	 cout<<"NO"<<endl;
	 
	


}



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

int main() {
  vector<int> t(3);
  rep(i ,t.size()) cin >> t[i];

  int s = 0;
  rep(i ,t.size()) s += t[i];

  int ans = 1e9;

  rep(i, t.size()) { 
    int a = s - t[i];
    ans = min(ans, a); 
  }

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

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


int main()
{
	int a, b;
	cin >> a >> b;

	string s = to_string(a) + to_string(b);
	int c = stoi(s);

	int p = sqrt(c);

	if (p * p == c)
	{
		println("Yes");
	}
	else
	{
		println("No");
	}
}


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

using ll = long long;

int main() {
	int N, M;
	std::cin >> N >> M;

	std::vector<std::tuple<ll, ll, ll>> state(N);
	for(int i = 0; i < N; i++) {
		std::cin >> std::get<0>(state[i]) >> std::get<1>(state[i]) >> std::get<2>(state[i]);
	}

	ll result = -1;

	// x, y, zが、(+, +, +), (+, +, -), ...にわけて考える
	for(ll a : {-1, 1}) {
		for(ll b : {-1, 1}) {
			for(ll c : {-1, 1}) {
				std::sort(state.begin(), state.end(),
					[=](const std::tuple<ll, ll, ll> &x, const std::tuple<ll, ll, ll> &y) {
					return (std::get<0>(x) * a + std::get<1>(x) * b + std::get<2>(x) * c) > (std::get<0>(y) * a + std::get<1>(y) * b + std::get<2>(y) * c);
				});
				ll sum_x = 0ll, sum_y = 0ll, sum_z = 0ll;
				for(int i = 0; i < M; i++) {
					sum_x += std::get<0>(state[i]);
					sum_y += std::get<1>(state[i]);
					sum_z += std::get<2>(state[i]);
				}
				ll sum = std::abs(sum_x) + std::abs(sum_y) + std::abs(sum_z);
				if(sum > result) {
					result = sum;
				}
			}
		}
	}

	std::cout << result << std::endl;

	return 0;
}

Measured memory_bytes: 256
N=int(input())
xyh=[list(map(int,input().split())) for i in range(N)]
xyh.sort(reverse=True,key=lambda x:x[2])

for i in range(101):
  for j in range(101):
    H=xyh[0][2]+abs(i-xyh[0][0])+abs(j-xyh[0][1])
    cnt=1
    for k in range(1,N):
      if max(H-(abs(i-xyh[k][0])+abs(j-xyh[k][1])),0)==xyh[k][2]:
        cnt+=1
      else:
        break
    if cnt==N:
      print(i,j,H)
      exit()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
//macros
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)

int main(){
    int N;
    cin >> N;
    double sum = 0;
    rep(i,0,N){
        double x;
        string u;
        cin >> x >> u;
        if(u == "JPY") sum += x;
        else sum += 380000.0*x;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;
map <int, int> alt_near_ind;
int main(){
  string S;
  cin >> S;
  stack <pair <pair <int, int>, int> > st;
  int cur_alt = 0;
  for(int i = 0; i < S.size(); i++){
    if(S[i] == '\\'){
      alt_near_ind[cur_alt] = i;
      alt_near_ind[cur_alt - 1] = i + 1;
      cur_alt --;
    } else if(S[i] == '/'){
      cur_alt ++;
      if(alt_near_ind.find(cur_alt) != alt_near_ind.end()){
        int pond_begin = alt_near_ind[cur_alt];
        int pond_end = i + 1;
        if(st.empty()){
          st.push(make_pair(make_pair(pond_begin, pond_end), (2 * (pond_end - pond_begin) - 2) / 2));
        } else {
          int base = 0;
          while(!st.empty()){
            int top_pond_begin = st.top().first.first;
            int top_pond_end = st.top().first.second;
            if(pond_begin < top_pond_begin && top_pond_end < pond_end){
              base += st.top().second;
              st.pop();
            } else {
              break;
            }
          }
          st.push(make_pair(make_pair(pond_begin, pond_end), base + (2 * (pond_end - pond_begin) - 2) / 2));
        }
      }
    }
  }

  int A = 0;
  vector <int> ans;
  while(!st.empty()){
    ans.push_back(st.top().second);
    A += st.top().second;
    //cout << st.top().first.first << " " << st.top().first.second << endl;
    st.pop();
  }
  cout << A << endl;
  reverse(ans.begin(), ans.end());
  if(ans.size() == 0){
    cout << 0 << endl;
    return 0;
  }
  cout << ans.size() << " ";
  for(int i = 0; i < ans.size(); i++){
    if(i != ans.size() - 1){
      cout << ans[i] << " ";
    } else {
      cout << ans[i] << endl;
    }
  }


  return 0;
}



Measured memory_bytes: 4136
#include <bits/stdc++.h>
#define FOR(i,b,e) for (common_type_t<decltype(b),decltype(e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define rep(i,n)   FOR (i, size_t{}, n)
#define ALL(x)     begin (x), end (x)
using namespace std;
using ll = int64_t;
constexpr ll inf = 2e18;

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

  size_t n;
  double t, a;
  cin >> n >> t >> a;

  vector <double> h (n);
  rep (i, n) cin >> h [i];

  transform (ALL (h), begin (h), [&] (auto x) {
    return t - x * 0.006;
  });

  size_t ans = 0;
  double ans_dt = inf;

  rep (i, h.size ())
  {
    auto dt = abs (h [i] - a);
    if (dt < ans_dt)
    {
      ans = i + 1;
      ans_dt = dt;
    }
  }
  cout << ans << endl;
}

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = 0;
    ll l = 0, r = n - 1;
    while (l < r) {
        if (s[l] == 'R') {
            l++;
            continue;
        }
        if (s[r] == 'W') {
            r--;
            continue;
        }
        l++;
        r--;
        ans++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using P = pair<int,int>;

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

    int sz = 1<<n;
    vector<ll> a(sz);
    rep(i,sz) cin >>a[i];

    vector<P> top2(sz);
    rep(i,sz) top2[i] = {i,-1};

    auto UPD = [&](P p, P q, int idx){
        vector<int> v;
        v.pb(q.fi);
        if(q.se != -1) v.pb(q.se);
        v.pb(idx);

        for(int ii:v){
            if(ii==p.fi || ii==p.se) continue;

            if(a[ii]>a[p.fi]){
                p.se = p.fi;
                p.fi = ii;
            }
            else{
                if(p.se==-1 || a[ii]>a[p.se]){
                    p.se = ii;
                }
            }
        }
        return p;
    };

    rep(mask,sz){
        rep(i,n)if(!(mask>>i&1)){
            int nmask = mask|(1<<i);
            top2[nmask] = UPD(top2[nmask], top2[mask], nmask);
        }
        // dbg(top2[mask]);
    }
    // dbg(top2);

    vector<ll> dp(sz);
    dp[0] = a[0];
    for(int i=1; i<sz; ++i){
        dp[i] = a[top2[i].fi] + a[top2[i].se];
    }

    rep(mask,sz){
        rep(i,n)if(!(mask>>i&1)){
            int nmask = mask|(1<<i);
            dp[nmask] = max({dp[nmask], dp[mask]});
        }
    }
    for(int i=1; i<sz; ++i) dp[i] = max(dp[i], dp[i-1]);

    for(int i=1; i<sz; ++i) cout << dp[i] << "\n";
    return 0;
}


Measured memory_bytes: 9216
import sys

lines = sys.stdin.readlines()

dic = {}
chars = "abcdefghijklmnopqrstuvwxyz"

for c in chars:
    dic[c] = 0

for line in lines:
    for c in line:
        c = c.lower()
        if not c in chars:
            continue
        dic[c] += 1

for c in chars:
    print(c, ":", dic[c])


Measured memory_bytes: 5572
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
int main()
{
	long long int i,n,p,x,c=0;
	string s;
	cin>>n;
	cin>>s;
	p=s.length();
	for(i=0;i<n-1;i++)
	{
		if(s[i]-s[i+1]!=0)
			c++;
	}
	cout<<c+1<<endl;
}

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;

int main()
{
    int h, a, m, sec, S;

    cin >> S;

    h = S / 3600;
    a = S - 3600 * h;
    m = a / 60;
    sec = a - 60 * m;

    cout << h << ":" << m << ":" << sec << endl;

    return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
int main(){
  int s,h,d;cin>>s;
  h=s/100;
  d=s%100;
  if((h==0) or (h>12)){
    if((d==0) or (d>12)){
      cout<<"NA"<<endl;
    }else{
      cout<<"YYMM"<<endl;
    }
  }else{
    if((d==0) or (d>12)){
      cout<<"MMYY"<<endl;
    }else{
      cout<<"AMBIGUOUS"<<endl;
    }
  }
}

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

using namespace std;

typedef long long int ll;

int main(){

    ll h, w;

    while (scanf("%lld%lld",&h,&w)&&h&&w){

        char c = '#';

        for (ll i=1; i<=h; i++){
            if (i%2==1){
                for (ll j=1; j<=w; j++){
                    if (j%2==1)
                        cout << '#';
                    else
                        cout << '.';
                }
            }
            else{
                for (ll j=1; j<=w; j++){
                    if (j%2==1)
                        cout << '.';
                    else
                        cout << '#';
                }
            }
            cout << endl;
        }

        cout << endl;

    }

    return 0;

}



Measured memory_bytes: 3156
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A

class UnionFindWithRank
  def initialize(n)
    @parent = Array.new(n, -1)
    @rank = Array.new(n, 0)
    @size = n
  end

  def root(x)
    raise "UnionFindWithRank::IndexError" if x < 0 || @size <= x
    return x if @parent[x] == -1
    @parent[x] = root(@parent[x])
    return @parent[x]
  end

  def same?(x, y)
    return root(x) == root(y)
  end

  def merge(x, y)
    x, y = root(x), root(y)
    return false if x == y
    x, y = y, x if @rank[x] < @rank[y]
    @rank[x] += 1 if @rank[x] == @rank[y]
    @parent[y] = x
    return true
  end
end

n, q = gets.split.map(&:to_i)
uf = UnionFindWithRank.new(n)
ans = []
q.times do |i|
  com, x, y = gets.split.map(&:to_i)
  if com == 0
    uf.merge(x, y)
  else
    ans << (uf.same?(x, y) ? 1 : 0)
  end
end
puts ans



Measured memory_bytes: 7548
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

int main()
{
    char s[5];
    cin >> s;
    if (s[0] == 'a' || s[0] == 'i' || s[0] == 'u' || s[0] == 'e' || s[0] == 'o')
    {
        cout << "vowel" << endl;
    }
    else
        cout << "consonant" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

int main() {
    int N, m, p1, p2, g1, g2;
    auto comp = [](const pair<int, int> &a, const pair<int, int> &b) {return a.second > b.second; };
    std::scanf("%d", &N);
    deque<pair<int, int> > v;
    int res[N+1];
    v.push_back({0, 0});
    for (int i = 1; i <= N; i++) v.push_back({i, 0});
    m = N * (N-1) / 2;
    for (int i = 0; i < m; i++) {
        std::scanf("%d %d %d %d", &p1, &p2, &g1, &g2);
        if (g1 == g2) v[p1].second += 1, v[p2].second += 1;
        else if (g1 > g2) v[p1].second += 3;
        else v[p2].second += 3;
    }
    v.pop_front();
    int prev, curr_pos = 1, prevpos_num = 1;
    std::sort(v.begin(), v.end(), comp);
    prev = v[0].second; res[v[0].first] = 1;
    for (int i = 1; i < v.size(); i++) {
        if (v[i].second != prev) {
            res[v[i].first] = curr_pos = curr_pos + prevpos_num;
            prev = v[i].second;
            prevpos_num = 1;
        }
        else {
            res[v[i].first] = curr_pos;
            prevpos_num++;
        }
    }
    for (int i = 1; i <= N; i++) printf("%d\n", res[i]);
    return 0;
}



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

// same # > N => Ai=Bi always exists
bool judge( vector<int> &CA, vector<int> &CB, int N ){
    for( int i=0; i<=N; ++i ){
        if( CA[i]+CB[i] > N ) return false;
    }
    return true;
}

// CA[i], CB[i]: count (element < i)
// condition of x:
// all i in [1,N];
// for 3 sections (following) S1..S3, (S1^S2)v(S2^S3)v(S3^S1) = null
// S1 = ( CA[i-1], CA[i] ]
// S2 = ( x+CB[i-1], x+CB[i] ]
// S3 = ( N+CA[i-1], N+CA[i] ]
// <=> all i in [1,N]; CA[i] - CB[i-1] <= x <= N + CA[i-1] - CB[i]

int B_shift( vector<int> &CA, vector<int> &CB, int N ){
    vector<int> TA(N+1,0), TB(N+1,0);
    for( int i=1; i<=N; ++i ){
        TA[i] = CA[i] + TA[i-1];
        TB[i] = CB[i] + TB[i-1];
    }
    int xmax=0;
    for( int i=1; i<=N; ++i ){
        xmax = max( xmax, TA[i]-TB[i-1] );
    }
    return xmax;
}

int main(){
    int N;
    cin >> N;
    vector<int> A(N),B(N);
    vector<int> CA(N+1,0), CB(N+1,0); // # of Ai/Bi = n
    rep(i,N){
         cin >> A[i]; // Ai,Bi = 1...N, Ai,Bi are sorted
         ++CA[A[i]];
    }
    rep(i,N){
         cin >> B[i]; // Ai,Bi = 1...N, Ai,Bi are sorted
         ++CB[B[i]];
    }
    bool tf = judge(CA,CB,N);
    if(!tf) cout << "No" << endl;
    if(tf){
        cout << "Yes" << endl;
        // construct B_purmutation by shift B by x;
        int x = B_shift(CA,CB,N);
        rep(i,N){
            if(i) cout << " ";
            cout << B[(i-x+N)%N];
        }
        cout << endl;
    }
    return 0;
}


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

int main(){
  int N, D;
  scanf("%d %d", &N, &D);
  vector<vector<int>> X(N, vector<int>(D));
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j < D ; j++){
      scanf("%d", &X[i][j]);
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++){
    for (int j = i+1; j < N; j++){
      int tmp = 0;
      for (int k = 0; k < D; k++){
        int diff = abs(X[i][k] - X[j][k]);
        tmp += diff * diff;
      }
      bool f = false;
      for (int k = 0; k <= sqrt(tmp); k++){
        if (k * k == tmp){
          f = true;
          break;
        }
      }
      if (f) ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#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 a,b,c;
    cin>>a>>b>>c;
    if(a<b && b<c) printf("Yes\n");
    else printf("No\n");
    return 0;
    
   
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define pt pop_front
#define pk pop_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
template<class T> T count_bit(T p){
  if(typeid(p)==typeid(int))return __builtin_popcount(p);
  else if(typeid(p)==typeid(long))return __builtin_popcountl(p);
  else return __builtin_popcountll(p);
}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                                      ins(T &p){for_each(all(p),in<decltype(p[0])>);}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
inline                                              void out(double p){printf("%.10f\n",p);}
template<class T>inline                             void outs(T p){for_each(all(p),out<decltype(p[0])>);}

inline void solve(void){
  long a,b;
  in(a,b);
  out(max({a+b,a-b,a*b}));
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define REPS(i, n) for (int i = 1; i <= (n); i++)
#define RREPS(i, n) for (int i = (n); i > 0; i--)
#define mp make_pair
#define pb(a) push_back(a)
typedef long long ll;
int main() {
  int X;
  cin >> X;
  int ans = 1;
  for (int i = 2; i * i <= X; i++) {
    int num = i;
    while (num * i <= X) num *= i;
    ans = max(num, ans);
  }
  cout << ans << endl;
  return 0;
}


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

int n;
int m;
int p;
int d;
int field[100][100];

int GetGoalPos(int s) {
  for (int i=0; i<d; i++) {
    if (s < n-1 && field[i][s]) ++s;
    else if (s-1 >= 0 && field[i][s-1]) --s;
  }

  return s;
}

int solve() {
  scanf("%d", &n);
  if (n == 0) return -1;

  scanf("%d", &m);
  scanf("%d", &p);
  scanf("%d", &d);
  for (int i=0; i<d; i++) {
    for (int j=0; j<n-1; j++) {
      scanf("%1d", &field[i][j]);
    }
  }

  --m;
  --p;
  if (GetGoalPos(m) == p) {
    puts("0");
    return 0;
  }

  for (int i=0; i<d; i++) {
    for (int j=0; j<n-1; j++) {
      if (field[i][j]) continue;
      if (j-1 >= 0 && field[i][j-1]) continue;
      if (j+1 < n-1 && field[i][j+1]) continue;

      field[i][j] = 1;
      if (GetGoalPos(m) == p) {
        printf("%d %d\n", i+1, j+1);
        return 0;
      }
      field[i][j] = 0;
    }
  }

  puts("1");
}

int main() {
  while (1) {
    if (solve() == -1) return 0;
  }
}

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

int main() {
	int a[3];
	for(int i=0;i<3;i++)
	cin>>a[i];
	sort(a,a+3);
	if(a[0]==a[1] && a[1]!=a[2])
	cout<<"Yes";
	else if(a[0]!=a[1] && a[1]==a[2])
	cout<<"Yes";
	else
	cout<<"No";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int a = N / 100;
        N = N - a * 100;
        int b = N / 10;
        N = N - b * 10;
        int c = N;

        if(a==7 || b==7 ||c==7){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35776
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cmath>
/*
#include <map>
#include <functional>
#include <set>
#include <iterator>
#include <queue>
*/
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;

/* Union-find
int par[100010];
int trank[100010];

void init(int n) {
   for (int i=0;i<n;i++) {
      par[i] = i;
      trank[i] = 0;
   }
}
int find(int x) {
   if (par[x] == x) {
      return x;
   } else {
      return par[x] = find(par[x]);
   }
}
void unite(int x, int y) {
   x = find(x);
   y = find(y);
   if (x == y) return;
   if (trank[x] < trank[y]) {
      par[x] = y;
   } else {
      par[y] = x;
      if (trank[x] == trank[y]) trank[x]++;
   }
}
bool same(int x, int y) {
   return find(x) == find(y);
}
*/

int N;
int p[20];

int main() {
   cin >> N;
   int maxval = 0;
   int sum = 0;
   for (int i=1;i<=N;i++) {
      cin >> p[i];
      sum += p[i];
      maxval = max(maxval, p[i]);
   }
   cout << sum - maxval/2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define pb push_back
#define fi first
#define se second


int main(){
    ll i,j;
    ll n;
    cin>>n;
    string a,b,c;
    cin>>a>>b>>c;

    ll ans=0;
    for(i=0;i<n;i++){
        if(a[i]==b[i]&&b[i]==c[i]) ans+=0;
        else if (a[i]!=b[i]&&b[i]!=c[i]&&c[i]!=a[i]) ans+=2;
        else ans+=1;
    }
    cout<<ans<<endl;
    return 0;
    
}


Measured memory_bytes: 256
#include<stdio.h>
long gcd(long a, long b){
	if(a == 0){
		return b;
	}
	else if(b == 0){
		return a;
	}
	else if(a<b){
		return gcd(a, b%a);
	}
	else if(a>b){
		return gcd(b, a%b);
	}
	else{
		return a;
	}
}

int main(void){
	long a, b;
	long x = 0;
	scanf("%ld", &a);
	scanf("%ld", &b);
	if(a == 0 || b == 0){
		x = 0;
	}
	else{
		x = a*b/gcd(a,b);
	}
	printf("%ld\n", x);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using namespace std;
using std::cout;

bool linear_search(const vector<int> &vi, int key) {
    int last = vi.size() - 1;
    int i = 0;
    while (vi.at(i) != key) {
        i++;
    }
    return i != last;
}

int main() {
    fastIO;

    int n;
    cin >> n;
    vector<int> S(n);
    rep(i, n) cin >> S.at(i);

    int q;
    cin >> q;

    int cnt = 0;
    rep(i, q) {
        int key;
        cin >> key;
        S.push_back(key);
        if (linear_search(S, key)) {
            cnt++;
        }
    }
    cout << cnt << endl;
}




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

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

    auto rec = [&](auto&& rec, int D, string S)->void{
        if(S.size() == D){
            K--;
            if(K == 0){
                cout << S << endl;
                exit(0);
            }
            return;
        }
        for(char c='0'; c<='9'; c++){
            if(S == "" && c == '0') continue;
            if(S.size() && abs(S.back()-c) > 1) continue;
            string S2 = S;
            S2.push_back(c);
            rec(rec, D, S2);
        }
    };

    for(int d=1; d<=10; d++) rec(rec, d, "");
    return 0;
}


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


const long long MAXVAL = (long long) 1e18 + 1;
//const long long MOD = 1000000007;
const long long MOD = 998244353ll;
const int INF = 1000000000 + 1;

long long poww(int x, long long pow) {
  if (pow == 0ll ) return 1;
  if (pow == 1ll) return x % MOD;
  long long ans = poww(x, pow >> 1) % MOD;
  ans = (ans * ans) % MOD;
  if ((pow & 1)) {
    ans = (ans * x ) % MOD;
  }
  return ans % MOD;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int q = 1;
  //cin >> q;

  while (q-- >0) {
    int n, s;
    cin >> n >> s;
    int a[n];
    for (int i  =0 ; i < n; ++i) cin >> a[i];
    int dp[n + 1][s + 1];
    for (int i = 0; i < s + 1; ++i) dp[0][i] = 0;
    dp[0][0] = 1;
    for (int k = 1; k <= n; ++k) {
      for (int i = s; i >= 0; --i) {
        dp[k][i] = ( 2 * dp[k - 1][i]) % MOD;
        if (i >= a[k - 1]) {
          dp[k][i] = (dp[k][i] + dp[k - 1][i - a[k - 1]]) % MOD;
        }
      }
    }
    cout << dp[n][s] << endl;
  }
  return 0;
}



Measured memory_bytes: 38832
#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;
  vector<pair<int,int> > a(N);
  REP(i,N) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(a.begin(), a.end());

  ll ans = 0;

  set<int> s;
  s.emplace(-1);
  s.emplace(N);

//  for ( auto x: a)
//    cout << x.first << " " << x.second << endl;

  REP(i,N) {
    int idx = a[i].second;
    auto it = s.lower_bound(idx);
    ll r = *it;
    it--;
    ll l = *it;
    ans += (ll)((idx-l) * (r-idx)) * (ll)a[i].first;
//    cout << idx << ":" << l << " - " << r << " * " << a[i].first << " => " << (ll)((idx-l) * (r-idx)) * (ll)a[i].first << endl;
    s.emplace(idx);
  }
  cout << ans << endl;

}




Measured memory_bytes: 11136
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<memory.h>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int color[9];

int main(){
  int n;
  cin >> n;
  vector<int> v;
  int a[n];
  int cnt=0;
  rep(i,n){
    cin >> a[i];
    if(a[i]>=3200)cnt++;
    for(int j=1;j<=8;j++){
      if(a[i]<400*j){
        color[j]++;
        break;
      }
    }
  }
  int base=0;
  for(int i=1;i<=8;i++){
    if(color[i]>0)base++;
  }
  cout << max(1,base) << ' ' << base+cnt << endl;
return 0;}

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

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define LIMIT(d_in, d_min, d_max) max(d_min, min(d_max, d_in))
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	string S, T;
	cin >> S >> T;

	for (int i = 0; i < S.size(); i++)
	{
		bool flag = true;
		for (int j = 0; j < S.size(); j++)
		{
			if (S[j] != T[(i + j) % S.size()])
			{
				flag = false;
			}
		}
		if (flag)
		{
			cout << "Yes" << endl;
			return;
		}
	}
	cout << "No" << endl;
	return;
}

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

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;

int solve(vector< vector< pair<int, int> > > &G, int C){
  int n = G.size();
  vector< vector<int> > D(n, vector<int>(n, INF));
  priority_queue< pair<int, int> > wait;
  wait.emplace(0, 0);
  D[0][0] = 0;
  while(!wait.empty()){
    int v = wait.top().second/n, c = wait.top().second%n, d = -wait.top().first;
    wait.pop();
    if(D[v][c] < d || v == n-1) continue;
    for(int i = 0; i < G[v].size(); ++i){
      int d_ = d + G[v][i].first, v_ = G[v][i].second;
      if(d_ <= C && d_ < D[v_][c]){
        D[v_][c] = d_;
        wait.emplace(-d_, v_*n + c);
      }
      if(c < n - 1 && d < D[v_][c+1]){
        D[v_][c+1] = d;
        wait.emplace(-d, v_*n + c+1);
      }
    }
  }
  int ans = n;
  for(int i = 0; i < n; ++i){
    if(D[n-1][i] <= C){
      ans = i;
      break;
    }
  }
  return ans;
}

int main(){
  int n, m, c;
  while(cin >> n >> m >> c, n){
    int f, t, d;
    vector< vector< pair<int,int> > > G(n);
    for(int i = 0; i < m; ++i){
      cin >> f >> t >> d;
      --f;--t;
      G[f].emplace_back(d, t);
    }
    cout << solve(G, c) << endl;
  }
  return 0;
}



Measured memory_bytes: 3264
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    std::string s;
    std::cin >> s;
    for (char& c: s) {
        if (c=='?') c = 'D';
    }
    std::cout << s << '\n';
}


Measured memory_bytes: 3800
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int K;
    long long t;
    cin>>K;
    t = 7;
    for(long i=0;i<K;i++){
        if(t%K==0){

            cout<<i+1<<endl;
            return 0;
        }
        t = (t*10+7)%K;
    }
    cout<<-1<<endl;
    return 0;

}

Measured memory_bytes: 3632
#include<iostream>

using namespace std;

int main() {
	char alpha;

	cin >> alpha;
	if (alpha >= 'A' && alpha <= 'Z') {
		cout << 'A' << endl;
	}
	else if (alpha >= 'a' && alpha <= 'z') {
		cout << 'a' << endl;
	}

	return 0;
}

Measured memory_bytes: 3496
use proconio::input;

fn main() {
    input!(n: usize, mut a: [i32; n]);
    let c = a
        .iter()
        .enumerate()
        .max_by_key(|(_, &x)| x.abs())
        .unwrap()
        .0;
    let ac = a[c];
    let mut ans = vec![];
    let mut mv = |i, j| {
        ans.push((i, j));
        a[j] += a[i];
    };
    for i in (0..n).filter(|&i| i != c) {
        mv(c, i);
    }
    if 0 <= ac {
        for i in 0..n - 1 {
            mv(i, i + 1);
        }
    } else {
        for i in (0..n - 1).rev() {
            mv(i + 1, i);
        }
    }
    println!("{}", ans.len());
    for (x, y) in ans {
        println!("{} {}", x + 1, y + 1);
    }
}


Measured memory_bytes: 2184
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int mxn=2e5+1;

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

  int t=1;
//  cin>>t;
  int tt=1;
  while(t--){
      int n,l,i;
      cin>>n>>l;
      int tot=(n*(n-1))/2;
      tot+=n*l;
      int ans=1e9;
      int res;
      fr(i,0,n)
      {
        if(ans>abs(tot-(tot-l-i)))
        {
          res=tot-l-i;
          ans=abs(tot-(tot-l-i));
        }
      }
   // cout<<"Case #"<<tt<<": ";
   // tt++;
      cout<<res;
    }
  return 0;
}



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

using namespace std;

typedef long long int ll;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

const ll L = 20;

ll adj[L][L];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    ll N, M;
    cin >> N >> M;

    for(ll i=0; i<M; i++)
    {
        ll u, v;
        cin >> u >> v;
        adj[u][v]=1;
        adj[v][u]=1;
    }

    vector <ll> permute;

    ll fact = 1;

    for(ll i=1; i<=N; i++)
    {
        permute.pb(i);
        fact*=i;
    }

    ll ans = 0;

    for(ll i=1; i<=fact; i++)
    {
        if(permute[0]==1)
        {   
            ll flag = 0;
            for(ll j=1; j<sz(permute); j++)
            {
                if(adj[permute[j-1]][permute[j]]==0)
                {
                    flag = 1;
                    break;
                }   
            }

            if(!flag)
            {
                ans++;
            }

            next_permutation(all(permute));
        }
    }

    cout << ans << endl;

    return 0;
}

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


int GetDigit(int num){
    return log10(num) + 1;
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<ll>> PY(N + 1);
  vector<pair<int, ll>> V(M);
  for (int i = 0; i < M; ++i) {
    int P;
    ll Y;
    cin >> P >> Y;
    PY.at(P).push_back(Y);
    V[i].first = P;
    V[i].second = Y;
  }
  
  for (int i = 1; i <= N; ++i) {
    sort(PY.at(i).begin(), PY.at(i).end());
  }
  
  for (int i = 0; i < M; ++i) {
    auto itr = lower_bound(PY.at(V.at(i).first).begin(), PY.at(V.at(i).first).end(), V.at(i).second);
    int dif = itr - PY.at(V.at(i).first).begin() + 1;
    int d1 = GetDigit(V.at(i).first);
    int d2= GetDigit(dif);
    string m1 = "", m2 = "";
    m1.append("0000000", 6 - d1);
    m2.append("0000000", 6 - d2);
    cout << m1 << V.at(i).first << m2 << dif << endl;
  }
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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;}

int main () {
  int n, k, q;
  cin >> n >> k >> q;
  vi p(n,k-q);
  rep(i,q) {
    int a;
    cin >> a;
    --a;
    p[a]++;
  }
  rep(i,n) {
    puts(p[i]<=0?"No":"Yes");
  }
}

Measured memory_bytes: 1024
A, B = map(int, input().split())
S = list(input())
ans = "No"

if S[A] == "-":
    flag = True
    for i in range(len(S)):
        if i == A:
            continue
        if not S[i].isdecimal():
            flag = False
            break
    if flag:
        ans = "Yes"

print(ans)


Measured memory_bytes: 2940
import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)

Measured memory_bytes: 12812