## 10272 - DDR King

Moderator: Board moderators

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

### 10272 - DDR King

plz give me some data set.

#include <stdio.h>

#define M 510

int even1[M], even2[M];
int odd1[M], odd2[M];
int first[M], last[M];

int main()
{
int t1, t2;
int i, j;

even1[1]=0; even2[1]=0;
odd1[1]=1; odd2[1]=3;
first[1]=1; last[1]=3;

even1[2]=2; even2[2]=6;
odd1[2]=1; odd2[2]=3;
first[2]=2; last[2]=6;
for(i=3; i<=500; i++)
{
even1=even1[i-1]; even2=even2[i-1];
odd1=odd1[i-1]; odd2=odd2[i-1];

t1=first[i-1]+((int)(i/4))*((int)(i/4))+1;
t2=last[i-1]+(((int)(i/4))*((int)(i/4))+1)*3;
if(t1%2==1){ if(odd2<t2) odd2=t2; }
else{ if(even2<t2) even2=t2; }
first=t1; last=t2;

for(j=1; j<=i-2; j++)
{
if(even2[i]<odd2[j]+odd2[i-j-1]) even2[i]=odd2[j]+odd2[i-j-1];
if(even2[i]<even2[j]+even2[i-j-1]) even2[i]=even2[j]+even2[i-j-1];

if(odd2[i]<odd2[j]+even2[i-j-1]) odd2[i]=odd2[j]+even2[i-j-1];
if(odd2[i]<even2[j]+odd2[i-j-1]) odd2[i]=even2[j]+odd2[i-j-1];
}
}

int temp;
int n, m, k;
int t;

scanf("%d", &t);

for(int loof=0; loof<t; loof++)
{
scanf("%d %d %d", &n, &k, &m);
if(m%100 || n<k) printf("No\n");
else
{
m/=100;
if(n==k || n==k+1)
{
if(first[k]%2==m%2)
{
if(first[k]<=m && m<=last[k]) printf("Yes\n");
else printf("No\n");
}
else printf("No\n");
}
else
{
if(first[k]%2==m%2)
{
if(first[k]<=m && m<=last[k]) printf("Yes\n");
else if(m<first[k]) printf("No\n");
else
{
temp=n-k-1;
m-=last[k];
if(m%2==0)
{
if(even1[temp]<=m && m<=even2[temp]) printf("Yes\n");
else printf("No\n");
}
else
{
if(odd1[temp]<=m && m<=odd2[temp]) printf("Yes\n");
else printf("No\n");
}
}
}
else
{
if(first[k]>m) printf("No\n");
else
{
temp=n-k-1;
if(m>last[k]) m-=last[k];
else m=1;

if(m%2==0)
{
if(even1[temp]<=m && m<=even2[temp]) printf("Yes\n");
else printf("No\n");
}
else
{
if(odd1[temp]<=m && m<=odd2[temp]) printf("Yes\n");
else printf("No\n");
}
}
}
}
}
}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10272 - DDR King

Input:

Code: Select all

``````100
7 406 415400400
487 113 8853800
490 57 1182400
388 50 754500
80 421 463273600
253 129 13194900
208 28 153400
260 339 241476600
194 425 476641300
226 283 140252400
299 36 282100
150 269 120416000
202 259 107406800
199 393 376651600
384 473 657456700
262 473 657410700
317 180 35946800
157 187 40367300
68 381 343169500
344 106 7298300
444 405 412270500
450 302 170593600
61 3 32200
230 450 565981300
195 333 228912700
81 341 245805700
342 158 24247800
378 315 193599100
5 129 13192600
305 473 657418200
132 417 450159100
243 112 8586000
370 174 32427700
254 150 20781300
278 346 256808900
21 173 31953500
483 261 110006500
371 139 16491700
446 391 370937800
401 442 536246500
208 321 204915400
421 63 1584000
180 179 35368600
190 180 35991100
149 204 52410100
188 472 653269100
314 455 585032100
351 71 2246200
195 17 58500
423 418 453408100
370 126 12328300
479 293 155733800
200 219 64903800
95 410 427796600
134 305 175781200
17 493 744569300
74 52 858700
385 149 20398900
87 345 254565800
427 267 117798900
208 383 348542600
310 362 294197300
222 61 1457100
313 404 409225200
330 37 386300
50 54 949400
243 375 327140900
136 259 107482000
101 92 4800900
82 19 123500
228 474 661592700
246 284 141851100
56 252 98963300
86 311 186329200
271 140 16895900
261 437 518178400
491 427 483364200
272 309 182767700
202 156 23361400
478 239 84384800
266 213 59655200
183 460 604600300
463 262 111240200
49 348 261332400
286 366 304128500
59 126 12322300
133 363 296639100
329 134 14789900
30 83 3561300
324 60 1365900
129 72 2306000
161 255 102544300
224 464 620581300
284 12 105300
409 44 577500
165 103 6759000
359 484 704497400
225 58 1243400
401 88 4237400
479 158 24273100``````
AC output:

Code: Select all

``````No
Yes
Yes
Yes
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
Yes
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
Yes
Yes
No
Yes
Yes
No
No
No
No
Yes
Yes
No
Yes
No
No
Yes
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
No
No
No
No
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes``````
Check input and AC output for thousands of problems on uDebug!