Tuesday July 17, 2007
Locker Mania
There is a locker room in the club and they are numbered from 1 to 100. There are 100 members of the club who will enter the locker room in the following sequence. When the first member enters, he opens all the lockers. When the second member enters the locker room, he closes all even numbered lockers. When the next member enters the room, he toggles the state of every locker which is a multiple of 3.
This process continues till all the 100 members have been through the locker room. At the end of this process, which are the lockers that are open?
Posted by insidemyhead [Personal] ( July 17, 2007 07:40 PM ) Permalink | Comments[4]
Posted by Murali on July 18, 2007 at 12:55 AM IST #
#include <stdio.h> #include <string.h> #include <errno.h> extern int errno; typedef int Locker_t; #define NLOCKERS 100 #define NMEMBERS 100 enum { LOCKERCLOSED,LOCKEROPEN }; #define CLOSE_ALL_LOCKERS(L) memset(L,LOCKERCLOSED,sizeof(L)) #define LOCKER_IS_OPEN(L) ((L) == LOCKEROPEN) #define LOCKER_IS_CLOSED(L) ((L) == LOCKERCLOSED) #define TOGGLE_LOCKER(L) ((L) = LOCKER_IS_OPEN(L)?LOCKERCLOSED:LOCKEROPEN ) int pHeader(FILE *fp,int origin,size_t cnt,int indent); int pLockers(FILE *fp,Locker_t *l,size_t cnt); int pOpenLockers(FILE *fp,Locker_t *l,size_t cnt); Locker_t lockers[NLOCKERS]; int main(int argc,char *argv[]){ int i,l; int tripCnt; int totalTrips; CLOSE_ALL_LOCKERS(lockers); fputs("[HEADER] ",stdout); pHeader(stdout,1,NLOCKERS,10); fputs("[INITIAL] ",stdout); pLockers(stdout,lockers,NLOCKERS); totalTrips = 0; for(i=1;i<=NMEMBERS;i++){ tripCnt = 0; for(l=(i-1);l<NLOCKERS;l+=i){ TOGGLE_LOCKER(lockers[l]); tripCnt++; } printf("[%3d:%3d] ",i,tripCnt); pLockers(stdout,lockers,NLOCKERS); totalTrips += tripCnt; } printf("Total Trips: %d\n",totalTrips); pOpenLockers(stdout,lockers,NLOCKERS); return 0; } int pHeader(FILE *fp,int origin,size_t cnt,int indent){ int i; int n; if(!fp){ errno = EINVAL; return -1; } for(i=origin;i<(cnt+origin);i++) if( i%10 == 0 ){ n = i/10; if( n < 10 ) fprintf(fp,"%d",i/10); else fputs("X",fp); } else fputs(" ",fp); fputs("\n",fp); for(i=0;i<indent;i++) fputs(" ",fp); for(i=origin;i<(cnt+origin);i++) fprintf(fp,"%d",i%10); fputs("\n",fp); return 0; } int pLockers(FILE *fp,Locker_t *l,size_t cnt){ int n; if( !fp || !l ){ errno = EINVAL; return -1; } for(n=0;n<cnt;n++) fputs(LOCKER_IS_OPEN(l[n])?"o":"+",fp); fputs("\n",fp); return 0; } int pOpenLockers(FILE *fp,Locker_t *l,size_t cnt){ int i; if( !fp || !l ){ errno = EINVAL; return -1; } fprintf(fp,"Open Lockers: "); for(i=0;i<cnt;i++) if( LOCKER_IS_OPEN(l[i]) ){ if( (i!=0) ) fputs(",",fp); fprintf(fp,"%d",i+1); } fputs("\n",fp); return 0; }Posted by Erik O'Shaughnessy on July 18, 2007 at 01:20 AM IST #
Posted by InsideMyhead on July 18, 2007 at 07:31 PM IST #
Posted by Erik O'Shaughnessy on July 20, 2007 at 01:03 AM IST #