oj.uz

Submission #28164

# Submission time Handle Problem Language Result Execution time Memory
28164 2017-07-15T13:57:56 Z aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(#1199, suhgyuho_william) The Ethereum and The Bitcoin (FXCUP2_ethereum) C++14
1 / 1
 0 ms 2164 KB 
#include "ethereum.h"
#include <bits/stdc++.h>

#define pii pair<int,int>
#define pb push_back

using namespace std;

static int a,b,x,y;
static excinfo kinf;

static void get(int value){
	excinfo tmp = Exchange(value);
	x = tmp.BTC; y = tmp.ETH;
}
static long long gcd(long long x,long long y){
	return x ? gcd(y%x,x) : y;
}

static excinfo tmpextgcd(long long a, long long b){
	excinfo res, im;
	// a * BTC + b * ETH = gcd
	if(!b){ // a = gcd
		res.BTC = 1, res.ETH = 0;
		return res;
	}
	im = tmpextgcd(b, a%b); long long q = a/b;
	// a = bq + r : (bq+r) BTC + b ETH = b(q BTC + ETH) + r BTC = gcd
	res.BTC = im.ETH; res.ETH = im.BTC - q * res.BTC;
	return res;
}

static excinfo tmpExchange(long long K,long long B,long long E){
	excinfo A; A.BTC = kinf.BTC * K; A.ETH = kinf.ETH * K;
	if(A.BTC < 0){
		long long t = (-A.BTC) / E;
		A.BTC += t*E, A.ETH -= t*B;
		if(A.BTC < 0) A.BTC += E, A.ETH -= B;
	}
	if(A.ETH < 0){
		long long t = (-A.ETH) / B;
		A.BTC -= t*E, A.ETH += t*B;
		if(A.ETH < 0) A.BTC -= E, A.ETH += B;
	}
	if(A.BTC < 0) A.BTC = A.ETH = -1;
	return A;
}


excinfo GetExchangePrice() {
	int value,cnt = 5;
	vector<pii> tmp;

	while(cnt-- && tmp.size() != 1){
		if(cnt == 4){
			value = 100000000;
		}else{
			value--;
		}
		get(value);
		if(tmp.size() == 0 && x == -1){

		}else if(tmp.size() == 0){
			for(int i=2; i<=10000; i++){
				if(i*x > value) break;
				if((value-i*x)%y != 0) continue;
				int j = (value-i*x)/y;
				if(gcd(i,j) != 1 || j > 10000) continue;
				tmp.pb({i,j});
			}
		}else{
			vector<pii> tmp2;
			if(x != -1){
				for(auto &i : tmp){
					if((long long)i.first*x+(long long)i.second*y == value){
						tmp2.pb({i.first,i.second});
					}
				}
			}else{
				for(auto &i : tmp){
					if(tmpExchange(value,i.first,i.second).BTC != -1) continue;
					tmp2.pb({i.first,i.second});
				}
			}
			swap(tmp2,tmp);
		}
	}
	a = tmp[0].first; b = tmp[0].second;

	excinfo ans;
	ans.BTC = a; ans.ETH = b;

	return ans;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 0 ms 2024 KB Output is correct
13 Correct 0 ms 2024 KB Output is correct
14 Correct 0 ms 2024 KB Output is correct
15 Correct 0 ms 2024 KB Output is correct
16 Correct 0 ms 2024 KB Output is correct
17 Correct 0 ms 2024 KB Output is correct
18 Correct 0 ms 2024 KB Output is correct
19 Correct 0 ms 2024 KB Output is correct
20 Correct 0 ms 2164 KB Output is correct