Page 4 of 5

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 23, 2014 7:13 am
by mratan16
Thank you for the advice but I honestly have no idea on how to code that..

I do not understand how to set keep[1][901] to 2 and keep[1][902] to 0.

Can you please expound?

Thanks

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 23, 2014 12:25 pm
by lighted
I can tell you my dp algorithm.

I used one int array of length 10201 let's say cost[10201], where cost is max favour we can get with exactly price i
Set array cost to 0, and cost[0] = 1; We have only one possible price - its 0;

Now we will build new possible prices:

For every price and favour do cycle from i = m + 200 down to price and check:

if we already have price cost (if we have it will be greater than zero) then using current price we can get (or update) price cost

if (cost > 0 && cost + favour > cost) cost = cost + favour;

I do cycle in decreasing order to prevent using one clothes several times.
I look from biggest price i builded before down to smallest price (and make new price with current one).

At last we check array cost for maximal favour.
Do cycle from i = 0 to m + 200 and check:

if (i <= m || i > 2000)
if (cost > MAX) MAX = cost;

Answer will be MAX - 1, because i added to cost[0] = 1 at the beginning to make it greater than 0 and mark that we have it.

I check extra prices from m + 1 to m + 200 because if it is greater than 2000 than it is also possible price.

Hope it is not confusing

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 23, 2014 12:43 pm
by mratan16
I took your suggestion and attempted to do it. It still shows the wrong answer. Can you please help?

Code: Select all

Removed
Thanks

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 23, 2014 1:48 pm
by lighted
I sent you PM.

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 30, 2014 7:15 pm
by just_yousef
My Code Satisfies All Test cases Given in the post.
But still Gives WA.
Please Help !! :/

Code: Select all

#include <bits/stdc++.h>
using namespace std;

struct node {
	int p, f;
	bool operator<(const node &a) const {
		return a.p > p;
	}
} Q[101];

int n, m;
int dp[101][11001];
int solve(int id, int x, bool f) {
	if (x > 2000 && !f)
		x -= 200, f = 1;
	if (x > m)
		return -1e9;
	if (id == n)
		return 0;
	int &res = dp[id][x];
	if (res != -1)
		return res;
	res = max(solve(id + 1, x, f), solve(id + 1, x + Q[id].p, f) + Q[id].f);
	return res;

}
int main() {
	//freopen("a.in", "r", stdin);
	while (scanf("%d%d", &m, &n) > 0) {
		for (int i = 0; i < n; ++i)
			scanf("%d%d", &Q[i].p, &Q[i].f);
		memset(dp, -1, sizeof dp);
		sort(Q, Q + n);
		printf("%d", solve(0, 0, 0));
	}
	return 0;
}

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 30, 2014 7:50 pm
by brianfry713
Print a newline char at the end of each line.

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 30, 2014 8:39 pm
by just_yousef
brianfry713 wrote:Print a newline char at the end of each line.
I tried that too but still WA :/

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 30, 2014 9:28 pm
by brianfry713
It looks like you figured it out.

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 30, 2014 9:41 pm
by lighted
just_yousef you got accepted it two hours ago, how can it be still WA? :-? :)
see uhunt http://uhunt.felix-halim.net/id/202166

Re: 10819 - Trouble of 13-Dots

Posted: Wed Jul 30, 2014 9:47 pm
by just_yousef
lighted wrote:just_yousef you got accepted it two hours ago, how can it be still WA? :-? :)
see uhunt http://uhunt.felix-halim.net/id/202166
I used Different method for the trick in this knapsack question, But this specific code is Giving WA!!

Re: 10819 - Trouble of 13-Dots

Posted: Thu Jul 31, 2014 2:32 am
by lighted
just_yousef your code avove gives wrong output for one case of Brianfry's test.
brianfry713 wrote:Input:

Code: Select all

9677 55
191 3
3112 1
3238 4
1515 3
3117 3
3527 3
3822 1
1057 5
3117 1
1821 1
2497 4
3352 5
996 4
1212 3
1303 1
2540 2
2904 5
2090 1
2519 2
3306 4
1046 5
1547 2
3209 5
1050 5
1508 5
3706 2
3413 4
1232 2
1909 3
2609 5
364 3
1759 3
3151 2
1760 3
3803 4
3655 1
249 1
2420 3
860 2
2134 1
3042 2
2722 4
1247 1
3214 4
3100 2
3422 4
3321 3
3082 5
1380 3
843 1
2258 2
2382 2
2402 4
2315 3
973 1
3315 88
2990 1
3172 3
653 3
95 5
910 5
3567 1
1047 2
3405 5
193 1
3960 2
1096 5
1308 3
3846 2
3109 5
1126 5
1536 2
1786 3
1055 2
3443 4
2895 4
1016 4
1285 1
1813 3
488 4
936 5
454 4
3492 1
1879 4
2440 4
1210 4
2425 2
384 5
3803 5
3000 4
2939 2
300 4
707 5
2017 5
2273 4
523 1
3655 5
1942 3
3793 3
3538 2
1510 4
2501 2
3492 1
496 4
674 1
3243 2
2093 3
3919 4
1478 4
1669 5
1142 3
14 1
3870 1
645 3
2479 3
2246 2
929 1
626 3
3982 2
769 3
1672 2
971 1
257 4
2914 4
3175 1
2188 2
3124 4
1464 4
861 3
3007 1
2642 1
31 3
2350 2
1045 4
2833 3
42 4
2176 4
619 2
2253 2
518 2
113 4
2447 2
1610 1
2229 3
1408 90
2513 5
2839 1
1638 5
3903 1
575 2
495 3
3591 3
1980 1
1454 5
93 4
2362 1
1028 1
3793 4
1071 4
1811 3
3960 3
1508 5
3569 5
690 2
2179 4
2911 2
2584 5
2047 3
3414 5
1498 1
1823 2
64 5
1020 5
2191 1
2581 5
2234 1
675 5
1689 1
3590 5
418 1
699 5
1144 5
2533 4
549 3
3395 1
1452 3
2609 2
419 5
1723 3
2069 4
2961 3
3194 2
395 2
581 2
3964 4
2103 4
678 4
648 3
3492 2
1508 3
3945 1
103 1
1178 4
2533 3
3833 5
3554 2
903 3
2779 2
3980 4
1632 4
709 1
1309 1
3684 4
1300 3
3855 5
2413 4
2470 5
2705 2
3739 2
2898 4
2190 1
2715 1
1549 5
1093 3
1203 3
2175 5
3162 4
354 4
1791 5
2372 5
1164 3
1797 4
2 5
3631 3
2441 5
810 32
1682 3
427 1
220 5
1109 1
947 4
37 4
3119 4
3305 2
2747 1
3258 1
2811 5
3894 1
2610 2
2903 1
3107 3
2385 1
1291 3
369 3
1033 2
3988 4
1464 2
2440 4
1118 2
2195 1
124 4
3773 4
3210 4
2098 3
245 4
3221 2
268 1
490 2
9588 25
124 3
2686 4
1187 1
486 2
1083 3
2073 3
1466 4
1433 1
1482 5
1607 4
2812 1
1282 3
1553 5
693 1
3811 4
3603 4
1019 1
396 1
3142 5
2534 1
2484 1
205 1
3154 4
1891 4
2982 2
8899 65
2052 5
881 5
451 1
2350 4
3737 3
898 2
944 2
3663 3
2173 5
661 1
2801 3
1309 2
3205 1
3292 4
3047 1
330 3
2758 3
1054 1
2784 3
172 5
2058 2
3978 4
2361 2
3086 5
1835 5
1893 1
1314 2
3645 1
2399 3
2703 1
3496 5
2895 3
243 3
1812 5
54 3
2601 3
3403 1
1112 3
2569 3
2999 5
647 5
2093 1
91 1
2478 2
673 1
638 1
565 5
3124 2
3831 4
536 5
3269 4
2346 1
2065 3
785 5
359 5
1739 3
1026 2
3317 3
1920 3
309 2
3327 4
3463 1
829 3
1401 1
3872 4
9123 56
1423 2
2514 1
3400 4
823 5
3784 5
1467 3
3095 1
2629 5
3281 1
309 4
586 4
3201 3
3060 4
2424 1
2888 1
2774 4
3611 2
852 4
1640 1
3472 1
938 1
2936 5
2425 5
1750 1
1204 2
1016 1
2533 4
3554 3
1521 3
875 2
1997 5
1774 4
1639 3
970 5
651 4
1054 1
2083 5
2324 1
2257 4
2915 1
2836 2
1601 2
850 3
2960 4
3483 5
3129 5
3835 4
3438 2
3879 3
1103 2
1200 1
2820 3
2849 2
140 1
1921 2
1268 4
1102 63
2475 5
374 2
3258 2
1973 3
2038 1
3640 4
3983 1
1882 3
750 1
3593 1
2362 4
1416 3
249 3
2259 3
795 2
736 1
2834 2
1760 1
2020 1
828 4
2242 3
1533 2
336 4
3309 4
2847 2
1006 4
2046 5
413 3
2461 2
515 3
968 5
3228 2
3063 1
2243 2
1070 4
1491 5
3889 1
1887 3
2789 1
2013 2
1152 5
3546 5
2142 3
1844 5
3332 2
209 5
311 1
451 1
775 5
1159 5
2115 4
1507 4
1672 5
2930 5
1291 2
2798 4
663 3
1992 3
2653 5
3758 2
2896 4
2987 1
3754 1
3490 18
2834 3
2371 4
3089 3
3302 4
3973 2
1923 3
3877 1
58 5
3415 1
3695 1
2587 4
754 5
3770 2
1039 5
3529 3
402 1
761 2
3309 5
8886 74
961 2
1896 1
941 1
307 4
3015 5
3750 1
2139 1
2865 3
521 3
2984 5
2509 4
2232 2
873 3
2387 2
3193 3
3846 4
1416 4
3741 2
3865 3
57 2
120 1
2292 3
2845 5
1854 1
142 5
1276 3
3349 1
2265 2
2850 2
1106 1
2389 3
2196 2
3045 2
2864 3
2334 4
2140 3
3430 5
1415 1
1938 2
2343 3
457 5
1082 5
3476 1
379 1
3996 1
368 4
2787 1
2892 5
1554 1
740 3
1380 2
3044 1
13 1
139 3
77 5
29 2
2803 4
691 5
807 1
1308 4
2904 2
3538 5
941 1
3521 1
888 4
2732 2
194 4
3780 5
2584 3
2860 5
3103 3
3898 3
350 1
536 3
9870 9
2310 3
3869 1
2953 4
979 1
6 1
3789 4
837 2
864 3
892 3
6122 50
2811 1
2991 2
2949 3
3647 2
1199 4
1678 4
2917 3
1706 3
3058 1
1046 2
1255 3
2152 5
1169 3
3763 2
3517 2
2163 2
2395 5
1739 5
1196 4
1179 1
3391 4
2254 2
1106 4
880 1
3347 4
3578 5
3111 3
3748 1
1799 1
3395 2
1565 1
3995 2
3413 4
1302 5
3470 3
3353 3
1689 3
1871 3
2269 1
3309 5
1027 2
3272 4
1671 2
1120 1
3232 2
1489 4
2422 3
1106 3
3919 4
2793 5
8774 80
2601 2
807 2
2777 1
3573 2
1745 3
2028 4
1087 1
738 3
3871 1
3071 1
1468 4
3193 4
29 1
1685 2
2500 1
1670 1
2907 2
2274 1
1902 5
472 1
2444 1
1014 4
2197 3
2440 3
2424 4
3778 1
3354 3
3168 5
2081 3
2555 4
831 2
2383 4
3051 4
2124 4
3206 2
950 5
1094 5
1884 3
65 2
2060 3
1833 5
3083 2
807 4
1273 2
3806 4
171 4
755 3
1077 5
3913 5
757 5
1794 4
1120 3
20 4
3232 3
3325 1
3276 4
3480 5
3400 5
1663 3
3877 2
850 5
2808 4
3303 4
1761 4
3083 1
2686 4
926 3
819 5
3159 2
1732 5
1693 3
344 4
68 5
2162 3
414 3
3902 5
2788 1
3571 4
2592 3
2010 1
2878 71
3606 5
851 1
2772 4
473 4
2843 4
2214 3
42 2
3281 2
716 5
945 5
1662 2
3678 4
2878 4
3267 1
647 2
1581 2
1293 2
1027 3
2791 1
1271 4
16 1
1524 5
2118 4
2964 4
850 3
3449 5
695 1
447 1
1747 3
459 3
3529 5
3348 2
1174 3
1941 4
2224 2
2302 1
2695 2
3000 2
980 4
3996 3
2222 5
692 2
3274 2
2841 3
850 2
116 4
2042 1
2255 5
188 1
3884 5
3406 4
1355 2
2713 2
3616 1
2669 2
1521 3
3759 2
510 5
3702 3
404 5
3001 4
1634 2
686 2
609 5
435 1
341 4
3380 2
2995 5
2400 2
2136 2
2925 5
4979 21
2572 5
2067 3
3225 4
3529 3
46 5
3618 4
1753 3
2660 2
1070 4
2730 5
1046 2
3245 2
1038 3
1217 5
1388 4
3349 2
105 4
2584 2
589 1
2257 2
3977 1
3551 68
2452 5
268 5
80 4
675 5
1426 5
922 4
1651 5
3129 1
3072 3
3348 2
243 3
3208 4
747 4
2521 4
3690 4
2453 1
2021 1
2014 2
2421 2
3928 5
3311 3
3365 5
3692 1
350 3
1321 3
2643 2
1980 5
3098 5
3666 2
3802 4
2911 5
1847 4
1677 1
3382 1
3252 5
647 5
511 2
3874 3
3207 4
3668 3
3920 2
2442 5
512 1
1329 1
3861 2
3883 5
3735 2
3702 4
1941 2
1861 1
3097 5
106 4
3222 4
512 2
554 5
3307 4
2489 5
3428 3
3990 5
3528 3
2238 1
2622 5
1490 4
87 5
2110 1
1327 2
1158 3
1516 2
1166 31
3510 4
2558 4
3845 3
1267 3
749 2
732 2
1107 1
37 4
1644 3
2754 3
1660 1
29 1
2773 1
770 3
2268 1
3019 4
1904 5
1297 3
3325 4
1372 4
3820 3
700 3
1423 1
1005 1
2614 2
1149 5
1325 3
3259 2
2715 3
1090 3
3263 4
4790 64
2388 2
2915 2
3675 2
2137 3
2741 4
771 1
3924 5
3933 2
2236 4
3161 1
2610 1
10 1
3150 1
3009 4
1558 5
3931 4
3935 2
2009 2
3834 4
3454 2
3332 1
3441 1
3054 5
2143 5
806 4
1201 1
778 2
1442 5
2660 5
3044 2
3977 5
866 4
2522 1
3871 1
3722 5
1633 1
603 1
2660 3
797 1
945 5
3162 4
1720 2
59 4
218 3
315 5
3639 3
2938 3
906 2
434 4
3814 1
804 3
3913 1
2870 1
1414 4
430 3
1972 5
1206 1
3530 3
3556 4
334 4
64 2
864 4
1532 1
460 4
9820 18
2825 5
2070 2
1809 4
2364 1
1308 2
1931 4
2384 1
3674 4
752 5
2716 1
154 2
1761 4
1779 2
3138 2
1609 5
3214 4
2437 5
3873 3
9487 44
3467 2
1030 3
215 4
1237 5
2382 5
3820 4
3777 2
227 3
1342 2
1181 5
595 4
2864 1
3926 5
1443 5
1544 3
2386 4
951 2
3111 2
3532 3
1757 2
2687 3
3361 2
1901 4
352 2
1943 2
72 4
1377 4
3049 5
586 2
1451 3
1561 5
3491 2
3603 4
381 3
3300 1
1750 2
65 3
801 2
1400 1
1559 5
3388 5
2935 1
917 1
2417 5
8236 41
3984 5
408 5
305 4
2779 2
3848 2
3525 5
767 4
3411 2
1907 5
3424 5
856 2
1799 3
279 1
2125 1
218 2
3266 4
2743 1
26 5
387 4
787 1
1585 1
2534 1
252 2
271 1
3458 5
2679 1
3560 3
103 2
3192 5
3589 3
3881 1
313 1
3231 5
2725 1
3846 2
554 1
3821 1
134 4
1735 5
3286 1
1153 4
5383 38
2441 2
1254 1
890 4
1745 2
47 2
448 4
3099 2
3245 2
3034 2
1079 3
3237 4
3630 4
2319 3
2866 1
879 1
534 3
3735 4
1303 2
2980 4
1745 4
1807 2
2655 2
1715 3
906 2
2049 3
3954 4
3547 2
3311 3
2850 2
1687 3
3953 4
3399 2
711 2
663 3
451 5
3068 2
951 5
219 5
8002 89
3765 4
3107 1
363 5
4 5
1221 5
2905 4
2934 4
1830 2
2543 4
3737 2
2934 5
1964 4
3148 3
427 1
2634 1
489 2
3478 3
2467 2
2951 2
568 3
1676 3
3781 2
2328 1
3644 3
854 3
779 5
3919 4
2492 4
2359 3
3136 3
22 5
3742 1
3923 4
42 1
1383 5
3748 1
433 5
370 5
1842 2
334 3
3745 3
3186 3
558 5
3784 2
595 4
613 4
2895 1
466 1
3266 4
2745 4
1819 5
761 2
2372 3
1715 2
1847 5
3612 5
3864 1
1605 3
474 2
3690 5
659 5
2387 2
1007 5
3073 4
414 5
1976 2
661 3
1187 4
570 4
3948 1
1301 1
6 5
2709 4
1937 2
3702 2
954 1
2279 2
616 5
2544 3
614 5
2208 2
1541 1
2029 3
2603 5
1980 4
1014 1
2462 2
1148 2
3685 5
5628 91
1062 3
449 3
1348 2
3329 4
1455 3
3551 4
3235 3
2530 4
523 3
213 3
35 4
2838 2
2950 3
369 5
3420 4
2372 3
3431 3
525 5
236 5
1372 5
851 5
1352 4
3069 5
1699 4
1718 1
2797 2
3490 4
951 4
1970 4
1424 4
3093 1
2574 5
2967 3
3652 5
6 4
1595 5
2649 1
940 4
3532 2
1660 1
902 1
3704 1
2441 1
3181 1
2676 5
2150 4
399 3
291 5
524 2
3270 4
1669 2
1737 1
514 4
2385 4
2019 2
1997 1
851 2
3662 2
3057 3
52 4
3797 2
3500 4
3980 2
263 2
435 1
1737 4
1100 5
3123 3
2853 3
2362 5
2255 3
494 3
2410 3
3100 2
3700 3
3902 4
2409 2
43 3
3894 3
3243 3
541 5
3487 4
804 2
3957 4
820 1
1231 3
2675 5
2884 4
2583 1
3606 5
1838 2
1133 54
3259 1
2634 5
3534 4
535 1
3207 1
2418 1
2982 5
17 4
691 1
3227 2
3323 2
1505 2
797 5
538 5
968 4
3232 3
1544 1
81 2
444 2
1502 5
988 5
11 4
2644 4
121 3
1626 4
3403 5
2161 3
3204 2
2368 2
1943 2
2761 5
3560 1
3742 4
1380 5
606 5
3835 3
3504 3
1913 2
576 2
1833 1
2085 2
3501 5
2493 5
3554 5
2798 5
194 3
3373 3
1861 5
96 4
3650 2
2824 1
2646 4
3681 2
474 3
9002 45
2809 3
3892 4
1976 2
1366 4
3595 1
3728 5
2072 3
3892 2
2917 2
3875 4
1039 1
2402 3
1377 1
946 4
2689 2
859 3
1619 5
511 2
3837 4
1474 3
2742 1
3570 3
1004 3
1096 1
151 2
2837 5
19 4
1577 3
3671 5
3948 2
2761 2
913 1
1907 4
3972 3
2 3
1525 2
3349 3
3907 4
906 4
975 4
2675 1
2245 2
1401 3
440 3
2694 4
3476 1
1545 4
1791 82
3173 3
1546 1
3953 4
2268 2
516 3
357 1
3879 1
2477 1
1494 3
1597 3
1245 2
670 3
3127 3
1391 1
2906 3
825 5
1731 3
1251 2
2144 5
1687 5
2395 4
79 3
3726 3
1177 2
3979 1
817 5
1513 5
1512 3
2993 1
2013 5
3181 5
327 2
1911 1
3297 4
1798 4
3064 4
3378 4
2816 4
2401 5
1026 4
3469 1
306 4
32 3
2675 4
1775 1
1626 2
3875 1
2218 4
233 2
2190 5
2850 2
2926 5
1099 4
2386 3
2437 4
2581 3
1956 2
3941 3
1407 2
1363 5
3653 3
488 5
1643 4
2016 3
572 2
961 2
2162 3
2703 3
2330 5
3110 3
850 3
3726 2
1280 3
1144 1
2632 3
2570 3
2549 4
2515 5
2467 2
2770 2
1790 5
3514 5
6368 37
3562 1
3656 4
3766 3
1417 2
14 4
3509 1
1733 5
367 3
1128 4
63 3
3459 2
875 1
2270 5
2310 5
2967 3
3999 1
1276 4
1903 1
862 2
885 4
2366 1
2385 5
3237 5
1104 3
2370 5
358 3
399 5
760 3
3897 3
803 4
1696 3
1743 3
1158 2
365 3
3316 4
2894 1
2697 4
3855 49
733 1
3002 3
1456 4
1634 4
943 4
873 3
1813 4
54 2
3179 5
3183 3
2145 1
2355 4
1499 3
198 5
3230 3
2833 5
2618 4
3767 4
1544 3
2278 2
496 2
3677 2
1529 3
2520 5
2230 4
1395 2
1601 1
2890 1
2052 1
3998 2
1767 3
1946 2
1015 1
1160 5
3816 4
1397 4
3290 2
2971 3
1155 5
2229 5
3192 4
461 5
427 4
594 1
2789 3
111 2
3773 5
1642 3
472 5
9913 79
2589 5
1303 1
2518 1
3400 3
2115 2
3407 5
2306 3
2801 3
3570 2
1210 4
337 3
3265 2
79 2
1601 1
3707 3
1894 5
3095 2
877 1
3820 4
1636 4
2608 4
3591 4
1613 4
3997 3
2137 2
3540 3
3229 5
3286 1
61 5
562 1
2535 4
2766 5
2002 1
3945 2
270 1
107 2
3677 5
495 4
2792 5
2823 1
2049 5
104 4
1869 4
1288 5
627 5
2400 1
1007 2
1494 5
1159 5
1181 5
73 3
1009 4
2039 5
1391 3
2346 2
2461 3
2927 1
2726 2
2658 2
3076 4
2566 4
2797 1
2992 3
3284 1
2432 5
1930 4
2454 5
2606 3
793 3
2026 1
560 5
235 2
3755 3
985 5
3325 2
1695 2
2239 1
1815 2
1134 1
2516 66
1914 5
2069 1
2951 4
1563 1
1373 5
3584 4
427 3
1770 3
3129 1
2592 1
3518 1
1048 1
1129 1
3338 4
663 2
1827 2
1082 1
3647 2
1273 4
478 4
797 5
929 3
582 5
1755 1
2156 1
2516 1
984 5
133 3
3128 4
726 2
1243 5
2718 4
3150 2
3060 4
3924 4
3419 5
302 3
2647 4
3749 4
946 2
1099 2
281 3
3727 4
898 3
235 4
2643 3
526 4
505 5
3723 2
801 2
3806 2
719 1
1269 4
1342 5
118 5
3626 4
2451 2
2 1
671 2
1030 4
2873 2
3085 5
1384 5
3777 5
3858 4
1457 4
400 95
121 2
2243 4
488 5
805 1
3929 3
371 1
1784 5
829 1
2297 1
3190 3
3803 3
1674 5
2383 1
859 1
1545 1
2717 4
1827 1
3832 5
3320 5
2779 3
243 3
3529 4
189 4
1896 2
762 2
570 5
2361 4
494 5
126 1
1286 4
412 5
3687 3
962 5
1256 5
858 3
232 5
3183 2
182 5
469 2
2560 2
3161 5
1793 1
2076 4
2969 3
693 3
222 4
608 1
397 1
482 4
2553 3
1687 4
3143 4
2896 4
592 4
1401 4
593 4
2984 3
2786 2
1726 4
3963 1
2360 5
225 5
797 2
888 1
2625 3
2969 2
2576 1
1532 1
1434 1
1186 5
1978 4
99 5
1218 2
2372 4
990 3
2064 5
2871 1
3019 5
3612 4
1296 3
50 2
2899 4
2726 2
799 5
3257 5
3345 4
113 4
2547 5
2679 2
976 4
3605 5
3720 4
1678 5
2493 5
3348 4
8252 71
756 2
2725 1
3557 1
3992 3
1858 3
399 4
3483 5
3651 5
3863 3
2532 3
16 2
2293 3
1693 5
3685 5
1277 5
788 2
2689 2
1512 2
3386 5
1410 1
1544 3
3564 3
752 3
3891 1
543 2
785 2
1025 3
2602 3
214 4
460 1
2199 5
3873 2
1110 2
3484 2
3592 2
2089 3
3052 2
2864 2
1217 5
1121 4
1528 1
2668 3
1687 2
1972 1
258 5
3742 1
3677 2
3695 4
1702 3
1984 3
70 3
2779 4
2075 3
3628 5
748 3
1753 5
3357 5
1178 2
2744 3
3295 4
1579 1
1809 1
3001 2
3096 4
681 3
2347 4
1502 3
927 3
3472 3
3922 4
1654 1
9246 77
3149 2
2405 5
3876 2
1245 1
1086 1
3765 5
908 3
1492 5
291 1
3395 4
1668 2
2072 1
875 4
1709 3
371 5
241 3
1985 4
1411 2
1047 5
17 2
2411 4
3274 1
2641 1
1611 5
955 1
1074 5
1677 2
3760 2
1490 1
1782 1
3430 2
1730 5
1371 4
3625 2
2498 5
1605 2
3422 1
931 3
1643 4
1696 1
3897 2
1571 2
2618 3
476 2
3854 4
2670 2
983 4
697 5
3891 4
1475 2
315 1
1 4
3957 3
2502 1
3823 1
899 4
3670 4
1643 4
151 5
3098 3
727 4
3639 3
2519 4
414 1
1009 1
1501 3
967 3
1410 3
2783 5
3225 3
812 5
2675 3
2592 3
3472 3
2787 4
3449 5
689 3
6420 62
3775 4
2319 5
3875 3
2105 2
2024 3
2467 1
129 4
115 3
2165 2
2124 5
3459 3
553 1
517 5
1758 2
3441 5
1115 1
1317 5
349 3
3956 1
2383 5
2670 5
3490 4
2891 5
441 4
2745 3
2867 5
512 5
800 5
3773 3
2584 4
2591 3
2779 3
3482 2
1098 2
1931 3
1769 5
681 2
102 3
1213 3
1330 4
3458 5
2864 2
3968 4
1348 5
3275 5
2952 1
3980 5
2124 2
1208 2
3251 1
3052 5
793 4
2628 4
7 1
2140 5
149 3
2236 4
2270 5
3379 3
2294 2
3900 1
870 5
6038 60
3340 5
2917 5
726 2
3960 1
2404 4
2764 2
2779 2
450 3
2852 4
2643 2
1592 1
737 4
1379 5
1482 3
867 5
1945 4
2044 3
3500 3
3533 4
287 1
2398 2
1050 3
305 3
806 4
888 3
628 1
2174 4
2363 2
2704 4
2503 4
1003 2
480 4
2012 3
2518 1
141 4
3832 2
2559 3
417 2
2732 3
2371 3
1023 4
2449 5
1066 3
3451 2
1007 2
43 3
3104 4
1758 2
852 2
3362 1
3432 5
234 4
427 2
1204 1
1873 3
3129 1
3276 2
2794 2
2740 3
814 4
3508 79
2107 4
1730 3
1469 5
492 4
278 1
376 5
2616 3
1513 2
311 1
97 2
2983 4
1368 4
416 3
723 2
3853 2
2790 3
1625 2
2528 1
156 1
276 4
3293 5
1648 3
1804 5
2430 5
2897 1
1905 1
2601 1
359 4
82 4
950 3
3055 5
2598 1
1313 2
477 5
143 4
2253 4
2106 2
2046 2
3764 4
2374 5
3353 2
1242 5
605 5
1673 2
3385 2
973 4
3416 1
3822 5
694 4
2197 3
1401 3
974 1
1405 1
3766 1
197 3
179 2
3473 1
2206 2
3724 3
764 3
3204 5
2250 1
1657 4
3347 2
2721 5
3537 5
3048 4
3979 2
584 2
1619 2
2940 5
681 4
3920 2
2489 3
3467 3
3454 4
1691 5
1289 4
127 2
3336 16
3234 4
3672 1
3149 1
2732 3
99 2
512 2
2850 3
1801 4
1133 4
2764 2
245 4
3269 4
624 3
1634 4
2247 2
301 2
5835 82
3760 2
326 3
849 3
3544 4
3813 2
3607 5
1866 1
2607 4
1338 1
3549 3
1490 3
2218 3
1274 4
3157 4
2296 4
1898 2
2594 5
898 3
2999 5
1858 3
3538 3
1128 5
2555 3
2383 4
2937 4
1201 3
2455 1
3901 5
586 1
2006 4
886 1
935 3
2478 1
3625 4
3329 1
990 3
2947 1
620 3
2203 3
2097 4
1636 1
2269 4
3419 3
523 1
1930 1
3236 3
2783 2
2997 2
2706 5
3087 2
456 4
1251 1
2545 4
1606 2
1575 5
2942 2
3703 2
356 5
3731 3
3828 3
3758 2
1530 3
3936 2
503 1
3499 1
1026 4
16 4
3707 3
849 3
12 5
1718 3
2337 5
515 5
892 2
3922 2
2960 1
485 1
2922 4
1366 1
3413 4
3364 5
818 1
8671 60
2643 2
2541 2
3041 1
2311 5
2030 2
421 5
3773 3
696 4
724 4
3572 5
1952 5
3420 2
1801 5
2155 3
2513 1
199 2
2190 1
161 1
3700 1
2959 1
1647 1
1354 4
72 1
854 4
3580 2
791 5
1714 2
3248 5
3344 1
3188 4
3677 2
3012 1
2828 2
3449 2
1995 3
608 2
2138 3
1764 3
361 1
3708 2
3394 3
2176 5
1412 4
1324 3
3176 5
2611 2
249 2
1070 2
1146 2
1604 3
2925 2
3484 3
876 2
3974 2
216 3
1880 1
531 1
1419 5
1829 2
3048 2
8143 40
208 4
3632 4
2930 4
2147 4
620 5
3447 3
2484 1
2054 4
2262 4
2490 4
2581 3
548 2
1665 4
3093 3
84 2
2722 2
2902 3
2271 4
3834 3
3419 2
1839 4
909 1
3539 4
3483 2
1583 2
2645 4
1695 3
514 2
2271 4
422 3
3006 4
2996 4
1849 3
442 2
1683 2
2135 1
2726 4
547 5
2709 1
768 1
6617 32
1157 2
2955 3
108 5
1979 2
3931 5
3673 5
2892 1
544 1
3202 5
3545 2
2452 4
1435 2
1590 3
3731 3
1137 4
2120 4
2832 4
315 1
3354 1
3820 4
3278 4
2562 4
1364 1
2205 5
1683 3
2606 2
723 4
3484 2
887 2
1020 4
1647 3
668 1
4761 28
121 3
3628 2
257 2
136 2
1777 3
1923 4
2768 3
2786 5
91 5
2117 4
2172 4
3139 3
1377 4
3386 5
1967 5
3379 1
1979 4
2730 1
2262 5
1405 5
716 5
1074 2
3283 5
1560 5
3720 5
3298 3
3030 3
2138 3
8675 32
2802 1
2881 1
329 5
1537 1
3445 5
2275 3
539 1
879 2
3176 3
1824 2
238 5
1114 3
137 3
2675 5
1253 5
150 4
489 1
2938 2
592 4
579 4
624 3
1589 5
2546 4
3126 2
2980 3
3160 1
3195 3
3105 3
768 2
1958 1
730 5
2425 2
5728 78
2739 4
2188 1
3170 2
2873 3
676 5
3577 3
3842 4
1454 3
2477 1
3274 4
332 3
64 1
2412 4
747 3
2362 3
2902 1
1368 5
768 1
603 4
1999 2
1761 3
1783 5
834 3
603 2
237 1
1243 3
620 3
3208 1
2450 3
571 1
3243 2
2263 4
1264 5
1498 3
3374 3
3847 1
1422 5
2737 5
1218 3
2270 1
271 4
2373 2
1170 5
273 2
2237 1
782 5
1018 4
2088 2
3131 3
850 2
3785 4
3990 1
2325 3
517 3
3121 2
1347 1
2650 1
280 1
2002 1
141 2
1746 3
1716 5
671 5
1747 5
444 3
2656 1
3644 3
2137 3
2075 5
2214 4
1439 5
585 5
3631 5
610 2
2120 2
2222 1
2025 3
3332 2
1981 75
3199 4
26 5
1114 1
1203 1
2341 2
2255 5
824 1
465 1
485 1
2977 2
2431 5
2197 3
1665 2
940 1
3619 2
2427 3
2269 2
1374 4
2825 2
2984 2
2558 2
2422 5
1635 1
1493 3
37 2
3918 1
2269 2
3470 4
2686 3
1281 1
2144 4
1472 2
2863 2
3794 5
1773 2
3555 4
1070 5
63 1
1213 5
1528 2
2728 1
67 5
3910 3
1632 3
649 5
898 3
2971 4
3555 1
1917 5
3871 5
3180 5
371 2
1752 5
3306 3
2340 2
917 3
2629 4
3118 1
1575 3
1484 4
13 5
1718 1
1453 1
1520 5
1676 4
3410 3
1519 1
1105 1
213 3
2939 2
1946 4
674 2
1894 4
3463 1
540 1
780 62
3678 4
239 5
2089 5
850 4
3501 4
971 5
40 4
641 2
3188 4
3860 1
490 3
2058 3
676 3
2203 5
2817 2
2470 5
1414 4
3975 4
819 4
3969 5
1084 4
1689 5
3366 5
2430 5
2612 1
390 4
3174 1
1836 3
319 4
1415 5
1339 1
1981 4
2944 2
2605 1
2780 2
432 4
3865 5
2041 1
802 2
2487 5
3111 3
2866 4
1676 4
2484 1
1090 1
1833 5
485 4
1532 4
1769 4
3542 4
3414 5
1114 4
2094 3
2859 1
3975 5
2659 3
926 2
2072 4
2224 3
1298 5
1156 1
2446 1
9223 3
1421 2
465 4
1963 2
1882 32
3155 3
2933 5
2274 1
63 4
3048 3
2808 5
292 4
2026 4
1049 4
1071 1
821 4
3470 1
1429 3
3555 2
164 1
3170 4
221 1
2388 4
1713 4
3778 2
141 2
2230 1
3969 2
2372 5
3788 4
862 5
160 5
3553 3
969 1
1683 2
3947 5
1507 3
2596 98
3013 1
3047 5
2481 2
2079 4
322 3
1669 4
3767 3
2839 1
2768 5
1663 1
1291 5
1778 3
819 3
3825 1
2595 2
2922 3
852 4
1100 5
1858 5
1099 1
1929 4
1224 2
575 3
3027 2
3412 2
2013 1
376 2
3675 5
2217 1
223 1
3333 1
2769 1
1816 2
573 1
103 5
2204 1
437 1
430 4
3840 1
704 4
1201 4
657 1
2505 1
3474 3
534 4
1884 3
3543 3
1106 5
1577 5
2087 3
3700 4
3709 5
68 4
1499 1
299 4
214 5
1270 4
3427 1
1553 2
1200 5
3299 3
3008 5
439 3
1255 3
2143 5
45 1
3982 4
2682 1
596 4
659 3
3087 4
2744 3
2095 1
834 2
1773 2
2437 3
1468 1
264 4
1908 3
625 3
1210 2
2596 4
774 1
1591 2
1809 4
2614 4
3473 5
1603 5
231 2
1566 1
821 1
3426 2
1797 5
897 1
1910 4
106 3
2542 4
309 1
2106 96
1388 4
500 3
3032 3
2062 2
1539 1
3422 5
1352 1
3457 2
2881 2
1170 3
1308 4
2002 4
2550 3
465 5
561 3
1109 4
2931 5
2653 3
1931 4
3300 1
3710 1
3276 1
3314 1
2190 2
336 1
2674 1
3141 4
3408 2
1921 5
900 3
1018 4
1133 3
3967 3
2261 2
1203 4
2070 2
984 4
2677 5
429 2
2842 1
928 1
2759 3
2894 3
2110 4
2743 2
352 4
1368 5
3707 1
1973 1
3934 4
231 5
790 3
3700 4
1863 1
683 3
1243 1
3275 5
2030 4
2872 1
3687 4
3147 4
1725 5
2225 1
2551 1
101 2
3723 1
839 3
1897 3
330 3
1017 1
1166 3
2974 1
2964 3
3313 3
1141 2
152 4
3388 4
1856 1
3658 4
2161 1
3594 4
441 5
3099 2
1321 4
3151 4
441 4
1299 4
1461 4
417 3
2449 3
123 4
2548 3
828 5
1825 3
1161 1
244 5
9150 8
1537 1
3725 5
1098 4
1897 5
3543 3
1304 2
3809 5
2127 2
9561 0
2417 10
2110 4
3634 1
3226 5
271 1
2251 1
857 2
512 4
3699 3
159 4
3499 5
5396 61
1408 2
3225 4
263 2
2135 4
2435 1
1268 2
531 3
3565 4
666 3
3995 5
2305 2
2806 1
2466 3
3597 2
3722 4
3117 4
2742 4
1367 1
1545 1
1883 2
450 1
2750 1
3996 5
2132 4
128 1
2535 3
2983 2
434 2
1360 1
3764 2
1822 1
2562 1
1221 1
623 3
3781 2
3799 3
2360 5
1561 3
861 2
3719 5
2522 5
123 5
297 2
3657 3
1641 1
3089 2
2652 3
730 5
1929 5
3693 4
913 5
2291 2
2391 2
1978 2
3896 2
591 4
653 4
977 1
1973 1
2957 3
405 4
2489 43
46 3
3984 4
2212 4
35 2
3520 5
2748 1
2177 5
1513 3
3126 4
1544 1
3521 3
1079 1
3505 3
1458 2
2783 1
3669 2
1745 5
1505 2
3680 4
3785 5
217 1
1461 2
3609 5
1168 3
1780 1
2864 3
1935 5
3145 4
1032 5
1700 2
2191 1
3345 5
1724 5
243 1
3092 5
1306 2
2911 3
2052 3
2442 1
1957 1
2634 2
1521 2
1817 3
4134 64
1619 3
3013 1
2482 4
95 4
3909 5
1960 5
1068 1
2660 2
2734 3
2849 2
282 5
1396 5
2328 2
187 4
285 4
3343 5
3307 3
2063 5
1415 4
1993 5
3199 5
1027 4
3920 1
244 2
398 3
3828 4
600 1
650 5
843 2
3422 1
3380 3
3382 4
1470 4
827 2
306 4
558 4
3475 4
121 2
1623 4
2047 1
159 2
3754 1
3800 5
36 3
1238 3
2122 4
2572 5
8 3
3299 1
3276 4
4 4
3459 1
2122 3
2872 2
647 4
2467 5
3847 3
2267 5
2623 1
640 5
2463 2
1533 1
616 5
1427 5
1420 35
3518 5
1240 1
2910 3
3259 1
3456 3
3402 3
1415 2
493 5
3598 3
2687 2
3679 2
3350 5
2536 3
3455 5
230 4
1368 4
1611 2
3427 2
1967 1
2653 2
3294 4
3695 2
2006 5
1093 5
6 3
2192 4
1280 1
1599 3
1857 5
129 3
3583 3
2537 1
103 4
2066 3
999 1
5477 53
3476 5
1704 1
780 4
3788 1
2927 3
1173 4
223 1
21 1
175 1
869 1
2348 3
1303 5
1367 5
1223 3
437 2
3713 4
2361 5
2098 2
564 3
630 2
568 2
48 4
1277 5
3221 5
1272 1
1560 1
3845 4
2069 2
2581 3
279 3
1411 3
3634 4
1760 3
3615 3
319 5
2517 4
2750 1
2028 1
3335 1
1476 5
2040 3
576 1
2249 4
3446 1
2638 5
199 1
419 5
523 2
1914 5
1205 2
733 4
3470 3
2988 2
5961 79
3448 4
3631 4
721 2
3370 1
3554 2
151 2
3242 1
2943 4
532 3
2542 2
3953 5
1028 3
170 2
870 4
2697 4
2534 3
2414 1
3982 1
3074 1
2807 3
3221 2
817 4
9 5
2827 1
3927 5
3336 5
1818 2
1620 1
1564 4
2200 5
3569 3
3460 3
3601 4
1820 2
3496 4
1300 3
639 2
1883 3
2579 2
1187 4
2780 5
2736 4
1589 2
3288 1
3197 5
117 4
2571 2
1451 1
3369 1
1196 2
951 2
2285 5
963 4
2236 2
1227 1
2397 4
647 1
955 5
2192 1
1740 2
2432 3
504 3
2135 2
3525 1
1927 1
1072 5
3567 3
466 3
3874 4
421 3
2826 2
1457 2
301 5
2412 1
3004 4
231 1
2710 5
2789 2
3392 4
386 66
3736 1
900 2
3829 2
182 5
770 4
1505 2
3771 2
3771 2
1724 3
3267 2
2684 5
2866 2
935 3
2589 4
670 4
2349 2
1761 1
59 3
964 4
1995 1
842 3
2032 4
2812 2
1035 4
688 3
1967 3
149 1
1116 2
2838 1
2114 4
990 4
616 4
61 2
1043 5
1267 1
3461 2
2887 5
3072 2
3997 1
2938 3
1110 4
55 1
2439 5
3397 5
873 3
1487 2
2675 4
1316 4
3128 2
463 3
1746 1
3206 5
2118 2
2682 4
3438 4
2798 1
3226 2
2508 4
373 5
3292 2
118 2
162 5
3584 3
2231 2
186 3
3809 5
7369 18
2915 4
1994 1
3902 3
271 1
2329 4
2254 1
1512 1
3444 1
574 1
2637 2
2706 5
2564 5
1635 1
3981 1
1384 5
1160 1
1439 5
2949 3
1030 77
390 4
3067 1
98 3
1620 5
2085 2
3103 3
3279 2
3293 5
3095 2
1295 4
3073 2
3078 3
3679 2
3384 1
2207 4
2198 1
3228 1
1590 1
2545 1
2867 4
1753 5
1703 1
480 1
3225 2
2626 1
3353 4
3548 3
2282 5
3297 3
2556 5
1983 3
450 5
2720 5
887 4
1247 5
2246 3
2425 4
29 5
1646 1
3182 5
123 3
2673 4
1315 2
3599 4
2970 1
2465 2
3611 2
2514 4
952 1
3947 5
3505 3
1196 2
2491 4
1185 1
1181 1
1111 3
3603 5
2029 3
736 2
1879 4
485 5
1009 3
3256 3
2778 2
2921 2
2756 4
1267 5
706 3
1878 2
244 2
2959 5
1417 4
1136 1
3477 2
1775 3
2280 2
2049 2
2167 42
3161 1
1862 3
911 1
858 4
1271 2
2285 3
3804 5
2910 3
234 4
1674 3
474 1
3944 2
3560 5
1211 5
2214 3
3263 1
2808 4
3806 1
2444 5
2598 3
2577 4
3213 2
3762 2
2197 4
3503 5
2067 5
1723 3
2928 5
936 2
3241 5
1463 4
522 5
330 5
692 3
1342 5
3190 4
523 1
3354 5
1580 4
630 1
1772 3
1762 1
4893 76
1480 1
1531 3
1494 1
3575 5
3966 5
2694 2
3733 2
298 3
1010 3
2029 5
1455 3
2265 3
1042 4
1131 2
3883 4
3844 3
533 2
2434 1
1070 1
40 1
2969 1
2044 1
3825 1
1975 1
3512 4
1548 3
3611 1
3401 3
3849 2
3455 2
2719 3
1796 4
1376 3
1628 2
2942 1
3833 5
1105 2
962 1
569 1
2114 2
3291 2
1750 1
3825 1
3553 5
2033 5
107 4
3009 4
706 5
3188 5
3182 4
353 1
742 4
1241 4
3089 5
991 1
2945 4
1566 2
3534 4
1843 1
1415 3
2797 3
1331 4
480 2
2893 1
721 2
2147 4
1439 5
3233 5
1294 2
1192 3
226 2
2918 1
1181 2
3182 3
2241 1
3603 3
1323 64
3545 5
3672 5
3318 3
863 3
1817 4
1055 2
1685 2
74 4
985 1
3364 5
2443 4
3056 1
271 1
2923 1
3036 3
1157 4
1395 1
1370 4
1573 3
2528 2
885 1
1142 3
1931 4
1797 1
1867 5
3520 2
2407 1
2636 5
223 3
2902 3
3653 3
1838 1
1591 3
2112 4
2143 3
2903 4
573 2
1948 2
1964 5
2121 4
1607 5
490 5
215 3
3042 2
1034 2
3694 4
2706 2
1734 4
1442 1
3810 5
835 1
2963 2
3460 5
614 2
1005 3
1252 5
374 1
2975 3
1569 5
1376 2
312 5
3641 2
3657 4
3664 1
9291 98
1386 3
2536 3
867 5
1961 1
3418 1
567 2
2279 2
3466 2
2232 3
3621 2
341 4
1732 4
3652 3
2410 3
2838 5
3139 3
3790 3
1274 2
22 4
2489 4
2550 1
1164 2
698 3
2432 5
2368 1
3240 5
2688 5
3744 1
2711 5
2006 3
2835 3
2122 2
3523 1
3984 5
2980 1
38 4
2230 4
2708 2
2183 5
2560 4
3895 5
3961 4
3122 3
1274 4
1856 2
3731 1
1127 2
17 2
1598 1
896 1
2824 2
2105 4
2487 1
685 4
2654 4
1570 4
1395 4
1131 5
1233 3
3051 1
2386 5
833 1
984 5
865 4
1201 1
3157 3
3398 2
1782 3
3128 4
2552 1
2061 1
329 1
1650 2
674 1
566 4
3025 4
2856 4
3168 2
705 4
2419 4
2496 3
2634 2
3891 5
128 5
3232 3
1151 4
3151 4
1451 4
3642 2
385 1
2552 4
3862 4
3265 2
1246 1
117 2
2579 1
2295 4
1209 4
7661 46
1555 1
367 1
3556 5
535 2
669 3
3834 3
1087 5
814 5
143 5
681 5
1103 5
2108 2
3760 1
1596 2
2938 5
2656 5
1837 4
3900 2
2890 3
2750 2
1314 3
1315 5
1319 5
3700 5
2909 4
3553 2
1528 2
44 5
2413 4
2959 5
1564 3
2546 1
1339 1
1145 3
3584 3
138 4
2829 2
3649 2
3931 4
2312 5
431 4
3202 2
228 5
300 1
1237 1
343 5
3786 83
2552 5
2037 3
3141 1
3942 2
3221 5
1081 2
3620 4
2568 1
201 4
500 5
1659 5
3352 2
3719 5
1920 3
3739 3
3653 4
2759 3
2338 1
365 4
1528 1
1752 5
2453 5
322 4
7 2
1073 2
628 3
1936 3
1392 4
918 5
2419 1
3157 2
3651 3
464 5
165 5
971 5
764 2
1003 4
797 1
939 4
2197 3
1660 3
1445 5
3155 3
1602 1
2499 3
1081 2
2795 5
3921 1
3070 5
789 5
2128 2
3466 2
1119 5
453 2
1417 4
771 4
1825 3
3375 5
1402 5
1404 3
1700 5
1906 4
3566 4
103 1
1910 2
3379 3
2794 2
3166 4
3457 4
2672 5
2971 3
301 2
1656 5
2126 5
1003 4
3309 4
2364 4
3547 4
3392 1
1268 1
1595 1
1338 3
193 3
7842 68
1177 4
874 2
3115 2
1293 4
1200 2
530 4
3299 4
1607 3
1404 5
647 5
1857 5
2447 4
3263 1
3838 1
991 5
3456 5
513 4
2665 4
1502 2
1100 4
3727 3
1607 5
1819 3
1744 3
718 2
368 5
656 4
2377 5
2950 3
3725 4
3406 2
3162 2
3860 3
3897 1
2135 3
765 1
2977 3
1942 1
1936 1
369 2
2427 5
1578 2
3903 4
3703 4
2520 4
3848 2
2958 2
2194 4
1187 4
881 2
3790 3
2237 3
720 1
3561 4
215 5
1659 5
1018 3
2426 4
3894 2
475 4
1907 3
689 4
3683 5
385 5
2028 4
541 3
3615 2
583 2
5361 38
3341 5
776 4
2866 4
939 3
3416 2
3772 3
3597 1
564 3
2894 3
224 3
1818 4
896 1
420 3
1487 2
1547 4
1848 5
1018 2
2238 1
1120 1
1527 1
8 1
426 3
3327 5
242 1
1939 1
1499 2
3067 1
2466 1
3959 1
839 4
1800 5
2392 4
2014 5
3405 4
156 3
3668 1
2580 4
120 5
5421 81
478 3
1529 1
183 1
1073 5
433 5
3655 1
2888 3
661 5
624 4
2259 1
2159 3
1310 4
2929 3
2623 1
2498 5
112 5
1187 1
1303 5
2587 1
721 1
3758 1
993 5
2181 5
275 1
1031 1
3535 3
1299 4
1367 4
1084 4
3979 1
1100 2
2909 5
2082 3
358 1
2586 5
390 3
1805 1
1340 4
3739 2
3493 2
851 5
310 2
223 4
2728 3
2368 3
1591 3
3147 4
2456 4
710 5
2599 4
243 2
2342 5
1426 2
2736 4
2000 4
2285 3
1606 2
1351 2
974 5
3838 5
3839 4
3512 3
2279 5
917 3
781 3
2986 2
3207 3
3422 3
1713 2
2147 4
1088 4
3265 4
3730 3
1225 2
1748 3
396 2
2841 1
571 5
2227 4
458 4
1705 4
3619 13
1123 1
1894 1
3014 5
3250 3
1176 1
3146 4
3481 5
1959 5
1783 3
2814 2
2966 3
2094 1
1574 4
1415 16
2346 5
541 1
2492 3
2654 1
3178 2
2310 3
417 3
1609 5
1824 4
1828 3
2274 3
580 1
728 1
3134 3
1576 3
2283 2
8432 28
3389 5
1960 2
3424 4
297 5
2194 3
3539 3
1313 3
3370 4
1671 5
133 5
3585 5
1275 2
3865 5
3808 5
3122 4
2025 1
98 2
1256 1
1825 3
1605 2
2616 4
3821 3
2856 3
3419 2
1536 3
3127 1
763 2
893 3
6672 6
3829 5
3582 4
1585 3
2188 4
3551 2
743 5
1373 94
3001 3
3637 5
96 3
3085 1
2958 3
3806 2
3316 5
1050 3
1749 3
1993 3
3082 5
1009 4
3121 5
1634 1
2418 3
3573 3
2922 3
3626 1
2616 4
1703 5
1273 4
1645 3
2205 4
3858 2
276 3
1282 2
2130 3
979 2
3553 2
1817 4
1683 2
91 4
949 4
324 3
3130 2
1842 1
3533 4
1342 1
2884 4
2393 1
3752 5
2869 1
2668 4
187 2
3162 2
1245 3
3743 4
1799 5
1403 4
960 2
499 2
1285 1
2638 3
2471 4
881 2
1033 3
1240 5
3570 1
99 2
2830 1
1759 5
455 4
1761 3
2896 3
726 5
46 2
3359 4
1606 2
1012 2
3870 3
1642 3
2877 2
1154 1
3140 3
2553 2
863 1
2395 3
2516 2
3569 2
21 3
1970 4
1869 3
2099 3
3676 1
253 1
1355 5
798 4
1126 3
3380 1
3554 2
2938 2
2947 1
1732 4
2190 4
2512 14
1945 5
2627 5
3225 3
3638 2
539 5
2797 2
2487 3
2475 4
1897 3
229 1
490 5
1866 1
849 1
1249 4
3128 53
1599 1
3073 5
3358 2
1654 2
1548 2
3589 4
437 4
290 5
2039 3
1469 3
339 5
1785 3
1393 1
2505 1
2375 3
168 5
3649 1
902 5
1888 3
3057 2
1803 1
131 5
1071 4
1501 2
3661 2
2081 4
1278 5
2555 2
3202 2
2014 4
1163 4
2254 4
2125 4
521 2
2766 3
3800 2
2573 3
3158 2
1054 1
3457 5
331 4
1065 4
2105 3
630 5
1030 4
3587 5
1528 3
3356 2
2050 3
17 3
3805 2
2086 1
449 4
3002 55
2605 2
2568 2
420 5
542 4
3603 2
535 1
518 5
3529 3
3016 5
2049 4
3463 5
2584 5
2232 4
2348 1
2264 1
534 3
3955 5
154 3
3437 1
3602 5
2218 1
375 1
960 5
1131 3
3138 5
1392 5
1596 1
2219 5
995 3
2508 3
2693 5
829 1
2494 4
3724 4
2029 2
1672 1
3813 3
3684 2
1949 3
1099 4
345 2
3687 5
2816 1
1768 2
3527 3
3772 2
19 4
1217 3
2286 4
1145 5
617 1
1615 2
863 2
1906 5
2816 1
9187 48
1846 5
1452 2
2896 1
823 1
197 2
640 2
2251 3
3431 3
3499 3
1906 1
3392 3
1249 2
1522 1
3768 1
2861 2
3848 2
655 1
1719 5
870 5
1971 3
191 4
1986 2
1169 1
3681 3
2343 5
1487 1
1457 1
3043 2
2592 5
3666 1
3179 2
2510 1
1165 3
3383 3
3120 1
156 5
1019 1
2103 1
3909 4
3558 3
3720 3
1041 4
130 2
506 3
3245 3
525 4
389 5
2608 4
2491 93
642 2
398 2
2394 3
3290 1
3955 2
2631 5
2505 2
908 1
3879 5
3979 4
462 1
1611 4
1998 1
371 4
255 2
3650 3
2714 2
2046 3
1463 3
1956 5
885 4
1281 3
3288 4
3285 5
3928 3
254 3
2838 4
1374 4
215 3
2144 1
2078 4
1717 4
2193 2
2251 2
1449 5
1776 3
1495 5
2425 3
1947 5
652 4
1323 4
2615 5
3121 1
1700 5
2436 5
155 3
1988 3
1656 4
1985 5
187 1
815 5
2469 4
1721 5
3444 3
2953 2
1892 2
1704 1
788 1
846 4
510 2
2681 3
145 4
3239 1
1552 1
2058 1
1360 5
403 3
1182 4
1073 3
2141 2
1423 1
653 3
890 1
301 5
278 2
1719 5
1826 5
330 1
16 1
2991 4
323 5
1297 1
179 1
3200 5
3806 1
1276 1
1725 1
1058 5
3719 1
1053 1
2872 3
3658 3
1338 2
1778 66
2572 5
130 5
1805 2
324 1
608 3
3586 3
1215 5
2697 3
3493 1
2257 5
1817 3
3911 4
2783 3
1737 5
258 1
2177 1
1655 2
2780 1
84 5
1794 3
2625 3
1807 4
2944 2
3482 4
610 1
2350 3
1398 1
3113 5
2531 1
653 1
1401 1
2322 4
1487 1
2515 3
555 2
3316 5
2039 1
3722 2
1977 4
3769 4
1293 1
1363 5
730 1
3223 3
2028 2
2752 5
3055 4
2484 5
2877 3
3166 5
2009 1
2962 1
3955 4
1732 5
2238 1
869 2
322 3
2573 1
3058 3
1014 5
2021 3
866 1
1190 2
2672 1
1050 2
3849 4
7273 57
3809 2
2197 1
3258 2
96 1
668 1
2709 2
2171 5
1386 3
3555 4
3301 3
1537 5
120 3
1261 3
2396 1
1283 4
271 2
744 3
3334 4
3604 2
479 4
197 2
3863 2
1657 4
2255 1
1358 1
1983 5
2749 4
3453 4
327 4
1470 1
1969 4
3051 5
558 5
3066 1
2517 3
784 1
3435 5
1784 2
2599 1
2653 3
1944 1
3202 5
3441 3
701 1
1558 2
1727 5
261 2
2591 2
3864 5
1683 3
1903 2
2149 3
3816 4
2779 2
321 4
2722 2
2418 4
4341 49
1280 3
1624 4
2530 3
2716 5
478 1
312 3
17 4
3777 4
812 1
3960 5
1856 4
3393 3
521 1
792 4
388 1
1148 4
107 4
1208 4
2825 2
1779 3
1932 5
700 5
84 3
219 1
2401 2
2577 3
3267 3
3136 4
434 5
3430 2
25 3
3544 2
52 4
3472 1
674 2
2883 5
3339 2
905 2
57 4
1372 3
1652 2
3065 4
2269 3
1057 5
2478 3
227 1
1415 4
3337 5
873 1
8119 86
57 1
854 1
3509 3
3521 3
2880 1
2374 3
841 3
1801 5
341 4
2163 2
3695 3
1672 2
2863 4
2926 5
168 5
1632 5
3547 1
323 1
243 1
2973 1
1088 5
357 1
3136 5
1740 2
1366 3
2646 5
2996 2
2872 4
2028 3
1593 2
1768 2
3475 4
1709 5
722 4
344 4
1778 4
1039 3
62 4
643 1
354 4
2408 5
123 1
19 5
3612 4
790 3
1297 1
780 3
224 3
1271 5
1143 5
638 2
3749 2
1758 3
2906 3
2316 2
1463 4
2961 5
2829 5
578 4
1728 2
348 2
276 1
498 4
670 4
1795 1
87 5
1436 4
812 5
349 5
2296 2
3327 1
90 3
1342 2
1617 5
2062 4
3638 4
3072 1
591 3
764 4
1689 2
3776 5
1694 2
1962 4
1108 5
2573 2
1678 4
95 70
185 4
1389 5
3125 1
1496 2
2914 2
3027 2
488 4
1115 2
3051 3
655 3
2806 1
3600 3
1629 3
3668 2
422 1
1777 1
387 1
2758 5
3318 3
2625 1
1524 1
2086 3
2496 1
891 2
794 3
2994 5
512 1
3864 5
1117 2
2150 3
3415 5
2496 1
3090 1
3664 5
2562 4
989 5
994 1
2448 1
2977 1
1738 3
1234 3
73 1
3676 2
589 3
171 4
3033 3
2663 5
3738 5
3837 4
862 3
2744 3
2835 2
1627 2
3577 3
972 5
1077 1
2749 1
302 2
1789 1
3919 5
3979 4
1896 3
1535 1
744 5
1737 1
120 2
158 5
568 5
237 1
3091 1
6472 48
3765 2
2020 4
3684 2
1308 4
2119 4
3257 2
279 4
1998 3
2513 5
3331 1
565 4
1938 1
1976 2
1627 1
86 1
1585 5
1400 2
620 4
3764 4
1389 3
3566 3
2248 5
2139 1
1570 3
683 3
3987 3
1093 5
3083 1
1154 5
486 2
1201 1
1792 2
2377 5
35 2
691 1
23 4
2420 3
803 2
3219 4
1561 5
3977 2
1501 2
3823 1
840 3
1644 3
2918 2
98 1
1796 4
448 60
1319 5
3253 2
1121 3
314 3
2583 4
648 3
3434 3
1690 1
2396 1
2220 4
3191 5
912 4
3411 3
3168 1
539 1
3388 5
3153 2
3549 2
1016 4
2549 3
3395 3
3741 3
523 5
465 2
3997 3
2504 4
2899 4
1998 2
1128 5
3867 5
156 3
3875 4
2598 4
3934 3
3285 3
3563 2
2029 4
1858 3
1436 1
1820 4
1358 4
1322 5
442 3
2917 4
835 1
3938 4
2389 1
651 2
3235 1
951 4
3065 1
1550 3
167 5
3995 4
2785 2
3385 1
2840 2
1101 3
376 1
1553 3
5480 20
2552 1
1654 1
2879 4
137 5
111 4
341 3
997 2
1770 2
2460 3
3508 4
1047 1
3253 5
2332 5
2869 5
1541 5
1727 1
3913 5
350 2
972 1
2971 2
3354 66
3445 3
169 5
3082 4
2120 5
1175 2
1641 3
2369 4
758 2
208 2
3257 1
3447 1
2018 2
2664 1
634 4
422 5
1297 2
3116 1
1431 3
797 2
1490 2
3772 4
3454 2
3806 5
3377 4
3214 3
2299 5
2858 2
2807 3
8 2
3508 3
1169 1
998 1
2973 4
2832 3
2682 2
2797 4
155 5
944 5
2813 5
325 2
9 3
1389 3
3642 1
739 3
692 4
781 1
1402 5
2495 3
557 1
1199 1
1999 3
2042 5
2597 1
2465 3
361 4
139 4
1763 4
3587 4
2426 4
1404 5
923 4
1328 4
313 1
3753 4
1500 5
107 2
6165 78
2707 1
2190 2
1303 2
312 5
3271 1
3319 5
3830 2
3533 2
1917 1
121 2
3482 5
3770 4
1303 5
538 4
1471 1
261 3
1377 2
1700 5
1000 1
471 2
438 2
3830 1
2589 2
2204 2
521 1
102 5
3110 2
3588 1
1492 2
2172 5
1960 4
3842 5
1234 3
2718 4
3905 5
3206 5
32 2
960 5
2749 1
3478 1
1840 4
3622 1
3801 4
1712 2
38 4
1309 3
3019 2
1684 1
3044 3
3189 1
292 5
3993 2
2133 4
3296 4
819 3
853 3
2703 5
310 5
388 5
851 1
2256 5
2422 4
3661 4
1878 2
1210 4
2355 2
3813 1
2176 2
3651 2
3530 1
243 4
3831 2
1208 2
2504 5
2161 5
2020 1
1864 3
2393 3
5394 43
932 1
1689 5
663 2
1633 3
149 3
309 5
2456 3
412 3
552 1
2425 4
3566 5
2760 2
2056 2
3081 5
2851 4
719 1
3843 3
3069 2
259 5
3694 3
3040 4
789 4
1257 5
3780 5
2818 3
1214 1
3845 5
671 5
1299 2
2700 1
432 2
284 5
2528 1
1482 4
1108 3
3897 5
1529 2
1641 5
1884 2
1296 2
680 3
3788 1
3185 1
6170 18
561 3
984 4
1948 4
1969 4
1322 3
3965 5
976 5
2576 1
897 4
1992 4
2692 2
537 4
2499 1
246 1
1485 3
2518 5
1903 5
3388 3
2674 57
1029 1
1157 5
1926 4
1206 3
988 4
1422 5
1586 5
2970 3
3836 2
2797 4
3151 3
157 4
2678 3
1521 1
2613 3
125 4
2488 1
986 2
3414 1
1619 2
646 1
3732 5
3504 3
1057 2
522 1
124 5
838 2
1692 5
2691 1
2285 4
3259 3
1295 4
3690 3
2863 1
824 5
3856 1
3872 4
403 4
2992 3
3418 4
1664 3
3537 1
173 1
2368 5
1495 3
517 2
3061 3
2850 3
443 2
2557 3
2193 3
3438 4
2702 5
1792 1
1299 1
1558 4
1102 4
3949 95
3025 4
488 4
1186 4
1271 4
3518 3
3699 3
2185 1
1930 2
1370 4
2793 3
1208 4
2469 1
2497 1
2172 1
1824 3
1223 1
871 3
1367 5
3065 1
3005 4
3461 2
2894 1
1662 2
2726 4
2191 2
3455 5
2806 3
2255 5
2652 4
1603 1
763 5
1323 5
534 4
41 1
2381 3
2179 1
2101 4
190 5
2248 4
3145 2
1137 3
3835 1
1225 4
1947 1
2867 2
351 4
2725 4
1614 5
1417 5
3207 5
700 3
2343 2
3161 2
3265 2
1799 3
2197 2
2064 2
3580 3
824 4
3517 3
1426 2
3670 4
2596 2
111 1
3290 2
161 4
1405 1
3492 3
1387 3
2677 3
2221 2
2823 4
3608 5
3925 4
631 1
472 3
11 3
2909 4
2129 1
2970 4
3039 3
2110 2
1985 5
1712 3
1060 3
3259 1
1966 3
3917 3
1186 3
2004 1
3633 1
223 2
3320 5
2953 3
2853 5
6528 16
1755 1
2685 3
3630 1
3813 4
1489 2
674 3
2207 4
1378 5
782 4
1911 3
2560 1
1112 5
1967 1
31 1
2689 4
3061 4
9227 1
886 1
9847 44
2651 4
473 4
3787 4
265 2
2775 1
1249 3
2163 1
3170 3
2390 2
42 4
2659 5
2371 1
3526 5
3465 4
1608 1
1461 5
2643 4
3934 1
1317 1
296 4
1596 1
1128 4
1703 1
89 5
2138 3
2864 5
3212 1
2867 4
1584 2
3500 1
992 4
3802 2
3597 1
2766 5
285 3
1356 4
957 3
2343 3
3132 2
3104 1
2912 1
2769 4
3553 4
1212 5
AC output:

Code: Select all

38
47
25
17
31
58
41
12
18
67
17
21
63
33
25
41
8
43
27
50
49
34
81
66
25
41
4
20
40
33
65
33
14
46
61
50
43
45
17
43
44
34
25
27
49
44
31
13
8
21
39
34
16
0
11
39
14
56
19
39
46
11
18
18
19
30
20
62
59
42
55
34
49
9
4
31
14
23
15
42
29
49
34
18
42
47
79
1
39
8
24
43
59
40
26
27
39
22
1
50
Your output

Code: Select all

38
47
25
17
31
58
41
12
18
67
17
21
63
33
25
41
8
43
27
50
49
34
81
66
25
41
4
20
40
33
65
33
14
46
61
50
43
45
17
43
44
34
25
27
49
44
31
13
8
21
39
34
16
0
11
39
14
56
19
39
46
11
18
18
19
30
20
62
59
42
55
34
49
9
4
31
14
23
15
42
29
49
35
18
42
47
79
1
39
8
24
43
59
40
26
27
39
22
1
50
Acc output

Code: Select all

..
49
34
18
..
Your output

Code: Select all

..
49
35
18
..

Re: 10819 - Trouble of 13-Dots

Posted: Thu Jul 31, 2014 2:36 pm
by just_yousef
Solved,, Thank you :D

Re: 10819 - Trouble of 13-Dots

Posted: Wed Sep 03, 2014 5:40 pm
by raj
Is this problem solvable with top-bottom techniques? If not then why?

Re: 10819 - Trouble of 13-Dots

Posted: Thu Sep 04, 2014 1:07 am
by brianfry713
raj wrote:Is this problem solvable with top-bottom techniques?
yes

TLE: 10819 - Trouble of 13-Dots

Posted: Fri Sep 05, 2014 12:10 am
by raj
Need Help. :(
Getting Time Limit Exceeded

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
	public static BufferedReader k;
	public static int dp[][];
	public static int[] weight,value;
	public static int budget;
	

	
	public static int knapSack(int i,int w){
			
			if(i==weight.length){
				return 0;
			}
			else{
				int max1 = 0,max2 = 0;
				if(dp[i][w]!=-1) return dp[i][w];
				
				if(w+weight[i]>2000){
					if(w+weight[i]-200<=budget){
						max1 = value[i]+knapSack(i+1,w+weight[i]);
						max2 = knapSack(i+1,w);
					}
					else{
						max2 = knapSack(i+1,w);
					}
				}
				else{
					if(w+weight[i]<=budget){
						max1 = value[i]+knapSack(i+1,w+weight[i]);
						max2 = knapSack(i+1,w);
					}
					else{
						max2 = knapSack(i+1,w);
					}
				}
				
				return dp[i][w] = Math.max(max1, max2);
				
				
			}
			
			
	}
	
	
	public static void fill(int [][] array, int element) {
	    for(int[] subarray : array) {
	        Arrays.fill(subarray, element);
	    }
	}
	

	
	public static void main(String [] args)throws IOException{
		k = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter z = new PrintWriter(System.out);
		
		String line;
		while((line = read())!=null){
			StringTokenizer s = new StringTokenizer(line);
			budget = Int(s.nextToken());
			int n = Int(s.nextToken());
			weight = new int[n];
			value = new int[n];
			if(n!=0){
				int total = 0;
				for(int c = 0;c<n;c++){
					StringTokenizer ss = new StringTokenizer(read());
					weight[c] = Int(ss.nextToken());
					value[c] = Int(ss.nextToken());
					total += weight[c];
				}
				
				dp = new int[n][total+500];
				fill(dp,-1);
				
				knapSack(0,0);
				z.println(dp[0][0]);
			}
			else{
				z.println(0);
			}
		}
		z.flush();
	}
	
	
	
	
	
	
	
	
	
	
	
	
	public static int Int(String line){
		return Integer.valueOf(line);
	}
	
	
	
	
	public static String read() throws IOException{
		return k.readLine();
	}
}