2014
02-12

# Let the Balloon Rise II

Contest will be end at 17:00! How excited it is to see balloons floating around.

I knew you had solved the HDOJ 1004 Let the Balloon Rise already, so please settle the another version quickly. I have a lot of balloons and each has a color and I give each of them a number, same color has the same number. For example, red balloon is No.1, pink is No.2, black is No.3 . etc. I also have many rooms to store all the balloons.
There are some rules :
1. Every room stores several balloons but no two have the same color.
2. Collect all the balloons, we can find each color has even number of times of balloons except one.

Your task is to find which is the odd color and calculate its number of times.

Input file consists from multiple data sets separated by one or more empty lines.
Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.
Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of No.X, X+Z, X+2*Z, X+3*Z, …, X+K*Z, …(while (X+K*Z)<=Y). This line represents that in this room there exists (K+1) balloons whose No. is No.X, No.X+Z, No.X+2*Z, No.X+3*Z, …, No.X+K*Z, …etc.

Input file consists from multiple data sets separated by one or more empty lines.
Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.
Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of No.X, X+Z, X+2*Z, X+3*Z, …, X+K*Z, …(while (X+K*Z)<=Y). This line represents that in this room there exists (K+1) balloons whose No. is No.X, No.X+Z, No.X+2*Z, No.X+3*Z, …, No.X+K*Z, …etc.

1 10 1
1 10 1

1 5 1
6 10 1
1 10 1
4 4 1

1 5 1
2 5 1
2 5 1
2 5 1

None.
4 3
1 1

【题意】

【思路】

【代码】

#include <iostream>
using namespace std;

const int maxn = 50000;

__int64 a[maxn+5], b[maxn+5], c[maxn+5];
__int64 d[maxn+5];
char str[maxn+5];

inline __int64 max(__int64 a, __int64 b)
{
if (a>=b) return a;
else return b;
}

inline __int64 min(__int64 a, __int64 b)
{
if (a<=b) return a;
else return b;
}

inline __int64 get(__int64 x, __int64 y, __int64 z)
{
return (y-x)/z+1;
}

int solve(__int64 mid, int n)
{
int i;
int al = 0, ar = 0;
int t, ct;
for (i=0; i<n; i++)
{
ct = 0;
if (mid>=a[i])
{
t = min(mid, b[i]);
ct += get(a[i], t, c[i]);
}
al += ct;
ar += d[i] - ct;
}
if (al%2==1) return 1;
else if (ar%2==1) return -1;
else return 0;
}

int main()
{
int i;
int n;
__int64 low, high, mid;
__int64 ans, act;
bool flag = true;
while(flag)
{
i = 0;
flag = false;
while(gets(str) && (flag=true))
{
if (str[0]>='0' && str[0]<='9') break;
flag = false;
}
if (!flag) break;
flag = false;
do
{
sscanf(str, "%d %d %d", &a[i], &b[i], &c[i]);
i++;
flag = false;
}while(gets(str) && (flag=true) && str[0]>='0' && str[0]<='9');
n = i;
for (i=0; i<n; i++) d[i] = get(a[i], b[i], c[i]);
low = (__int64)INT_MAX*2;
high = (__int64)INT_MIN;
for (i=0; i<n; i++)
{
low = min(low, a[i]);
high = max(high, (d[i]-1)*c[i]+a[i]);
}
low--;
high++;
bool f = false;
while(low<=high)
{
mid = (low+high)>>1;
switch(solve(mid, n))
{
case -1:
low = mid + 1;
break;
case 0:
f = true;
break;
case 1:
ans = mid;
high = mid-1;
break;
}
if (f) break;
}
if (f) printf("None.\n");
else
{
act = 0;
for (i=0; i<n; i++)
{
if (ans>=a[i] && ans<=b[i] && (ans-a[i])%c[i]==0)
act++;
}
printf("%I64d %I64d\n", ans, act);
}
}
return 0;
}