Virus Testing
National Olympiad — Regional round
Submission name: virus.cpp
Problem summary
Exactly one of N samples is infected. All tests must be prepared at once, because results arrive only at the deadline. A box becomes positive if it receives any of the infected sample; you may mix portions of arbitrary samples. Minimize the number K of boxes needed to identify the infected sample with certainty. For N≤500 also output one optimal assignment of samples to boxes.
Input
An integer N.
Output
K on the first line. Only when N≤500, output K further lines: a box’s sample count followed by those distinct sample indices. Any valid optimal assignment is accepted.
Constraints
1 < N ≤ 10^10; sample indices are 1…N.
Worked example
An independently prepared example for this explanation.
Input
3
Output
2 1 2 1 3
Solution analysis
- K binary test results distinguish at most 2^K possibilities, so choose the smallest K with 2^K≥N.
- Assign sample i the binary code i−1. Put it in box b when bit b is set.
- The all-negative outcome identifies sample 1; exactly one infected sample is guaranteed.
Why it works
The information bound requires K≥ceil(log2 N). Distinct binary codes give every possible infected sample a different result vector, reaching that bound.
Watch out. For N>500 print only K. Sample 1 may occur in no box; its unique zero code is still informative.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The information bound requires K≥ceil(log2 N). Distinct binary codes give every possible
// infected sample a different result vector, reaching that bound.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
long long n;
cin>>n;
int k=0;
while((1LL<<k)<n){
k++;
}
cout<<k<<'\n';
if(n>500){
return 0;
}
for(int b=0;b<k;b++){
vector<int>members;
for(int i=1;i<=n;i++){
if(((i-1)>>b)&1){
members.push_back(i);
}
}
cout<<members.size();
for(int x:members){
cout<<' '<<x;
}
cout<<'\n';
}
}