39
loading...
Solving Codeforces Problem: 136A - Presents
Today we are going to attempt to solve the Codeforces problem: 136A - Presents. Alright! so let's begin.
Little Petya very much likes gifts. Recently he has received a new laptop as a New Year gift from his mother. He immediately decided to give it to somebody else as what can be more pleasant than giving somebody gifts. And on this occasion he organized a New Year party at his place and invited n his friends there.
If there's one thing Petya likes more that receiving gifts, that's watching others giving gifts to somebody else. Thus, he safely hid the laptop until the next New Year and made up his mind to watch his friends exchanging gifts while he does not participate in the process. He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi. He also remembered that each of his friends received exactly one gift.
Now Petya wants to know for each friend i the number of a friend who has given him a gift.
The first line contains one integer n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party. The second line contains n space-separated integers: the i-th number is pi — the number of a friend who gave a gift to friend number i. It is guaranteed that each friend received exactly one gift. It is possible that some friends do not share Petya's ideas of giving gifts to somebody else. Those friends gave the gifts to themselves.
Print n space-separated integers: the i-th number should equal the number of the friend who gave a gift to friend number i.
Now, before discussing the solution, I first need to address a mistake in the description in the input of the question as given on Codeforces. In the input description, it says that:
the i-th number is pi — the number of a friend who gave a gift to friend number i.
This is not how the input is given in the various test cases. On closer inspection this is very similar to the description of the expected output of the questions:
i-th number should equal the number of the friend who gave a gift to friend number i.
So, now the natural question you'll be asking is "What exactly is the input format?"
If we re-examine the description of the Problem Statement above, we see the line:
He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi.
Eureka! This is the correct description of the input format! We can verify this as well with the given sample examples. Let's try that now.
4
2 3 4 1
Here, on the first line we are given that Petya invited 4 friends to the party (I sincerely hope none of his friends got left out 😅), and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):
Alright, so now what we need to do is to output a list of numbers such that at the
i-th position we give the number of the friend who gave a present to friend i.So our output should be:
4 1 2 3
Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):
4 1 2 3
3
1 3 2
Here, on the first line we are given that Petya invited 3 friends to the party, and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):
Alright, so other than the fact that Friend 1 doesn't seem to have the New Year spirit, what we need to do is to output a list of numbers such that at the
i-th position we give the number of the friend who gave a present to friend i.So our output should be:
1 3 2
Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):
1 3 2
2
1 2
Here, on the first line we are given that Petya invited 2 friends to the party, and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):
Alright, so other than the fact that Friend 1 and Friend 2 should starting asking themselves why they came with presents to the party, what we need to do is to output a list of numbers such that at the
i-th position we give the number of the friend who gave a present to friend i.So our output should be:
1 2
Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):
1 2
Alright, so now we know how to interpret out input and process it to get our output. To be extra sure we have also verified our logic over the given examples as well. Let's now translate this logic into code. For this I'll be using modern C++ (C++11 and beyond), so that it's easier to get the big picture logic which is implemented in the code.
Another interesting reason to use modern C++ is that some of its features make the code more readable and similar looking to Python code (many people consider this a plus).
/**
* @file 136A-Presents.cpp
* @author Rishit Chaudhary (@rishitc)
* @version 1.0
* @date 2021-06-23
*
* @copyright Copyright (c) 2021
*
*/
#include <iostream>
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
int p;
std::cin >> n;
int ans[n];
for (int i = 1; i < n + 1; ++i)
{
std::cin >> p;
ans[p - 1] = i; // Zero index correction for p
}
for (int i = 0; i < n; ++i)
{
std::cout << ans[i] << " ";
}
std::cout << "\n";
}| Complexity Type | Answer | My Comments |
|---|---|---|
| Time Complexity | O(n) | n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party. |
| Space Complexity | O(n) | n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party. |
| Difficulty (subjective value) | Easy | The use of language in the question combined with the mistake in the description of the input does make the question a bit hard to grasp at first. |
Link to the problem: https://codeforces.com/problemset/problem/136/A
Link to my submission: https://codeforces.com/contest/136/submission/120021060
Link to the solution at my GitHub Repository: https://github.com/rishitc/Codeforces-Codes/blob/main/136A-Presents.cpp
Link to my submission: https://codeforces.com/contest/136/submission/120021060
Link to the solution at my GitHub Repository: https://github.com/rishitc/Codeforces-Codes/blob/main/136A-Presents.cpp
39