[ZSTU4214 2015년 12월 절강성 이공계 대회 E] [구간 DP처럼 보이지만 선형에 뇌홀을 더하면 좋은 문제] 파워에그즈의 최소 계란 던지기 횟수로 그 견고도 측정 학회 상태 표시

4627 단어 동적 계획 - 구간 DP뇌구멍좋은 제목
4214: Power Eggs
Time Limit: 1 Sec  
Memory Limit: 128 MB
Submit: 130  
Solved: 24
Description
Benedict bought K identical power eggs from Dropeggs.com, and now he wants to test them by dropping them from different floors of his building. His building has N floors numbered 1 to N. F is an unknown number in the range from 0 to N, inclusive. Each egg will break if dropped from floor F+1 or above, but will not break if dropped from floor F or below. Benedict can drop each egg as many times as he wants from any floor until it breaks. He wants to know the minimum number of egg drops necessary to ensure that he can determine F.
For example, if there are three floors and Benedict has only one egg, then he has to first throw the egg from the first floor, then from the second floor (if the egg survived), and then from the third floor (if the egg survived). Therefore, three drops are required in the worst case
Input
The first line contains one number T (1 ≤ T ≤ 10000) which is the number of test cases, followed by T lines. Each of the next T lines contains two numbers: N, the number of floors (1 ≤ N ≤ 2000000007) and K, the number of eggs (1 ≤ K ≤ 32).
Output
For each of the T lines, print the minimal number of drops required, or if it's greater than 32, print the word Impossible. After that many drops, Benedict gets too tired and cannot continue.
Sample Input 
4
10 1
100 2
30 30
2000000000 2

Sample Output 
10
14
5
Impossible
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template inline void gmin(T1 &a,T2 b){if(b=n)
{
ans=i;
break;
}
if(ans==0)puts("Impossible");
else printf("%d",ans);
}
return 0;
}
/*
[Trick & & 토크]
자신에게 심리적 부담을 주지 마라. 어려울 줄 알았던 문제들이 어렵지 않을 수도 있다.
[제목]
n(2e9)층이 있는데 우리 손에 m(1<=m<=32)개의 계란이 있는데 계란은 같은 견고도를 가지고 있다.
우리는 계란의 견고도를 측정할 수 있도록 최소한의 테스트 횟수를 통과하고 싶다.
(견고도는 [0,n] 범위의 값으로 계란이 가장 많이 깨지지 않는 층을 표시한다).
PS: 32 단계에서 이 값을 측정할 수 없으면 impossible를 출력합니다.
【유형】
DP
【분석】
시합할 때 제목과 제목을 보고 생각했어요.
《IOI 2004 국가훈련팀 논문 주천광-《매알》이라는 문제에서 동적 기획 알고리즘에 대한 최적화를 간단히 분석하였다.
이 논문을 나는 보지 못했는데, 단지 이 문제는 틀림없이 깊이를 헤아릴 수 없을 것 같아서 할 수 없다고 느낀다.
그러나 마지막에 시가 나와서 나는 이 문제가 돌파할 수 있다는 것을 알게 되었다. 단지 시간이 없어졌을 뿐이다.
======================================================================
우리는 우리의 사유 논리를 좀 명확하게 하고 냉정하게 이 문제를 분석해 봅시다.
우선, 층수 n이 매우 많기 때문에 우리는 그에 대해 가장 많이log급의 알고리즘만 취할 수 있다.
그러나 달걀 수와 최대 걸음 수는 크지 않아 돌파구가 될 수 있다.
그래서 한 가지 상태를 생각하면
f[i][j]로 현재 i회도 시도할 수 있고 계란 j개도 있어 가장 많이 측정할 수 있는 층 범위를 나타낸다.
여기에 도입해야 할 하나의 사상은 자문제 사상이다.
비록 층수가 n이지만 답안의 수치 범위는 [0, n]이고 모두 n+1개의 값이 있다.
그러나 답은 범위 내에서 정해져 있고 폐쇄적이다.
그래서 우리의 가장 많은 검증 횟수는 여전히 n회이지 n+1회가 아니다.
예를 들어 우리가 계란의 견고도가 [1,n]이 아니라는 것을 측정하면 그 견고도는 반드시 확실한 0이다.
좀 더 구체적으로--
처음에 [0, n]은 n+1에 계란을 던지고, 깨지고, 0에 계란을 던지고, 깨지지 않았다는 것을 고려할 수 있다.
한 구간이 [l,r]의 자 상태인 것은 우리가 r+1에 계란을 던져서 깨졌기 때문이다.l에 계란을 던져, 깨지지 않았어.
우리mid자리에서 계란 던지면
깨지면 f[남은 시도 횟수-1][남은 계란 수-1]의 상태에 도달하고 대응하는 구간 범위는 [l,mid-1]
깨지지 않으면 f[남은 시도 횟수-1][남은 계란 수]의 상태에 도달하고 대응하는 구간 범위는 [mid, r]
분명히 토폴로지 서열은 (잉여 시도 횟수 승차, 잉여 계란 수 승차) 라는 서열일 것이다.
f[i][j]어떻게 구하죠?와우, f[i-1][j-1]+f[i-1][j]인 것 같아.
그래서 점차적인 출발점만 찾으면 된다.
우리는 정의할 수 있다--
1, f[남은 시도 횟수==1][남은 계란 수>=1]=2,
우리는 한 번에 계란을 던져서 조작할 수 있음을 나타낸다. 견고도는 [x, x+1] 중의 x이거나 x+1이다.
2,f[남은 시도 횟수>=1][남은 계란 수==1]=남은 시도 횟수+1.
이 계란이 깨지지 않도록 1층에서 던져야 한다는 뜻이다. 측정된 견고도의 구간차는 바로.
마지막으로 f[num][초기 계란수]>=(n+1)의 가장 작은num이 답이다(또는 impossible).
[시간 복잡도 & & 최적화]
O(n^2)
물론 이 문제는 또 다른 각양각색의 방법이 있다.
그러나 가장 중요한 단계는 DP로 이 문제를 해결하는 상태를 나타내는 것이다.
*/
NeosVR Write를 사용하여 원하는 시간에 레지스터에 시간을 기록합니다.
nginx 간단 한 CC 공격 방어 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage