×

# SMRSTR - Editorial

Author: Misha Chorniy
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

CAKEWALK

None

# PROBLEM:

You're given array $D$ of size $N$ and $Q$ queries $X$. In each query you have to compute the result of the program

read X
for i = 1..N:
X = floor(X / D[i])
print X


# QUICK EXPLANATION:

You should consider only $O(\log X)$ terms such that $D_i\neq 1$.

# EXPLANATION:

You may keep keep first $\min(2\cdot\log_2 X, N)$ terms of $D$ which aren't equal one. If there are more non-one terms than $X$ wiil definitely be equal zero at the end of procedure.

# ALTERNATIVE SOLUTION:

You can keep product $P$ of non-one terms of $D$ instead of keeping this terms and divide $X$ by $P$. But you should check then that you output zero if there are too much such terms.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

# RELATED PROBLEMS:

This question is marked "community wiki".

4★melfice
811737
accept rate: 0%

19.7k350498541

 1 Can anyone explain how alternative solution given in editorial is correct. Also if ceil is considered (instead of floor) in the question, is the alternative solution (divide the given number with the product of array elements and then take ceil) still works? answered 29 Dec '17, 15:05 5★kvsk 53●1●4 accept rate: 0% Can someone explain this please? (24 Nov '18, 01:03) 2 [[x/a]/b]=[x/(a*b)], where [y] means the greatest integer not greater than y. Prove it ;) So, [[[x/d1]/d2]/...]/dn] = [[[x/(d1d2)]/d3]/...]/dn] = ... [x/(d1d2....*dN)], the only one problem is that d1 * d2 * d3 * ... * dn can not fits in long long, so you need to take min(d1 * d2 * ... * dn, 1e18), but you need accurately do that. long long INF = (long long)1e18 + 1; if (curMul * di > INF) curMul = INF; // curMul * di can overflow, cause curMul < 1e18, di < 1e9. if (curMul > INF / di) curMul = INF; else curMul *= di; //OK Also, you can try to use __int128 (24 Nov '18, 18:46) mgch6★ Thank you! (25 Nov '18, 00:16)
 0 not clear, mine code shows nzec error answered 27 Nov '17, 18:57 1 accept rate: 0% It is unclear from what you said. Please provide a link to your code. And also check if you are dividing by zero in any case. (27 Nov '17, 19:37)
 0  #include using namespace std; #define ll long long int main() { int t; cin>>t; while(t--) { int n,q; cin>>n>>q; vectora; for(int i=0;i>x; if(x>1) a.push_back(x); } int qr[q]; for(int i=0;i>qr[i]; for(int i=0;i0) { temp/=a[idx]; idx++; } cout<

Hey GUYS, PLz Give it a look , when i was doing this question i came to know an interesting fact that if i was using floor func then it's giving TLE for subtask 2 , and if I was using int then it's giving correct ans NOTE: always use int type only. SOLN :

* Language: C++14

# define ll long long int

using namespace std;

int main() { ll t;

cin>>t;
while(t--)
{
ll i,n,q,p=1,z=0,flag=0;
cin>>n>>q;
ll d[n+1]={0};
for(i=0;i<n;i++) cin>>d[i];
for(i=0;i<n;i++)
{
p*=d[i];
if(p>1000000000)
{    flag=1;
break;
}
}
if(flag==1)
{
while(q--)
{
cin>>z;
cout<<"0"<<" ";
}
}
else
{
while(q--)
{
cin>>z;
cout<<z/p<<" ";
}
}
cout<<endl;
}
return 0;


}

11
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,482
×1,609
×98
×28

question asked: 25 Nov '17, 08:28

question was seen: 3,168 times

last updated: 25 Nov '18, 00:16