Waffle Choppers
Problem
The diners at the Infinite House of Pancakes have gotten tired of circular pancakes, so the chefs are about to offer a new menu option: waffles! As a publicity stunt, they have made one large waffle that is a grid of square cells with R rows and C columns. Each cell of the waffle is either empty, or contains a single chocolate chip.
Now it is time for the chefs to divide up the waffle among their hungry diners. A horizontal cut runs along the entire gridline between two of the rows; a vertical cut runs along the entire gridline between two of the columns. For efficiency's sake, one chef will make exactly H different horizontal cuts and another chef will make exactly V different vertical cuts. This will conveniently create one piece for each of the (H + 1) × (V + 1) diners. The pieces will not necessarily all be of equal sizes, but that is fine; market research has shown that the diners do not care about that.
What the diners do care about is the number of chocolate chips they get, so each piece must have exactly the same number of chocolate chips. Can you determine whether the chefs can accomplish this goal using the given numbers of horizontal and vertical cuts?
Input
The first line of the input gives the number of test cases, T; T test cases follow. Each begins with one line containing four integers R, C, H, and V: the number of rows and columns in the waffle, and the exact numbers of horizontal and vertical cuts that the chefs must make. Then, there are R more lines of C characters each; the j-th character in the i-th of these lines represents the cell in the i-th row and the j-th column of the waffle. Each character is either
@
, which means the cell has a chocolate chip, or
.
, which means the cell is empty.
Output
For each test case, output one line containing
Case #x: y
, where
x
is the test case number (starting from 1) and
y
is
POSSIBLE
if the chefs can accomplish the goal as described above, or
IMPOSSIBLE
if they cannot.
Limits
1 ≤ T ≤ 100.
Time limit: 6 seconds per test set.
Memory limit: 1GB.
Test set 1 (Visible)
2 ≤ R ≤ 10.
2 ≤ C ≤ 10.
H = 1.
V = 1.
Test set 2 (Hidden)
2 ≤ R ≤ 100.
2 ≤ C ≤ 100.
1 ≤ H < R.
1 ≤ V < C.
Sample
| Input | Output |
| |
Note that the last two sample cases would not appear in test set 1.
In Sample Case #1, one possible strategy is to make the horizontal cut between the second and third rows from the top, and make the vertical cut between the fourth and fifth columns from the left. That creates the following pieces, each of which has exactly two chocolate chips:
[email protected]@. [email protected]
.... [email protected]
@[email protected] @@
In Sample Case #2, no matter where you make the horizontal cut and the vertical cut, you will create pieces with unequal numbers of chocolate chips, so the case is impossible.
In Sample Case #3, there are no chocolate chips in the waffle. Any cutting strategy creates pieces which have the same number of chocolate chips (zero), so the diners are happy... but maybe not as happy as they would have been if they had gotten chocolate chips!
In Sample Case #4, just as in Sample Case #2, you cannot succeed regardless of where you make your horizontal cut and your vertical cut.
In Sample Case #5, the chefs can make the only two possible horizontal cuts, and make the two vertical cuts to the right of the first and third columns.
Although Sample Case #6 would be possible for other numbers of horizontal and vertical cuts, remember that you must use exactly H horizontal cuts and exactly V vertical cuts. No matter where you make your one horizontal cut and two vertical cuts, you cannot succeed.
题意：一块饼干，R行C列，上面有若干巧克力点，现在横切H刀，竖切V刀，问能否有一种切法，使得每块的巧克力点一样多。
思路：如果不是(H+1)*(V+1)倍数，那么肯定是否，否则横着竖着分开来看，横着切每一份是所有巧克力点的1/(H+1)，竖着切是所有巧克力点的1/(V+1)，这样我们就可以确定一种切法（实际上不同切法不影响结果，只要保证上面两条），然后判断切出来每块里面的点的个数是不是正确。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
int sum[105][105];
char a[105][105];
int V[105];
int H[105];
int main()
{
int r,c,h,v;
int t;
scanf("%d",&t);
for(int tt=1;tt<=t;tt++)
{
memset(sum,0,sizeof(sum));
scanf("%d%d%d%d",&r,&c,&h,&v);
for(int i=0;i<r;i++)
{
scanf("%s",a[i]);
}
int cnt=0;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+(a[i-1][j-1]=='@'?1:0);
cnt+=a[i-1][j-1]=='@'?1:0;
}
}
if(cnt%((v+1)*(h+1)))
{
printf("Case #%d: IMPOSSIBLE\n",tt);
continue;
}
int cnt1=cnt/(v+1);
int p=0;
for(int i=0;i<v;i++)
{
for(;p<c;p++)
{
if(sum[r][p]==cnt1*(i+1))
{
V[i]=p;
break;
}
}
}
V[v]=c;
int cnt2=cnt/(h+1);
p=0;
for(int i=0;i<h;i++)
{
for(;p<r;p++)
{
if(sum[p][c]==cnt2*(i+1))
{
H[i]=p;
break;
}
}
}
H[h]=r;
bool flag=true;
int cnt3=cnt2/(v+1);
for(int i=0;i<=h;i++)
{
for(int j=0;j<=v;j++)
{
if(sum[H[i]][V[j]]!=cnt3*(i+1)*(j+1))
{
flag=false;
break;
}
}
}
if(!flag)
{
printf("Case #%d: IMPOSSIBLE\n",tt);
}
else
{
printf("Case #%d: POSSIBLE\n",tt);
}
}
}
Bit Party
Problem
These days, robots can drive cars, but can they throw a good party? The Code Jam team's research into this topic is still at an early stage. We just deployed R robot shoppers to our local supermarket to buy party supplies for our World Finals in Toronto, but their first-order model of a Canadian party was very simple: they just bought B "bits" (a bit being a small donut-like treat found in the area). We will work on improving their AI later, but for now, we want to help them purchase all of those bits as quickly as possible.
The supermarket has C cashiers who can scan customers' purchases. The i-th cashier will:
- accept a maximum of Mi items per customer
- take Si seconds to scan each item
- spend a further Pi seconds handling payment and packaging up the bits.
That is, a customer who brings N bits to the i-th cashier (where N must be less than or equal to Mi) will spend a total of Si × N + Piseconds interacting with that cashier.
Before the robots interact with any cashiers, you will distribute the bits among the robots however you want. (Bits must remain intact; you cannot break them up into fractional pieces!) Any robot that gets no bits will not get to interact with a cashier, and will go away disappointed.
Then, for each robot with at least one bit, you will choose a different single cashier. (Two robots cannot use the same cashier, and a robot cannot use more than one cashier.) The robots all start interacting with their cashiers at time 0. Note that once a robot finishes interacting with its cashier, it cannot be given more bits and cannot interact with other cashiers.
If you help the robots make optimal choices, what is the earliest time at which all of the robots can finish interacting with their cashiers?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with three integers R, B, and C: the numbers of robot shoppers, bits, and cashiers. Then, there are C more lines. The i-th of these represents the i-th cashier, and it has three integers Mi, Si, and Pi: the maximum number of bits, scan time per bit (in seconds), and payment/packaging time (in seconds) for that cashier, as described above.
Output
For each test case, output one line containing
Case #x: y
, where
x
is the test case number (starting from 1) and
y
is the earliest time (in seconds) at which all robots can finish interacting with their cashiers.
Limits
1 ≤ T ≤ 100.
1 ≤ Mi ≤ 109, for all i.
1 ≤ Si ≤ 109, for all i.
1 ≤ Pi ≤ 109, for all i.
The sum of the R largest values of Mi ≥ B. (It is possible for at least one subset of R cashiers to handle all of the bits.)
Time limit: 15 seconds per test set.
Memory limit: 1GB.
Test set 1 (Visible)
1 ≤ R ≤ C ≤ 5.
1 ≤ B ≤ 20.
Test set 2 (Hidden)
1 ≤ R ≤ C ≤ 1000.
1 ≤ B ≤ 109.
Sample
| Input | Output |
| |
In Sample Case #1, there are two robots, two bits, and two cashiers, and each cashier can only handle one item. So, you must give one bit to each robot. Cashier 1 takes 5 seconds, and Cashier 2 takes 3 seconds, so the time required is 5 seconds.
Sample Case #2 is similar to the previous case, except that now Cashier 2 can handle up to 2 items. So, it is best to give all the bits to one robot and have that robot use Cashier 2. This takes 1 second per item plus 2 seconds = 4 seconds.
In Sample Case #3, the optimal strategy is to send one robot with 2 bits to cashier 2, and two robots with 1 bit each to any of the other cashiers.
题意：有R,B,C分别表示顾客数，商品数，售货员数，每个售货员都有一个最大的能处理的商品数，以及处理每个的时间，和对每个交互的顾客的额外处理时间，求把所有B商品处理完的最短时间。
思路：二分这个时间，达到满足即可。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef unsigned long long ll;
const ll maxx=9223372036854775806;
ll m[1005],s[1005],p[1005];
ll num[1005];
bool cmp(int a,int b)
{
return a>b;
}
ll r,b,c;
bool check(ll x)
{
for(int i=0;i<c;i++)
{
if(x<=p[i])num[i]=0;
else num[i]=(x-p[i])/s[i]>m[i]?m[i]:(x-p[i])/s[i];
}
sort(num,num+c,cmp);
ll sum=0;
for(int i=0;i<min(r,c);i++)
{
sum+=num[i];
if(sum>=b)return true;
}
return false;
}
int main()
{
int t;
scanf("%d",&t);
for(int tt=1;tt<=t;tt++)
{
scanf("%lu%lu%lu",&r,&b,&c);
for(int i=0;i<c;i++)
{
scanf("%lu%lu%lu",&m[i],&s[i],&p[i]);
}
ll l=0,r=maxx;
ll ans,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
if(r<2)break;
}
printf("Case #%d: %lu\n",tt,ans);
}
}
C题没写出来，好像是暴力，有时间再看。
![[GCJ14 R1A Problem A]Charging Chaos 位运算+矩阵[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)