The first line gives n and the second line n integers. A run is a stretch of equal values standing next to each other (a single value is a run of length 1). Print the starting position (counted from 1) and the length of the longest run, separated by a single space. If several runs are equally longest, print the first one. Try solving it with a function that takes two pointers, one to the first element and one just past the last, walks by moving a pointer one element at a time, and returns a pointer to the start of the longest run. Get the starting position by subtracting the pointer to the first element from that pointer.
Input
1 ≤ n ≤ 100,000, every value is an integer from -1,000,000,000 to 1,000,000,000
Output
One line: start length
Example 1 · stdin
7
3 1 2 2 2 1 1
stdout
3 3
Example 2 · stdin
5
1 2 2 3 3
stdout
2 2
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 2 languages
This problem accepts only C and C++. Pointers that hold an address and walk with p++, and subtracting pointers, exist only in those two; Python, JavaScript, TypeScript, Java and Craykon walk with an index i (C# has pointers only inside unsafe). The function takes [first, last), as in const int *longest_run(const int *first, const int *last, int *len). last = a + n is one past the end, so you only point at it, never read it, and the loop condition is p != last. Subtracting two pointers into the same array gives elements, not bytes, so start - a is the 0-based position and q - p is the run length. C++ passes a.data() and a.data() + a.size(), and real code more often uses iterators of the same shape (a.begin(), a.end()). Three traps: (1) computing the length inside the function with sizeof(a) / sizeof(a[0]) fails, because the parameter int a[] is really a pointer, giving 8 / 4 = 2 on 64-bit, so only the first two elements are seen; pass the length or the end pointer separately. (2) Don't divide again as in (start - a) / sizeof(int); pointer subtraction already counts elements. (3) Comparing lengths with >= switches to the later run on a tie; replace only when strictly longer (>).
C++main.cpp · 31 lines
#include <iostream>#include <vector>// [first, last) 를 포인터로 걷는다. 길이는 참조로 돌려준다const int* longest_run(const int* first, const int* last, int& len) { const int* best = first; len = 0; for (const int* p = first; p != last;) { const int* q = p; while (q != last && *q == *p) ++q; if (q - p > len) { best = p; len = static_cast<int>(q - p); } p = q; } return best;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<int> a(n); for (int& v : a) std::cin >> v; int len; const int* start = longest_run(a.data(), a.data() + a.size(), len); std::cout << (start - a.data()) + 1 << " " << len << "\n";}
Cmain.c · 34 lines
#include <stdio.h>#include <stdlib.h>/* [first, last) 구간을 포인터로 걸으며 가장 긴 같은 수 덩이를 찾는다. 덩이의 시작을 가리키는 포인터를 돌려주고, 길이는 *len에 써 넣는다. */const int *longest_run(const int *first, const int *last, int *len) { const int *best = first; *len = 0; const int *p = first; while (p != last) { const int *q = p; while (q != last && *q == *p) q++; /* q는 덩이 바로 다음 칸 */ if (q - p > *len) { /* 포인터 빼기 = 칸 수. 더 길 때만 바꿔서 비기면 앞의 것 */ best = p; *len = (int)(q - p); } p = q; } return best;}int main(void) { int n; scanf("%d", &n); int *a = malloc(n * sizeof *a); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int len; const int *start = longest_run(a, a + n, &len); /* a + n은 끝 바로 다음: 가리키기만 하고 읽지 않는다 */ printf("%d %d\n", (int)(start - a) + 1, len); /* start - a 가 0부터 센 자리 */ free(a); return 0;}