Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2733
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2733
The Reader's Locker
By Valeska Uchôa, UFPI Brazil
Timelimit: 1
Carla owns a vast collection of books containing 100 copies. She spends a lot of time in college so she likes to leave some of them in her closet. However, the closet has room for only 4 books, one compartment for each one.
She is very organized person, therefore she keeps track of every time she wants to read a book. The books stored in her locker are chosen as follows: when Carla wants to read a book that is not in her locker, she brings it the next day and puts it in the place of the least recently read book. Each book has an associated ID that is a number from 1 to 100.
Given a sequence of books read, her algorithm must determine the number of times Carla wanted to read a book that was not in her locker.
Input
The first line is an integer N representing the number of book Carla wants do read. The next N lines are integers L1, L2, ..., LN (1≤Li≤100)">
representing the IDs of the books Carla wanted to read. Input finishes when an EOF is found.
Output
Outputs an integer representing the number of times Carla wanted to read a book that was not in her locker.
Input Sample | Output Sample |
10 |
8 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iterator>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<stack>
#include<queue>
#include<math.h>
#include <utility>
#include <sstream>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef long long ll;
int main(int argc, char** argv) {
//freopen("c.txt","w",stdout);
int n;
while(cin>>n)
{
vector<int> a;
vector<int>::iterator it;
int count=0;
int v;
int add=0;
for(int i = 1; i < = n; i++)
{
cin>>v;
if(add<4)
{
it=find(a.begin(),a.end(),v);
if(it==a.end())
{
a.push_back(v);
add++;
count++;
}
}
else
{
it=find(a.begin(),a.end(),v);
if(it!=a.end())
{
int temp=*it;
a.erase(it);
a.push_back(temp);
//cout << "putting at last " << v << endl;
}
else
{
count++;
a[0]=v;
it=a.begin();
a.erase(it);
a.push_back(v>;
//cout << "adding " << v << endl;
}
}
}
cout << count << endl;
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
1
45
23
73
56
23
23
1
45
89
Output
#2 Code Example with Python Programming
Code -
Python Programming
while True:
try:
x,a=[0,0,0,0],0
for i in range(4,int(input())+4):
n=int(input())
x.append(n)
x.append(0)
for i in range(4,len(x)-1):
tmp=[x[i-1],x[i-2],x[i-3],x[i-4]]
if x[i] not in tmp and x[i+1]!=x[i]:a+=1
if a==3:a=4
if a==10:a=11
print(a)
except:break
Copy The Code &
Try With Live Editor
Input
1
45
23
73
56
23
23
1
45
89
Output