10154 - Weights and Measures

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 10154 - Weights and Measures

Post by Igor9669 »

Please tell me what's wrong???
Here is my code:
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 5607
int MIN(int a,int b)
{
return a<b?a:b;
}

typedef struct
{
int strenght,weight;
}turtle;

bool CMP(const turtle& a,const turtle& b)
{
if(a.strenght!=b.strenght)
{
return a.strenght>b.strenght;
}
return a.weight>b.weight;
}

turtle a[MAXN+10];
int l[MAXN+10],p[MAXN+10];
int main(){
//freopen("weights.in","r",stdin); freopen("weights.out","w",stdout);
int i,j,pos=0;

while(scanf("%d%d",&a[pos].weight,&a[pos].strenght)!=EOF)
{
pos++;
}

sort(a,a+pos,CMP);

int max,maxlen=0,k;
for(i=0;i<pos;++i)
{
max=0;
l=1;
p=a.strenght-a.weight;
for(j=0;j<i;++j)
{
if(a.weight<=p[j])
{
if(l<=l[j]+1)
{
l=l[j]+1;
k=MIN(p[j]-a.weight,a.strenght-a.weight);
if(k>max)
{
p[i]=k;
max=k;
}
}
}
}
if(l[i]>maxlen)maxlen=l[i];
}
printf("%d\n",maxlen);
return 0;
}

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 10154 - Weights and Measures

Post by tryit1 »

RS (residual strength) = Actualstrength (AS) - weight(W)

RS = AS - W
if i 've RS1 < RS2 how would i order and why ?You are odering it from bottom{maximum residual strenght at bottom} (turtle 2)RS2 < (turtle 1) RS1 because RS2 can carry more weight.lets say AS1 = 1000, W1=900, AS2=800, W2=600, now RS2 < RS1 but we cannot order T2<T1, this is because residues doesnot tell anything about the total strength.AS1=1200,W1=900 RS1=300, AS2=900,W2=200, RS2=700 , you cannot do T2 < T1 ie T1 on top of T2 (just on the basis of residue) but T1 < T2 is certainly possible.

Ordering by weight,============
maximum weight (turtle TMW) at bottom position 1 and total height is H.

TMW is at position 1. and the ordering is TMW1 < TK < TP < TZ ... H .If TMW1 is at position p instead of 1 , we can form a total height of H as per the above ordering. If i could somehow find a turtle with strength that could carry the weight of H turtles i'm increasing the height of the turtle. That means we can still increase our height by ordering by weight if we can find a better turtle.

Ordering by strength.

Maximum Strength(Turtle TMS) at bottom position 1 and total height H.

TMS is at position 1. and the ordering is TMS < TK < TP < TZ ... H .

Here we have something. TMS>= WMS + WK + WP + WZ + .. WH

If TMS is at position p instead of 1 ,we can form a total hieght of H as per above ordering. Can i find a turtle of greater strength than TMS so that it could carry itself + total height H.If it were present say TX, then it can carry WMS + WK + WP +WZ +..WH + WX<=TSX(turtle X's strength) . So contradiction.


maximum height of first i turtles when ordered by increasing order of strength and the corresponding weight Cummulative weight.

Same heights different weights , store lower weights because a good turtle will be able to carry more.


That made me to stop thinking and code below

height[i+1]=1


for(all j <=i)

if(W[i+1]+CW[j]<=TS[i+1]) {
if(h[j]+1>height[i+1]){
height[i+1]=h[j]+1;
CW[i+1]=CW[j] + W[i+1];
}
if(h[j]+1==height[i+1]){
height[i+1]=h[j]+1;
if(CW[i+1]>CW[j]+W[i+1]) CW[i+1]=CW[j] + W[i+1];
}
}


until i found this

101 101
100 201
99 300
98 301
5 302

This approach has a fault with it . Best approach is 2,3,4,5 where as we always do do 1,2.

If turtle 1 can be stacked on turtle 2. we loose any stacking such as 2,3,4,5, because we always say height[2]=2 (since is 1 can be on top 2 ).
So one way to get rid of this is to store the turtles by heights with least weight. Now can i+1 the turtle contribute increasing heights made by i turtles. What is the maximum height.
mw(th,i) = min( mw(th,i-1),mw(th-1,i)+curturtle); This means minimum weight of turtles with height th using first i turtles is mw(th,i) is equal to

minimum of
minimum weight of turtles of height th formed by first i-1 turtles.
minimum weight of turtles of height th-1 formed by SOME i-1 turtles and this current turtle. ( *This is important because the curtutle can only take previous i-1 turtles because it is sorted in increasing order of strength *, had it been not ordered we cannot say whether curturtle can take any of the i-1 turtles. )


You can optimize space seeing that ith height requies only i-1th row. Similar to LCS.





Code: Select all


#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
using namespace std;

typedef long long lint;
typedef unsigned long long ulint;

struct turtle
{
  int w, s;
};

int n = 0;
#define MAX 5700
turtle tarr[MAX];
int mw[MAX][MAX];

bool
operator< (const turtle & a, const turtle & b)
{
  if (a.s != b.s)
    return a.s < b.s;
  return a.w > b.w;
}

int
main ()
{
  int i = 1, j, a, b;
  while (scanf (" %d %d", &a, &b) != EOF)
    {
      tarr[i].w = a;
      tarr[i].s = b;
      i++;
      n++;
    }
  sort (tarr+1, tarr + n+1);
  int ans = 1, BIG = (1<<30);

  for (i = 1; i <= n; i++)
  for (j = 0; j <= n; j++)
     mw[i][j] = BIG;

// printf("n=%d\n",n);

  mw[0][0]=0;
  for (i = 1; i <= n; i++)
    {
      for (int h = 1; h <= i; h++)
	{
          mw[h][i]=mw[h][i-1];
	  if ((mw[h - 1][i - 1] + tarr[i].w) < tarr[i].s)
	    mw[h][i] = min(mw[h][i],mw[h - 1][i - 1] + tarr[i].w);
	  else if ((mw[h - 1][i - 1] + tarr[i].w) == tarr[i].s)
	    mw[h][i] = min (mw[h][i], mw[h - 1][i - 1] + tarr[i].w);


	  if (mw[h][i] < BIG) ans = max (ans, h);
	}
    }
  printf ("%d\n", ans);
  return 0;
}

eduardoufv
New poster
Posts: 1
Joined: Sat Jun 19, 2010 2:27 am

Re: 10154 - Weights and Measures

Post by eduardoufv »

My code is

Code: Select all

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<string>
#include<map>
#include<list>
#include<queue>
#include<stack>
using namespace std;

class tartaruga {
	public :
	
	int weight;
	int strength;
	int real;
	int cont;
	int ant;
	
	
	bool operator<(const tartaruga &e) const{
		return weight > e.weight;
	}
};

int compare (const void * a, const void * b)
{
  tartaruga v1 = *(tartaruga*) a;
  tartaruga v2 = *(tartaruga*) b;
  
 
  if (v1.strength != v2.strength){
	return v1.strength - v2.strength;
  
  }
  else
   	return v1.weight - v2.weight;
  
 
	
 

}  




int main ()
{

	int x, y;
	tartaruga bando[10000];
	int ind = 0;
	while(cin >> x){
		cin >> y;
		
		tartaruga t;
		t.weight = x;
		t.strength = y;
		t.real = x;
		t.cont = 1;
		bando[ind] = t;
		ind++;
		
	}
	
	qsort(bando,ind,sizeof(tartaruga),compare);
	
	/*for (int i = 0; i<ind; i++)
		cout << bando[i].weight << " " << bando[i].strength << endl;
		
	cout << endl;*/
	
	
	for (int i = 0; i<ind; i++){
		for (int j = i+1; j<ind; j++){
			
			
			if (bando[j].real+bando[i].weight <= bando[j].strength){
				if (bando[i].cont + 1 > bando[j].cont){
					
						bando[j].cont = bando[i].cont + 1;
						bando[j].ant = i;
						bando[j].real+=bando[i].weight;
					}
					
				
			
			}
			
			/*for (int e = 0; e<ind; e++){
					cout << bando[e].weight << " " << bando[e].strength << " " << bando[e].cont << endl;
			}
			cout << endl;*/
		
		}
	}
	
	int max = 0;
	int pmax;
	
	for (int i = 0; i<ind; i++){
		if (max < bando[i].cont){
			max = bando[i].cont;
			pmax = i;
		}
			
	}
	
	
	
	cout << max << endl;
	
	/*for (int i = 0; i<max; i++){
		cout << bando[pmax].weight << " " << bando[pmax].strength << " "<< bando[pmax].real << endl;;
		pmax = bando[pmax].ant;
	
	}*/
	
	
	
		
		

	
	
		
	
return 0;
}
but i just get WA. Can you help me please??? Maybe any tip or input???

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

Re:

Post by pdwd »

seogi81 wrote:I used DP

Let me explain my algorithm.

first, sort turtles by strength..

Let, H[n][w] = maximum stack height, using 1'st~n'th turtles.
and total weight is no more than 'w'

H[n][w] =
1 (if n=1 and weight[n] <= w)
0 (if n=1 and weight[n] > w)

this is initialization..

and recursively,

H[n][w] =
max( H[n-1][ min(strength[n] - weight[n], w - weight[n]) ] + 1, H[n-1][w]) (if weight[n] <= w)
H[n-1][w] (if weight[n] > w)

but, it is impossible to make such a big table regarding all possible w( there's not specification about maximum strength of any turtle..)
Space of subproblems seems correctly. I decided to start from the strongest turtle and try to put next one on the top of the stack, so in this case you need dp[j] - max height of the stack using first i turtles, when remaining strength (to put other turtles on the top) is >= j. When you limit second dimension by 66100 and make memory optimization dp[2][66100] it is accepted. Probably your approach could be also correct with such limitation. However the best solution was suggested by Adrian Kuegel.

For those of you, who wish to sort by residual strength, consider such an example:

Code: Select all

1 5
5 7

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 10154 - Weights and Measures

Post by DJWS »

This problem can be modelled as a scheduling problem. It exists a O(nlogn) greedy algorithm which is better than modified-LIS method mentioned here. See Hodgson's algorithm.

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 10154 - Weights and Measures

Post by Bruno »

I used the greedy approach, but its giving WA :/, I tried all the inputs here on this thread and its all ok. Could anyone post more inputs? Thank you!

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10154 - Weights and Measures

Post by DD »

stcheung wrote:For kissish's post above:
Sorry , but the answer is not 8.


In my program that got AC,

the answer is 7.
My AC program (submitted on 10/3/2008) did return 8 for the answer. No offense, but given they have rejudged the submissions, maybe yours is no longer considered AC?
My A.C. program also gives 8.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Leo66
New poster
Posts: 2
Joined: Sun May 01, 2011 5:11 pm

Re: 10154 - Weights and Measures

Post by Leo66 »

Hi,

Why W.A?

Code: Select all

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct zolwie
	{
		int w, m;

		zolwie(): w(0), m(0)
		{}

		zolwie(int _w, int _s): w(_w), m(_s-_w)
		{}

		bool operator<(zolwie const & ref) const
        {
            return(m>ref.m);	
        }
	};

int main()
{
	vector<zolwie> tab; 
	long liczba1, liczba2;
	bool ok = true;

	while (cin >> liczba1 >> liczba2)
	{
		tab.push_back(zolwie(liczba1, liczba2));
	}
	
	int ilosc = 1;

	sort(tab.begin(), tab.end());

	for(int j= 1; j<tab.size(); j++)
	{
		if(tab[j].w<=tab[j-1].m&&tab[j].w<=tab[0].m)
		{
			for(int k= j-2; k>=0; k--)
			{
				if(tab[j].w>tab[k].m)
				{
					ok = false;
					tab.erase(tab.begin() + j);
					break;
				}
			}

			if(ok)
			{
				for(int k= j-2; k>=0; k--)
					tab[k].m-=tab[j].w;

				tab[j-1].m-=tab[j].w;
				ilosc++;
			}
			ok = true;
		}

		else
		{
			tab.erase(tab.begin() + j);
			j--;
		}
	}
		cout << ilosc;
		//system("pause");

	return 0;
}

ghadir
New poster
Posts: 1
Joined: Sat Jul 07, 2012 11:27 am

Re: 10154 - Weights and Measures

Post by ghadir »

hi
plz give me a compeleted code for this problem
i need this
ok
plz help me
i most send this for my teacher if i do not this
then i ....
tank you

37squared
New poster
Posts: 6
Joined: Sun Sep 16, 2012 4:15 pm

Re: 10154 - Weights and Measures

Post by 37squared »

I hav tried all the critical inputs given in ths forum and got correct answers for all.... my algo uses DP(not exactly LIS, actually quite different from it)...
m quite sure tht my algo is correct... m missing somethng silly(either silly inputs or some output format)... tried debugging a lot... couldnt find nythng... if ny1 can plz help me, i ll b highly grateful...
Here's my code:

Code: Select all

#include<iostream>
using namespace std;
int pile_weight=0;
 
int largest_stack(int weight[],int capacity[],int n,int maximum,int pos)
{
      int dp[6000]={0};
      bool included[6000]={0};
      dp[1]=maximum;included[pos]=1;/*initializing the sequence*/
 
      int i=1,j,max,position,current_capacity,flag=0,stack_pos=0,next_weight,top=0,bottom=0;
 
      while(dp[i]>=0)
      {
            i++;max=-250000;position=-1;
            for(j=1;j<=n;j++)
            {
                  if(included[j]==0)
                  {
                        top=capacity[j]<dp[i-1]-weight[j]?capacity[j]:dp[i-1]-weight[j];
                        bottom=capacity[j]-pile_weight<dp[i-1]?capacity[j]-pile_weight:dp[i-1];
                        current_capacity=top>bottom?top:bottom;
                        if(max<current_capacity)
                        {
                              max=current_capacity;
                              position=j;
                              next_weight=weight[j];
                        }
                  }
            }
            pile_weight+=next_weight;
            dp[i]=max;
            included[position]=1;
      }
      return(i-1);
}
 
int main()
{
      int wt[6000],strength[6000],capacity[6000];
      int i=1,max=-250000,max_length,pos;
 
      while(cin>>wt[i]>>strength[i])
      {
            capacity[i]=strength[i]-wt[i];
            if(max<capacity[i])
            {
                  max=capacity[i];
                  pos=i;
                  pile_weight=wt[i];
            }
            i++;
      }
 
      max_length=largest_stack(wt,capacity,i-1,max,pos);
      cout<<max_length;
 
      return 0;
}

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

Re: 10154 - Weights and Measures

Post by brianfry713 »

Print a newline at the end of the output. For this input:

Code: Select all

384 1271
778 1694
794 1130
387 880
650 1072
363 391
691 751
764 1691
541 968
173 910
AC output is 4
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10154 - Weights and Measures

Post by lighted »

I get WA. I need some input.

I subtracted own weights of turtles from their strengths to get residual (remaining) strengths.

Code: Select all

#define LEN 5620

struct turtle {

  int strength, weight;   // strength is residual strength

} a[LEN];
My sort function is

Code: Select all

int cmp(const void *a, const void *b) {

  turtle A = *(turtle *)a;
  turtle B = *(turtle *)b;

  if ( min(A.strength - B.weight, B.strength) != min(B.strength - A.weight, A.strength) ) 

    return min(B.strength - A.weight, A.strength) - min(A.strength - B.weight, B.strength);

  if (A.strength != B.strength) return B.strength - A.strength;

  return 0;
}
It sorts like this: Let 2 turtles be A and B. We can build (if possible) stack(or tower) using both of them in two ways.

1 way
B ---> B is at top
A ---> A is at bottom

Remaining strength of stack in first way is min(A.strength - B.weight, B.strength)

2 way
A ---> A is at top
B ---> B is at bottom

Remaining strength of stack in second way is min(B.strength - A.weight, A.strength)

If first remaining strength is greater than second one then we prefer order of A and B like in 1st way, otherwise like in second way.
In this case i call turtle A stronger than B, otherwise B is stronger than A. Sorting is in descending order.

Code: Select all

removed, after acc..
Last edited by lighted on Wed Jul 30, 2014 7:58 am, edited 2 times in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

Re: 10154 - Weights and Measures

Post by brianfry713 »

Input:

Code: Select all

141 623
401 753
386 968
446 674
634 1278
401 1108
216 1068
568 642
647 1423
458 1217
384 703
272 833
381 1144
887 930
957 1398
368 465
275 1043
800 1460
702 947
887 1222
240 879
393 849
842 1155
529 1018
440 778
599 1422
9 231
384 773
985 1607
783 1724
63 213
389 1078
270 458
348 1319
433 1020
657 1329
225 626
479 898
713 720
907 1059
697 1202
975 1032
726 1436
797 859
331 910
354 1099
80 822
433 782
930 1063
671 1385
71 750
737 1384
80 296
65 857
574 1545
944 1566
827 1097
678 1583
331 805
318 331
52 76
758 890
765 1307
832 878
26 881
111 207
533 1381
743 1355
63 222
404 1392
482 1181
610 918
968 1255
564 1214
761 1643
662 826
905 1676
295 316
313 792
419 1109
333 1214
138 1003
728 960
477 619
390 622
482 1353
930 1021
531 780
377 471
898 1387
327 886
653 1236
330 629
956 1950
777 1503
683 792
606 778
974 1660
403 1205
179 972
33 693
15 329
750 1295
562 1041
991 1802
967 1284
721 1692
252 302
270 829
395 441
284 714
507 748
601 1081
926 930
633 738
148 813
116 278
330 1196
707 950
696 1393
53 715
365 1138
985 1953
175 429
526 1095
651 1460
350 859
50 1001
988 1315
306 1278
783 1236
636 1535
614 931
764 1436
559 1018
368 979
472 557
736 1192
52 962
61 991
830 894
90 270
572 1063
482 1394
818 957
883 1483
591 1462
498 702
187 800
228 974
423 1018
708 955
31 474
702 1137
352 467
364 898
178 983
65 814
296 842
660 773
684 1579
64 690
765 1679
181 1132
878 1286
48 349
355 1111
547 932
198 798
171 1073
714 1600
435 678
691 1190
344 1330
396 751
450 881
249 762
56 69
778 1014
316 972
644 1359
308 1306
470 1324
734 754
805 1710
273 1144
790 849
113 593
557 1365
817 1121
163 429
734 1145
131 272
776 1036
728 1171
915 1638
157 731
720 1699
427 1233
350 934
62 684
454 1305
680 1598
683 1271
726 1577
891 1779
469 1445
650 1601
468 1245
210 405
219 696
918 1294
50 1039
706 1535
794 849
412 619
676 893
410 1117
134 578
294 505
294 830
450 1212
863 963
64 394
876 1150
524 619
750 1543
822 973
782 1661
979 1906
933 1675
134 1094
958 1853
666 1110
338 1297
654 1285
846 950
745 1453
555 1363
389 819
433 1345
876 1058
57 106
685 1523
927 1590
116 327
405 1006
170 532
495 1330
157 989
145 956
815 1157
266 1177
49 869
718 1155
601 1104
701 1530
36 145
229 949
298 806
383 796
718 857
366 1254
852 1712
74 83
44 615
171 1029
912 1348
120 433
607 796
101 660
691 844
387 1114
261 1229
446 1004
475 655
323 515
318 1006
431 601
547 1052
178 1120
427 1127
151 489
135 405
650 743
459 1210
651 800
255 645
227 743
357 1030
73 256
204 599
374 896
82 239
43 1024
13 585
922 1361
271 696
128 885
694 1472
849 1001
880 1379
653 787
240 1119
1 949
903 977
130 237
820 1676
980 1882
12 34
234 610
593 1100
814 1677
931 1224
619 1596
70 889
480 781
669 801
787 1696
363 1150
208 473
212 550
723 755
545 1247
285 1193
723 1593
283 598
376 824
529 1188
740 1239
635 797
317 431
814 1800
598 1198
246 1206
739 1192
576 878
142 441
685 1371
1000 1321
593 668
190 1065
741 1659
674 944
928 1342
120 682
575 1364
27 767
126 750
692 1063
583 1013
175 686
83 400
809 1577
354 514
88 1035
234 864
173 1148
899 1746
596 1422
612 1327
387 925
503 916
277 905
389 1357
350 673
749 1274
833 1665
193 834
951 1497
153 543
844 1230
19 36
360 1277
215 1170
742 1568
22 502
363 887
245 1236
504 1137
959 1812
955 1662
729 1517
890 1163
780 1620
171 1103
230 244
670 1270
382 411
517 1465
336 946
773 1130
90 577
880 1566
478 1213
318 1106
940 1564
494 514
411 795
293 836
575 1038
826 1630
828 1323
404 966
524 796
509 720
233 515
567 1241
120 918
359 1308
533 1209
736 1208
300 882
491 553
317 452
956 1847
949 1731
695 1472
276 726
338 489
73 919
361 666
479 758
979 1930
77 414
899 1508
365 1352
432 448
568 1490
429 1313
57 442
774 779
518 1338
133 278
621 1443
648 1341
668 1028
998 1496
639 1615
448 1163
664 1011
675 703
333 439
395 647
379 1203
487 1274
560 1172
144 221
432 708
573 625
98 318
745 862
580 674
614 832
69 131
284 368
760 1070
464 908
415 1273
695 840
33 566
932 1524
144 219
20 595
702 1295
979 1130
812 887
267 1010
168 1049
960 1548
294 889
671 724
904 1038
848 1518
344 886
815 1191
426 1172
968 1537
172 511
496 721
931 1405
376 471
900 1542
837 1256
874 1023
6 525
743 771
571 1218
514 932
316 1173
311 793
232 968
579 1130
657 759
242 394
327 851
977 1679
970 1846
695 1502
646 1567
307 310
439 840
30 392
47 942
131 846
751 1545
548 883
881 1008
237 774
228 1058
688 1242
354 370
607 930
243 897
481 1369
926 1713
890 1606
188 460
429 1015
166 726
652 921
705 905
955 1540
326 869
122 1027
373 534
811 1537
529 946
48 819
422 1303
659 1358
667 1567
415 621
523 1366
792 833
754 1197
661 1119
994 1609
43 362
509 1025
576 1457
28 414
606 1162
154 160
679 1255
238 927
626 1530
588 628
110 573
235 488
503 1491
47 562
446 487
481 1321
711 1700
707 993
870 1604
671 1498
642 1467
184 504
752 1173
8 385
677 1624
769 907
761 764
390 1005
990 1426
129 916
828 1437
626 1165
598 1282
176 995
418 617
645 1056
375 556
82 560
601 1042
854 1131
739 1713
414 914
976 1131
114 432
943 1186
104 874
851 933
660 1460
765 953
618 1152
386 1001
296 1056
795 1172
237 984
817 1259
24 580
416 1205
407 1150
296 816
60 298
114 278
7 324
597 616
116 829
206 292
247 838
700 1242
702 1548
271 561
592 1031
83 1050
346 844
108 860
593 996
624 1276
640 1377
167 1165
53 816
16 537
476 697
606 680
163 820
967 1183
502 739
857 950
676 1616
60 433
789 956
125 506
569 1317
33 593
484 683
557 1446
314 1239
409 1198
497 511
214 226
22 202
227 750
417 501
615 1059
23 49
816 979
192 484
544 656
391 1319
23 898
126 1058
115 906
856 1379
931 1635
888 1032
715 1624
324 1266
783 875
377 774
535 1286
423 1125
913 1879
994 1450
430 814
383 1187
610 1471
735 811
3 945
950 1884
646 1483
77 437
97 497
653 1532
843 872
628 1005
779 1181
431 1123
719 1495
499 647
159 393
952 1073
94 132
196 292
980 1478
381 1006
686 1144
336 1119
209 1198
13 65
17 1009
780 928
393 603
839 1303
985 1674
611 1107
922 1836
968 1335
304 819
463 746
12 855
259 957
652 1598
832 1693
934 1130
264 567
188 231
450 1382
253 893
395 984
328 686
436 686
623 1026
616 1542
918 1348
560 841
625 1443
978 1606
116 277
840 889
357 460
703 1599
146 298
179 929
143 1069
690 1513
283 409
424 681
528 919
183 980
173 267
78 875
264 671
776 1155
920 1536
427 1055
718 1200
523 1386
985 1038
964 1092
978 1632
302 914
779 1504
869 1527
115 518
455 742
496 1380
435 1194
642 853
489 1402
826 1094
540 1435
749 1163
110 843
467 540
212 656
726 1239
56 912
237 513
514 1218
678 998
990 1515
555 1332
284 832
987 1111
461 625
391 1391
58 197
414 581
872 1752
592 675
675 1344
948 1678
525 709
357 747
887 921
61 290
559 1174
5 199
162 505
317 1291
858 1566
974 1889
846 1585
434 503
970 1347
504 1148
45 496
726 1647
986 1068
662 1535
468 1190
101 127
688 1145
571 1421
799 1686
175 831
946 1446
922 1066
238 593
212 771
83 150
203 331
517 797
48 903
713 1423
727 907
783 962
205 676
635 1410
672 1105
14 860
440 1399
346 707
102 1037
68 734
494 644
732 1428
277 878
327 1004
455 494
738 1271
219 739
711 1486
342 1039
902 915
129 1044
859 1779
225 781
280 607
490 1189
344 1327
849 924
30 507
27 383
505 1338
747 1341
365 1330
114 189
91 546
771 1763
820 1071
258 936
522 1005
585 1387
161 235
852 1356
409 461
930 1368
881 1838
146 531
141 1033
979 1485
208 652
932 1230
250 305
642 711
657 1556
98 277
733 1415
332 1225
108 291
748 1264
235 265
953 1068
986 1436
851 1329
341 522
983 1531
624 1539
198 424
321 1160
646 1623
89 185
155 977
129 615
66 302
669 835
103 358
195 603
369 901
857 1428
9 559
752 1744
449 1176
258 904
952 1530
836 1786
554 1479
45 106
98 271
546 1061
761 1327
680 895
820 1694
622 1162
757 1236
111 877
380 594
109 937
940 1306
474 1366
295 604
193 393
585 822
260 294
761 1567
549 1422
371 599
88 631
454 1163
434 644
539 1083
327 1245
757 1192
746 1443
152 723
940 1386
231 363
646 814
720 977
201 1033
62 811
705 1490
329 473
327 461
204 964
695 1438
656 678
12 776
808 917
812 1772
31 134
757 1019
234 988
429 734
11 992
137 561
730 923
208 618
336 1222
543 1082
998 1587
633 1286
610 1255
768 1538
105 685
81 217
682 1519
749 1017
943 1472
572 877
509 569
80 670
252 540
999 1586
525 1418
478 1000
482 592
526 969
106 400
212 775
873 1165
698 1604
481 927
173 948
326 423
431 1265
156 666
776 1536
797 1571
698 1372
19 194
195 1047
637 1358
294 388
366 1224
656 1246
149 854
495 1476
502 522
755 1582
116 301
661 1284
695 1131
382 1225
561 993
516 1447
606 669
782 1376
135 563
688 1188
285 980
441 1226
400 1335
766 1667
954 1474
728 1149
705 1445
44 795
527 1304
593 1032
208 669
370 536
875 1378
111 120
AC output: 44
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10154 - Weights and Measures

Post by lighted »

Thanks!
Can you generate test with smaller value of n (number of turtles).
It will be more easy to understand why my algorithm fails.
Thanks in advance!
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

Re: 10154 - Weights and Measures

Post by brianfry713 »

I tried generating a few random test cases for a smaller number of turtles and your code isn't failing them. There are at most 5,607 turtles. There are 1000 in the I/O I most recently posted.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”