D - Toll Road
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87493#problem/D
Description
Exactly N years ago, a new highway between two major cities was built. The highway runs from west to east. It was planned as one big segment of a toll road. However, new highway was not popular: drivers still used free roads.
After analyzing the situation, the administration decided to perform a marketing trick to increase the popularity of the new highway.
The highway was divided into segments. Initially, there was only one segment. Every odd year, each of the existing segments was divided into two new segments with lengths divided as X: Y. This means that the length of the western segment relates to the length of the eastern segment as X relates to Y. Every even year, each of the existing segments was also divided into two new segments, but this time, the ratio was Y: X. After each division, the first of the two resulting segments was declared a free road and the second one a toll road. Each year, the segments are numbered from 1 from west to east. For simplicity, X and Y are positive integers which sum up to exactly 100.
As a result, the administration was able to significantly increase the income: the drivers started to drive on free segments and did not dare to turn away at the sight of the next toll segment. But after N years, the plan of the highway became so complex that it is now hard to calculate the exact lengths of the segments.
Knowing the total length of the highway P, one can calculate the length Lk of the segment with number k using the formula
for some integers Ak and Bk. Here, Ak is the number of years in which, during the division, this segment was in the part proportional toX, and Bk is the number of years when it was in the part proportional to Y.
You need to answer to the queries containing numbers Ki of segments. To answer each query, you must print the values of Aki and Bkifor the corresponding segment.
Input
The first line of the input contains three integers: the number of years N (1 ≤ N ≤ 1018) that have elapsed since the highway was built, followed by the percentages X and Y (1 ≤ X, Y ≤ 99, X + Y = 100) used each year to divide the segments.
The second line contains one integer: the number of queries Q (1 ≤ Q ≤ 104).
The following Q lines contain queries. Each query is an integer Ki (1 ≤ Ki ≤ 1018), the number of some segment. It is guaranteed that the segment with such number exists.
Output
Sample Input
3 25 75 4
1
3
5
8
Sample Output
2 1
3 0
1 2
1 2
HINT
题意
前面全是废话
给你一个二叉树，第i层，第k个节点，如果(i+k)%2==0，那么这个节点就是A，否则节点就是B
Q次询问，每次问你第n层的第x节点，如果一直往上面爬，爬到第1层第1个节点，一共经历了几次A，几次B
题解：
首先O(层数)的做法很明显是不可行的，应该要O(log)的，很容易发现，往上面爬和在同层次往左边爬是一样的
所以我们log爬到同层的第一个，然后再O（1）计算就好了
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <stack> #include <map> #include <set> #include <queue> #include <iomanip> #include <string> #include <ctime> #include <list> #include <bitset> typedef unsigned char byte; #define pb push_back #define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0) #define local freopen("in.txt","r",stdin) #define pi acos(-1) using namespace std; int C(long long x,long long y) { if(x%2==1) { if(y%2==1) return 1; else return 2; } else { if(y%2==1) return 2; else return 1; } } int main() { long long n; long x1,x2,q; cin>>n>>x1>>x2>>q; for(int i=0;i<q;i++) { long long t1 = n; long long t2; scanf("%lld",&t2); long long ans1=0,ans2=0; while(1) { if(C(t1,t2)==1) ans1++; else ans2++; if(t2==1LL||t1==1LL) break; t2=(t2+1LL)/2LL; t1--; } t1--; if(t1!=0) { ans1+=t1/2LL; ans2+=t1/2LL; if(t1%2LL==1LL) { if(C(t1,t2)==1) ans1++; else ans2++; } } printf("%lld %lld ",ans1,ans2); } }