10273 - Eat or Not to Eat?

[johnnydog33]

Delete after AC

[Monsoon]

I think your program is correct but you have problems with boundary cases, exactly i noticed that your program have problems when amount of milk is equal to zero..., but maybe i am wrong

[johnnydog33]

I made a stupid mistake----Is that 2520 days really enough? I am wrong.
Because we need to simulation about 3000 days to get right answers. Some cow will be eaten in second 'round'.

Now I get AC, thanks

Tips: Heap is a way to get AC

[Imti]

I used almost rude simulation to solve the problem which results in run-time of 0.712 seconds.I did another silly task in my code.At first I was breaking loop when M consecutive days can't remove any cow.But I discovered a case at which my code produce wrong answer.Case is:

Code: Select all

1
3
4 4 2 7 9
3 4 3 2
3 4 2 2

and output is

Code: Select all

0 8

But when I increased my loop breaking condition to 500,It gave me accepted..
As I know this is not a valid process,Someone would please explain when and how we can decide that further increase of day would not remove any cow??

[VSZM]

Hello!

I have been trying to solve this problem, but somewhere my code fails. I have tried to come up with some good test cases, but for all of them my code works well -I think-.

Can you guys give me some good test cases please?

Also here is my code: http://pastebin.com/P7KZrrPr

[brianfry713]

You can generate output at:
http://www.uvatoolkit.com/problemssolve.php

Input:

Code: Select all

1
562
7 59 145 96 11 151 31 30
5 172 87 199 244 105
4 88 235 76 25
3 130 53 221
10 156 219 166 61 80 246 142 95 118 36
9 130 0 36 224 220 208 60 168 14
9 19 103 214 160 192 85 103 58 55
7 214 88 81 24 232 76 166
10 195 15 145 138 15 181 175 235 202 48
1 216
8 49 68 54 209 9 203 61 67
8 227 94 159 58 118 140 198 97
5 206 112 239 93 192
8 81 240 184 130 19 213 221 68
5 24 90 168 227 215
5 47 192 79 20 250
9 224 197 108 3 153 221 55 59 226
7 141 215 221 84 234 248 54
1 92
3 205 9 118
2 58 229
1 202
7 174 213 223 184 70 39 86
3 95 210 79
4 164 44 167 248
5 164 115 207 69 6
8 142 124 144 201 166 4 216 165
10 178 137 176 61 240 75 166 84 34 58
8 11 166 197 8 7 174 187 27
3 193 188 198
6 82 148 46 150 113 24
3 104 225 67
2 214 142
1 48
1 203
4 1 183 88 74
3 75 10 30
1 17
2 78 147
2 227 6
5 153 30 32 7 4
6 237 219 54 195 80 44
4 222 110 143 123
2 146 198
9 240 78 24 21 156 236 11 196 242
8 163 86 184 234 154 96 33 186
7 228 79 72 188 50 182 145
8 179 40 184 187 94 75 211 115
7 196 126 241 1 92 217 87
9 200 54 186 233 241 214 210 69 35
4 184 31 106 170
9 210 104 210 53 179 235 232 37 180
8 28 245 13 58 81 102 8 136
4 54 190 64 78
9 164 39 192 8 209 112 31 232 29
2 35 21
5 80 59 32 65 151
3 142 209 172
9 30 121 159 85 60 224 163 69 201
9 10 209 37 186 53 18 215 172 117
9 211 11 45 57 76 196 84 219 154
6 26 185 127 185 83 0
10 59 69 236 138 144 194 175 79 61 6
2 233 124
10 7 135 203 64 24 212 148 56 179 217
2 177 157
8 9 158 116 68 40 102 19 184
2 194 77
4 201 185 30 138
9 37 86 108 101 174 69 62 231 248
7 190 239 250 84 248 157 14
9 10 180 149 195 102 157 85 86 171
4 116 58 175 217
7 96 131 131 165 193 175 226
8 115 214 97 199 25 67 213 219
3 142 117 22
6 87 107 144 7 190 73
7 178 39 86 23 170 31 1
6 206 227 23 70 4 121
7 93 188 109 61 15 1 242
9 59 79 21 16 86 211 89 216 138
1 115
1 111
3 226 100 102
6 123 236 20 244 68 113
10 178 174 10 243 165 112 115 57 133 131
6 158 33 173 109 225 37
9 85 248 59 249 99 75 121 148 159
1 30
1 110
3 8 120 13
2 45 192
10 179 72 1 150 169 238 8 143 89 92
8 86 216 39 249 104 160 210 13
5 240 98 198 10 171
7 87 158 113 28 15 105 164
3 4 82 132
10 225 221 169 15 120 198 118 182 52 28
7 65 116 131 227 64 142 147
3 229 118 58
1 134
1 235
8 232 67 160 122 41 195 41 121
3 52 239 60
5 80 202 233 197 82
1 74
5 106 19 80 225 141
3 172 118 135
2 164 202
1 35
5 181 140 242 59 193
6 119 110 124 134 93 134
7 116 21 67 222 40 211 9
2 111 181
9 59 7 26 75 245 61 196 175 15
5 47 21 43 166 131
3 49 37 178
4 153 199 210 189
2 170 198
6 94 193 96 153 200 122
4 194 247 173 183
1 173
6 96 217 210 228 10 72
1 189
9 168 137 174 170 126 157 117 173 0
1 18
10 137 204 195 80 13 182 76 89 168 56
3 198 15 226
7 151 54 147 116 35 33 39
8 223 10 135 145 10 8 227 228
3 180 237 38
7 168 115 96 149 235 94 97
1 134
4 214 188 202 79
8 48 183 241 21 193 125 230 16
4 207 245 91 200
10 194 207 25 122 116 174 170 24 20 233
6 139 9 159 154 153 195
10 149 185 37 155 123 16 171 70 36 229
6 237 22 168 6 47 103
1 35
1 211
6 68 246 8 142 154 162
10 162 114 6 160 151 161 32 232 81 102
6 60 77 67 146 58 74
4 226 10 42 61
8 161 194 29 169 85 247 145 193
4 8 199 131 224
6 163 18 3 79 35 127
5 103 23 91 241 30
6 0 136 192 98 46 135
3 29 33 187
3 39 222 246
3 102 32 160
8 50 227 157 150 104 190 2 191
1 56
8 161 56 234 166 218 29 114 158
5 147 158 45 186 129
4 237 44 73 210
8 188 0 93 87 168 32 153 108
5 209 206 102 78 189
6 45 31 132 16 154 92
5 199 92 116 53 78
3 191 102 95
4 102 188 215 19
5 117 191 225 139 210
3 217 212 158
2 56 39
8 210 195 78 223 36 194 25 179
10 216 94 75 157 9 13 185 28 111 51
2 85 190
10 162 220 16 69 231 72 172 71 96 180
5 132 30 156 157 209
3 187 52 212
9 125 38 92 153 149 207 249 47 211
10 22 180 133 155 225 18 140 109 114 70
9 246 100 228 217 122 178 217 238 139
10 112 241 28 14 203 236 76 250 196 193
8 125 75 177 99 157 131 22 85
10 94 144 50 135 110 172 62 140 159 14
8 20 68 105 98 20 90 238 20
10 180 106 225 68 96 137 225 227 223 59
4 66 204 40 202
8 25 77 81 248 156 158 81 224
10 179 245 167 230 78 15 159 248 53 227
7 4 15 134 227 138 188 107
3 229 122 32
1 199
6 65 104 84 210 142 160
10 136 140 182 27 156 91 24 22 131 245
2 210 192
1 98
9 238 2 172 109 98 239 57 211 117
8 108 77 181 18 93 130 158 24
7 127 115 245 214 60 239 53
5 245 184 181 124 171
4 45 29 31 97
2 56 28
1 164
1 120
1 11
2 218 35
10 94 215 27 121 24 79 175 107 73 172
8 197 157 35 55 186 130 153 150
2 245 153
5 163 86 223 174 149
10 22 118 98 237 209 219 74 38 207 246
3 129 97 122
8 132 177 34 11 143 249 11 201
8 175 113 238 147 100 136 151 123
5 249 173 26 217 61
1 238
7 240 116 217 175 215 98 165
10 173 58 247 184 8 212 172 186 199 133
8 84 33 222 152 31 209 243 61
4 56 48 139 109
1 169
10 192 16 199 4 2 70 64 0 142 25
4 77 224 118 177
8 151 212 87 246 234 79 57 66
2 169 18
2 147 187
4 88 16 104 92
9 238 157 19 129 182 4 20 220 123
2 155 87
9 242 83 206 135 204 21 148 122 40
7 18 40 175 107 57 92 12
1 79
4 159 209 165 163
4 198 99 52 102
3 23 157 83
6 105 36 64 2 158 168
3 177 21 197
2 78 103
1 218
4 28 126 204 6
5 246 204 202 47 119
4 135 89 34 177
9 70 54 10 229 35 32 219 57 43
2 135 146
2 103 141
8 229 95 21 145 90 38 97 202
3 48 86 247
4 12 4 217 67
6 8 102 111 227 223 218
8 108 113 29 24 3 44 66 162
4 212 66 168 58
4 139 170 167 199
8 179 203 97 59 30 105 226 205
6 198 172 0 119 98 93
9 166 138 210 77 17 171 143 249 42
3 137 212 140
6 92 133 37 189 5 132
6 231 86 66 243 8 67
1 106
1 68
1 111
10 163 192 75 119 191 117 93 77 142 46
4 234 179 13 236
1 145
3 42 232 223
9 53 103 210 159 77 91 245 188 246
3 194 70 25
6 187 182 211 78 42 187
3 221 201 175
4 159 17 75 140
2 109 193
5 132 166 234 36 160
6 31 130 179 165 219 62
6 215 86 57 6 87 183
1 37
1 73
5 189 148 150 243 70
7 213 16 71 197 116 44 182
5 238 110 126 20 236
10 235 135 98 241 222 94 94 8 201 167
6 203 128 232 8 199 201
8 28 22 168 144 130 163 105 182
2 45 202
1 86
5 19 248 240 242 91
5 63 105 64 145 58
6 190 130 140 141 101 168
2 82 126
2 58 231
6 144 25 52 28 175 51
9 172 104 103 76 1 230 182 65 125
9 6 64 183 211 205 98 192 181 244
5 101 52 176 202 9
5 68 102 190 119 214
5 37 130 65 38 109
4 167 47 113 237
5 109 10 194 20 16
5 14 147 39 130 72
8 139 87 122 241 90 55 204 14
6 83 79 194 6 203 174
1 65
7 42 239 235 237 72 0 175
6 147 27 216 33 81 169
10 17 159 210 136 113 37 41 9 181 48
7 133 222 133 12 195 175 0
7 161 136 179 149 36 140 176
4 173 71 234 106
1 143
9 37 69 166 78 78 96 126 158 230
6 40 242 105 28 55 34
10 4 26 152 40 230 142 106 152 26 89
9 178 232 136 215 50 52 42 193 148
3 100 191 142
7 246 247 232 114 94 235 119
4 201 159 100 92
7 66 118 168 137 45 213 23
2 77 139
8 19 100 96 183 41 238 136 100
6 181 215 142 166 147 12
9 55 176 21 134 55 203 115 193 61
3 29 134 154
5 249 237 17 158 169
4 209 118 223 5
5 187 147 28 83 223
5 202 213 42 149 17
2 77 23
5 155 52 2 122 220
2 109 238
4 27 109 180 210
9 249 72 81 210 164 228 246 185 244
1 40
6 39 98 220 62 217 188
1 219
7 212 32 168 199 67 9 122
5 32 16 58 104 162
1 17
7 77 15 132 98 55 88 201
10 57 77 119 58 5 151 117 217 247 99
5 63 108 165 123 140
7 245 57 156 140 74 45 217
7 177 64 144 78 15 110 135
3 229 6 161
5 124 127 125 223 170
2 144 84
4 33 79 182 90
6 71 228 93 101 130 84
1 87
3 58 197 111
8 239 117 124 117 241 64 55 26
8 56 170 132 244 16 24 239 170
5 124 147 166 225 90
4 17 177 226 75
2 86 38
9 16 226 105 7 40 160 97 152 29
6 33 86 97 122 139 17
9 76 228 174 114 68 238 132 58 213
9 246 112 59 170 128 34 89 199 138
8 46 39 92 127 137 242 37 72
3 54 16 19
1 3
4 164 241 15 35
9 35 30 128 94 14 6 193 103 205
8 165 64 248 70 191 198 62 42
7 5 96 99 25 192 102 223
10 93 238 205 109 22 48 238 181 62 57
4 229 11 80 208
3 141 27 80
5 153 122 107 223 32
5 61 37 122 33 207
9 84 225 137 170 22 188 100 149 245
1 191
3 181 148 210
10 240 103 224 206 39 144 242 135 164 116
7 35 213 192 63 46 230 13
9 66 15 130 28 73 231 219 143 225
3 166 109 234
6 82 189 186 40 245 70
5 110 55 52 73 61
9 183 40 192 213 170 207 93 198 30
10 167 237 111 97 217 220 144 49 116 146
6 156 140 118 173 64 237
7 201 47 153 133 152 94 96
10 51 2 19 145 139 250 131 250 96 161
8 53 210 148 199 7 117 89 189
1 217
2 77 167
1 230
1 188
9 209 9 189 211 92 83 99 91 27
4 0 189 195 53
3 156 1 33
7 154 222 126 184 211 17 100
2 247 214
7 134 236 7 72 10 99 219
10 3 60 85 3 62 93 56 87 249 122
5 149 89 156 25 23
7 106 187 177 102 214 176 237
9 183 122 210 96 155 196 99 215 30
8 90 187 36 177 250 222 111 148
1 16
5 148 196 92 148 187
1 112
3 245 125 108
3 148 204 148
8 117 176 188 33 15 124 133 6
8 105 117 21 230 197 71 127 206
1 88
6 172 200 67 230 138 176
1 35
8 121 129 123 46 130 220 62 3
2 68 191
6 249 25 187 195 96 127
1 9
9 106 245 229 173 224 116 162 197 216
1 67
7 41 177 37 11 52 40 114
7 44 135 182 69 135 126 166
3 90 239 103
9 234 81 182 20 11 94 217 227 12
3 134 53 88
5 64 140 24 242 74
2 190 69
6 74 9 117 149 99 106
8 108 153 147 103 173 158 197 140
4 209 50 17 12
9 1 140 92 26 132 166 95 71 48
1 210
9 164 172 220 19 238 77 172 135 245
2 106 191
6 54 214 162 71 226 113
9 115 205 163 60 184 7 132 233 53
2 39 217
10 73 49 64 214 221 12 208 193 118 149
8 172 112 215 57 151 78 194 15
5 106 140 30 177 21
1 230
9 115 10 1 188 59 129 152 94 141
5 36 9 71 89 245
8 54 51 147 196 245 227 41 164
5 135 90 137 211 134
10 140 144 191 77 203 70 42 46 211 216
5 33 100 172 28 97
8 143 244 48 202 220 153 115 85
4 19 35 62 217
7 202 110 166 93 126 49 135
3 73 164 68
4 14 53 199 111
3 91 168 204
6 138 107 222 223 209 54
6 20 20 46 223 194 212
9 69 10 13 55 148 178 124 4 5
2 16 180
7 107 97 100 214 235 207 249
3 229 52 93
6 72 203 222 15 165 36
10 239 113 204 136 40 141 204 109 131 220
10 27 141 136 192 168 184 148 166 205 127
8 111 190 167 64 161 246 42 10
2 94 123
9 44 228 50 61 86 182 95 189 22
8 138 214 217 71 176 196 90 116
10 14 55 207 142 29 202 184 103 158 92
3 68 200 16
9 10 167 113 105 105 200 154 243 227
9 63 152 129 217 81 169 232 200 125
9 42 76 121 145 235 213 185 116 162
1 234
10 117 161 91 35 110 245 27 150 179 155
10 57 121 197 227 166 211 101 39 2 242
4 148 39 186 82
8 161 96 202 146 214 112 50 249
4 45 90 186 37
2 51 94
7 61 134 159 21 49 11 24
2 235 236
2 234 131
1 144
5 249 103 3 111 154
5 210 12 156 145 49
6 9 143 19 71 91 178
9 140 189 244 180 237 229 72 220 173
6 113 150 181 30 217 41
6 32 65 196 188 23 245
5 33 201 235 168 41
4 73 181 229 67
6 215 109 246 185 32 178
7 246 109 141 212 214 138 245
9 83 246 52 141 24 149 92 8 66
8 234 139 128 212 19 115 241 193
8 239 225 102 99 33 211 54 58
10 192 116 16 89 112 132 230 136 30 135
10 160 146 191 113 23 217 132 138 20 74
4 8 112 229 107
10 189 225 17 241 167 133 7 5 245 203
7 194 47 248 151 207 143 156
9 230 186 15 181 206 153 57 27 15
2 198 224
1 173
8 28 89 188 99 158 246 51 19
9 98 80 154 119 223 123 1 15 122
8 10 141 170 67 168 249 102 116
3 203 38 26
8 191 27 143 162 22 195 181 25
2 75 244
9 47 116 40 127 239 56 137 129 226
6 47 224 119 227 9 135
3 99 116 18
5 8 180 212 16 174
6 187 249 231 225 110 160
7 50 148 135 187 91 174 204
3 212 136 178
9 20 5 133 200 23 8 22 16 33
6 3 20 38 66 64 77
7 225 91 226 122 39 226 26
4 179 164 175 128
7 145 148 160 91 98 247 99
3 76 132 35
4 217 74 146 30
8 135 68 55 174 4 95 213 30
10 141 8 233 82 163 191 230 137 31 141
1 194
9 210 139 110 103 169 248 62 13 212
2 81 16
3 85 175 146
2 233 100
9 28 182 100 32 225 237 127 116 120
9 3 143 23 177 246 5 174 57 18
10 131 100 216 64 249 140 23 114 187 187
3 28 182 152
6 156 138 188 85 71 72
10 27 159 79 22 164 67 143 183 15 23
3 231 151 94
1 238
9 185 174 137 213 105 102 23 11 54
7 160 125 161 62 153 69 142
10 46 209 196 229 37 219 138 18 184 233
8 171 68 201 95 205 227 13 57
1 88
6 89 249 49 63 124 15
3 15 4 178
9 200 221 75 232 108 157 229 154 237
9 35 0 58 241 227 135 111 40 224
4 129 35 84 192
7 100 137 175 168 129 25 117
3 164 162 20
6 141 239 120 104 23 184
6 13 161 110 188 201 83
8 144 118 57 149 91 221 36 79
7 229 104 68 141 82 43 161
4 184 149 150 101
4 147 76 63 57
1 1
9 147 224 152 79 94 50 170 64 150
7 15 128 166 83 18 248 127
6 27 124 206 241 39 192
3 179 5 8
9 70 16 76 107 232 155 202 95 74
6 59 136 95 187 51 242
10 113 182 76 140 120 31 194 159 37 144
8 106 152 80 176 232 156 32 213
3 47 58 198
1 117
3 35 117 198
5 200 60 86 25 13
9 121 20 114 158 165 14 77 130 94
9 112 250 162 138 123 210 9 134 150

AC output:

Code: Select all

429 594