agile mesa
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;
int log2ll(long long int val) {
int ans = 0;
long long int det = val;
while (det > 1) {
det /= 2;
ans++;
}
return ans;
}
int main() {
vector<long long int> twon_minus_one(64, 0);
for (int i = 1; i < 64; i++) {
twon_minus_one[i] = twon_minus_one[i - 1] * 2 + 1; //two avoid overflow
}
long long int numerator, denominator;
cin >> numerator >> denominator;
bool found = false;
for (int i = 0; i < 64; i++) {
if (twon_minus_one[i] % denominator == 0) { //Here's the issue. this conditional statement zeroes out all the values. Why?
found = true;
numerator *= (twon_minus_one[i] / denominator);
denominator = twon_minus_one[i];
break;
}
}
if (!found) {
cout << -1;
return 0;
}
int length;
if (denominator == LLONG_MAX) {
length = 63;
}
else {
length = log2ll(denominator + 1);
}
if (length > 60) {
cout << -1;
return 0;
}
long long int det = numerator;
string ans(length, '-');
for (int i = length - 1; i >= 0; i--) {
if (det % 2 == 1) {
ans[i] = '*';
}
det /= 2;
}
if (det != 0) {
cout << -1;
}
else {
cout << ans;
}
return 0;
}
Here's the objective:
Problem
Youngshik and Minshik are planning to share a cake. First, Youngshik eats half of the cake, and then Minshik eats the remaining half. They continue eating half of what is left in turns. If they keep doing this infinitely, they will eventually eat the whole cake. Here's a table illustrating how it works:
Copy
Youngshik Minshik
1/2 1/4
1/8 1/16
1/32 1/64
1/128 1/256
... ...
As shown, Youngshik always eats twice as much as Minshik, so he will eat 2/3 of the cake while Minshik eats 1/3.
To make eating the cake more fun, they created various patterns. Depending on the pattern, the amount of cake that Youngshik eats will change. For example, if the pattern is "Youngshik, Minshik, Youngshik," they eat as follows:
Copy
Youngshik Minshik Youngshik
1/2 1/4 1/8
1/16 1/32 1/64
1/128 1/256 1/512
In this case, Youngshik eats 5/7 of the cake.
Your task is to write a program to output the eating pattern, given the fraction of cake that Youngshik eats.
Input
The first line contains two integers, a and b, representing the fraction a/b that Youngshik eats.
Output
On the first line, print the eating pattern. Use * for Youngshik and - for Minshik. If no pattern with length 60 or less is found, print -1. If there are multiple possible patterns, print the shortest one.
Constraints
0≤a≤b≤2^63−1
a and b are coprime.
Time to enlist the expert coders!
(Source: Baekjoon Online Judge No. 1341)
(Used Microsoft CoPilot for translation due to my laziness.)
https://www.acmicpc.net/problem/1341
coral cave
idle patio
