Zadanie 61. Ciągi arytmetyczne
Treść zadania
Ciąg arytmetyczny to ciąg, w którym różnica każdych dwóch kolejnych wyrazów jest taka sama; rozważamy tylko ciągi o dodatniej różnicy i co najmniej pięciu wyrazach. Plik ciagi.txt zawiera 100 ciągów liczb całkowitych dodatnich nie większych niż 1 000 000. Każdy ciąg zajmuje dwa wiersze: w pierwszym jest liczba wyrazów (od 5 do 1000), w drugim — wyrazy oddzielone pojedynczymi spacjami, np.:
5
1 3 6 7 9
5
17 22 27 32 37Podaj, ile ciągów w pliku jest arytmetycznych, oraz największą różnicę spośród tych ciągów. Obie liczby zapisz w pliku wynik1.txt.
ciagi = []
with open("ciagi.txt") as file:
wiersze = file.read().split("\n")
for i in range(1, len(wiersze), 2): # co drugi wiersz zawiera wyrazy ciągu
ciagi.append(list(map(int, wiersze[i].split())))
count = 0
najwieksza_roznica = 0
for ciag in ciagi:
r = ciag[1] - ciag[0]
arytmetyczny = True
for j in range(1, len(ciag)):
if ciag[j] - ciag[j - 1] != r:
arytmetyczny = False
break
if arytmetyczny:
count += 1
najwieksza_roznica = max(najwieksza_roznica, r)
print(count)
print(najwieksza_roznica)#include <algorithm>
#include <fstream>
#include <print>
#include <sstream>
#include <string>
#include <vector>
// co drugi wiersz pliku (licząc od zera: 1, 3, 5, ...) zawiera wyrazy ciągu
std::vector<std::vector<long long>> wczytaj_ciagi(const std::string& nazwa) {
std::ifstream plik(nazwa);
std::vector<std::vector<long long>> ciagi;
std::string wiersz;
int numer = 0;
while (std::getline(plik, wiersz)) {
if (numer % 2 == 1) {
std::istringstream strumien(wiersz);
std::vector<long long> ciag;
long long x;
while (strumien >> x) {
ciag.push_back(x);
}
ciagi.push_back(ciag);
}
numer++;
}
return ciagi;
}
int main() {
std::vector<std::vector<long long>> ciagi = wczytaj_ciagi("ciagi.txt");
int count = 0;
long long najwieksza_roznica = 0;
for (const auto& ciag : ciagi) {
long long r = ciag[1] - ciag[0];
bool arytmetyczny = true;
for (size_t j = 1; j < ciag.size(); j++) {
if (ciag[j] - ciag[j - 1] != r) {
arytmetyczny = false;
break;
}
}
if (arytmetyczny) {
count += 1;
najwieksza_roznica = std::max(najwieksza_roznica, r);
}
}
std::println("{}", count);
std::println("{}", najwieksza_roznica);
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
public class Zadanie {
// co drugi wiersz pliku (licząc od zera: 1, 3, 5, ...) zawiera wyrazy ciągu
static List<long[]> wczytajCiagi(String nazwa) throws Exception {
List<String> wiersze = Files.readAllLines(Path.of(nazwa));
List<long[]> ciagi = new ArrayList<>();
for (int i = 1; i < wiersze.size(); i += 2) {
String[] t = wiersze.get(i).trim().split("\\s+");
long[] ciag = new long[t.length];
for (int j = 0; j < t.length; j++) {
ciag[j] = Long.parseLong(t[j]);
}
ciagi.add(ciag);
}
return ciagi;
}
public static void main(String[] args) throws Exception {
List<long[]> ciagi = wczytajCiagi("ciagi.txt");
int count = 0;
long najwiekszaRoznica = 0;
for (long[] ciag : ciagi) {
long r = ciag[1] - ciag[0];
boolean arytmetyczny = true;
for (int j = 1; j < ciag.length; j++) {
if (ciag[j] - ciag[j - 1] != r) {
arytmetyczny = false;
break;
}
}
if (arytmetyczny) {
count += 1;
najwiekszaRoznica = Math.max(najwiekszaRoznica, r);
}
}
System.out.println(count);
System.out.println(najwiekszaRoznica);
}
}Odpowiedź: 44 ciągi arytmetyczne, największa różnica: 246849
↑Treść zadania
Dane jak w zadaniu 61.1 (100 ciągów w pliku ciagi.txt).
Dla każdego ciągu znajdź — o ile istnieje — największy wyraz, który jest sześcianem liczby naturalnej (w przykładzie: 1 = 1³ w pierwszym ciągu, 27 = 3³ w drugim). Znalezione liczby (po jednej dla każdego ciągu, w którym taka występuje) zapisz w pliku wynik2.txt w kolejności ciągów w pliku.
def czy_szescian(x):
a = round(x ** (1 / 3))
return a ** 3 == x
ciagi = []
with open("ciagi.txt") as file:
wiersze = file.read().split("\n")
for i in range(1, len(wiersze), 2):
ciagi.append(list(map(int, wiersze[i].split())))
for ciag in ciagi:
najwiekszy = 0
for liczba in ciag:
if czy_szescian(liczba) and liczba > najwiekszy:
najwiekszy = liczba
if najwiekszy > 0:
print(najwiekszy)#include <cmath>
#include <fstream>
#include <print>
#include <sstream>
#include <string>
#include <vector>
bool czy_szescian(long long x) {
long long a = std::llround(std::cbrt(x)); // pierwiastek sześcienny zaokrąglony do całości
return a * a * a == x;
}
std::vector<std::vector<long long>> wczytaj_ciagi(const std::string& nazwa) {
std::ifstream plik(nazwa);
std::vector<std::vector<long long>> ciagi;
std::string wiersz;
int numer = 0;
while (std::getline(plik, wiersz)) {
if (numer % 2 == 1) {
std::istringstream strumien(wiersz);
std::vector<long long> ciag;
long long x;
while (strumien >> x) {
ciag.push_back(x);
}
ciagi.push_back(ciag);
}
numer++;
}
return ciagi;
}
int main() {
std::vector<std::vector<long long>> ciagi = wczytaj_ciagi("ciagi.txt");
for (const auto& ciag : ciagi) {
long long najwiekszy = 0;
for (long long liczba : ciag) {
if (czy_szescian(liczba) && liczba > najwiekszy) {
najwiekszy = liczba;
}
}
if (najwiekszy > 0) {
std::println("{}", najwiekszy);
}
}
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
public class Zadanie {
static boolean czySzescian(long x) {
long a = Math.round(Math.cbrt(x)); // pierwiastek sześcienny zaokrąglony do całości
return a * a * a == x;
}
static List<long[]> wczytajCiagi(String nazwa) throws Exception {
List<String> wiersze = Files.readAllLines(Path.of(nazwa));
List<long[]> ciagi = new ArrayList<>();
for (int i = 1; i < wiersze.size(); i += 2) {
String[] t = wiersze.get(i).trim().split("\\s+");
long[] ciag = new long[t.length];
for (int j = 0; j < t.length; j++) {
ciag[j] = Long.parseLong(t[j]);
}
ciagi.add(ciag);
}
return ciagi;
}
public static void main(String[] args) throws Exception {
List<long[]> ciagi = wczytajCiagi("ciagi.txt");
for (long[] ciag : ciagi) {
long najwiekszy = 0;
for (long liczba : ciag) {
if (czySzescian(liczba) && liczba > najwiekszy) {
najwiekszy = liczba;
}
}
if (najwiekszy > 0) {
System.out.println(najwiekszy);
}
}
}
}Odpowiedź: 1, 27, 551368, 1000000, 250047, 1000, 35937, 531441
↑Treść zadania
Plik bledne.txt ma taką samą strukturę jak ciagi.txt, ale zawiera 20 ciągów. Każdy z nich jest ciągiem arytmetycznym, w którym dokładnie jeden wyraz zastąpiono liczbą naturalną nienależącą do ciągu.
Dla każdego ciągu znajdź błędny wyraz. Wyniki zapisz w pliku wynik3.txt, każdy w osobnym wierszu, w kolejności ciągów w pliku wejściowym.
ciagi = []
with open("bledne.txt") as file:
wiersze = file.read().split("\n")
for i in range(1, len(wiersze), 2):
ciagi.append(list(map(int, wiersze[i].split())))
for ciag in ciagi:
# różnica ciągu to najczęściej występująca różnica kolejnych wyrazów
roznice = {}
for j in range(1, len(ciag)):
d = ciag[j] - ciag[j - 1]
roznice[d] = roznice.get(d, 0) + 1
r = max(roznice, key=roznice.get)
# pierwszy wyraz: najczęstsza wartość ciag[j] - j * r
pierwsze = {}
for j in range(len(ciag)):
a = ciag[j] - j * r
pierwsze[a] = pierwsze.get(a, 0) + 1
a1 = max(pierwsze, key=pierwsze.get)
for j in range(len(ciag)):
if ciag[j] != a1 + j * r:
print(ciag[j])#include <algorithm>
#include <fstream>
#include <print>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
std::vector<std::vector<long long>> wczytaj_ciagi(const std::string& nazwa) {
std::ifstream plik(nazwa);
std::vector<std::vector<long long>> ciagi;
std::string wiersz;
int numer = 0;
while (std::getline(plik, wiersz)) {
if (numer % 2 == 1) {
std::istringstream strumien(wiersz);
std::vector<long long> ciag;
long long x;
while (strumien >> x) {
ciag.push_back(x);
}
ciagi.push_back(ciag);
}
numer++;
}
return ciagi;
}
// licznik wartości w kolejności pierwszego wystąpienia (jak słownik w Pythonie)
using Licznik = std::vector<std::pair<long long, int>>;
void dodaj(Licznik& licznik, long long wartosc) {
for (auto& [klucz, ile] : licznik) {
if (klucz == wartosc) {
ile += 1;
return;
}
}
licznik.push_back({wartosc, 1});
}
// pierwsza wartość o największej liczbie wystąpień - jak max(slownik, key=slownik.get)
long long najczestsza(const Licznik& licznik) {
auto najlepsza = licznik[0];
for (const auto& para : licznik) {
if (para.second > najlepsza.second) {
najlepsza = para;
}
}
return najlepsza.first;
}
int main() {
std::vector<std::vector<long long>> ciagi = wczytaj_ciagi("bledne.txt");
for (const auto& ciag : ciagi) {
// różnica ciągu to najczęściej występująca różnica kolejnych wyrazów
Licznik roznice;
for (size_t j = 1; j < ciag.size(); j++) {
dodaj(roznice, ciag[j] - ciag[j - 1]);
}
long long r = najczestsza(roznice);
// pierwszy wyraz: najczęstsza wartość ciag[j] - j * r
Licznik pierwsze;
for (size_t j = 0; j < ciag.size(); j++) {
dodaj(pierwsze, ciag[j] - (long long)j * r);
}
long long a1 = najczestsza(pierwsze);
for (size_t j = 0; j < ciag.size(); j++) {
if (ciag[j] != a1 + (long long)j * r) {
std::println("{}", ciag[j]);
}
}
}
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Zadanie {
static List<long[]> wczytajCiagi(String nazwa) throws Exception {
List<String> wiersze = Files.readAllLines(Path.of(nazwa));
List<long[]> ciagi = new ArrayList<>();
for (int i = 1; i < wiersze.size(); i += 2) {
String[] t = wiersze.get(i).trim().split("\\s+");
long[] ciag = new long[t.length];
for (int j = 0; j < t.length; j++) {
ciag[j] = Long.parseLong(t[j]);
}
ciagi.add(ciag);
}
return ciagi;
}
// pierwsza wartość o największej liczbie wystąpień - jak max(slownik, key=slownik.get)
// (LinkedHashMap pamięta kolejność dodawania, tak jak słownik w Pythonie)
static long najczestsza(Map<Long, Integer> licznik) {
long najlepsza = 0;
int najwiecej = -1;
for (var wpis : licznik.entrySet()) {
if (wpis.getValue() > najwiecej) {
najwiecej = wpis.getValue();
najlepsza = wpis.getKey();
}
}
return najlepsza;
}
public static void main(String[] args) throws Exception {
List<long[]> ciagi = wczytajCiagi("bledne.txt");
for (long[] ciag : ciagi) {
// różnica ciągu to najczęściej występująca różnica kolejnych wyrazów
Map<Long, Integer> roznice = new LinkedHashMap<>();
for (int j = 1; j < ciag.length; j++) {
roznice.merge(ciag[j] - ciag[j - 1], 1, Integer::sum);
}
long r = najczestsza(roznice);
// pierwszy wyraz: najczęstsza wartość ciag[j] - j * r
Map<Long, Integer> pierwsze = new LinkedHashMap<>();
for (int j = 0; j < ciag.length; j++) {
pierwsze.merge(ciag[j] - j * r, 1, Integer::sum);
}
long a1 = najczestsza(pierwsze);
for (int j = 0; j < ciag.length; j++) {
if (ciag[j] != a1 + j * r) {
System.out.println(ciag[j]);
}
}
}
}
}Odpowiedź: 6, 36, 421503, 362326, 303276, 534127, 40828, 949, 90367, 177326, 390126, 842436, 37889, 11106, 149243, 80882, 529815, 988401, 29559, 953023
↑